Algorithms in Action
Haim Kaplan and Uri Zwick
Fall Semester 2020

Final grade = 80% * exam grade + 20% * homework grade
Homework grade = Average of 5 homework assignments.

 

Introduction

Presentation (pptx)

 

SAT Solving
Conflict Driven Clause Learning (CDCL)
Randomized algorithms

Directory with presentation and videos


Homework 1 (pdf)

Fast Fourier Transform
Integer and Polynomial Multiplication
String Matching

Presentation (pptx)
Directory with videos

Homework 2 (pdf)

Multiplicative Weight Updates
Predicting using expert advice
Learning a linear classifier
Approximately solving 0-sum games
Maximum Multicommodity flow problems

Presentation (pptx)

Directory with videos

Homework 3 (pdf)


SDP-based approximation algorithms
MAX-CUT and COLORIING

Presentation (pptx)
video

 

Gradient Descent and variants

Presentations and videos

Homework 4 (pdf)

Local Search

Directory with presentation and videos

 

Some past material (subject to change)

Local Search
MAX CUT, Min Bisection
Image Segmentation

Part1 (pptx)
Part2 (pptx)


Homework 3 (pdf)

Bibliography (pdf)

Clustering
k-center, k-median, k-means

Presentation (pptx)

Bibliography (pdf)

Markov Chain Monte Carlo

Part1 (pptx)
Part2 (pptx)


Homework 4 (pdf)