Kursusbasen

Kursusoversigt

Kursusbeskrivelse

Kursusnavn (dansk):	Algorithm Design
Kursusnavn (engelsk):	Algorithm Design
Semester:	Efterår 2014
Udbydes under:	cand.it., softwareudvikling og -teknologi (sdt)
Omfang i ECTS:	7,50
Kursussprog:	Engelsk
Kursushjemmeside:	https://learnit.itu.dk
Min. antal deltagere:	12
Forventet antal deltagere:	50
Maks. antal deltagere:	75
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" or "Algorithms and Data Structures" (BADS).
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, the student should able to: Identify and formulate precisely (if possible) the algorithmic problem underlying in a given programming task. Apply the following algorithmic techniques when solving a problem: Greedy, divide and conquer, dynamic programming, reduction to network flow. Look up suitable NP hardness results in a compendium, and perform simple reductions from such problems to establish NP hardness.
Fagligt indhold:	This course introduces 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 algorithms, divide and conquer, dynamic programming, network flow, reductions.
Læringsaktiviteter:	Teaching consists of a mix of lectures and exercises. Condensed course: The lectures will run in the first half of the semester week 35-41, at double pace. The exam is written; a number of mandatory assignments must be approved to qualify for the exam. --------------------------------------------------------- Information about study structure For students on the SDT August 2014 curriculum: This course is a mandatory backbone course for SDT-AC track. This course is part of the SDT-D-track specialization Algorithms For students on the SDT August 2012 curriculum: This course is a mandatory backbone course for SDT-SE track. This course is part of the SDT-DT track specializations Scalable Computing and Data Processing- For students on SDT curricum before August 2012: This course is part of the SDT-DT and SDT-SE track specializations Scalable Computing and Data Processing- see the descriptions here: SDT specializations NB!! Course restriction!! Please note that there is a course restriction between this course and the course Algorithm Design 15 ECTS and Advanced Algorithms. That means that you cannot take this course, if you have already taken Algorithm Design 15 ECTS or Advanced Algorithms and that you cannot take Algorithm Design 15 ECTS or Advanced Algorithms if you take this course.
Obligatoriske aktivititer:	The exam is written; a number of mandatory assignments must be approved to qualify for the exam. Submission/completion of mandatory activities before 10 October
Eksamensform og -beskrivelse:	X. experimental examination form (7-scale; external exam), 7-trins-skala, Ekstern prøve 4 hours written exam on premises with all written aids (course book, own notes, printouts of slides, etc.). No use of electronic communication tools such as PC, laptop, tablet or e-reader with internet or other network connection or mobile phone. Please notice that the exam takes place 23 October 16:00-20:00 at ITU.
Litteratur udover forskningsartikler:	Algorithm Design, by Eva Tardos and Jon Kleinberg, Addison-Wesley, 2005. ISBN-10: 0321372913, ISBN-13: 978-0321372918.