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:PDFSolution 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 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.