We have selected a number of course-related programming exercises at the self-checking Kattis server.

(This system works very much like the ACM programming contest: You can upload your solution to a server, which checks them against known input-output pairs.)

This activity is optional, but useful.

* Register on kattis: https://lu.kattis.com/

The course consists of lectures and mandatory labs.

For 2017, labs are completed in groups of 4 students. You can now register at

https://sam.cs.lth.se/LabsSelectSession?occasionId=506

This is an advanced course in algorithms, targeted at students who are familiar with fundamental data structures (stacks, queues, trees, hash tables), algorithms (sorting, graph connectivity, dynamic programming, network flow), and computation complexity (NP-hardness). At LTH, this currently corresponds to the courses EDAA01 and EDAF05.

The focus of the course is “Algorithms for Hard Problems,” which could be a good alternative title for this course. Here, “hard” means one of two things. Either the instance is huge compared to what was seen in previous courses, so we need algorithms and data structures that work on massive data sets. Or the problem is hard in the sense of computational complexity (for example NP-hard), so no good algorithm is known even for tiny instances.

Technically, the glue that keeps this course together is randomisation: many of our troubles will be solved by randomised algorithms—a large part of the course could equally well be called “Randomised Algorithms”. That’s why the course also requires a solid background in discrete probability theory (events, probabilities, conditional probabilities, stochastic variables, mean, variance), corresponding to the LTH course FMS012. This allows us to visit (or revisit) a bunch of famous, useful, and important algorithms like Quicksort, Hashing or Google’s PageRank algorithm.

Finally, the course attempts to include a significant amount of bleeding edge current research of the highest international caliber, so that parts of the course material will (I hope) be research articles where the ink is still fresh.

The required textbook for this course is

• Kleinberg and Tardos, Algorithm Design, Addison Wesley, 1st edition (2005)

We’ll use the second half of this book. Many LTH students own this book from EDAF05, which is why I chose it. We’ll supplement this book with additional material from various sources (single chapters, online course notes, etc.). This will be announced. If you have too much money, you can buy two other excellent books:

• Mitzenmacher and Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press (2005)
• Hromkovic, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics , 2nd edition, Springer (2010)

However, I won’t be using enough from either of these books to justify elevating them to required course books. View them as secondary references.

The course contains of a number of mandatory exercises that are typically a mixture of implementation (coding) and analysis (maths). These are graded pass/fail; successful completion accounts for 3 of the 7.5 credits for this course.

The course ends with a written exam. The format is open book (you can bring the course book and your notes and whatever other printed material you want). The exam accounts for 4.5 of the course’s 7.5 credits. The final grade for EDAN55 is entirely determined by the performance at the exam.