Andrew McGregor

Welcome to the Spring 2012 homepage for CMPSCI 711: More Advanced Algorithms.

• Instructor:
  • Andrew McGregor.
  • Office hours: By appointment.
  
  
• Lectures:
  • Monday, Wednesday, 2:05 to 3:20 pm in LGRC A310.
  
  
• Textbooks:
  • There is no official textbook for the class and all required material will be distributed in class.
  • Background on Randomized Algorithms:
    • Randomized Algorithms by Motwani and Raghavan
    • Probability and Computing by Mitzenmacher and Upfal
    • Concentration of Measure for the Analysis of Randomised Algorithms (Dubhashi, Panconesi)
  • Related Courses:
    • Dartmouth (Chakrabarti)
    • MIT (Indyk)
  • Useful Surveys:
    • Sketch Techniques for Apporximate Query Processing (Cormode)
    • Sparse Recovery Using Sparse Matrices (Gilbert, Indyk)
    • Data Streams: Algorithms and Applications (Muthukrishnan)
    • Chapter on Communication Complexity (Arora, Barak)
  
  
• Homeworks:
  • Homework 1: Due 2/22.
  • Homework 2: Due 3/14.
  • Homework 3: Due 4/16.
  • Homework 4: Due 4/30.
  
  
• Slides:
  • Section 0: Overview
  • Numbers:
    • Section 1-1: Sampling
    • Section 1-2: Intro to Sketches: F0 and F2
    • Section 1-3: Multi-Purpose Sketches: Count-Min, Count-Sketch for Heavy Hitters, Range Queries, Quantiles
    • Section 1-4: Sampling via Sketches: Lp sampling and Applications
    • Section 1-5: Approximate Representations and Signal Reconstruction
    • Associated Papers:
      • An Improved Data Stream Summary: The Count-Min Sketch and its Applications (Cormode, Muthukrishnan)
      • The space complexity of approximating the frequency moments (Alon, Matias, Szegedy)
      • Streaming Algorithms from Precision Sampling (Andoni, Krauthgamer, Onak)
      • Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems (Jowhari, Sağlam, Tardos)
  • Graphs:
    • Section 2-1: Connectivity, k-connectivity, Spanners, Sparsification
    • Section 2-2: Graph Sketches
    • Section 2-3: Matchings and Bipartiteness
    • Associated Papers:
      • Analyzing Graph Structure via Linear Measurements (Ahn, Guha, McGregor)
      • On Graph Problems in a Semi-streaming Model (Feigenbaum et al.)
      • Finding Matchings in the Streaming Model (McGregor)
  • Clustering and Geometry:
    • Section 3-1: Coresets and Clustering
    • Section 3-2: Gridbased Sketching
    • Associated Papers:
      • Tight results for clustering and summarizing data streams (Guha)
      • Algorithms for Dynamic Geometric Problems over Data Streams (Indyk)
  • Sequences:
    • Section 4-1: Longest Increasing Sequences and DYCK
    • Section 4-2: Memory Checking
    • Associated Papers:
      • Recognizing well-parenthesized expressions in the streaming model (Magniez, Mathieu, Nayak)
      • Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition (Chakrabarti, Cormode, Kondapally, McGregor)
      • Estimating the Sortedness of a Data Stream (Gopalan, Jayram, Krauthgamer, Kumar)
  • Lower Bounds:
    • Section 5-1: Basic Connections, Examples, Hamming Distance
    • Section 5-2: Information Statistics and Disjointness
    • Associated Papers:
      • An information statistics approach to data stream and communication complexity (Bar-Yossef, Jayram, Kumar, Sivakumar)
      • The One-Way Communication Complexity of Hamming Distance (Jayram, Kumar, Sivakumar)
  • Special Topics:
    • Section 6-1: Sliding Windows
    • Section 6-2: Distributed Streams and Functional Monitoring
    • Section 6-3: Stochastic Streams
    • Associated Papers:
      • Selection and Sorting with Limited Storage (Munro and Paterson)
      • Smooth Histograms for Sliding Windows (Braverman and Ostrovsky)
      • Optimal Random Sampling from Distributed Streams Revisited (Tirthapura and Woodruff)
      • Algorithms for Distributed Functional Monitoring (Cormode, Muthukrishnan, Yi)