EFFICIENT SEQUENTIAL ALGORITHMS

Detailed Syllabus

The lecture material is given by the full content of the slides supplemented by lecture notes and additional reading lists. Exam question may be based on ANY word contained in the lecture material. Here is a detailed summary of such material for your convenience.

  • Algorithmic paradigms
  • Lect 1: Introduction. Computational problems: decision, construction, optimisation, counting. Example 1: boolean formulae. Example 2: web-search.
  • Lect 2 Greedy algorithms. Activity selection problem (ASP). Variant related to web-crawling. GREEDY-ACTIVITY-SELECTOR and SGREEDY-ACTIVITY-SELECTOR (comparisons and differences). Time complexity analysis. Examples.
  • Lect 3 Greedy algorithms. Correctness (detailed proof by induction) and limitations of the ASP. Proposed exercise: Timetabling. Weighted ASP (WASP). Examples and comparisons with ASP.
  • Lect 4 Dynamic programming algorithm for WASP: divide and conquer and then memoization. Proposed exercises.
  • Lect 5 Dynamic programming (general definitions and cookbook recipe). Matrix chain multiplication. Problem definition. Algorithms: recursive and dynamic programming solution (algorithm MATRIX-CHAIN-ORDER).
  • Lect 6 More examples and issues on matrix chain multiplication. Example. Complexity of the recursive solution. Complexity of the dynamic programming solution. Constructing an optimal solution: algorithm MATRIX-CHAIN-ORDER with table s and algorithm MATRIX-CHAIN-MULTIPLY. Proposed exercises: Golf-playing; Pretty printing.
  • Pattern matching
  • Lect 1 Pattern matching. Hystorical introduction. Problem definition. Examples. Notations (suffix, prefix, etc). Algorithm BRUTE-MATCHING. Time complexity of BRUTE-MATCHING. Examples. Features of the given algorithm. Improvement? Definition of deterministic finite state machine (DFSM). Examples of DFSM. String-matching automaton. Algorithm FINITE-AUTOMATON-MATCHING.
  • Lect 2 Examples and results on string matching with finite automata. Detailed construction of a string matching automaton and simulation on a given text. Time complexity analysis of FINITE-AUTOMATON-MATCHING. Correctness analysis: main result and technical auxiliary statements. Preprocessing: computing the automaton transition function: algorithm COMPUTE-TRANSITION-FUNCTION.
  • Lect 3 More on automaton string matching. Knuth, Morris and Pratt algorithm.
  • String algorithms; Text compression
  • Lect 1 Longest Common Subsequence (LCS) problem: definitions (common subsequence, LCS problem as optimization problem), applications, examples. Dynamic programming algorithm. Simulation. Constructing the longest common subsequence: algorithm PRINT-LCS.
  • Lect 2 Huffman codes. Definition of code and prefix code. Encoding-Decoding, with examples. Representing a code as a tree. Optimal codes: trees of minimal average path length. Huffman codes: greedy algorithm HUFFMAN. Running time. Optimality.
  • Lect 3 Lempel-Ziv Welch compression and decompression algorithms. Compression. Example. Efficiency. Decompression. Example. Application in computer graphics: particular issues.
  • Graph-theoretic matchings
  • Lect 1 Preliminary definitions (I can't be more specific here without reading out the slides!)
  • Lect 2 Initial algorithms: GREEDY-MATCHING1 and GREEDY-MATCHING2. Independent systems. Maximal matchings as independent systems. Relationship between maximal and maximum matchings. Maximum matchings on paths and cycles. Greedy algorithm for maximum matching in trees. Examples. Correctness proof.
  • Lect 3 Maximum matchings in bipartite graphs: mathematical preliminaries. Vertex covers. Independent set. Edge covers. Relationship between these concepts.
  • Lect 4 Bipartite matchings: Hall's condition. Example. Validity argument with description of a recursive algorithm for matching one set of vertices to the other.
  • Lect 5 Bipartite matching: Hungarian algorithm. Alternating paths. Augmenting paths. Berge's result. Hungarian algorithm explained. Forest construction. Examples. Correctness. Bipartite matching via maximum flow.
  • Lect 6 Another example with the Hungarian algorithm. Trees, paths, and flowers, matchings in general graphs. Shrinking lemma. Edmonds algorithm. Properties of the forest.
  • Lect 7 Example simulation of Edmonds algorithm. Correctness of Edmonds algorithm, examples.
  • Space complexity
  • Lect 1 Preliminary definitions. Deterministic Turing machines (DTM). DTM computations. Language accepted vs. functions computed. Examples. Generalizations. Deterministic vs. Non-deterministic devices. Examples. Resource bounded Turing machines. Complexity classes. Space bounded algorithms can't run forever!
  • Lect 2 Time-complexity bounds imply space-complexity bounds. Examples. Crossing sequences. Blocked computation. Compatibility. Block-wise simulation. Final remarks: further results.
  • Lect 3 Non-determinism and running time. Brute-force string matching. Deterministic simulation of non-deterministic TMs.
  • Lect 4 Non-determinism and space. Savitch argument. Recursive simulation of non-deterministic TMs. Complexity analysis. Interactive proof systems. Characterizations of NP and PSPACE.
  • Approximation algorithms
  • Lect 1 Context: copying with hard problems. Definitions: NPO problems. Examples: VERTEX COVER, BIN PACKING. Approximation algorithms. Examples. Absolute approximations. Planar Vertex Colouring. Algorithms: 6-colouring, 5-colouring. Absolute approximation for Planar Vertex Colouring.
  • Lect 2 Absolute approximations. Example: vertex colouring planar graphs. more examples. Edge colouring. Definition and results. (Vizing theorem). Negative results. The power of a graph. The CLIQUE problem. The CLIQUE problem does not have an absolute approximation algorithm.
  • Lect 3 Relative approximations. Scheduling: deefinition. Algorithm LS. Analysis (averaging argument). Algorithm LPT. Analysis. Definition of relative approximation algorithms. Examples.
  • Lect 4 Vertex Cover. Algorithms GREEDY1 and GREEDY2. Example of "bad" graph. Algorithm MM. Analysis. Algorithm DFS.
  • Lect 5 Approximation complexity classes: PTAS, APX, NPO. Polynomial time approximation schemes. PTAS for scheduling with analysis. Examples and Exercises. Other problems: KNAPSACK.
  • Lect 6 Bounds on approximability. General remarks: comparison with the theory of NP-completeness. MAX-3-SAT. Example. Non-approximability of MAX-3-SAT. Gap preserving reductions. Remarks: (1) combining several reductions (2) mapping of solutions (3) reductions for minimization problems (4) comparison with stronger reductions (5) on the name "gap preserving". PTAS vs. APX. CLIQUE is not in PTAS. Example. VERTEX COVER is not in PTAS.
  • Lect 7 Hardness of approximating Clique within a constant factor (via graph products). Boosters. Examples. Booster products. Hardness of approximating Clique within a polynomial bound.