Health Protocol
The class adheres to the university/department policies. Here are the rules as of January 10th January 20th, February 5th March 14th, which will evolve as the university/department policies change.
- Masks are optional for fully vaccinated students during class. Anyone can choose to wear or to not wear a mask.
- If a student is ill (with anything), they can ask for excused absences and access the recorded lectures.
- If a student is placed in “Quarantine or Isolation” (i.e., Q/I), they must inform the instructor immediately. They can either (i) have access to live-streamed zoom sessions for the lecture or (ii) access the recorded lectures later.
- If a student is not placed in Q/I yet but is ill and has a reason to believe they might have COVID, they must inform the instructor immediately and schedule a test at [link]. They can either (i) have access to live-streamed zoom sessions for the lecture or (ii) access the recorded lectures later.
- If a student is not placed in Q/I and is not ill either, but wishes to attend the class remotely, they should work with the Center for Student Support and Care unless the instructor approves remote attendance.
General Information
For course policies, please see [logistics].
For online Q&A and discussion, please go to [slack].
For assignment submission, please go to “Gradescope” on Canvas.
For office hours, please see [schedule].
For some preliminaries, please see [preliminaries].
All the source files/solutions etc. will be shared with any faculty/teachers (whether ND or not) upon request.
Exams
Supplementary materials | Solutions |
[sample final] * This is the exam from the last semester I taught this course. * The scope is slightly different. IGNORE Question 3. * The format/contents/difficulty would be very similar. [guide] [Collaboration for sample final] | [Final solution] |
[sample exam] * This is the exam from the last semester I taught this course. * The scope is slightly different. * The format/contents/difficulty would be very similar. [guide] [Collaboration for sample exam] | [Mid-term solution] |
Assignments
Assignments | Supplementary materials | Solutions | Deadline |
WA01: on Gradescope | 01/14 | ||
[WA02] | [WA02-answer.tex] | [WA02-solution] | 01/21 |
[WA03] | [WA03-answer.tex] | [WA03-solution] | 01/30 (SUN) |
[WA04] | [WA04-answer.tex] | [WA04-solution] | 02/06 (SUN) |
[WA05] | [WA05-answer.tex] | [WA05-solution] | 02/11 |
[WA06] | [WA06-answer.tex] | [WA06-solution] | 02/18 |
[WA07] | [WA07-answer.tex] | [WA07-solution] | 02/25 |
[WA08] | [WA08-answer.tex] | [WA08-solution] | 03/18 |
[WA09] | [WA09-answer.tex] | [WA09-solution] | 03/25 |
[WA10] | [WA10-answer.tex] | [WA10-solution] | 04/03 (SUN) |
[WA11] | [WA11-answer.tex][chain.pdf] You need both to compile the tex. | [WA11-solution] | 04/08 |
[WA12] | [WA12-answer.tex][prim-answer.pptx] You need to convert prim-answer.pptx to pdf to compile the tex. | [WA12-solution] | 04/19 (TUE) |
[WA13] | [WA13-answer.tex] | [WA13-solution] | 04/26 (TUE) |
Assignments | Supplementary materials | Solutions | Deadline |
Lectures & materials
Date | Lecture # | Topic | PPT | Extra Note | CLRS to Read |
01/11 TUE | 01 | Intro. to Algorithms | [ppt] | ||
01/13 THU | 02 | Complexity/Correctness Analysis | [ppt] | [note] | pp 16-29, 43-52 |
01/18 TUE | 03 | Complexity/Correctness Analysis 2 & Divide-and-Conquer | [ppt] | pp 24-38 | |
01/20 THU | 04 | Divide-and-Conquer 2 | [ppt] | [note] | pp 88-93 |
01/25 TUE | 05 | Divide-and-Conquer 3 | [ppt] | pp 65-74 | |
01/27 THU | 06 | Randomized Algorithms & Probabilistic Analysis & Quicksort | [ppt] | [sheet] [sheet-answer] | pp 114-124 |
02/01 TUE | 07 | Analayis of Average-Case Complexity of Quicksort | [ppt] | [note] | |
02/03 THU | 08 | Solving Complex Recurrence & Sorting in Linear Time | [ppt] | pp 191-199 | |
02/08 TUE | 09 | Radix sort, Heap & Heapsort | [ppt] | pp 197-199, 151-166 | |
02/10 THU | 10 | Hash table & search in hash tables | [ppt] | [note] | pp 253-260 |
02/15 TUE | 11 | Dynamic Programming 1 | [ppt] | [note] | pp 359-369 |
02/17 THU | 12 | Dynamic Programming 2 | [ppt] | ||
02/22 TUE | 13 | Dynamic Programming 3 | [ppt] | [A running example] | |
02/24 THU | 14 | Dynamic Programming 4 & Greedy Algorithm 0 | [ppt] | ||
03/01 TUE | Review | [ppt] | |||
03/03 THU | Exam | ||||
03/15 TUE | 15 | Greedy Algorithm 1 | [ppt] | [note] | pp 414-421 |
03/17 THU | 16 | Greedy Algorithm 2 & Intro. to Amortized Analysis | [ppt] | pp 451-455 | |
03/22 TUE | 17 | Amortized Analysis 1 | [ppt] | pp 456-462 | |
03/24 THU | 18 | Amortized Analysis 2 | [ppt] | pp 463-471 | |
03/29 TUE | 19 | Amortized Analysis 3 & Fibonacci Heap 1 | [ppt] | pp 505-518 | |
03/31 THU | 20 | Fibonacci Heap 2 | [ppt] | pp 518-526 | |
04/05 TUE | 21 | Minimum Spanning Tree | [ppt] | pp 624-638 | |
04/07 THU | 22 | Single-Source Shortest Paths | [ppt] | pp 643-662 | |
04/12 TUE | 23 | All-Source Shortest Paths | [ppt] | pp 684-705 | |
04/14 THU | 24 | NP-Completeness 1 | [ppt] | ||
04/19 TUE | 25 | NP-Completeness 2 | [ppt] | [note] | pp 1089-1090 |
04/21 THU | 26 | NP-Completeness 3 & Summary | [ppt] |