IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Applied Algorithms 
Kursusnavn (engelsk):Applied Algorithms 
Semester:Efterår 2016 
Udbydes under:cand.it., softwareudvikling og -teknologi (sdt) 
Omfang i ECTS:7,50 
Kursussprog:Engelsk 
Kursushjemmeside:https://learnit.itu.dk 
Min. antal deltagere:1 
Forventet antal deltagere:0 
Maks. antal deltagere:50 
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).

This can be achieved, for example, by taking the courses "Foundations of Computing - Algorithms and Data Structures" (SGDS) or "Algorithms and Data Structures" (BADS).

The course Algorithm Design (SAD1) is not a prerequisite. The two course actually complement each other. 
Læringsmål:After the course, the student should be able to implement an algorithm from a high level description like pseudocode, perform correctness and scalability testing.
In particular, the student should able to:
- implement a (parallel) algorithm with or without the use of specific libraries or frameworks
- perform an experimental scalability analysis of computational resource requirements using adequate families of synthesized and real world test cases
- judge if a particular language, library and hardware platform is suited for an algorithmic task
- create adequate tests of correctness
- judge if an experimental analysis conforms to a theoretical performance model 
Fagligt indhold:This course introduces the students to some classical examples of widely used algorithms and uses these to show how to implement an algorithm in a correct and scalable way in the context of a particular application.
The focus of the course is the implementation, its correctness, the experimental analysis, and the connection to the performance models.

Examples of well understood computational tasks that can be considered in depth are:
- shortest path for cars on road networks
- sorting: why different variants of quicksort differ in performance
- cache oblivious search trees as file system or database index
- dense matrix matrix multiply
- sparse matrix dense vector multiply, page rank, map reduce
- locality sensitive hashing
- k-means clustering

The course introduces the different algorithmic tasks, the algorithms, the testing methodology and the performance models.
The exercises focus on implementation, testing and interpretation of the measurements. 
Læringsaktiviteter:12 forelæsninger og 12 øvelsesgange

Teaching consists of a mix of lectures and exercises.
There are homework exercises, both to be answered as text and as source code that describes a correct and sufficiently efficient implementation. 

Obligatoriske aktivititer:Der er ingen obligatoriske aktiviteter. Vær venlig KUN at ændre denne tekst når der er obligatoriske aktiviteter.

There are no mandatory activities. Please, change this text ONLY when there are mandatory activities. 
Eksamensform og -beskrivelse:C: Skriftlige arbejder uden mundtlig eksamen., (pass/fail, internal exam)

Parts of the exam are to be answered as text and other parts as source code that describes a correct and sufficiently efficient implementation.

Written take-home exam (individual mini-project)
- Total duration 6 hours
- Individual
- Date and time for exam publication and solution hand-in will be published in LearnIT.
- Submission in LearnIT
- All materials, including Internet access, allowed
- Plagiarism, collaboration and copying of solutions not allowed.
- There is no oral exam but a fraud check will be conducted after the hand-in. The study administration will randomly select 20 % of students who will have to show up at ITU to check authorship of submitted solutions. The selection of students and the place and time for the fraud check will be published in Learn IT.  

Litteratur udover forskningsartikler:Catherine McGeoch "A Guide To Experimental Algorithmics"
Cambridge University Press; 1 edition (January 30, 2012)
ISBN-13: 978-0521173018