## 15-853: Algorithms in the "Real World" Carnegie Mellon University, Computer Science Department Fall 2008

Instructors: Guy Blelloch and Daniel Golovin
Time: Tuesday and Thursday 10:30 - 11:50 Note: first class is September 9
Place: 4623 Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Guy, Tuesday 1:30-2:30pm : Daniel, Thursday 2:00-3:00pm

• Course announcements.
• Course overview and topic list.
• Course Requirements and Grading Criteria.
• Approximate schedule (TENTATIVE).
• Assignments.
• Information on algorithms available on the web
• Companies that sell products that use various algorithms

• ### Announcements:

• There is a minor bug in the statement of the Chernoff bound in the notes provided for nearest neighbors here. Until we get the source files and correct it, you can find an authoritative statement of (one of) the Chernoff bounds in the following list of large deviation inequalities.
• Assignment 5 clarifications:
• Problem 3: For both parts, assume Phi is given in conjunctive normal form. For part 1, a variable assignment F ensures "each clause has at least one literal set to false" if and only if when we substitute F(x_i) for x_i, then each clause contains at least one "false" value. Let 0 denote false, and 1 denote true as usual. For example, if the clause was (a, b, not(c)), then (a=0,b=1,c=0) makes the clause literals evaluate to (0,1,1) and thus contains at least one "false" literal, namely "a", whereas (a=1,b=1,c=0) makes the clause literals evaluate to (1,1,1) and thus does not contain at least one "false" literal.
• Assignment 5 is now posted
• Final Exam info: The final will be a 48 hour take-home exam. You will have some choice as to when you take it. Specifically, you will pick up the exam between Dec. 8th and Dec 12th from Guy's assistant Denny Marous (Wean 7116), sign a form pledging confidentiality, and submit your answers 48 hours later.

• ### 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

• Cryptography
One-way functions, basic protocols
Number theory review: groups, fields, Galois fields
Private key cryptosystems (Block Ciphers, Rijdael)
Public key cryptosystems (SSL, RSA, ElGamal, Diffie-Hellman key exchange)
Kerberos and Digital Cash

• Error Correcting Codes
Hamming Codes, Linear Codes
Reed Solomon Codes, Cyclic Codes (uses in CDs, DVDs, DSL, ...)

• Computational Biology
Approximate String Matching
Various gap and cost models
BLAST/FAST
Sequencing the Human Genome

• String Searching/Matching
Suffix Arrays and Suffix Trees

• 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
Airline crew scheduling

• Satisfiability
Proof Systems, Resolution
DPLL type algorithms, with advanced features (clause learning, backtracking heuristics, ...)
Local-search based methods
Reduction strategies to encode your problems as SAT instances

• Nearest Neighbors

• ### 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

• Assignment 1: Cyptography (due September 25)
• Assignment 2: Error Correcting Codes (due October 9) (solutions)
• Assignment 3: Computaional Biology and String Matching (due October 23)
• Assignment 4: Linear and Integer Programming (due Nov 13) (solutions)
• Assignment 5: Nearest Neighbors and SAT (due Dec 4)

• ### Relevant Books

See the lists within each of the topic pages

Guy Blelloch, guyb@cs.cmu.edu.