1. Introduction
• What is an algorithm?
• What is a data structure?
• Inductive reasoning
• Inductive proof
• Complexity of an algorithm
• Sorting by insertion
• Analysis of sorting by insertion
• Asymptotic notations
2. Sorting, Heap, Recursion
• Divide-and-conquer method.
• Sorting by merging - MergeSort.
• Complexity of merge sorting.
• Recursion, computing recursive complexity, solving recursion, the universal recursion theorem.
• Heap, heap property, restoring heap property, building a heap.
• Analysis of heap algorithms
• Heap Sorting, Priority Queues, Priority Sorting, Quicksort.
3. Priority queues, Quicksort, Linear time sorting.
• Priority queues
• Heap operations
• Implementation of priority queues
• Quicksort
• Algorithm
• Quicksort analysis
• Decision Tree Model alg. Sorting
• Sorting by counting, positional sorting, bucket sort.
• Dynamic Sorts, Stack, List
4. Data structures, Stack, Queue, List, BST and RB Trees.
• Dynamic Sets
• Stack
• Queue
• List
• BST tree
• browse, search, delete operations
• complexity of BST tree operations
• Well-balanced trees
• Red-Black Tree (RB-Tree)
• inserting into RB-tree
5. Skip lists, hash tables, positional statistics
• Skip lists
• hash tables
• List implementation, collision resolution
• Hashing function
• positional statistics
• selection problem, selection in pessimistic linear time
• dynamic positional statistics
6. Dynamic positional statistics, interval trees, graphs.
• dynamic positional statistics
• determination of an element of a given rank
• rotation in a tree of dynamic positional statistics
• Interval trees
• rotation in an interval tree
• searching for an interval in an interval tree
• Graphs
• graph representation, neighborhood matrix, neighborhood lists
• graph search, BFS algorithm
7. Graphs, DFS, graph spanning tree, topological sorting.
• Graph algorithms
• Graph Searching
• BFS, DFS
• spanning tree creation
• edge classification
• forward edge, traversal edge, backward edge, spanning tree edge.
• directed acyclic graph
• topological sorting
• properties of topological sorting
8. Graph algorithms, search for minimal paths.
• Minimum spanning tree
• Observation, optimal structure consists of optimal substructures.
• Prim algorithm for searching a minimal spanning tree * Prima algorithm for searching a minimal spanning tree
• Searching for minimal paths in any directed graph, Ford Bellman algorithm.
• A version of the Ford Bellman algorithm for directed acyclic graphs.
• Searching for shortest paths in a graph with nonnegative edge weights, Dijkstra's algorithm.
9. Graph algorithms, amortised cost method.
• Dijkstra's algorithm
• operation, complexity, correctness
• Spanning trees
• Kruskal algorithm
• Kruskal algorithm correctness
• The problem of shortest paths between each pair of vertices in a graph.
• Warshal Floyd algorithm
• Amortised cost analysis
• dynamic arrays
• analysis by the summary cost method
• analysis by accounting method
10. Flow networks, pattern finding algorithms
• Flow networks
• Ford-Fulkerson algorithm, residual network, augmented path, flow function.
• minimum crosssection, maximum flow.
• Maximal associations in bipartite graphs.
• reduction to a flow network problem
• pattern search in text
• „naive” algorithm, Rabin Karp algorithm,
• Finite state automata, introduction to KMP
11. Text algorithms
• Pattern search
• finite automata
• searching for a pattern in a text using automata
• KMP algorithm (reduction of transition functions to an array)
• Boyer-Moore algorithm
• heuristics
• inconsistencies
• good suffix
12. Text compression, Parallel algorithms
• text compression
• Information theory, Shannon's entropy measure
• Huffman coding
• Huffman coding algorithm
• LZW compression
• Parallel algorithms
• Flynn's taxonomy of parallel systems
• parallel architectures
• PRAM model
• EREW, CREW, ERCW, CRCW
• examples of parallel algorithms
• Pascal's triangle, minimum search, positional statistics, determining the rank of an element in a list.
13. Geometric algorithms
• basic concepts
• determining the position of points relative to each other
• the problem of intersection of two segments.
• construction techniques for geometric algorithms
• the problem of finding the convex envelope of a set of points
• Graham's algorithm for finding the convex envelope of a set of points.
• Finding intersecting segments in a set of segments.
• algorithm for finding intersecting segments by the sweeping method
• problem of finding the least distant pair of points in a point set
• the divide and conquer algorithm
14. Summary lecture