Randomized, parallel and dynamic algorithms, F2003

2.part course at the Department of Computer Science, University of Aarhus in the Spring Semester, 2003.

web site for old course: Randomized, parallel and dynamic algorithms, F2002

• course description.
• Instructor: Gudmund Skovbjerg Frandsen
• Classes: Monday 10-12 and Thursday 13-15 in Coll R3

Usually each two-hour class will start with a lecture and end with a problem session.

Literature

• Randomized algorithms (12 lectures)
  
  • (MR) Rajeev Motwani and Prabhakar Raghavan: Randomized algorithms. Cambridge University Press, 1995.
  • Problems for randomised algorithms
  Supplementing literature
  • Yuval Peres, Iterating von Neumann's procedure for extracting random bits, The Annals of Statitiscs 20 (1992) 590-597.
  • Devdatt Dubhasi and Alessandro Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Manuscript .
• Parallel algorithms (8 lectures)
  
  • (S) Skyum: Introduction to parallel algorithms.
  • (Problems 1-5) Problems for parallel algorithms.
    
  • (J) JaJa: An introduction to parallel algorithms. Addison Wesley, 1992.
• Dynamic algorithms (9 lectures)
  
  • (Problems 1-11) Problems for dynamic algorithms.
    
  • (Note) Introduction to dynamic algorithms.
    
  • (Note) van Emde Boas trees.
    
  • (S2) Skyum: A self-adjusting datastructure - splay trees.
  • (T) Tarjan, Data structures and Network algorithms, SIAM, 1983. Chapter 5: Linking and cutting trees.
  • (EITTWY) Eppstein, Italiano, Tamassia, Tarjan, Westbrook, Yung, Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph, J. Algorithms 13 (1992) 33--54, and J. Algorithms 15 (1993) 173.
  • (HLT) Holm, Lichtenberg, Thorup: Poly-logarithmic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. JACM 48 (2001) pp.723-760
    
  • (T) Thorup: Near-optimal fully-dynamic graph connectivity. STOC'00 pp.343-350
    
  • (DI) Demetrescu, Italiano: A new approach to dynamic all pairs shortest paths STOC'03
  • (RS) Rauhe, Skyum: Dyck sprogene, Dynamiske algoritmer og deres kompleksitet, speciale (in Danish), 1995.
  • (MSU) Mehlhorn, Sundar, Uhrig: Maintaining Dynamic Sequences Under Equality-Tests in Polylogarithmic Time. Algorithmica 17 (1997) 183-198.
  • (FHMRS) Frandsen, Husfeldt, Miltersen, Rauhe, Skyum: Dynamic Algorithms for the Dyck Languages. WADS'95, LNCS 955, pp.98-108.
  • (ABR) Alstrup, Brodal, Rauhe: Dynamic Pattern Matching. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 819-828, 2000.

Homework assignments

• Homework 1 (hand in by Mar. 3): Do either A or B:
  A: MR 1.9, 2.7, 4.12.
  B: This assignment involves analysing and implementing a treap based dictionary and run experiments to compare it with a standard library implementation of a dictionary:
  • Read the description of treap based dictionaries (see note, pp.15-17) .
  • Compute good bounds on the complexity (expected usage of time and random bits) for each of the basic operations: lookup, insert, delete (see note, problem 2) .
  • Implement a treap based dictionaries with operations for lookup, insert, delete. Use you favorite programming language. You may assume that the dictionary will be used to hold integers.
  • Run experiments to compare the efficiency of your implementation with the built-in tree based dictionary in the programming language your are using (ex. TreeMap in case of Java). Be careful how you choose test input!
• Homework 2 (hand in by Mar. 24): At least one of the following (A,B):
  A: MR 7.12, 13.12; Problem 1 from randomized algorithms problem set
  B: This programming project consists in implementing the static dictionary with constant time query operation described in MR section 8.5. Note that randomisation is only used for the construction of the dictionary. The theory behind is contained in lectures R9 and R11.
  • Make a subroutine that given integer b returns some b-bit prime number (MR section 14.6)
  • Make a subroutine that given a list of n numbers constructs a static dictionary for the list elements with look-up time O(1) using space O(n) and based on two level hashing (MR section 8.5).
  • Make experiments to determine bounds on the constants hidden under the O(.) notation (including trade-off with time spent on constructing the data structure) and compare with theoretical predictions.
