Asymptotic analysis of complexity borders in the worst case and on average. To identify differences between behaviours of algorithms in the best case, the worst case, and on average. The Master theorem The notations of ordo, omega and theta. The most common complexity classes. Empirical estimate of complexity. Complexity in time and memory. the use of recursion to analyse algorithms. Strategies for algorithms and data abstraction.
Brute-force algorithms. Greedy algorithms. Decomposition algorithms. Backtracking. Heuristics. Basic algorithms
Simple numerical algorithms. Sequential and binary search algorithms. Quadratic sorting algorithms (selection, insertion). Sorting in O(N log N) (Quicksort, Heapsort, Mergesort). Hash tables including such that avoid collision. Binary search trees. Representations of graph (neighbour lists, neighbour matrices). Depth first search and Width first search. Shortest path algorithms (the algorithms of Dijkstra and Floyd). Transitive closure (Floyd's algorithm). Minimum spanning trees (the algorithms of Prim and Kruskal). Topological sorting. Basic computability
Solvable and unsolvable problems. computable and non-computable functions. The halting problem Consequences of undecidability. P and NP.
Definitions of the classes P and NP. NP-completeness (Cook's theorem). Some common NP-complete problems.
The aim of the course is to provide a solid knowledge on how to design and analyse the most important classes of algorithms. The course intends to give the students skills that give them the opportunity to design computer program that use time and memory in an efficient way independently. The students should learn to identify problems that are unreasonably demanding in terms of resources or that indeed are impossible to solve with common computing models. At the end of the course the students should be able to develop their own algorithms to solve problems and be able to compare different solutions and how well they function.
Upon completion of the course, the students should be able to
develop and implement algorithms and data structures and analyse them regarding correctness. define the terms P, NP, NP-completeness and computability. analyse how efficient algorithms and data structures are based on different measures on efficiency such as time complexity and memory complexity. write programs that use algorithms and data structures with the help of good programming principles such as the specification of APIs and the use of tests that utilise algorithms or data structures. solve problems through the use of data structures such as linear lists, stacks, queues, hash tables, binary trees, heaps, binary search trees, and graphs, and write programs for the solutions. solve problems by using algorithm design methods such as greedy algorithms, decomposition, dynamic programming, backtracking, and write programs for the solutions. given a specific problem, either design an appropriate data structure or create an algorithm that solves the problem or identify the problem as one that cannot be solved efficiently.