EXAM AUGUST 21 2015 CANCELLED
The exam scheduled for August 21 2015 is cancelled since nobody has signed up for the exam.
The course is given only every second year. The next time the course will be given is autumn 2016.
The course consists of lectures and mandatory labs.
Labs are completed in groups of 2 students. 2016 students can now register their group at https://sam.cs.lth.se/LabsSelectSession?occasionId=456.
Electronic communication between students and instructors outside of class is on the Piazza platform, see piazza.com/class#fall2012/edan55. If you have properly registered for this course, you should have received an email on 17 August 2012 inviting you to join this course. The Piazza platform is used for questions, announcements, and comments. Please do not send email to your instructors.
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.