Algorithms, December 2020 at CIS

Instructor: David Woodruff

Lectures: 7-9pm ET on Saturday for first 6 weeks, then 7-10pm ET Saturday

Office Hours: Talk with Tianrui

TAs: Tianrui Liu

Course Description

Grading

Latex

Lectures

Problem Sets

References

Course Description

Design and Analyze Algorithms!
Algorithms: divide-and-conquer, hashing and data structures, randomization, linear programming
Analysis: recurrences, probabilistic analysis
Dual to Algorithms: complexity theory and lower bounds
New Models: data streams

Grading

Grading is based on 4 homeworks each worth 8%, an exam worth 18%, a final project worth 40%, and class participation worth 10%

Latex

We encourage homework solutions, scribe notes, and final projects to be typeset in LaTeX. If you are not familiar with LaTeX, see this introduction.

Lectures

Topic 1 (Selection)
Topic 2 (concrete bounds)
Topic 3: Convex geometry. See these slides at CMU for similar material, as well as these slides at CMU for similar material
Topic 4: Gradient Descent (mostly whiteboard)
Topic 5 (linear programming)

Problem Sets

Homework 1

Homework 2

Homework 3

Homework 4 on gradient descent - see TA for a copy

Homework 5

References

Materials from the following course might be useful in various parts of this course: Undergraduate Algorithms Class at Carnegie Mellon University

Maintained by David Woodruff