# Advanced Algorithmics, 2014, 1DL480

Visit this page often for updated information and important news.

- (2014-05-22) The schedule and some brief information about the oral exam are available here.
- (2014-04-07) The lecture on Apr 11 is cancelled.
- (2014-01-21) This page is now available.

## Teachers

**Practical questions:** Call Arne: 0733 66 55 15 or Karl: 0760 39 53 40. Alternatively visit Karl in 1310, at any time.

## Important!

- Written Exam, 2014-05-28
- Oral Exam, between 2014-06-02 and 2014-06-03

All assignments are done individually.

## Assignments from Text Book

See schedule. Will be updated.

At the end of the course, each student will have an oral examination, where you

must bring solutions to

(i) all mandatory assignments, and

(ii) at least half of the other assignments.

Your solutions must be nicely printed (not handwritten, but it is ok to include handmade figures if they are nicely done)

The level of detail should be roughly as the explanations in the book.

## Other Assignments

These assignments have to be handed in by the deadline in an open and widely adopted format (such as PDF).

### Assignment 1

- 1a: Use Citeseer or Google Scholar and try to find the most cited paper presenting a solution to the Traveling Salesman Problem (TSP).
- 1b: Find, using Citeseer and/or any search engine, your own favorite paper on TSP and make a four-slide executive summary.
- You should deliver
- (i) Title, author, journal/conference etc of the most cited paper,
- (ii) the same for the paper presenting the best solution (in your opinion),
- (iii) plus a 4-slide executive summary of your favorite paper.

Email your solution to Karl, make sure to write "AdvAlg" in the header.

Make sure your own name is clearly written on the solution.

Deadline: See Schedule

### Assignment 2

- 2a: Find your favorite paper on Tabu Search and write a 2 page executive summary.
- 2b: Do the same for your favorite paper on Simulated Annealing.
- 2c: Do the same for your favorite paper on Genetic Algorithms.

Deadline: See Schedule

### Assignment 3

Find a good paper on algorithms and/or optimization, preferrably from a ACM or IEEE journal or conference. Write a 2-3 page executive summary, make a 5-slide presentation.

Hint: Use Uppsala University Library's List of Journals to get access to all major journal and conference homepages. Examples of good journals include, but are not limited to, SODA (Symposium on Discrete Algorithms) and FOCS (Foundations of Computer Science).

Deadline: See Schedule

## Schedule (will change dynamically)

Day | Time | Room | Topic | Book Chapter | Assignment deadlines | |
---|---|---|---|---|---|---|

Ons Jan 22 | 10.15-12.00 | Pol 1245 | Review of old knowledge, Probabilistic Analysis, Randomized Algorithms. Introducing assignment 1. | 1-4, 5 | ||

Mon Jan 27 | 13:15-15:00 | Pol 1245 | Sorting in linear time, Median and Order statistics | 8, 9 | ||

Ons Jan 29 | 15:15-17:00 | Pol 1245 | Variants of Balanced trees, red-black trees, etc | 13 | Problems 9-1, 9-2 a,b,c | |

Fri Jan 31 Thu Feb 6 | 13:15-15:00 | Pol 1245 | NO LECTURE | |||

Thu Feb 6 | 10:15-12:00 | Pol 1245 | NO LECTURE | |||

Ons Feb 12 | 15:15-17:00 | Pol 1245 | NO LECTURE | |||

Mon Feb 17 | 10:15-12:00 | Pol 1245 | The Traveling Salesman Problem. Genetic Algorithms, Simulated annealing, Tabu Search, introducing Assignment 2. | Assignment 1 | ||

Thu Feb 20 | 13:15-15:00 | Pol 1245 | NO LECTURE | |||

Tue Feb 25 | 13:15-15:00 | Pol 1245 | Augmenting data structures | 14 See also http://wwwisg.cs.uni-magdeburg.de/ag/lehre/WS1112/GDS/slides/S5.pdf, http://wwwisg.cs.uni-magdeburg.de/ag/lehre/WS1011/GDS/slides/S4.pdf and http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2009/GDS/slides/S10.pdf | ||

Thu Feb 27 | 13:15-15:00 | Pol 1245 | B-trees | 18 | Problem 17-3 (mandatory) | |

Thu Mar 6 | 13:15-15:00 | Pol 1245 | NO LECTURE | |||

Mon Mar 10 | 8:15-10:00 | Pol 1245 | No LECTURE | |||

Thu Mar 13 | 10:15-12:00 | Pol 1245 | EMPTY SPACE | |||

Mon Mar 24 | 10:15-12:00 | Pol 1245 | Amortized Analysis | 17 | Answer the questions on the last slide of the handout on radix sort. Do Exercises 14.3-1, 14.3-2, 14.3-3 | |

Thu Mar 27 | 13:15-15:00 | Pol 1245 | Universal hashing Perfect Hashing, Tries, van Emde Boas-trees | 11.3, 11.5, Handout | Problem 18-2 (mandatory) | |

Wed Apr 2 | 15:15-17:00 | Pol 1245 | Tries, van Emde Boas-trees, Packed computation, very fast sorting and searching | Handout "New bounds on sorting and searching,", sections 1-4 | Exercise 11.5-1, Problem 11-4* (It is mandatory to do at least one of these two) | |

Mon Apr 7 | 10:15-12:00 | Pol 1245 | Genetic Algorithms, Simulated annealing, Tabu Search | Assignment 2 | ||

Fri Apr 11 | 13:15-15:00 | Pol 1245 | Tries, van Emde Boas-trees, Packed computation, very fast sorting and searching | Handout "New bounds on sorting and searching,", sections 1-4 | Exercise 11.5-1, Problem 11-4* (It is mandatory to do at least one of these two) | |

Mon Apr 14 | 10:15-12:00 | Pol 1245 | NP-completeness | 34 | ||

Tue Apr 15 | 15:15-17:00 | Pol 1245 | NP-completeness | 34, see also http://www.cs.uky.edu/~lewis/cs-heuristic/text/class/more-np.html | ||

Mon Apr 28 | 15:15-17:00 | Pol 1245 | Polynomials and Fast Fourier Transforms | 30 | ||

Mon May 5 | 10:15-12:00 | Pol 1245 | Linear Programming and Integer Programming, NP-completeness | 29, 34, see also the wikipedia article http://en.wikipedia.org/wiki/Linear_programming | Problem 3 in the handout on sorting and searching. Exercises 29.2-2, 29.2-4, 29.2-6 | |

Wed May 7 | 15:15-17:00 | Pol 1245 | CANCELLED | |||

Tue May 13 | 10:15-12:00 | Pol 1245 | Presentations of Assignment 3 | Assignment 3 | ||

Tue May 20 | 15:15-17:00 | Pol 1245 | Exam preparation | Exercises 30.2-2, 30.2-3, 34.1-4, 34.2-6, 34.2-7 (Hint, use topological sorting), 34.2-10, 34.4-6, 34.5-2 | ||

Mon May 26 | 10:15-12:00 | Pol 1245 | Exam preparation | Exercises 30.2-2, 30.2-3, 34.1-4, 34.2-6, 34.2-7 (Hint, use topological sorting), 34.2-10, 34.4-6, 34.5-2 | ||

Wed May 28 | ? | Pol | Written Exam |

## Course Material

### Old Exams

### Literature and Notes

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, 2nd edition, MIT Press, 2001 (last available printing: 4th). Visit the book's web site at http://mitpress.mit.edu/algorithms/ (errata etc.)

- Lecture notes, Proofs of NP-completeness.
- Lecture notes, Introduction, chapters 1-4,5 (pdf).
- Lecture notes on Radix Sort (pdf).
- Lecture notes Chapter 13 Red-Black Trees (SBB-trees) (pdf).
- Lecture notes Chapter 11.3 and 11.5 Universal Hash functions and Perfect Hashing (pdf).
- A. Andersson. New bounds on sorting and searching, http://user.it.uu.se/~arnea/algoritmanalys/sortsearch2.pdf. (Figure 1 is missing in the manuscript, a low-quality scanned figure can be found here http://user.it.uu.se/~arnea/algoritmanalys/trie.pdf.
- Lecture notes in Linear programming (LP) anf Integer Programming (IP), Chapter 29 (pdf).
- Lecture Fast Fourier Transforms (FFT), Chapter 30 (pdf).
- Wikipedia on universal hashing http://en.wikipedia.org/wiki/Universal_hashing
- Slides on NP-completeness (by Michael T. Goodrich and Roberto Tamassia) can be found at the following link http://ww3.algorithmdesign.net/handouts/NPComplete.pdf. (Slides only for use within non-profit institutions, chapter references are for another textbook, written by Goodrich and Tamassia http://ww3.algorithmdesign.net .)
- Nice lecture notse on NP-completeness by Mark De Berg: http://www.win.tue.nl/~mdberg/Onderwijs/Algoritmiek_Material/Slides/AlgorithmsLecture_10.pdf

### Some other useful links

- A very good decription of TSP http://www2.research.att.com/~dsj/papers/TSPchapter.pdf
- CiteSeer, for finding articles, refernces, etc: http://citeseer.ist.psu.edu/
- A nice presentation of the Traveling Salesman Problem: http://www.tsp.gatech.edu/
- See also this page on TSP art: http://www.oberlin.edu/math/faculty/bosch/making-tspart-page.html
- Dictionary of Algorithms and Data Structures http://www.nist.gov/dads/
- Compendium on NP Optimization Problems http://www.nada.kth.se/~viggo/problemlist/compendium.html
- DIMACS Implementation Challenges http://dimacs.rutgers.edu/Challenges/
- The art gallery problem Given a polygon-shaped art gallery with n sides, what is the minimal number of guards that need to be placed in the gallery so that they see every corner of it? There are museums with 3n walls for which n guards are required. On the other hand, floor(n/3) guards are enough for any n walls museum, but an algorithmic problem could be to determine the positions of them. http://mathworld.wolfram.com/ArtGalleryTheorem.html
- Related (difficult) problems are 5, 6, 7 of http://www.ics.uci.edu/~eppstein/280g/open.html
- Solving Rubik's Cube. Maybe too famous, there are solutions at, e.g., http://helmsoft.org/cube/rubikscube
- Given a finite set of building blocks consisting of several 1x1x1 cubes (or, in the 2d version, 1x1 squares) glued together at facets, put them together into a big cube (rectangle) of given dimensions. The Slothouber-Graatsma Puzzle http://mathworld.wolfram.com/Slothouber-GraatsmaPuzzle.html and Conway's Puzzle http://mathworld.wolfram.com/ConwayPuzzle.html are special cases.
- Magic squares: How to generate magic squares (nxn matrices with constant row, column, and big diagonal sums). The magic squares are obviously solutions to a linear equation system so they form a subspace of the space of all nxn matrices. But you can easily invent restrictions that makes it more interesting, such as requiring all numbers to be prime, or powers, or any other numerologically interesting property. You can also try many-dimensional magic squares. see http://mathworld.wolfram.com/topics/MagicSquares.html
- The Domino game: Given a game board consisting of a subset X of {0,...,n}^2, player 0 and 1 alternatingly remove two adjacent squares from X. (Equivalently, paint some squares of a chessboard red, then try to cover only red squares with domino bricks.) The player that gets stuck first (cannot move) loses.
- http://www.ics.uci.edu/~eppstein/junkyard/open.html. Open Problems in Computational Geometry
- http://cs.smith.edu/~orourke/TOPP/Welcome.html. The Open Problems Project
- http://www.ics.uci.edu/~eppstein/280g/open.html. Mesh Generation for Graphics and Scientific Computation, Open Problems
- http://www.ics.uci.edu/~eppstein/cgt/. Combinatorial Game Theory
- http://mathworld.wolfram.com/topics/MagicSquares.html
- http://mathworld.wolfram.com/topics/Chess.html
- Good page containing a lot of proofs for NP-completeness, http://www.cs.uky.edu/~lewis/cs-heuristic/text/class/more-np.html

### Reading instructions for the written exam

See schedule

Prepare yourself by

- reading and understanding all material (textbook chapters and handouts)
- solving more exercises in the book
- refresh your memory of the book chapters covered by earlier courses. (Altogether, the AD1, AD2, and AD3, have covered chapters 1 - 18, 21 - 30, 32 - 34)

## Examination

i. Written Exam

ii. Mandatory assignments

iii. Oral examination, each student will have an oral exam, after the written exam. At the oral exam, you must bring written solution (not handwritten, but nicely formatted)

solutions to at least half of the assignments.)

Rules for exam:

In addition to the normal stuff (pens, pencils, eraser, ruler and so forth), you should bring the textbook. At the exam, you will also be provided with a copy of sections 1-4 of "New bounds on sorting and searching".