MATH 354 – Analysis of Algorithms – Fall 2017

Course Syllabus

  • Course URL (this page): http://prof.msoltys.com/?page_id=2664
    (This course was taught previously in the fall 2016)
  • Canvas: https://csuci.instructure.com/courses/1181
  • Course Slides: http://prof.msoltys.com/?page_id=2751
  • CI Catalogue URL: https://ciapps.csuci.edu/ScheduleOfClasses/SOC/CourseInformation/Fall-2017/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, random, string, etc.
  • Lectures: Mondays and Wednesdays at 12-1:15pm, in Sierra 1111.
  • 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 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.
  • Check this web page regularly for announcements.

Announcements and class diary

  • Final Exam: Part 1 and Part 2.
  • Nov 29, Lecture 25: Review
  • Nov 27, Lecture 24: We outlined the issues of Randomized Algorithms, the Rabin-Miller Algorithm for primality testing, and we showed examples of openssl and gpg.
  • Nov 20, Lecture 23: Activity Selection with Profits. We covered all three steps of the dynamic programming solution, and we showed how to recover the actual schedule from the profit of an optimal one.
  • Nov 22, open office hours
  • Nov 15, Lecture 22: Webinar on Dynamic Programming. Here are the slides.
  • Nov 13, Lecture 21: Knapsack Problem dynamic programming solution, including a greedy approximation algorithm.
  • Nov 8, Lecture 20: NP-hardness, and short discussion of the Knapsack Problem. We then covered the solutions to the Midterm in detail.
  • Nov 1, Lecture 19: Quiz 6, all-pairs-shortest path; we discussed solutions.
  • Oct 30, Lecture 18: Second dynamic programming algorithm: all-pairs-shortest-path, in section 4.2. On Wednesday (next lecture) we will look in more detail at the “overwriting” technique.
  • Oct 25, Lecture 17: Midterm.
  • 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 ($latex O(\log^2n)$), 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 $latex O(n^{3.59})$ steps), and Savitch’s algorithm for reachability in $latex O(\log^2n)$ 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:
    • Dispensing change
    • 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 18, Lecture 6: Finish Stable Marriage, Quiz 2, and cover Pairwise Comparisons.
  • Sep 13, Lecture 5: The Stable Marriage algorithm.
  • 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.

Assignments

  • Assignment 1: Problem 1.27 in the textbook (2nd ed), due on September 13, 2017, submit using Canvas. Here is the solution to this problem.
  • Assignment 2: Problem 2.24,25,26 in the textbook (2nd ed), due on October 4, 2017, submit using Canvas. (Use Python 3.6 for 2.25.)
  • Assignment 3: Problem 4.28 – note, this problem is only in the new 3rd edition, and so here is the write up of the problem: Assignment 3. Extension: due on November 13.
  • Assignment 4: implement in Python the Dynamic Programming solution that you designed in Assignment 3. Due on Nov 27.