MATH 354 – Analysis of Algorithms – Fall 2018

Course Information

Course URL (this page): http://prof.msoltys.com/?page_id=3519
(This course was taught previously in the fall 2016 and fall 2017)
Canvas: https://csuci.instructure.com/courses/4954
Course Syllabus (Updated November 23, 2018)
Lectures: MW 12:00-1:15 in Sierra Hall 1422
Course Slides: http://prof.msoltys.com/?page_id=2751
CI Catalogue URL: https://ciapps.csuci.edu/ScheduleOfClasses/SOC/CourseInformation/Fall-2018/MATH/354/None/Analysis-Of-Algorithms
Instructor: Michael Soltys <michael.soltys@csuci.edu>
Twitter: @MichaelMSoltys
Course Outline: This course is an introduction to the analysis of algorithms. We are going to cover some basics of proving algorithm correctness (pre/post-condition, loop invariants, and termination), and then we are going to spend the bulk of the time on three classical categories of algorithms: Greedy, Divide-and-Conquer, and Dynamic Programming. We are going to see examples of problems that yield to these types of algorithms. Depending on the time, we may also see some modern types of algorithms: online, approximation, random, string, etc.
Textbook: An Introduction to the Analysis of Algorithms, by Michael Soltys.
Grading: Four assignments worth 15% each. The assignments will consist in a mixture of theory and practice (reasoning about properties of algorithms, and implementing algorithms and obtaining experimental results). The assignments have to be completed in groups of three. It would be best if you formed a group at the beginning of the course, and worked on all the assignments with the same group. There is tremendous value in working on problems with your group; it amplifies the learning experience, and teaches teamwork. There will be midterm for 20%, and a final exam also worth 20%; both will be written individually.
How to avoid plagiarism: As mentioned above, the assignments will be written in groups. Each group has to work independently of the other groups; verbal discussions of problems among groups are allowed, but you should not show written notes, and you should not leave such discussions with written notes.
Attendance: Students are encouraged but not required to attend the lectures. The assignments will be posted online. The final exam will be written in class.
Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.
Check this web page regularly for announcements.

Announcements and class diary

Dec 10, 2018: Final Exam.
Nov 26, 2018: We covered the final exam (see slides for Chapter 0), and repeated the lecture on all pairs shortest path. The next two lectures will be on the simple knapsack problem, and this will cover the student learning outcomes for the course.
Nov 12, 14, 19, 21, 2018: Campus closed due the the Ventura fires.
Nov 7, 2018: We spoke briefly about Assignment 3, and returned the midterms, and covered the solutions to the midterm.
Nov 5, 2018: Second lecture on dynamic programming, all pairs shortest path (Floyd’s algorithm – Ryan McIntyre).
Oct 31, 2018: We covered the requirements for Assignment 3, and were about to return the midterms, when there was an alarm, and campus evacuation.
Oct 29, 2018: Start of dynamic programming, lecture on longest monotone subsequence (Ryan McIntyre)
Oct 25, 2018: Assignment 3 posted below.
Oct 24, 2018: Midterm
Oct 22, 2018: Quiz 12, about fast integer-in-binary multiplication, and we finished Savitch’s algorithm.
Oct 17, 2018: Quiz 11, which examines one of the cases in the proof of correctness of the Job Scheduling with Profits algorithm, and then we started Chapter 3: Divide & Conquer. We examined 3 algorithms: Merge Sort, Fast Integer Multiplication and Savitch’s reachability. We will finish Savitch, and Chapter 3, next lecture.
Oct 15, 2018: We finished Greedy algorithms, with a proof of correctness of Job Scheduling with Profits, and an outline discussion of Perfect Matching with Weights, Dijkstra’s reachability and Huffman Codes.
Oct 10, 2018: We discussed Assignment 2 in detail.
Oct 8, 2018: Started the proof of correctness of Job Scheduling with Profits.
Oct 3, 2018: We discussed how to do capstone research, and research in general, and how it relates to your potential future careers. Thus, today’s lecture was a break from our usual discussion of algorithms; we will continue with Scheduling Jobs with Profits on Monday.
Oct 1, 2018: Quiz 9, and we finished the proof of correctness of Kruskal’s algorithm. We started the discussion of the next greedy algorithm: job scheduling with profits. The midterm will be written on Wednesday October 24 during the usual class time.
Sep 26, 2018: We discussed Assignment 1, which now has a two day extension (due Sep 28). We then gave an example run of Kruskal’s algorithm, in order to illustrate the idea of T being promising.
Sep 24, 2018: We started with Quiz 8 (we skipped Quiz 7) and then discussed the problem in the quiz at length; the solution is covered in the course slides. We then discussed how to check for a cycle in the while condition in Kruskal’s algorithm.
Sep 19, 2018: We started chapter 2 with the coin change problem. We covered the background to Kruskal’s algorithm (graphs, paths, cycles, trees, spanning trees), and we started working with Kruskal’s algorithm itself.
Sep 17, 2018: Quiz 6 (we skipped Quiz 5 as it has material that has been covered several times already). We discussed the correctness of the Gale-Shapley algorithms, in particular, we showed that the resulting marriage is always stable (i.e., no blocking pairs), and that it is boy-optimal. Make sure you can define what it means to be “boy-optimal“. We left some parts of the proof as exercises.
Sep 12, 2018: Quiz 4, and we covered the Stable Marriage algorithm, and gave an example computation. We will analyze the algorithm in detail on Monday.
Sep 10, 2018: Quiz 3, and we covered the PageRank algorithm used by the Google Search Engine.
Sept 5, 2018: Quiz 2, and correctness of Euclid’s algorithm. Please do problems 1.3,1.4,1.5, and read section 1.1.4. on your own.
August 29, 2018: Quiz 1, and partial correctness of the division algorithm.
August 27, 2018: First class, we covered the course syllabus in detail. Please watch The secret rules of modern living: Algorithms.
Assignment 1: due on September 26, 2018: Consider Problem 1.9(c), where there is a typo: instead of min{m,n}, it should be min{(m)_b,(n)_b}, that is, the running time ought to be bound in terms of the length of the binary encoding of the inputs, not their values. Implement Euclid’s Extended algorithm and run an experiment to verify this claim.
Assignment 2: due on October 24, 2018: [pdf]
Assignment 3: due on November 30, 2018: [pdf (updated Nov 7, 2018)]