**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.