Kursussøgning, efter- og videreuddannelse – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Kursussøgning, efter- og videreuddannelse

Advanced Algorithms and Data Structures (AADS)

Practical information
Study year 2016/2017
Time
Block 1
Programme level Full Degree Master
ECTS 7,5 ECTS
Course responsible
  • Mikkel Thorup (7-7f867a8184878252767b407d8740767d)
  • Department of Computer Science
Course number: NDAA09023U

Course content

Algorithms is about finding scalable solutions to computational problems, and the reliance is only increasing as we enter the world of Big Data. We want algorithms that solve problems efficiently relative to the input size. Exponential time is hopeless. We generally want polynomial time, and for large problems we need linear time. Sometimes we employ data structures that represent the input so that queries about it can be answered very efficiently. In this mandatory course, we will study the list of algorithmic topics below. Some of these topics are covered in more depth in more specialized elective courses.

Learning outcome

Knowledge of:

  • Graph algorithms such as max flow
  • NP-completeness
  • Approximation algorithms
  • Randomized algorithms
  • Computational geometry
  • Linear programming and optimization

 

Skills to:

  • Analyze algorithms with respect to correctness and efficiency.
  • Explain and use basic randomized algorithms.
  • Recognize NP-hard problems and address them, e.g., using approximation algorithms.
  • Explain and use algorithms for different abstract domains such as graphs and geometry.
  • Formulate real-life problems as algorithmic problems and solve them.

 

Competences to:

  • Analyze a computational problem in order to find an appropriate algorithmic approach to solve it.

Recommended prerequisites

It is assumed that the students are familiar with basic algorithms (sorting, selection, minimum spanning trees, shortest paths) and data structures (lists, stacks, binary trees, search trees, heaps).

Sign up


As an exchange, guest and credit student - click here!

Continuing Education - click here!

Education

MSc Programme in Computer Science

Studyboard

Study Board of Mathematics and Computer Science

Course type

Single subject courses (day)

Duration

1 block

Schedulegroup

C
---- SKEMA LINK ----

Teaching and learning methods

A mix of lectures and exercises.

Capacity

No limit

Language

English

Literature

See Absalon when the course is set up.

Workload

Category Hours
Lectures 36
Theory exercises 84
Preparation 84
Exam 2
English 206

Exam

Type of assessment

Oral examination, 30 minutes
Oral exam with preparation (30 minutes) in course curriculum.

Aid

All aids allowed

Marking scale

7-point grading scale

Criteria for exam assessment

See learning outcome.

Censorship form

External censorship

Re-exam

If student is not qualified then qualification can be achieved by hand-in and approval of equivalent exercises.

Re-exam same as ordinary exam.

Mere information om kurset
Er du BA- eller KA-studerende?
Er du bachelor- eller kandidat-studerende, så find dette kursus i kursusbasen for studerende:

Kursusinformation for indskrevne studerende