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.
Grading: Three assignments worth 20% 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.
April 30: Quiz on SKS, NP-hardness and approximation algorithms; we finished the course material by presenting the activity selection with profits problem. We will discuss the final exam on May 2. Next week I am away at a conference; please use the lecture time to review – I will give guidance on how to do that on Thursday.
April 25: Quiz on SKS – including an introduction to approximation algorithms, greedy performance on SKS, and pseudo-code for Dynamic programming solution to SKS (overwriting technique once again).
April 23: Quiz on SKS – filling out the table, understanding the recurrence.
April 18: Quiz on Floyd’s algorithm, and started The Simple Knapsack Problem, and a discussion of NP-hardness.
April 16: Continue with Dynamic programming, we covered Floyd’s algorithm, All pairs shortest path.
April 10: Read article Math delusion, to see the limits of algorithms.
April 9: We started Dynamic Programming algorithms, with the example of the Longest Monotone Subsequence.
Mar 7: For the solution of the algorithm questions in assignment 1, please see the course’s github repo for Problem 1.15. We did a quiz on Kruskal’s algorithm, we spoke about the midterm and finished the chapter on Greedy algorithms with a few more examples from the book.
Mar 5: We finished the proof of correctness of Kruskal’s algorithm, and we introduced job scheduling with deadlines and profits, and we presented the proof of correctness: our second example of using the technique of a promising set as a loop invariant. We also had a quiz on Kruskal’s algorithm.
Feb 28: We did the first part of the proof of correctness of Kruskal’s algorithm: using the technique of a promising set we showed the output is connected and acyclic.
Feb 26: Students were to start working on the correctness of Kruskal’s algorithm (pp 32-36 in textbook) and do problems 2.8 and 2.13.
Feb 21: The midterm will take place on March 14, during the usual lecture time.
Feb 21: No quiz today. We showed how to check the truth of the following assertion in Kruskal’s algorithm: add edge e to T if this does not create a cycle. We used the notion of a connected component.
Feb 19: No quiz today. We started chapter 2: Greedy Algorithms. We talked about graphs, and run Kruskal’s algorithm on an example graph.
Feb 18: Please note that there will be no COMP/MATH 354 lectures this term on the following dates: March 18-22 (Spring break), and then I will be away at conferences during these two dates: April 11, 25, and May 2, 7, 9. I will assign work to be completed instead of those lectures (except of course the Spring break lectures).
Feb 14: Finished the proof of correctness of Gayle-Shapley, did a quiz on Gayle-Shapley, introduced and finished Pairwise Comparisons, and hence chapter 1.
Feb 12: Introduced the Gayle-Shapley algorithm to solve the stable marriage problem, and we did a quiz on PageRank (computing the PageRank of a clique and of a linear graph).
Feb 7: Quiz on designing an algorithm to translate from decimal to binary notation. Finished PageRank.
Feb 5: Quiz on complexity of the division algorithm – we then started Ranking algorithms, with PageRank.
Jan 31: Quiz on termination of Euclid’s algorithm. We covered Euclid’s algorithm and palindromes algorithm.
Jan 29: Quiz on correctness of the division algorithm.