Check
CS5800 Algorithms (Fall 2023)
Course CS 5800: Algorithms
Semester Fall 2023
Instructor Soheil Behnezhad (WVH 348)
Meeting Time Mon Thu 11:45 am— 1:25 pm at Richards Hall 458
Prerequisites Prior to enrolling in this course, students should possess a strong foundation in rigorous mathematical reasoning and basic functions (such as logarithms, exponentials, etc.). Additionally, having completed a course in discrete mathematics would be beneficial.
TAs
  • Amir Azarmehr (Head TA)
  • Rishabh Chhaparia
  • Mili Parikh
  • Pravin Pawar
  • Hemasumanth Rasineni
  • Jamie Tjia
  • Ryan Zhu
Useful Links Office Hours, Canvas, Piazza, Office Hours Waitlist, Anonymous Feedback
Discussions Please use Piazza for course-related inquiries such as material, assignments, due dates, etc. Unless necessary, avoid direct emailing to the TAs or the instructor to promote efficient and collaborative discussions within the course.
Course Overview

This course will present the mathematical techniques used for the design and analysis of algorithms. Topics will include asymptotic notation, recurrences, sorting, greedy algorithms, dynamic programming, data structures, graph algorithms, NP-hardness, and if time permits, we will cover advanced topics such as randomized algorithms, massively parallel (e.g. MapReduce) algorithms, or streaming algorithms.

Grading
  • 15% Quizzes & Participation
  • 25% Homework Assignments
  • 30% Midterm
  • 30% Final Exam
Schedule
# WD Date Topics Notes/References
1 Thu 09/07/23 Introduction and Course Policy [E, Chap 0], slides
2 Mon 09/11/23 Algorithm Design and Asymptotic Analysis [E, Chap 0], [CLRS, I-3]
3 Thu 09/14/23 Recurrences [E, Chap 1], [E, Apx 2], HW1 (due 9/28)
4 Mon 09/18/23 Recurrences + Merge Sort [E, Chap 1], [E, Apx 2]
5 Thu 09/21/23 Amir's Recitation Session
6 Mon 09/25/23 Dynamic Programming: Fibonacci [E, Chap 3], [KT, Chap 6], slides
7 Thu 09/28/23 Dynamic Programming: WIS [E, Chap 3], [KT, Chap 6], slides
8 Mon 10/02/23 Dynamic Programming: Knapsack, LCS [E, Chap 3], [KT, Chap 6], slides
9 Thu 10/05/23 Dynamic Programming: LIS [E, Chap 3], slides, HW2 (due 10/16)
Mon 10/09/23 No class (Indigenous Peoples' Day)
10 Thu 10/12/23 Dynamic Programming: Edit Distance [E, Chap 3], slides
11 Mon 10/16/23 Midterm Review slides
Thu 10/19/23 Midterm Exam
12 Mon 10/23/23 Greedy Algorithms [E, Chap 4], [KT, Chap 4], slides
13 Thu 10/26/23 Greedy Algorithms [E, Chap 4], slides, HW3 (due 11/09)
14 Mon 10/30/23 Basic Graph Algorithms [E, Chap 5], [KT, Chap 3], slides
15 Thu 11/02/23 Basic Graph Algorithms [E, Chap 5], [KT, Chap 3], slides
16 Mon 11/06/23 Basic Graph Algorithms [E, Chap 5], [KT, Chap 3], slides
17 Thu 11/09/23 Ryan's Recitation Session
18 Mon 11/13/23 Graph Optimization: Dijkstra [E, Chap 8], [KT, Chap 4], slides, HW4 (due 11/27)
19 Thu 11/16/23 Graph Optimization: BellmanFord [E, Chap 8], slides
20 Mon 11/20/23 Graph Optimization: MST [E, Chap 7], slides
Thu 11/23/23 No class (Thanksgiving) HW5 (due 12/11)
21 Mon 11/27/23 Graph Optimization: MST [E, Chap 7], slides
22 Thu 11/30/23 NP Hardness [E, Chap 12] slides
23 Mon 12/04/23 Randomized Algorithms [E, Lec 13] slides
24 Thu 12/07/23 Randomized Algorithms [E, Lec 13] slides
25 Mon 12/11/23 Final Review slides
26 Thu 12/14/23 Final Exam
Academic Integrity

You cannot collaborate with anyone on quizzes and exams. However, you are encouraged to work with your classmates on homework problems. Note that using the internet or collaborating with students/people outside the class are prohibited. If you collaborate with other students on a homework, then:

  • You must write all solutions by yourself.
  • You may not share any written solutions.
  • You must state all your collaborators.
  • We reserve the right to ask you to explain any solution.
You are expected to maintain highest academic integrity standards throughout, including all tests and assignments. See Northeastern's Academic Integrity Policy.

Resources