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