• Homework 3 (hand in by April 24): At least one of the following (A,B):
  A: S 8.2, J 2.46;
  Give a parallel algorithm for constructing an Euler circuit for an undirected graph (you may use the results of problem J 5.22);
  B: This programming project consists in implementing the simulation of a CRCW PRAM on an EREW PRAM as described in note (S) 7 and determine the overhead involved in the simulation. Since we do not have access to a PRAM, a simulation will be done on a usual sequential computer
  • decribe how the overhead ("constant" factor increase of work) involved in simulating a CRCW PRAM on an EREW PRAM can be determined from running the simulation algorithm on a sequential computer.
  • is the overhead expected to be dependent on the parallel slack? - on the problem size? - on the memory size?
  • program the simulation algorithm and select a simple CRCW program such as the max algorithm of (S) 8.1.a for making experiments to determine the overhead as a function of relevant parameters.
  • Comment on your results.
• Homework 4 (hand in by May 15): At least one of the following(A, B):
  A: Problem 10, Problem 11 from dynamic algorithms problem set
  B: Implement dynamic road clearance (explained in problem 2), ie. you should do both the trivial O(n), the simple O(log n) and the advanced O(log log n) solutions. Design and perform experiments that can tell you under what conditions (such as size of n) the various solutions are preferable in practice.

Links

• randomization
  • CD-ROM of random numbers; testing random number generators
  • Downloading random numbers from the web/internet
  • Hardware for generating random numbers
  • Random number generation website
• parallellization
  • SB PRAM
  • Practical PRAM Programming

Course Plan

Feb. 3	Lecture R1	Introduction to randomized algorithms Randomization on inputs versus algorithms. Analysis by linearity of expectation and indicator variables. Las Vegas and Monte Carlo algorithms. The complexity classes RP, BPP. MR 1-1.2, 1.5, 10.2
Feb. 6	Lecture R2	Introduction to randomized algorithms (cont.) Another example of a Las Vegas algorithm and analysis by linearity of expectation. Proof of existence by the probabilistic method. A Las Vegas algorithm that beats any deterministic strategy. MR 1.3, 2.1	Problems for R1,R2: MR 1.1, 1.2, 1.4, 1.8
Feb. 10	Lecture R3	Randomized algorithms: Proving lower bounds von Neumann's minimax principle Yao's techniques for proving lower bounds Average case time usage for best deterministic algorithm relative to a known worst case input distribution equals expected time usage of best randomized algorithm on worst case input MR 2.2
Feb. 13	Lecture R4	Derandomization Trading randomness for nonuniformity. Markov's and Chebyshev' inequalities. Trading time for random bits. MR 2.3, 3.2, 3.4	Problems for R3,R4: MR 2.3, 2.6, 2.12
Feb. 17	Lecture R5	Chernoff bounds and randomized rounding Chernoff Bound: The sum of independent indicator variables is distributed closely around the expectation. Randomised rounding: Good approximate solutions to hard combinatorial problems. MR 4.1, 4.3
Feb. 20	Lecture R6	Chernoff bounds (cont.) Application to analysis of a routing algorithm. MR 4.2	Problems for R5,R6: MR 4.8, 4.9, 4.13
Feb. 24	Lecture R7	Algebraic techniques in randomization Fingerprinting for result checking. Schwarz-Zippel theorem. Application to perfect matching. MR 7-7.3
Feb. 27	Lecture R8	Algebraic techniques (cont.) Distributed equality test. (On-line) pattern matching. MR 7.4-7.6	Problems for R7,R8: MR 7.2, 7.5, 7.8, 7.10
Mar. 3	Lecture R9	Dictionaries Universal hashing and dynamic dictionaries. 2-level hashing and static dictionaries. MR 8.4-8.5	Problems for R9: MR 8.22
Mar. 6	Lecture R10	Competitive analysis of on-line algorithms Competitiveness: Comparison of on-line solution to best off-line solution. Paging algorithms: deterministic and randomised solutions. MR 13-13.3	Problems for R10: MR 13.6
Mar. 10	Lecture R11	Competitive analysis of on-line algorithms Paging algorithms: Lower bounds on competitiveness using Yao's technique. MR 13.3	Problems for R11: MR 13.10
Mar. 13	Lecture R12	Primality test Randomised primality test. Generation of random primes. MR 14.6	Problems for R12: MR 14.12 2

