Center Hall 115 (Russell Impagliazzo) MWF 12:00pm - 12:50pm
WLH 2001 (Qipeng Liu) MWF 2pm - 2:50pm
TBD
24% homeworks + 24% quizzes + 4% surveys + 48% final
Cutting-edge applications from large language models to bioinformatics to data science to circuit design to internet commerce require efficient use of computational resources. In this course, we will learn how to precisely specify the requirements of applications and learn the most useful general techniques for designing and analyzing efficient algorithms for these applications. These techniques include graph search, reductions, greedy algorithms, divide-and-conquer, dynamic programming and hill-climbing algorithms such as for network flow. We will also look at inherent limitations of algorithms due to the computational complexity of problems, and how to circumvent some of these limitations, e.g., by designing approximation algorithms.
We assume that students will have had exposure to basic discrete mathematics, including graphs, probability, counting techniques, asymptotic notation, recurrence relations, and proof techniques, such as are covered in CSE 20 and CSE 21. We also assume familiarity with basic data structures, such as linked lists, arrays, hash tables, and stacks which are covered in CSE 12. Some assignments will require students to implement algorithms in the programming language of their choice, and measure and plot their performance.
Sept 26-29: Introduction. Horner’s method for polynomial evaluation. Review of correctness proofs, loop invariants, asymptotic time analysis, recursive algorithms, recurrence relations. Chapter 1 and appendices.
Oct 1–8: Graph search, depth first search and applications. Chapter 2.
October 10-17: BFS, Shortest paths, Dijkstra’s algorithm, using data structures (heaps). Chapter 3 (first half)
October 20-22: Reductions. Chapters 3 (second half)
October 24-29: Greedy algorithms. Chapter 4.
Oct 31-Nov 3: Kruskal’s MST algorithm, DSDS. Chapter 5.
Nov 5–12: Divide and conquer. Chapter 6.
Nov 14-26: Backtracking and Dynamic programming. Chapter 7-8
Dec 1-5: Some of network flow and applications; hillclimbing, and/or NP-completeness as time permits. Chapter 9-11
Podcasts: podcast.ucsd.edu
Textbook: 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.