Course Syllabus

Welcome to CS-326, Analysis of Algorithms.  See our homepage for our schedule, room, and zoom link.

Staff and Hours: 

• Instructor Michelangelo Grigni (mgrigni@emory.edu), writing this. My office hours are here.
• Our TA is Hanqi Chen (hanqi.chen@emory.edu). He should announce office hours.

Canvas: We use Canvas for announcements, discussions, assignments, quizzes, and grading. We plan to provide:

• Pages: a "page" per meeting, with a summary of the meeting, a zoom recording, and a scan of my notes
• Modules: a "module" per week, listing meetings, discussions, assignments, and exams (see also the Canvas Calendar)

Overview: we study the design of advanced data structures and algorithms, with an emphasis on understanding and analysis. Your work for this course is mostly written, not programming. Students will practice techniques used to argue correctness, and to analyze the performance of algorithms. We will study many specific examples and their applications. We will study several general paradigms of algorithm design.

Prerequisites: this course has both CS-224 and CS-253 (or equivalents) as prerequisites. In particular, you should have already seen an introduction to basic data structures (heaps, search trees, hashing, graphs), basic algorithms (mergesort, quicksort, BFS/DFS, Dijkstra, MST, max-flow), asymptotic notation (big-O, Ω, Θ), and basic mathematical tools (truth tables, induction, probability, calculus). If you have concerns about your preparation, let me know!

Materials: our main textbook is Introduction to Algorithms (4th edition) by Cormen, Leiserson, Rivest, and Stein (2022). We refer to it as CLRS4 to emphasize that it is the 4th edition. You should have access to a copy of it, in whatever format. Since we refer to page numbers, please find a correctly paginated version: check that page 1000 has the problem "32-3 Burrows-Wheeler transform". Correct PDF versions do exist.

Health: we plan to meet in person, but we will also follow any Emory guidelines regarding meetings and masking. We will attempt to share and record our meetings using zoom, but I encourage you to attend in person in order to stay engaged. On days when you feel sick or may be contagious, please do not attend in person.

Graded Work: we will have six written homework assignments (hw1, hw2, ...). These assignments will be weighted equally, and I will drop your lowest mark among them. Together, they count for 25% of your course grade. We will have two in-class midterm exams (mid1 and mid2); they are both Canvas quizzes counting for 15% of your course grade, so 30% for both. There will be a traditional (closed-book, in classroom, on paper) final exam, counting for 25% of your course grade.  The remaining 20% will be participation. Participation includes everything else, such as discussions and surveys. Each homework and exam mark will be curved up, if necessary, so that its median non-zero grade is at least 82 out of 100 (B-). Your final course grade is determined by this grading scheme:

Effort: Of the graded work, the participation is relatively easy. The written assignments can be time-consuming, but they are not too hard since I allow collaboration including AI (see Grading of Written Assignments); their median grade is typically an A without needing a curve. The exams are the most challenging part; they usually do require a curve, and it is harder to get a high mark on the exams.

Schedule: I expect to cover roughly a topic per week, from the following list. The numbers are chapters in CLRS4:

• review (asymptotic notation, mergesort): parts of 2, 3
• Divide and Conquer: most of 4
• Selection, sorting, Quicksort: parts of 7, 8, 9
• Dynamic Programming: 14
• Greedy Algorithms: 15
• Amortized analysis: 16
• Disjoint Sets: 19
• Shortest Paths (single-source, all-pairs): 22, 23
• Max-Flow: 24
• Bipartite Matching: 25 (partial)
• Linear Programming: 29
• NP-completeness: 34
• Approximation Algorithms: 35
• FFT: 30

Disclaimer: this plan is subject to change, any changes will be announced.

Policies: See the OUE addendum for common college policies and dates. It is your responsibility to know what is covered in class meetings, to review course materials, and to attempt all assigned work. You need an OUE note to document an extended illness.

Late policy: for the late policy on assignments (including extensions), see Grading of Written Assignments. For the late policy on readings, see Grading of Readings. Other graded items should state a late policy.

Honor Policy: Your work for this class is governed by the Emory Honor Code. Unless instructed otherwise, you should not seek or share help from others on assignments or exams. On the other hand, the following kind of collaboration is allowed: interpreting the statement of a problem, understanding tools and error messages, or reviewing the course materials. If you are in doubt about what is allowed, ask your instructor. Any programming work is also covered by the Computer Science SPCA. Apparent honor code violations will be referred to the Emory Honor Council. We may use automated means to help detect plagiarism.

Accessibility: The Department of Accessibility Services (DAS) works with students who have disabilities. In order to request accommodations, you first register with DAS, and then submit their letter to your instructors. For more information, contact accessibility@emory.edu.