# Advanced Algorithms

## Lecture handout

Distributed during the first lecture. An electronic copy of the handout can be found here.

## Lectures

- All slides combined PDF

### I. Sorting Networks, Counting Networks (Slides PDF)

- 27/04/2018: Lecture 1 (Course Intro, Sorting Networks), References: CLRS (2nd edition), Chapter 27 PDF
- 30/04/2018: Lecture 2 (Sorting Networks continued, Glimpse at the AKS Sorting Network, Counting Networks), References: see additional references below, Additional Notes from the Lecture PDF

### II. Matrix Multiplication (Slides PDF)

- 02/05/2018: Lecture 3 (Matrix Multiplication, Dynamic Multithreading, Parallel Matrix Multiplication) References: CLRS (3rd edition), Chapter 4 and 28 (Serial and Parallel Matrix Multiplication), Chapter 27 (Multithreading)

### III. Linear Progamming (Slides PDF)

- 04/05/2018: Lecture 4 (Linear Programming (Conversion into Standard and Slack Form, Geometry and Structure of Optimal Solutions)), References: CLRS (3rd edition), Chapter 29 A more detailed version of the proof on slide 21 (which is non-examinable) can be found here PDF.
- 07/05/2018: Lecture 5 (Linear Programming (Simplex Algorithm), References: CLRS (3rd edition) Chapter 29
- 09/05/2018: Lecture 6 (Linear Programming (Finding an Initial Solution), Introduction to Approximation Algorithms), References: CLRS (3rd edition) Chapter 29

### IV. Approximation Algorithms: Covering Problems PDF

- 11/05/2018: Lecture 7 (Covering Problems (Vertex Cover, Set Cover)), References: CLRS (3rd edition), Chapter 35.1
- Slide 22: "|X|=u_0" should be replaced by "|S|=u_0"

### V. Approximation Algorithms via Exact Algorithms PDF

- 14/05/2018: Lecture 8 (Approximation Algorithms via Exact Algorithms (Subset-Sum, Machine Scheduling)), References: CLRS (3rd edition), Chapter 35.3, Chapter 35.5
- Slides 21-22 dealing with the PTAS for Parallel Machine Scheduling were skipped and are not examinable.

### VI. Approximation Algorithms: Travelling Salesman Problem PDF

- 16/05/2018: Demonstration: Solving TSP exactly via Linear Programming, Slides (Many thanks to Andrej Ivaskovic and Petar Velickovic) PDF, Solution Progress PDF (Remark: These slides are from a previous year and show a slightly different progress.)
- Any material presented on 16/05/2018 is not examinable.
- 18/05/2018: Lecture 10 (Travelling Salesman Problem (Metric TSP: MST-Approximation, Christofides Algorithm), References: CLRS (3rd edition), Chapter 35.2

### VII. Approximation Algorithms: Randomisation and Rounding PDF

- 21/05/2018: Lecture 11 (Randomised Approximation Algorithms, MAX3-CNF, Vertex Cover), References: CLRS (3rd edition), Chapter 35.3
- 23/05/2018: Lecture 12 (Randomised Approximation Algorithms cntd., Set Cover), References: CLRS (3rd edition), Chapter 35.3

## Exercises (complete solution notes are available to the supervisors)

## Recommended Reading

- [CLRS] Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2009).
*Introduction to Algorithms. MIT Press (3rd ed.)*

## Additional References

### Sorting and Counting Networks

- Miklos Ajtai, Janos Komlos, Endre Szemeredi.
*Sorting in c log n parallel steps*, Combinatorica 3(1):1-19, 1983. - James Aspnes, Maurice Herlihy, Nir Shavit.
*Counting Networks*, Journal of the ACM 41(5):1020-1048, 1994. - Costas Busch, Maurice Herlihy.
*A Survey on Counting Networks*, Proceedings of the 1st Workshop on Distributed Data and Structures, pages 13-20, 1998. - Vasek Chvatal.
*Lecture Notes on the AKS Sorting Network*, PDF - Shlomo Hoory, Nathan Linial, Avi Wigderson.
*Expander Graphs and their Applications*, Bulletin of the American Mathematical Society, 43(4):439-561, 2006.

### Simplex Algorithm

- Robert G. Bland.
*New finite pivoting rules for the simplex method*, Mathematics of Operations Research 2, (2):103-107, 1977. - Daniel A. Spielman and Shang-Hua Teng.
*Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time*, Journal of the ACM, 51(3):385-463, 2004.

### Approximation Algorithms

- Vasek Chvatal, William J. Cook, George B. Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson.
*Solution of a Large-Scale Traveling-Salesman Problem*, 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 7-28, 2010. - G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson,
*Solution of a Large-Scale Traveling-Salesman Problem*, Operation Research 2:393-410, 1954. - David P. Williamson and David B. Shmoys.
*The Design of Approximation Algorithms*, Cambridge University Press, 2011. (electronic version available here)