Mar. 17	Lecture P1	PRAM The PRAM model for parallel programming. Time, work, optimality, Brent's scheduling principle. Parallel Prefix computation. S 4, 5, 6.1	Problems for P1: S 8.1; 3, 1b-d
Mar. 20	Lecture P2	Parallel sorting Merging, bucket sort, radix sort. Simulating strong CRCW PRAM on weaker EREW PRAM. S 6.2-6.4, 7	Problems for P2: 5
Mar. 24	Lecture P3	Basic techniques for PRAM programming Parallel prefix on pointer structures using list ranking. List ranking by pointer jumping. List ranking by symmetry breaking. J 2.2, 2.7, 3.1-3.1.1	Problems for P3: J 2.41, 2.43
Mar. 27	Lecture P4	Basic techniques (cont.) Euler tour technique. pre/in/post-order numbering of tree nodes. Tree contraction. Expression evaluation. J 3.2-3.3	Problems for P4: J 3.13, 3.20
Mar. 31	Lecture P5	Parallel algorithms for undirected graphs Connected components. Dense graphs: incidence matrix representation and creating supergraph hierarchy. Sparse graphs: adjacency lists and the pointer jumping technique. Minimum spanning tree. J 5-5.2	Problems for P5: J 5.16, 5.22
Apr. 3	NB! NB! NB! NB! NB! NB!	Præsentation af mulige specialeemner i algoritmik v/ Gerth Stølting Brodal, Rolf Fagerberg, Gudmund Skovbjerg Frandsen, Peter Bro Miltersen
Apr. 7	Lecture P6	Parallel algorithms for directed graphs and matrix problems Parallel matrix multiplication and powering. All pairs shortest paths in directed graph. Matrix inverse and determinant computation. J 5.5, 8.2.1., 8.8.1-Cor.8.3	Problems for P6: J 5.29, 5.31(b)
Apr. 10	Lecture P7	Randomized parallel algorithms Randomized symmetry breaking. Fractional independent set of planar graph. Point location in planar subdivision. J 9.2-9.3	Problems for P7: J 9.11, 9.13
Apr. 14	Lecture P8	Randomized parallel algorithms (cont.) Existence of perfect matching. Finding maximum matching. J 9.7	Problems (for P8): 9.31

Apr. 24	Lecture D1	Introduction to dynamic algorithms Partial and fully dynamic algorithms. The balanced binary tree technique. Note	Problem for D1: 6
Apr. 28	Lecture D2	van Emde Boas trees van Emde Boas trees. Note	Problems for D2: 1, 2, 3
May 1	Lecture D3	Dynamic trees Linking and cutting trees. S2, T	Problem for D3: 4
May 5	Lecture D4	Dynamic MST for plane graph minimum and maximum spanning tree for plane graph and dual. Maintaining min/max spanning tree for dynamic plane graph. EITTWY
May 8	Lecture D5	Dynamic algorithms for undirected graphs Euler tour tree data structure. Dynamic maintenance of connected components. HLT 2.1,3
May 12	Lecture D6	Dynamic algorithms for directed graphs Fully dynamic all pairs shortest paths. DI
May 15	Lecture D7	Dynamic string algorithms Deterministic coin tossing. Signature encoding of strings. Dynamic, persistent maintenance of a set of strings under concatenation, split, lcp, comparison. RS 7 (MSU)	Problem for D7: 7
May 19	Lecture D8	Dynamic string algorithms (cont.) Dynamic Maintenance of parenthesis balance information. Randomized solution using the finger print technique. Deterministic solution using the dynamic string data structure. RS 2,5,6,8 (FHMRS 1-4)	Problem for D8: 8
May 22	Lecture D9	Dynamic string algorithms (cont.) Dynamic range search. Dynamic Pattern Matching. ABR	Problem for D9: 9