Algorithms and Data Structures 2

• Describe an algorithm accurately, concise and unambiguous.
• Apply algorithms and data structures from the course.
• Analyze algorithms and data structures, including being able to determine the worst case, expected, and amortized running time and space consumption in asymptotic notation.
• Argue for the correctness of algorithms.
• Identify and formulate the underlying algorithmic problem in a given problem.
• Analyze, evaluate, and compare algorithms / data structures and in the light of this, select an appropriate algorithm / data structure for solving a given problem.
• Use flow graphs to model a given problem.
• Modify algorithms and data structures to solve a given problem.
• Compare different algorithmic paradigms (fx. divide-and-conquer, dynamic programming, randomized algorithms, and flow algorithms) and select an appropriate one for solving a given problem.
• Recognize an NP-complete problem and prove that it is NP-complete.
• Implement and test data structures and algorithms, and make appropriate tests and empirical analysis of them.
• Argue for choices made when solving a problem.

Flow algorithms. Data structures for indexing and partial sum (fx. hash tables, Fenwick trees). Algorithms for string matching. Techniques for the design and analysis of algorithms (dynamic programming, divide-and-conquer, randomized algorithms and data structures, analysis of expected running times, and amortized analysis). NP.

02105/02326, The course builds on 02105 Algorithms and Data Structures I. Students are expected to know the curriculum for 02105, which includes

Basic algorithm analysis, asymptotic notation.
Data structures: stacks, queues, linked lists, trees, heaps, priority queues, union-find, balanced binary search trees.
Searching and sorting: binary search, heap sort, insertion sort, merge-sort.
Graph algorithms: single source shortest paths (Dijkstra and SSSP in DAGs), Minimum spanning trees, topological sorting, Breadth first search, Depth first search, representation of graphs.

Lectures and exercises.