IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Avanceret algoritmik 
Kursusnavn (engelsk):Advanced Algorithms 
Semester:Efterår 2005 
Udbydes under:cand. it, softwareudvikling (swu) 
Omfang i ECTS:7,50 
Kursussprog:Engelsk 
Kursushjemmeside:http://www.itu.dk/courses/AVA/E2005/index.html 
Min. antal deltagere:0 
Forventet antal deltagere:30 
Maks. antal deltagere:99 
Formelle forudsætninger:Students from DIKU will be able to follow different parts of this course, and will have 5 ECTS credit transferred. Please see "format of course" below.

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.
 
Læringsmål: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:

  • Describe the difference between and meaning of different models of computation.

  • Show that a problem is NP-hard.

  • Apply the algorithms and data structures presented in the course, when designing a program.

  • Read and point out the most important ideas in an algorithmic research paper.

  • Efficiently solve challenging programming tasks, by applying algorithmic research results.

 
Fagligt indhold: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

  • Dealing with hard problems

  • RAM algorithms


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.
 
Læringsaktiviteter:12 forelæsninger og 12 øvelsesgange

Lectures and exercise sessions.

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

The 5 ECTS version of the course for DIKU students consists of 8 lectures. The 4 lectures on "Dealing with hard problems", as well as the hand-ins and exam questions on this part of the course, is not included. However, you are all welcome to come to all lectures.

Note that this course is only offered in fall semesters.

NB! In the introductory week, meaning from 29 August to 2 September 2005, exercises from 13:00 to 16:00 are cancelled. This means, that there will be only lectures from 9:00 to 12:00.
 

Eksamensform og -beskrivelse:X. experimental examination form (7-scale; external exam), Bestået/ikke bestået, Intern censur

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

Litteratur udover forskningsartikler:Selected chapters from Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, research papers, course notes and handouts. 
 
Afholdelse (tid og sted)
Kurset afholdes på følgende tid og sted:
UgedagTidspunktForelæsning/ØvelserStedLokale
Mandag 09.00-12.00 Forelæsning ITU 4A14
Mandag 13.00-16.00 Øvelser ITU 4A14

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2005-11-25 before 3 pm Eksamensopgave 1 ITU Examination Office