Combinatorial Algorithms and Data Structures
CS 270 - Spring 2023 (Syllabus)
Design and analysis of efficient algorithms for combinatorial problems. Graph algorithms; linear programming; data structures; analysis of data structures; online algorithms; primal-dual methods; approximation algorithms; randomized algorithms; streaming; learning from experts; word RAM model.
This is a graduate course, though there may be room for a limited number of advanced undergraduate students satisfying the following prerequisites: mathematical maturity and comfort with algorithms (e.g. CS 170), discrete probability, and linear algebra.
Combinatorial Algorithms and Data Structures CS 270 - Spring 2023 (Syllabus) Design and analysis of efficient algorithms for combinatorial problems. Graph algorithms; linear programming; data structures; analysis of data structures; online algorithms; primal-dual methods; approximation algorithms; randomized algorithms; streaming; learning from experts; word RAM model.
This is a graduate course, though there may be room for a limited number of advanced undergraduate students satisfying the following prerequisites: mathematical maturity and comfort with algorithms (e.
Links: scribe template, lecture video playlist (must be logged into YouTube with @berkeley.edu account to view).
Lecture Schedule Lec# Date Topic Scribe(s) 1 Tuesday, 1/17/23 logistics, course topics, single-source shortest paths w/ negative edges
(price fns, scaling, Bernstein-Nanongkai-WulffNilsen) Altan Haan 2 Thursday, 1/19/23 BNW wrap-up, scaling for max flow Sanjay Gollapudi
Andrew Lin 3 Tuesday, 1/24/23 blocking flow, link-cut trees Alejandro Sanchez
Course Project The project can take several forms:
Solve an open theory problem, formulate a new problem, or make some other contribution to the study of algorithms/lower bounds for processing big data. Implementation: there are a few options here. For example, (1) pick a problem and implement at least one sophisticated algorithm for the problem (e.g. BNW for shortest paths), or possibly multiple to compare, trying to find heuristics that might provide practical speedup, or (2) design and build a system that uses provably good algorithms such as those learned in class.
CS 270 - Spring 2023 Syllabus Announcements Email cs270-s23-staff@lists.eecs.berkeley.edu to be added to the course EdStem. Also, if you haven’t already, please fill out this Google form. Specifics Lecture time: Tuesday & Thursday 2–3:30pm First lecture: Tuesday, January 17, 2023. Lecture room: McCone 141. Contact: Email cs270-s23-staff@lists.eecs.berkeley.edu Grading Scribing/grading (10%). Each student must either (co-)scribe one lecture or grade one problem in one problem set.