CSE 40113 Design/Analysis of Algorithms, Spring 2022

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 materialsSolutions
[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

AssignmentsSupplementary materialsSolutionsDeadline
WA01: on Gradescope01/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)
AssignmentsSupplementary materialsSolutionsDeadline

Lectures & materials

DateLecture #TopicPPTExtra NoteCLRS to Read
01/11 TUE01Intro. to Algorithms[ppt]
01/13 THU02Complexity/Correctness Analysis[ppt][note]pp 16-29, 43-52
01/18 TUE03Complexity/Correctness Analysis 2 & Divide-and-Conquer[ppt]pp 24-38
01/20 THU04Divide-and-Conquer 2[ppt][note]pp 88-93
01/25 TUE05Divide-and-Conquer 3[ppt]pp 65-74
01/27 THU06Randomized Algorithms & Probabilistic Analysis & Quicksort[ppt][sheet]
[sheet-answer]
pp 114-124
02/01 TUE07Analayis of Average-Case Complexity of Quicksort[ppt][note]
02/03 THU08Solving Complex Recurrence & Sorting in Linear Time[ppt]pp 191-199
02/08 TUE09Radix sort, Heap & Heapsort[ppt]pp 197-199, 151-166
02/10 THU10Hash table & search in hash tables[ppt][note]pp 253-260
02/15 TUE11Dynamic Programming 1[ppt][note]pp 359-369
02/17 THU12Dynamic Programming 2[ppt]
02/22 TUE13Dynamic Programming 3[ppt][A running example]
02/24 THU14Dynamic Programming 4 & Greedy Algorithm 0[ppt]
03/01 TUEReview[ppt]
03/03 THUExam
03/15 TUE15Greedy Algorithm 1[ppt][note]pp 414-421
03/17 THU16Greedy Algorithm 2 & Intro. to Amortized Analysis[ppt]pp 451-455
03/22 TUE17Amortized Analysis 1[ppt]pp 456-462
03/24 THU18Amortized Analysis 2[ppt]pp 463-471
03/29 TUE19Amortized Analysis 3 & Fibonacci Heap 1[ppt]pp 505-518
03/31 THU20Fibonacci Heap 2[ppt]pp 518-526
04/05 TUE21Minimum Spanning Tree[ppt]pp 624-638
04/07 THU22Single-Source Shortest Paths[ppt]pp 643-662
04/12 TUE23All-Source Shortest Paths[ppt]pp 684-705
04/14 THU24NP-Completeness 1[ppt]
04/19 TUE25NP-Completeness 2[ppt][note]pp 1089-1090
04/21 THU26NP-Completeness 3 & Summary[ppt]

https://wheelofnames.com/k43-3ur