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.
• TA Zihao Zhang (zihao.zhang@emory.edu). His office hours were announced here.
• TA Xinliu Zhong (xinliu.zhong@emory.edu). Her office hours were announced here.

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 this book as CLRS4 to emphasize that it is the 4th edition. You should have access to a copy of it, in whatever format.

Health: we expect 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. 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 35% of your course grade. We will have two open-book one-hour midterm exams (mid1 and mid2); they are both Canvas quizzes counting for 12.5% of your course grade, so 25% for both. There will be a traditional (closed-book, in classroom, on paper) final exam, counting for 25% of your course grade.  The remaining 15% 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 83 out of 100 (low B). Your final course grade is determined by this grading scheme:

Of the graded work, the participation should be relatively easy. The written assignments are time-consuming, but not too hard to get a good grade if you start early and collaborate. They don't usually need 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: parts of 2, 3
• Divide and Conquer: 4
• Selection, Quicksort: parts of 7, 8, 9
• Dynamic Programming: 14
• Greedy Algorithms: 15
• Amortized analysis: 16
• Fibonacci Heap: 19 of CLRS3
• All-Pairs Shortest Paths: 23
• Bipartite Matching: 25 (partial)
• Linear Programming: 29
• NP-completeness: 34
• Approximation Algorithms: 35
• Machine Learning: 33
• 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 an automated system 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.