- 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

- 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.

- 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

- 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

- Skip lists, hash tables, positional statistics
- Skip lists
- hash tables
- direct addressing
- open addressing
- linear, square, double addressing

- List implementation, collision resolution
- Hashing function
- positional statistics
- selection problem, selection in pessimistic linear time
- dynamic positional statistics

- 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

- 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

- 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.

- 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

- 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

- 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

- 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.

- 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

- Summary lecture

- user/konrad/teaching/courses/wish/aizo/about_en.txt