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 

 

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.