Department of Information Technology

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

Some other useful links

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

Updated  2014-05-26 10:02:10 by Karl Sundequist.