IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Algoritmikdesign 
Kursusnavn (engelsk):Algorithm Design 
Semester:Efterår 2010 
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 "Foundations of Computing - Algorithms and Data Structures" 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. The course contains both theoretical and analysis and implementation exercises.

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

Teaching consists of a mix of lectures and exercises.

The exam is written; a number of mandatory assignments must be approved to qualify for the exam.

---------------------------------------------------------
Information about study structure

This course is part of the SDT specializations Scalable Computing and Data Processing- see the descriptions here:
SDT specializations

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

Se hvordan undervisningen er tilrettelagt her:
link til skemaoplysninger
Skemaoplysningerne vil være tilgængelige fra kort før semesterstart.

See the schedule here:
link to the time table
The schedule will be available shortly before the beginning of the term.

-------------------------------------
NB!! Course restriction!!

Please note that there is a course restriction between this course and the course Advanced Algorithms.
That means that you cannot take this course, if you have already taken Advanced Algorithms, and that you cannot take Advanced Algorithms if you take this course.
 

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

6 mandatory assignments 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
Tirsdag 08.30-10.30 Forelæsning ITU 3A14
Tirsdag 10.45-12.45 Øvelser ITU 3A14
Torsdag 08.30-10.30 Forelæsning ITU 2A18
Torsdag 10.45-12.45 Øvelser ITU 2A18

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2011-01-04 09.00-13.00 Skriftlig eksamen ITU 2A12 og 2A14