DM507: Algorithms and Data Structures

The course cannot be chosen if you have passed DM578, or if DM578 is a compulsory form of your curriculum.

Students taking the course are expected to:

• Have knowledge of the contents of DM549 Discrete Methods for Computer Science. In particular, some amount of mathematical maturity is assumed.
• Be able to use the methods from DM550 Introduction to Programming. In particular, familiarity with programming in Java or Python is assumed.

The aim of the course is to enable the student to apply a wide range of existing algorithms and data structures for fundamental problems, as well as general methods for developing new algorithms and mathematical tools for analyzing the correctness and efficiency of algorithms. This is of paramount importance for the ability to develop efficient software, and is central to the understanding of upper and lower bounds for computational problems.

• Give the competence to develop new variants of central algorithms and data structures developed within computer science.
• Give skills to analyze pros and cons of algorithms, in particular with respect to the use of resources.
• Give knowledge and understanding of a selection of core algorithms and data structures developed within computer science.

The learning objective of the course is that the student demonstrates the ability to:

• use the algorithms taught in the course on concrete problem instances.
• give precise arguments for the correctness or incorrectness of an algorithm.
• determine the asymptotic running time of an algorithm.
• adapt known algorithms and data structures to special cases of known problems or new problems.
• design new algorithms for problems similar to those taught in the course, including giving a precise description of the algorithm, e.g. using pseudocode.
• make expedient choices of data structures.
• design new data structures based on known data structures.
• design and implement a larger program, using algorithms and data structures taught in the course.
• give precise arguments for the choices made in connection with the previous four items.

The following main topics are contained in the course:

• Mathematical basis: recursion equations, invariants.
• Algorithms: correctness and complexity analysis, divide and conquer (Master Theorem, Strassen's algorithm), greedy algorithms, dynamic programming, sorting algorithms (insertionsort, mergesort, heapsort, quicksort, countingsort, radixsort), graph algorithms (BFS, DFS, topological sorting of DAGs, connected components, strongly connected components, MST, SSSP, APSP), Huffmann coding.
• Data structures: dictionaries (BSTs, red-black trees, hashing), priority queues, disjoint sets.

See itslearning for syllabus lists and additional literature references.

Teaching activities are reflected in an estimated allocation of the workload of an average student as follows:

• Intro phase (lectures) - 44 hours
• Training phase: 44 hours

Teaching form: Assignments in study groups.

Transitional arrangements describe how a course replaces another course when changes are made to the course of study.