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, random, string, etc.
Lectures: Mondays and Wednesdays at 12-1:15pm, in Sierra 1111.
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 at least two, and no more than 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.
Oct 23, Lecture 16: We started Dynamic Programming, with the example of Longest Monotone Subsequence (LMS). Everything up to, and including, section 4.1 (LMS) will be on the midterm on October 25.
Oct 18, Lecture 15: Long Quiz 5 on Savitch’s algorithm; we discussed the details of the space required for the stack of Savitch’s algorithm (), and we finished the Divide and Conquer chapter with the example of Quicksort and git bisect.
Oct 16, Lecture 14: Two Divide and Conquer algorithms: a clever method of binary integer multiplication (in steps), and Savitch’s algorithm for reachability in space.
Oct 13: Final exam for this course will take place during the last two lecture slots, on Dec 4 and 6, same time and place as regular lectures. The exam will be served in two parts: Part I on Dec 4, and Part II on Dec 6. No aids (no calculators, no notes, no aids) during the exam.
Oct 11, Lecture 13: Discussed solutions to Assignments 1 & 2, started Divide and Conquer, with the example of merge sort algorithm.
Oct 9, Lecture 12: Finished greedy algorithms, by covering the following four problems:
Weighted matching (and application to network switches)
Dijkstra’s shortest path (and applications to OSPF IP routing)
Hoffman codes and compression
Oct 4, Lecture 11: Proof of correctness of the algorithm for job scheduling with profits, as well as Quiz 4.
Oct 2, Lecture 10: We showed that “T is promissing” (i.e., can be extended to a MCST) is a loop invariant of Kruskal’s algorithm. We also started talking about job scheduling with profits, and introduced the “procrastination” algorithm.
Sep 27: Midterm will take place on October 25th, in the usual classroom.
Sep 27, Lecture 9: Quiz 3, discussed solution to Quiz 3 at length, and then defined promising set T, and example of Kruskal’s algorithm with respect to computing a MCST.
Sep 25, Lecture 8: We started working toward the correctness of Kruskal’s algorithm: if input is a connected graph, the output is a tree.
Sep 20, Lecture 7: Start Chapter 2, Kruskal’s algorithm; we covered the graph theoretic background.
Sep 11, Lecture 4: Proof of correctness of Euclid’s Algorithm, and started ranking algorithms with PageRank.
Sep 6, Lecture 3: Proof of termination of the division algorithm, Quiz 1, and started proof of correctness of Euclid’s algorithm.
Sep 6: A Note Taker is needed for this class; Note Takers are stipend and anyone interested can call (805) 437-3331 or visit Arroyo Hall 210 for more information.
Sep 30, Lecture 2: Introducing the concepts of pre, post-condition, loop invariant, (partial) correctness, and we saw an example of application to the division algorithm.
Aug 28, Lecture 1: First lecture, we went over the content of this web page (outline, grading, links and emails), and we motivated the course with the documentary The Secret Rules of Modern Living: Algorithms, by Marcus du Sautoy (you can finish it online here). The slides will be posted here.
July 20: First day of class is August 28, at 12pm in Sierra Hall 1111.