Algorithms in Action
Haim Kaplan and Uri Zwick
Spring Semester 2018

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


Introduction

Presentation (pptx)

 

Fast Fourier Transform
Integer and Polynomial Multiplication
String Matching

Presentation (pptx)
String matching examples (pptx)


Homework 1 (pdf)

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

Presentation (pptx)

 

MAX-CUT using Semidefinite Programming

Presentation (pptx)

 

Local Search
MAX CUT, Min Bisection
Image Segmentation

Part1 (pptx)
Part2 (pptx)

Local Search - Bibliography (pdf)

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

Presentation (pptx)

Clustering - Bibliography (pdf)

Markov Chain Monte Carlo

Part1 (pptx)
Part2 (pptx)

SAT Solving
Conflict Driven Clause Learning (CDCL)
Randomized algorithms

Part1 (pptx)
Part2 (pptx)

Lecture Summaries (from two yeas ago) by Arazim Project

Sample Exam (pdf)