Design and Analysis of Algorithms (CSE 202, 2024 Fall)

Course Information

Location: 

WLH 2001

Time

Tuesday and Thursday, 3:30 pm - 4:50 pm

TA(s)

Boyang Huang

Sudhansh Peddabomma

Chinmay Sharma

Raymond Sun

Pisit Wajanasara

Yangkun Wang

Office Hours:

Monday 3-4 PM, CSE B240A: Pisit Wajanasara

Tuesday 2-3 PM, CSE B275: Boyang Huang

Wednesday 4:30-5:30 PM, CSE B275: Sudhansh Peddabomma

Thursday 2-3 PM, CSE B260A: Raymond Sun

Friday 11 AM - 12 PM, CSE B270A: Chinmay Sharma

By appointment, CSE 4226, Qipeng Liu

Grading

Evaluation is based on five psets, one project and one final exam. 

30% homework + 20% project + 50% final (take-home) exam

FAQ

I am unable to manually add students to Canvas or Piazza, as they are automatically synced with the UCSD system. However, I truly appreciate your enthusiasm for this course!

Likewise, I do not have control over enrollment decisions. 

Course Description

The course will cover topics in the foundations of algorithm design and analysis, including the necessary backgrounds, graphs, greedy algorithms, dynamic programming, divide-and-conquer, network flows,  more advanced data structures, computational geometry, the class NP and NP complete/hard problems and how to deal with intractability. We will also cover how to implement these algorithms and give real coding and algorithm problems as examples. 

Prerequisites

We expect students to have some undergraduate-level knowledge of discrete mathematics, algorithms, and their analysis, as well as the ability to read, understand, and write valid proofs. Courses like CSE 20, CSE 21, and CSE 101 cover the necessary prerequisites. While we will revisit many topics from undergraduate algorithms courses, after a brief review of the fundamentals, we will progress to more advanced material. If your background in these areas is lacking, additional effort will be required to catch up. Please reach out to me if you have concerns.

Tentative Schedule

A detailed schedule will be continuously updated each week. An outline of the tentative course materials is below: 

Lecture 0 (Sept 26) : Welcome! [Slides] + Background

Lecture 1 (Oct 1) : Graph, Reachability, BFS, DFS [Slides, Annotated]

Lecture 2 (Oct 3) : DFS induced tree, bridges, cut vertices [Cont'd]

Lecture 3 (Oct 8) : connectivity in directed graphs [Cont'd] [Since I have to attend a workshop, the course has been recorded here. The in-person course has been canceled.

Lecture 4 (Oct 10) : shortest path, heaps [Slides, Annotated]

Lecture 5 (Oct 15) :  minimum spanning tree (MST), union-find, other variants [Slides, Annotated]     A proof of amortized log*(n) for union-find[Notes]

Lecture 6 (Oct 17) :  other greedy algorithms and matroid [Slides, Annotated]  A proof for the second MST [Notes]

Lecture 7 (Oct 22) :  other greedy algorithms cont'd, binary search  + greedy [Slides, Annotated]

Lecture 8 (Oct 24) :  binary search cont'd, divide-and-conquer start (count inversion/closest pair) [Slides, Annotated]

Lecture 9 (Oct 29) :  divide-and-conquer (faster multiplication/even faster multiplication) FFT [Slides, Annotated]

Lecture 10 (Oct 31) :  build data structures from ``useless'' divide-and-conquer -- Segment Tree [Slides, Annotated]

Lecture 11 (Nov 5) :  dynamic programming, knapsack problems and variants [Slides, Annotated]

Lecture 12 (Nov 7) :  range DP, tree DP [Slides, Annotated]

Lecture 13 (Nov 12) :  traveling salesman, the longest increasing subsequence (and speedup), Bellman-Ford and Floyd-Warshall [Cont'd]

Lecture 14 (Nov 14) :  randomized algorithm: selection, hash table [Slides, Annotated]

Lecture 15 (Nov 19) :  randomized algorithm cont'd; network flow, min-cut max-flow duality [Slides, Annotated]

Lecture 16 (Nov 21) : network flow [Cont'd]

Lecture 17 (Nov 26) : network flow cont'd and NP-complete [Slides]

Lecture 18 (Nov 28) :  Skip, Thanksgiving

Lecture 19 (Dec 3) :  review [Slides]

Lecture 20 (Dec 5) :  basics of computational geometry [Slides, Annotated]

After each class, I will upload annotated notes. The annotated notes may be different from the first version, as we may not have time to cover all materials. 

Homework

Assignments will be added biweekly. It is highly encouraged to typeset solutions in LaTeX. 

[For Project Option 2 Group Only] If your group choose to do project option 2, please include screenshots (for each group member) of at least 4 coding problems (per group member) done together with each homework submission. The screenshot should contain information like difficulties, date and problem names. Each member should also write a short solution bi-weekly for one problem, but you are not required to submit it with your homework. Just compile all solutions together into a single PDF, and it is due on the same date with project option 1 (TBA). I.e., if there are 5 homework in total, each member should solve in total 20 and 80 as a group of 5 at the end of the quarter. 

Homework 1: [File] [LaTeX Source]

Homework 2: [LaTeX Source]

Homework 3: [LaTeX Source]

Homework 4: [LaTeX Source]

Homework 5: [LaTex Source]



Template: [Overleaf Link]

Useful Resources

Podcasts: podcast.ucsd.edu

Textbook: Algorithm Design by Jon Kleinberg and Éva Tardos

Other recommended reading: Algorithm, A Gentle Approach by Russell Impagliazzo and Ragesh Jaiswal

Gradescope: submit assignments, view graded assignments, and make regrade requests.

Canvas: lecture slides, background materials and more.

Piazza: discussion, announcements, finding study groups.