Advanced algorithms, Fall 2006

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

News

November 14: Note that there is no handin due November 15.

October 11: There seem to be be some confusion about the grading of the mandatory exercises, so here is the scale: "A" is pass and "B" is fail.

August 1: Note! The lecture on August 30 is canceled. The first lecture will be Wednesday September 6, at 10.

Schedule

Lectures and exercises on Wednesdays 10-12 and 13-15.
The schedule is preliminary. It will be updated before and during the course. More detailed reading directions will also be provided. The three subject areas String Matching, Dealing with Hard Problems, and RAM Algorithms will use 4-5 weeks each.

Date Time Subject Literature Exercises / hand-ins Place
Aug. 30 10.00-12.00 Canceled
Sept. 6 10-12 Introduction. Exact string matching, deterministic automata. CLRS Chap. 32 Hand out 2A18
Sept. 13 10-12, 13-15 String indexing, tries, suffix trees. Copies from Gusfield Hand out 3A12 - 3A14
Sept. 20 10-12, 13-15 Approximate string matching, dynamic programming. Copies from Gusfield Hand out 3A12 - 3A14
Sept. 27 10-12, 13-15 Regular expression matching, non-deterministic automata. Copies from Sipser Hand out 3A12 - 3A14
Oct. 4 10-12, 13-15 Dealing with hard problems: Introduction, Polynomial time reductions, Definition of NP and efficent certification. Kleinberg and Tardos, pages 451-466. Hand out 3A12 - 3A14
Oct. 11 10-12, 13-15 Dealing with hard problems: NP Completeness Kleinberg and Tardos, pages 466-473, CLRS pages 995-1018 Hand out 3A12 - 3A14
Oct. 18   Fall Break. No teaching.      
Oct. 25 10-12, 13-15 Dealing with hard problems: Approximation algorithms. Chap. 35 in CLRS (pages 1022-1033), Chap. 2 in Ausiello et al. A compendium of NP optimization problems Hand out 3A12 - 3A14
Nov. 1 10-12, 13-15 Dealing with hard problems: Approximation algorithms. Complexity and Approximation Classes. 3A12 - 3A14
Nov. 8 10-12 Introduction to RAM algorithms. (No exercise session this week.) slides Hand out 3A12
Nov. 15 10-12, 13-15 van Emde Boas priority queues, Predecessor problem Hand out 3A12 - 3A14
Nov. 22 10-12, 13-15 Integer Sorting Hand out 3A12 - 3A14
Nov. 29 10-12, 13-15 Succinct data structures slides Hand out 3A12 - 3A14
Dec. 6 10-12, 13-15 Representing trees succinctly slides Hand out 3A12 - 3A14
Dec. 20 15.00 Exam handed in to the exam office. Notice that this is a firm deadline.

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 PASS or FAIL. At most 3 hand-ins are allowed to get grade FAIL in order to qualify for the exam, which is the last hand-in. The last hand-in covers all three subjects in the course and has to be graded PASS.

Examination

Internal examiner, Pass/fail, C1: Written work without oral exam.
Mandatory hand-ins every week, graded PASS or FAIL. At most 3 hand-ins are allowed to get grade FAIL in order to qualify for the exam. The last hand-in counts as the exam and is graded pass/fail. The exam has to be handed in at the latest December 20, at 15.00, in the exam office.

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