Official course description for:
Full info last published 15/05-19

Algorithm Design, MSc CS

Course info
Language:
English
ECTS points:
7.5
Course code:
KSALDES1KU
Offered to guest students:
yes
Offered as a single subject:
yes
Price (single subject):
10625 DKK (incl. vat)
Programme
Level:
MSc. Master
Programme:
Master of Science in Computer Science
Staff
Course manager
Associate Professor
Teaching Assistant
Teaching Assistant (TA)
Teaching Assistant
Teaching Assistant (TA)
Teaching Assistant
Teaching Assistant (TA)
Course semester
Semester
Efterår 2019
Start
26 August 2019
End
31 January 2020
Abbreviation
20192
Exam
Exam type
ordinær
Internal/External
ekstern censur
Grade Scale
7-trinsskala
Exam Language
GB
Abstract

This course is an advanced course on algorithms which builds on top of an introductory course on algorithms and data structures. The course focuses on advanced techniques for identifying and solving computationally hard problems and on how to adapt such techniques to real-world scenarios.

Description

This course introduces students to techniques for solving complex programming tasks arising in modern IT systems. The student taking this course will be able to quickly identify and solve a certain class of problems that can arise among the tasks that a skilled programmer must solve.

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.

Formal prerequisites
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).
Intended learning outcomes

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.
  • 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.
Learning activities

Teaching consists of a mix of lectures and exercises. 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.

Mandatory activities
12 mandatory programming assignments must be approved to qualify for the exam. 

The student will receive the grade NA (not approved) at the ordinary exam, if the mandatory activities are not approved and the student will use an exam attempt.

Course literature

The course literature is published in the course page in LearnIT.

Ordinary exam
Exam type:
A: Written exam on premises, external (7-trinsskala)
Exam variation:
A33: Written exam on premises on paper with restrictions
Exam description:

4 hours written exam on premises with all written aids (course book, own notes, printouts of slides, etc.). No use of pocket calculator and electronic communication tools such as PC, laptop, tablet or e-reader with internet or other network connection or mobile phone.  Only use of ballpoint pen is allowed for the final exam hand-in.