The role of algorithms in computing.
Algorithm analysis: input size, running time and space; worst case, best case, average case.
Algorithm design: incremental approach, applied in Insertionsort; "divide and conquer" approach, applied in Mergesort.
Growth of functions: asymptotic notations.
Recurrences: methods for solving recurrences, recursion trees, "master method".
Sorting algorithms: Heapsort. Heaps, priority queues.
Sorting algorithms: Quicksort, randomized Quicksort.
Performance limitations of comparison sorts, asymptotically optimal comparison sorts.
Sorting in linear time: Counting Sort, Radix Sort, Bucket Sort.
Medians and order statistics: selecting the minimum and maximum, general selection problem.
Elementary data structures: stacks, queues, linked lists, and rooted trees.
Hash tables: direct-address tables, hashing with chaining, open addressing.
Binary search trees: walk, search, insertion and deletion.
Graphs: representations, breadth first search, depth-first search, topological sort, shortest paths.
Dynamic programming: development of a dynamic-programming algorithms to face optimization problems.
Computability: Turing machine, Church-Turing thesis, universal Turing machine, halting problem, undecidability.
NP and beyond: decision problems vs. optimization problems; complexity classes of problems P, NP and coNP; NP-completeness; reducibility; class PSPACE.