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

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]

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