IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Avanceret algoritmik 
Kursusnavn (engelsk):Advanced Algorithms 
Semester:Efterår 2008 
Udbydes under:cand.it., softwareudvikling og -teknologi (sdt) 
Omfang i ECTS:15,00 
Kursussprog:Engelsk 
Kursushjemmeside:https://learnit.itu.dk 
Min. antal deltagere:0 
Forventet antal deltagere:0 
Maks. antal deltagere:40 
Formelle forudsætninger:Before the course, the student should be able to:
  • Perform basic analysis of algorithm correctness and complexity, using invariants and big-O notation.
  • Use basic algorithms and data structures when programming (e.g., lists, queues, stacks, search trees, hashing, sorting algorithms, and basic graph algorithms).
  • Recognize a proof that a problem is NP-hard.
  • Formulate computational problems using propositional logic, constraints, and optimization goals.

This can be achieved, for example, by taking the courses "Performance and Test" and "Efficient AI Programming". 
Læringsmål: After the course, the student should be able to solve a wide range of real-life programming problems in a scalable way, by employing algorithmic design techniques and tools. In particular, you should be able to:
  • Identify and formulate precisely (if possible) the algorithmic problem hidden in a given programming task.
  • Apply the following algorithmic techniques when solving a problem: Greedy, divide and conquer, dynamic programming, reduction to network flow.
  • Theoretically analyze the performance of a given algorithmic solution, including the analysis of basic approximation algorithms and basic randomized algorithms.
  • Look up suitable NP hardness results in a compendium, and perform simple reductions from such problems to establish NP hardness.
  • At a basic level, evaluate theoretically the performance of an algorithm in a parallel or distributed setting, and in situations where there is a massive amount of data.
  • Find results in the algorithms research literature relevant to a given problem.
 
Fagligt indhold: This course will introduce students to techniques for solving complex programming tasks arising in modern IT systems. Focus in the course is on algorithm design and identification of computationally hard problems. Special emphasis will be on theoretical analysis, and application of the theoretical understanding in a project. The project counts for approximately half of the course. It will be worked out in groups of 2-4 students and is individually defined for each group based on some (research related) project suggestions given by the project advisors. A project can range from mainly theoretical to include a substantial part of implementation and experiments. Topics related to both the course Efficient Artificial Intelligence Programming and to Advanced Algorithms are possible. Ideally, a by-product of the project is a suggestion for a thesis topic related to the specialisation Scalable Computing.

Contents of lectures includes: Formulating an algorithmic problem, greedy algorithms, divide and conquer, dynamic programming, network flow, reductions, approximation algorithms, randomized algorithms, parallel algorithms and architectures. 
Læringsaktiviteter:14 ugers undervisning bestående af forelæsninger, øvelser og vejledning

Teaching consists of a mix of lectures, exercises, and supervision within the time slots allocated for the course. The project runs concurrently with the other activities throughout most of the semester.

The exam is oral, and is concerned with the project as well as the other topics treated in the course. A number of mandatory hand-ins must be approved to qualify for the exam.

---------------------------------------------------------
Dette kursus er en del af SDT-specialiseringen Scalable Computing, som du kan finde beskrevet her: SDT specialiseringer
For at blive cand.it. i SDT skal du bestå SDT¿s backbonekurser, og desuden gennemføre en 22,5 ECTS specialisering samt to 7,5 ECTS valgfag.

This course is part of the SDT specialization Scalable Computing ¿ see the description here:
SDT specializations
In order to graduate as a MSc in SDT, you need to pass the SDT backbone courses, and also take a 22,5 ECTS specialization and two 7,5 ECTS electives.

------------------------------------
I intro-ugen (uge 35) er der ændrede kursustidspunkter ¿ se hvordan undervisningen er tilrettelagt her:
link til skemaoplysninger
Skemaoplysningerne for efterårssemesteret vil være tilgængelige fra august måned.

In the intro week (week 35) the course time table is changed ¿ see the schedule here:
link to the time table
The schedule for the fall term will be available in August.

-------------------------------------
 

Eksamensform og -beskrivelse:X. experimental examination form (7-scale; external exam), 7-trins-skala, Ekstern censur

A number of mandatory hand-ins must be approved to qualify for the exam.
 

Litteratur udover forskningsartikler:Algorithm Design, by Eva Tardos and Jon Kleinberg, Addison-Wesley, 2005. ISBN-10: 0321372913, ISBN-13: 978-0321372918. 
 
Afholdelse (tid og sted)
Kurset afholdes på følgende tid og sted:
UgedagTidspunktForelæsning/ØvelserStedLokale
Mandag 10.00-12.00 Øvelser ITU 2A12
Onsdag 10.00-12.00 Forelæsning ITU 2A12
Onsdag 13.00-15.00 Øvelser ITU 2A12

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2008-12-17 Handing in written work no later than 3 PM Skriftlige arbejder ITU The Examination Office
2009-01-12 Tidspunkt oplyses senere Mundtlig eksamen ITU Lokale oplyses senere
2009-01-13 Tidspunkt oplyses senere Mundtlig eksamen ITU Lokale oplyses senere
2009-01-14 Tidspunkt oplyses senere Mundtlig eksamen ITU Lokale oplyses senere
2009-01-15 Tidspunkt oplyses senere Mundtlig eksamen ITU Lokale oplyses senere