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



Problem Set 1:PDF †††Solution:PDFSolution to Exercise 3: Link

Problem Set 2:PDF†† Solution:PDF

Sorting networks

         Batcherís sorting networks

         The AKS sorting network


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 probingPPTX


Homework grades


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.