ADVANCED ALGORITHMS (0368-4485-01)
November 2016, Tel Aviv University
Lecturer: Uri Zwick
Exam:
Thursday, February 9, 2016
List of subjects
Matrix multiplication based graph algorithms
· Strassen’s matrix multiplication algorithm
· Matrix inversion and determinants
· Boolean matrix multiplication and transitive closure
· …
Presentation: PPTX
Problem Set 1: PDF Solution:
PDF
Solution to Exercise 3: Link
Problem Set
2: PDF
Solution: PDF
Sorting networks
·
Batcher’s sorting networks
·
The AKS sorting network
Presentation: PPTX
Problem Set
3: PDF Official
Solution: PDF
Integer sorting
Presentation: PPTX
Problem Set
4: PDF
Official Solution: PDF
Hash tables
·
Hash table basics (Review of undergrad
material) PPTX
·
Linear probing PPTX
Sample exam
from last year
(Question 3 is about Van Emde Boaz trees that were
not covered this term.)
(Question 4 is on Batcher’s sorting networks. AKS was not covered last term.)
Note that the
exam this term is without any material.