Course Syllabus

The goal of this course is to teach you to design, analyze, and implement algorithms. Algorithms play a fundamental role in today's world, guiding important technological, social, and economic decisions. In this course, we will

study some fundamental principles/paradigms of algorithm design
learn about efficient algorithms for some common problems
learn how to analyze algorithms, from an efficiency and correctness perspective
understand "reductions" between algorithmic problems, and the limits of efficient algorithms.

The course will also involve programming assignments that test your ability to convert algorithmic ideas into efficient code, which will be evaluated using an automated online judging system.

Textbook: Algorithms (Dasgupta, Papadimitriou, Vazirani)

Quick links: Piazza (access code: 41502025), Gradescope

Instructors & TA Office Hours

Prof. Aditya Bhaskara -- Tue 10am - 12pm (WEB 2692)
Prof. Varun Shankar -- Wed 10 am to 11 am, Friday 11 am to 12 pm (WEB 2891).

Norman Chase Canning -- Monday 1:30pm-3:30pm (MEB 3105)
Cen-Jhih Li -- Tue 1:00pm - 3:00pm (MEB 3147)
Derek Martinez -- Mon 1:30pm - 3:30pm (MEB 3105)
Sreekar Pasumarthi -- Wed 4:00pm - 5:00pm, Fri 2:00pm - 3:00pm (CADE lab)
Hung Phan Quoc Viet -- Wed 2:00pm-5:00pm, Fri 2:00pm-4:00pm (CADE lab)

Here is the link to the TA Queue

Course policies & syllabus document

Syllabus, lecture schedule

Here is a tentative lecture schedule for the semester. Lecture topics, slides, resources, etc. will be posted below. Videos are located in Media Gallery on Canvas.

Lecture #	Topic(s)	Resources
1 (Aug 18)	Introduction, Course outline, Policies and logistics	Slides
2 (Aug 20)	Data Structures: Lists, Arrays, Dynamic Array, BST;	Slides Additional material: Lecture notes on implementing BST
3 (Aug 25)	Data Structures: Prefix Trees (Trie), Hash Tables; Review of Asymptotic Notation	Slides (1) Slides (2) Bonus material: dynamic hash tablesLinks to an external site.
4 (Aug 27)	Finish up Set; Programming Session 1	InterviewQuestions.pdf [We did Big File Sort]
5 (Sep 3)	Divide and Conquer, Intro to Recurrences. Factorial, Fibonacci, Binary Search, Mergesort	Divide and Conquer, Intro to Recurrences. Reading: Dasgupta et al. textbook, chapter 2.2 and 2.3
6 (Sep 8)	Analysis via Recurrences, Master Theorem	Slides (unannotated) Slides (annotated) Reading: Dasgupta et al. textbook, chapter 2.2 and 2.3
7 (Sep 10)	Examples: Karatsuba Algorithm for Multiplication; Strassen's Algorithm Teaser	Slides (unannotated) Slides (annotated) Reading: Dasgupta et al. textbook, chapter 2.1 and 2.5
8 (Sep 15)	Review, examples of Guess-and-Prove, plug-and-chug; Programming Session 2	Slides (annotated)
9 (Sep 17)	Dynamic Programming as "recursion done right" (Fibonacci, Longest Palindromic Substring)	Slides: InterviewQuestions.pdf Reading: Dasgupta et al. textbook, Chapter 6.1
10 (Sep 22)	Graph Primitives: Adjacency matrices and lists. Graph exploration: DFS, connected components	Slides: Graphs.pptx Reading: Dasgupta et al. textbook, chapter 3 and 4
11 (Sep 24)	DFS + pre/post counting, topological sorting, intro to strongly connected components	Slides: Graphs_contd.pptx Reading: Dasgupta et al. textbook, chapter 4.6, 6.1
12 (Sep 29)	Graph Paths: BFS. Midterm review	Slides (not annotated) Slides (annotated) Reading: Dasgupta et al. textbook, chapter 4.6, 6.1
13 (Oct 1)	Midterm Exam
14 (Oct 13)	Dynamic Programming as memoization, CoinChange	Slides (not annotated) Slides (annotated) Reading: Dasgupta et al. textbook, chapter 6.1
15 (Oct 15)	Dynamic Programming Contd. (LIS, Shortest Path)	Slides (not annotated) Slides (annotated) Reading: Dasgupta et al. textbook, chapter 6.1, 6.2, 6.6
16 (Oct 20)	More Dynamic Programming (Shortest path, conclude DP)	Slides (annotated) Reading: Dasgupta et al. textbook, chapter 6.6, 6.4
17 (Oct 22)	From DP to Greedy Algorithms: detour via BFS and Dijkstra.	Slides
18 (Oct 27)	Conclude priority queues, more Greedy algorithms (making change, meeting scheduling)	Slides Reading: Dasgupta et al. textbook, chapter 5.1
19 (Oct 29)	Greedy algorithms for minimum spanning trees (Prim's, Kruskal's); disjoint sets (aka union finds).	Slides from Oct 27 + Slides
20 (Nov 5)	Finish union-find. Start Linear Programming -- formulating problems as LP	Slides: DisjointSets.pptx LP Slides: Reading: Dasgupta et al. textbook, chapter 7.1
21 (Nov 10)	Linear Programming: Duality, Flows in Networks	Slides (not annotated) Slides (annotated) Reading: Dasgupta et al. textbook, chapter 7,2, 7.3, 7.4
22 (Nov 12)	Lower Bounds Intro, Satisfiability, P and NP	Reading: Dasgupta et al. textbook, chapter 8.1 and 8.2 Lecture recording (Guest lecturer: Ben Jones)
23 (Nov 17)	Intractability, Reductions between problems	Slides (annotated) Reading: Dasgupta et al. textbook, chapter 8.3
24 (Nov 19)	Reductions (SAT - 3SAT - ILP)	Slides (annotated) Reading: Dasgupta et al. textbook, chapter 8.3
25 (Nov 24)	More Reductions (3SAT - ZOLP - ZOE - Subset Sum)	Slides (annotated) Reading: Dasgupta et al. textbook, chapter 8.3
26 (Nov 26)	LP recap, Matching, Flows as examples (Note -- day before thanksgiving)	Slides (annotated) Reading: Dasgupta et al. textbook, chapter 9
27 (Dec 1)	Algorithms in Science, Engineering, and Machine Learning
28 (Dec 3)	Review for final exam

Resource Links:

Logarithmic rules: https://www.youtube.com/watch?v=G1w0HB4XkrE

Arithmetic Series: https://www.youtube.com/watch?v=H52tlURZQYo

Geometric Series: