Advanced Algorithmics, 2012, 1DL480

Visit this page often for updated information and important news.

---

---

Teachers

• Arne Andersson
• Karl Sundequist

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, 2012-25-05
• Oral Exam, details TBA

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
  1. (i) Title, author, journal/conference etc of the most cited paper,
  2. (ii) the same for the paper presenting the best solution (in your opinion),
  3. (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

Day	Time	Room	Topic	Book Chapter	Assignment deadlines
Thu Mar 15	13.15-15.00	Pol_1145	Review of old knowledge, Probabilistic Analysis, Randomized Algorithms. Introducing assignment 1.	1-4, 5
Fri Mar 16	15:15-17:00	Pol_1145	Sorting in linear time, Median and Order statistics	8, 9
Mon Mar 19	13:15-15:00	Pol_1145	Giving you a chance to finalise assignment 1
Tue Mar 20	15:15-17:00	Pol_1145	The Traveling Salesman Problem		Assignment 1
Thu Mar 22	10:15-12:00	Pol_1145	Genetic Algorithms, Simmulated annealing, Tabu Search, introducing Assignment 2
Mon Mar 26	10:15-12:00	Pol_1145	Variants of Balanced trees, red-black trees, etc	13	Problems 9-1, 9-2 a,b,c
Tue Mar 27	15:15-17:00	Pol_1145	Augmenting data structures	14
Thu Mar 29	13:15-15:00	Pol_1145	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
Mon Apr 16	10:15-12:00	Pol_1145	B-trees	18	Problem 17-3 (mandatory)
Tue Apr 17	10:15-12:00	Pol_1145	Universal hashing Perfect Hashing, Tries, van Emde Boas-trees	11.3, 11.5, Handout	Problem 18-2 (mandatory)
Thu Apr 19	13:15-15:00	Pol_1245	Genetic Algorithms, Simmulated annealing, Tabu Search		Assignment 2
Fri Apr 20	13:15-15:00	Pol_1245	EMPTY SPACE
Mon Apr 23	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)
Tue Apr 24	10:15-12:00	Pol_1146	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)
Thu Apr 26	15:15-17:00	Pol_1145	NP-completeness	34
Fri Apr 27	10:15-12:00	Pol_1146	NP-completeness	34, see also http://www.cs.uky.edu/~lewis/cs-heuristic/text/class/more-np.html
Thu May 3	13:15-15:00	Pol_1145	Polynomials and Fast Fourier Transforms	30
Fri May 4	13:15-15:00	Pol_1145	EMPTY SPACE
Mon May 7	10:15-12:00	Pol_1145	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
Tue May 8	13:15-15:00	Pol_1145	EMPTY SPACE
Thu May 10	13:15-15:00	Pol_1145	EMPTY SPACE
Mon May 14	13:15-15:00	Pol_1145	Presentations of Assignment 3		Presentations of Assignment 3
Tue May 15	15:15-17:00	Pol_1145	Presentations of Assignment 3		Presentations of Assignment 3
Mon May 21	10:15-12:00	Pol_1145	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
Tue May 22	13:15-15:00	Pol_1145	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
Fri May 25	TBA		Written Exam

---

Course Material

Old Exams

• Exam June 2007
• Exam June 2011

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, 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 .)

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".