HEART: Exploring algorithms for hard problems in computer science
Wednesdays 3:00 - 4:15pm, Latrobe Hall 107
September 14 2017 – November 30 2017 (except Oct 18 and Nov 22)
Instructor: Charlotte Darby cdarby at jhu.edu
Summary
Many important optimization problems across engineering disciplines have been classified by computer scientists as computationally "hard" to solve. In this course, we'll step up to the challenge and work through the theoretical background of some of these famous problems and learn about algorithms developed to tackle them. We'll focus on graph problems, including Traveling Salesman, path-finding and graph coloring, with lessons based around visual representations and interactive activities.
Policy
These courses meet weekly for ten weeks in 90-minute sessions. Students in these tutorials are graded on a pass/fail basis only. Workload may include readings, presentations, and active participation in class, however no written work (such as papers or problem sets) may be assigned. Attendance is mandatory.
[Note: Excused absences for illness, religious holiday, emergency should be discussed with the instructor. If you have sports or an extracurricular activity that may cause you to miss class, I encourage you to still take a HEART class but register for a different section.]
Course Materials
Please get The golden ticket: P, NP, and the search for the impossible (Lance Fortnow). Readings will be assigned before and after related class sessions. E-book is fine, JHU library has it but there may be a limited number of electronic copies.
Advanced Resources
TSP
The Traveling Salesman Problem: A Computational Study (David Applegate et al).
Python tutorial on programming TSP heuristics
P vs. NP
MIT OCW Introduction to Algorithms: Computational Complexity
MIT OCW Design and Analysis of Algorithms: P,NP,NP-completeness,Reductions
Graph Paths in Bioinformatics
de Bruijn graphs and Eulerian walks from Ben Langmead's (JHU CS Professor) Coursera, Algorithms in DNA Sequencing
P vs. NP in popular culture
This episode of Elementary (CBS, 2013)
Related to the movie - essay by British mathematician G. H. Hardy A Mathematician's Apology
Cryptography
Schedule
1. The The Traveling Salesman Problem (TSP)
Readings (after class 1)
In Pursuit of the Traveling Salesman:
Mathematics at the Limits of Computation, Chapter 1.
The Golden Ticket, Chapter 1
Khan Academy video and the two accompanying exercises 1 2
2. P vs. NP
Readings (after class 2)
The Golden Ticket, Chapter 3, 4
New York Times article about a successful kidney transplant cycle
Refresher on DNA as preparation for Class 3
3. Graph paths in bioinformatics: genome assembly
Readings (after class 3)
Phillip Compeau, Pavel Pevzner, Glenn Tesler. How to apply de Bruijn graphs to genome assembly. Nature Biotech. 2011
Computational Complexity Zoo
4. P vs. NP and the Computational Complexity Zoo
Readings (after class 4)
The Golden Ticket, Chapter 6, 5
A perspective on the nuances of the TSP
5. Heuristics and Computability
Turing Machine Video
Halting Problem Video
Readings (after class 5)
"Antibodies" (short story) by Charles Stross
SIGACT News 2002 and 2012 surveys of computer scientists (William Gasarch)
The Golden Ticket, Chapter 2
5.5 Film: Travelling Salesman, 2012
6. Social implications of P vs. NP
Readings (after class 6)
The Golden Ticket, Chapter 7
7. Logic circuits
Readings (after class 7)
The Golden Ticket, Chapter 8, 10
8. Cryptography
Lava Lamps and Random Numbers Video
RSA Concept Video (Long Bank Number)
Zero-knowlege games
Readings (after class 8)
Lance Fortnow. The Status of the P Versus NP Problem. Communications of the ACM, 2009.
Zack Grossbart. P vs. NP: The Assumption That Runs The Internet Magazine article (Smashing Magazine), 2015.
9. Presentations
Liam, Eric, Sam, Matt, Christopher
10. Presentations cont'd.
Sara, David, Aidan, Elliot, Randy