Algorithm Design and Analysis (CSE 202, 2025 Fall)

Course Information

Location:

Galbraith Hall 242

Time:

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

TA(s):

Madhusudan Agarwal, Wednesday 4-5pm at B260A

Zhengan Cheng, Thursday 9-10am at B270A

Konstantin Radosvetov Garov, Thursday 6-7pm at B275

Chujia Guo, Tuesday 11am-12pm at B275

Rahul Sharma Nemmani, Friday 3-4pm at 240A

Vikram Sirupurapu, Friday 2pm-3pm at B260A

Haemanth Velmurugan, Mondays 11 am-12 pm at B270A

me, TBD

Grading:

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

20% homework + 20% project + 20% final (in-person) exam + 40% min(homework, final) (The exam format has changed this year. The primary reason is to ensure a fair environment for all students, particularly in light of the growing use of AI tools.)

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:

introduction
graph basics/reachability/topological sorting and more
shortest path/dijistra algorithm/heap and applications
more greedy algorithms, greed + binary search
divide-and-conquer/master theorem, segment tree and its variants
randomized algorithm, treap, hash table
dynamic programming
network flow: max-flow and min-cut
NP-complete problems and how to solve them using brute-force, dynamic programming and etc
a gentle touch on computational geometry
other materials may be added (string algorithms, approximate algorithms, or even intro to quantum computing)

Lecture 0 (Sept 25) : Welcome! + Background. [Slides1, Slides2]

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:

Homework 2:

Homework 3:

Homework 4:

Homework 5:

Template: [Overleaf Link]

Useful Resources

Podcasts: podcast.ucsd.edu

Textbook: Algorithm Design by Jon Kleinberg and Éva Tardos

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

Canvas: lecture slides, background materials and more.

Piazza: discussion, announcements, finding study groups.