CS 591 A1: Algorithms for the New Age

COURSE INFO
Professor: Shang-Hua Teng
Lecture Time: Monday 3:00 - 6:00 PM at CAS 223

Office Hour: Monday 1:00 -- 2:30pm or by appointment (Room 276)
Prerequisites: CS 530 or consent of the instructor.
The Class: I would like take the opporunity of this seminar to discuss some basic and advanced algorithms that are used in modern practical applications. I would also like to cover a new framework for algorithm analysis, the smoothed analysis of algorithms which is recently developed by Dan Spielman (MIT) and myself to help explain the success of many algorithm that both worst-case and average-case cannot: Sample topics include:
  • Spectral Techniques for
    • Graph partitioning
    • Web-structures
    • Data mining and data clustering
  • Algorithms for internet
    • Resource management for DNS
    • Web-structures
    • Data mining and data clustering
  • Data Communication
    • Data Compression
    • Coding theory
  • Smoothed Analysis
    • Linear Programming and Optimizations
    • Numerical Analysis
  • Internet phenomena
    • Power Law
    • Small World
  • Efficient Algorithmic Techniques
    • Sampling
    • Approximation
    • Randomization
Each lecture will discuss (1) methods used today (2) issues and problems, (3) formulation of concrete problems, and (4) potential new lines of research. I will try to make the lecture as self-constained as possible.
Requirements and
Performance Evaluation:		 The class will not have any exams, but instead, the performance will be evaluated based on the following:

  • Scribe notes: Each lecture will have an assigned "scribe", whose job is to take notes for later distribution to the class. The notes should not be a simple copy of what is written on the white/blackboard. It has to be written to show that the scribe understands the material. I recommend to use the latex package that Professor Jeff Erickson of UIUC has prepared to help scribing. The scribed notes should be return to me in a week and I will post the latex as well as the ps-files.

  • Algorithm Project: Each student (or a group of two student depending on the number of students we will have in the class) will choose a topic to read and,

  • Presentation: Everyone will will be asked to make a 40 minutes presentation in the class about his/her reading.

  • Outstanding Research Problems: Throughout the semester, I will post open problems for potential research.

    • LECTURE TOPICS (This section of the webpage will be growing and evolving)
    Number Topic Notes
    1 (Sept 16) Spectral Techniques I: Graph Partitioning ps , latex
    2 (Sept 23) Spectral Techniques II: Spetral Embedding ps , latex
    3 (Sept 30) Spectral Techniques III: LSI and Data Mining ps , latex
    4 (Oct 7) Spectral Technique IV: Web link structures /Resource Management for DNS ps1 , latex
    5 (Oct 14) Web Authorities ps, latex
    6 (Oct 21) More on Kleinberg and Semidefinite Programming for Combinatorial Optimization ps , latex
    7 (Oct 28) Mathematical Programming and On-Line Algorithms ps , latex
    8 (Nov 4) Smoothed Analysis II ps , latex
    9 (Nov 11) Smoothed Analysis I: Optimization ps , latex
    10 (Nov 18) Presentation: Ben Hescott on Random Walk; Mohamed Alimi on Expanders , Anna Karpovsky on Network Topology ps1 ps2 ps1 , latex
    11 (Nov. 25) Guest Lecture on Coding theory by Dan Spielman (MIT) ps , latex
    12 (Dec. 2nd) Presentation: Marwan Fayed on Searching in unstructured topologies , Anukool Lakhina on Network topology discovery from traceroute Dhiman Barman on clustering data streams , Chase Seibert and Macdowell on Grid Computing and Cheng Dihan on Interior Point Methods ps , latex
    13 (Dec. 9th) Presentation: Robert McNerney on Expander Codes , Chun-Yun Hsiao on list decoding , Raj Ashar on Evolutionary Algorithms, Ernest Kim on DNS, and Weichao and Manish on sketch-based summarization method to summarize streaming data words latex

    Useful Links

    steng@cs.bu.edu