Advanced algorithms, Fall 2005

[Schedule] [Course description] [Course goal] [Literature] [Prerequisites] [Course format] [Examination] [Lecturers]

News

November 15:A paper related to the guest lecture is available now. See schedule below.
October 21:Exercise sessions have been moved to room 2A18.
NOTE: DIKU students only get 5 ECTS for this course, since you have already had a course on NP-Compteteness. You do not have to hand in exercises on the "Dealing with hard praoblems part" and will not get exam questions (last hand in) on this part. If you have any questions, please contact Anna.
October 12: The last hand in counts as the exam and has to be handed in to the exam office the last day of the course period, November 25, 15.00. Note that this is a strict deadline.
October 2: Modification to the hand-in for next week. Exercise 7 in KT: We define 4-Dimentional Matching without the constraint that all the sets have size n. This makes the reduction much more straightforward.

The first lecture will be Monday August 29, 9-12, in room 4A14. No exercise session the first week.

Schedule

Lectures and exercises on Mondays 9-12 and 13-16.
The schedule is preliminary. It will be updated during the course. More detailed reading directions will also be provided.

Date Time Subject Literature Exercises / hand-ins Place
Aug. 29 9.00-12.00 Introduction. Exact string matching. CLRS Chap. 32 slides Hand out 4A14
Sept. 5 9-12, 13-16 Text indexing, tries, suffix trees. Copies from Gusfield slides Hand out 4A14
Sept. 12 9-12, 13-16 Approximate string Matching, dynamic programming, four russians technique. Copies from Gusfield slides Hand out 4A14
Sept. 19 9-12, 13-16 Finite automata, regular expression matching. Copies from Sipser slides Hand out 4A14
Sept. 26 9-12, 13-16 Dealing with hard problems: Introduction(slides), Polynomial time reductions, Definition of NP and efficent certification. Copies from KT, pages 451-466. Hand out 4A14
Oct. 3 9-12, 13-16 Dealing with hard problems: NP Completeness Copies from KT, pages 466-473. CLRS Chapter 34. Hand out 4A14
Oct. 10 9-12, 13-16 Dealing with hard problems: Approximation algorithms. CLRS Chapter 35. Copies from Ausiello et al. A compendium of NP optimization problems Hand out 4A14
Oct. 17   Fall Break. No teaching.      
Oct. 24 9-12, 13-16 Dealing with hard problems: Approximation algorithms. Introduction to RAM algorithms. . Copies of Chapter 3 in Ausiello et al., Slides. Hand out 4A14
Oct. 31 9-12, 13-16 Predecessor problem, van Emde Boas priority queues Hand out 4A14
Nov. 7 9-12, 13-16 RAM algorithms. (1 1/2 hour). Guest lecture by Henrik Reif Andersen. (1 1/2 hour) Intro to BBDs The first 3 sections (8 pages) are suggested reading. Hand out 4A14
Nov. 14 9-12, 13-16 RAM algorithms Hand out 4A14
Nov. 21 9-12, 13-16 RAM algorithms 4A14

Literature:

Course description

This is a theoretical and advanced course in algorithms, where we will present useful techniques for solving challenging programming problems, using efficient algorithms and data structures. It follows the spirit of IADS, but at a more advanced level. The course is a good source of inspiration for finding a good subject for your thesis or a project.

The course will have three main themes:

String matching:

DNA, The Web, XML, digital libraries: Data is represented as text or strings in many contexts. In order to search, compare, and combine information in strings we need specialized algorithms and data structures.The string matching theme will present both off-line and on-line methods for finding a pattern in a string, as well as methods for computing (edit) distance between strings. Also methods for compression of data will be discussed.

Dealing with hard problems:

Computational problems can be categorized according to the complexity of the problem. In the course we will define the two classes P and NP. Problems in the class P can be solved efficiently, whereas we have no efficient algorithms for solving NP-hard problems. Many natural problems are NP-hard. In order to deal with them we need will look at how to find non-optimal or approximative solutions. This can often be done efficiently, and the course will present some approximation algorithms for NP-hard problems. We will also look at how to show that a problem is NP-hard.

RAM algorithms:

Data in a computer is represented as words of bits. The computer deals with all bits in a word in parallel. This fact can be used when designing algorithms, to get more efficient algorithms. RAM stands for Random Access Machine, and when we talk about RAM algorithms we mean that we use the fact that the computer works in parallel on a whole word and that words of data and words of addresses is the same, i.e. we can manipulate addresses in the same way as we can manipulate data. We will look at algorithms that uses this more realistic model of the computer to improve efficiency.  See the schedule above for more details.

Literature

Selected chapters from Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, research papers, course notes and handouts.

Course goal

The goal with this course is to make you comfortable with both theoretical and practical challenging problems in the area of algorithms and data structures.
You should be able to read and apply recent research techniques in the field.
An overall goal is that students get a sufficient knowledge to be able to independently address algorithmic research questions after the course, e.g. as a thesis project.

After the course the student should be able to:

Prerequisites

The students should be familiar with basic algorithms, data structures and time and space analysis of algorithms. In particular the students should know and understand lists, queues, stacks, search trees, hashing, sorting algorithms, basic graph algorithms, Big-oh and Omega notation, amortized analysis, and dynamic programming.

This can be aquired by following the course Introduction to algorithms and data structures at ITU or a similar course at another university.

Course format

Lectures and exercise sessions.

Mandatory hand-ins every week. The last hand-in counts as the exam.

Note that this course is only offered in fall semesters.

Mandatory hand-ins

Mandatory hand-ins every week, graded A (pass) or B (not pass). 8 out of 10 should have the grade A, and the last (11th) hand-in has to be graded A (pass).

Examination

Internal examiner, Pass/fail, C1: Written work without oral exam.
Mandatory hand-ins every week, graded A (pass) or B (not pass). 8 out of 10 should have the grade A, and the last (11th) hand-in has to be graded A (pass).

Lecturers

Anna Pagh
Office: 3C.11
Email: annao@itu.dk
 Philip Bille
Office: 3C.
Email: beetle@itu.dk
 S. Srinivasa Rao
Office: 3C.04
Email: ssrao@itu.dk