COMP 354 – Analysis of Algorithms – Spring 2024

  • Course URL: http://prof.msoltys.com/?page_id=6904
  • Canvas Page: https://cilearn.csuci.edu/courses/27967
  • Course Material
  • CI Catalogue URL
  • Instructor: Michael Soltys <michael.soltys@csuci.edu>
  • 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. We will discuss NP-completeness when we meet Dynamic Programming algorithms.
  • Lectures: W 6:00-7:00 online
  • Textbook: Introduction to the Analysis of Algorithms, by Michael Soltys
  • Grading: 10 quizzes (best 8 selected), worth 5% each, and 4 assignments, worth 5% each, and two midterms, worth 10% each and a final exam worth 20%.
  • Missing or late work policy: Assignments are worth 5 points, and late assignments will have one (1) point deducted for each day they are late (up to five points). Regarding missing quizzes: since best 8 out of 10 quizzes are used for final grade, up to two quizzes can be missed. If more quizzes are missed, or a midterm or final exam is missed, this will be dealt with on a case by case basis, requiring a letter from the students explaining the situation. Please note that in the industry, work has to both meet requirements and be delivered on time.
  • How to avoid plagiarism: Verbal discussions of problems among students 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. All quizzes, assignments, midterms and the final exam will be written online.

Course outline

Jan 24Course Introduction
Jan 31Proving correctness1.1
Feb 7Stable Marriage1.2.2Quiz 1
Feb 14Greedy: MCST2.1Quiz 2
Feb 21Greedy: Jobs with deadlines & profits2.2Quiz 3
Assignment 1
Feb 28Greedy: Other examples2.3Quiz 4
Mar 7Midterm 1
Mar 14Divide & Conquer: Mergesort3.1Quiz 5
Assignment 2
Mar 21Divide & Conquer: Karatsuba3.2Quiz 6
March Break
Apr 4Divide & Conquer: Savitch3.3Quiz 7
Assignment 3
Apr 11Midterm 2
Apr 18Dynamic Programming: Longest Monotone Subsequence4.1Quiz 8
Apr 25Dynamic Programming: All Pairs Shortest Path Problem4.2Quiz 9
May 2Dynamic Programming: Knapsack Problem4.3Quiz 10
Assignment 4
May 9Final Exam
EachTotal
Quiz (top 8 out of 10)540
Assignment (1 pt off each day late)520
Midterms1020
Final Exam2020
100

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.