CS 4150-001 Fall 2025 Algorithms
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).
- Cen-Jhih Li
| Lecture # | Topic(s) | Resources |
| 1 (Aug 18) | Introduction, Course outline, Policies and logistics | Slides |
| 2 (Aug 20) | Data Structures: Lists, Arrays, Dynamic Array, BST; |
Additional material: Lecture notes on implementing BST |
| 3 (Aug 25) | Data Structures: Prefix Trees (Trie), Hash Tables; Review of Asymptotic Notation |
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 |
Reading: Dasgupta et al. textbook, chapter 2.2 and 2.3 |
| 7 (Sep 10) | Examples: Karatsuba Algorithm for Multiplication; Strassen's Algorithm Teaser |
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 |
Reading: Dasgupta et al. textbook, chapter 4.6, 6.1 |
| 13 (Oct 1) | Midterm Exam | |
| 14 (Oct 13) | Dynamic Programming as memoization, CoinChange |
Reading: Dasgupta et al. textbook, chapter 6.1 |
| 15 (Oct 15) | Dynamic Programming Contd. (LIS, Shortest Path) |
Reading: Dasgupta et al. textbook, chapter 6.1, 6.2, 6.6 |
| 16 (Oct 20) | More Dynamic Programming (Shortest path, conclude DP) |
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 |
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 |
Reading: Dasgupta et al. textbook, chapter 8.3 |
| 24 (Nov 19) | Reductions (SAT - 3SAT - ILP) |
Slides (annotated) |
| 25 (Nov 24) | More Reductions (3SAT - ZOLP - ZOE - Subset Sum) |
Reading: Dasgupta et al. textbook, chapter 8.3 |
| 26 (Nov 26) | LP recap, Matching, Flows as examples (Note -- day before thanksgiving) |
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: