Algorithms in the Real World F06 (original) (raw)
15-853: Algorithms in the "Real World"
Carnegie Mellon University, Computer Science Department
Fall 2006
Instructors: Guy Blelloch andAnupam Gupta
Time: Monday and Wednesday 10:30 - 11:50
Place: 4623 Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Monday 1:30-2:30pm (Guy), Wednesday 1:00-2:00pm (Anupam)
- Course overview and topic list.
- Readings, Notes and Slides
- Course Requirements and Grading Criteria.
- Approximate schedule.
- Assignments.
- Information on algorithms available on the web
- Companies that sell products that use various algorithms
Course Overview:
This course covers how algorithms and theory are used in "real-world" applications. The course will cover both the theory behind the algorithms and case studies of how the theory is applied. It is organized by topics and the topics change from year to year.
This year we will cover the following topics. The exact subtopics might change
- String Searching/Matching
Suffix Arrays and Suffix Trees - Computational Biology
Approximate String Matching
Various gap and cost models
BLAST/FAST
Sequencing the Human Genome - Linear and Integer programming
Flow problems as Linear programs
Simplex, Elipsoid and Interior point methods
Reductions to integer programs
Basic techniques for solving integer programs - Separators
- Dimensionality Reduction
- Error Correcting Codes
Hamming Codes, Linear Codes
Reed Solomon Codes, Cyclic Codes
Expander graphs, and LDPC Codes. - Compression
Information Theory
Huffman/Arithmetic/Gamma Codes
Context Coding/PPM
Lempel Ziv/Gzip/Burrows Wheeler
Graph Compression
Requirements and Grading Criteria
- Readings (handed out per topic)
- Homework Assignments (1 or 2 per topic) (50%)
- Take-home Midterm (10%)
- Take-home final exam (20%)
- Grading Assignments (1 over the semester) (10%)
- Class participation (10%)
Assignments
- Assign 1: Sorting Suffixes, Due September 18
- Assign 2: Computational Biology -- String Matching, Due October 2
- Assign 3: Convex Programming, Due October 16
- Assign 4: Separators, Due November 1
- Assign 5: Chernoff Bounds and Polynomials, Due November 15
- Assign 6: Error Correcting Codes and some Compression, Due November 29
- Assign 7: Compression and some Streaming, Due December 8
Relevant Books
See the lists within each of the topic pages