HONR 278J: Under the Hood: Algorithms and their Applications
General Information Course
and Handouts Lectures Related
||Tue, Thu 3:30-4:45.
||A.V. Williams 3369.
|Office Hours (for rest of semester)
||Office hours will be THURSDAY, May 13 11-12am and TUES May 18th 11-12am.
Ever wondered, how does google do such a remarkable job as a search engine? How does mapquest give directions? How do we compress large amounts of data? How do we sequence DNA using computers? How do companies mine data and learn about you?
The main point of this course is to study a few topics,
and to explore the algorithmic methods and technology
behind these methods. For the first few weeks we will
review the history of algorithms, study many diverse (and easy)
to understand algorithms. Finally we will pick a few topics and
study the required graph theory and algorithmic tools
required to understand the principles behind these
software tools and packages.
The topics and order listed below are tentative and subject to change.
- Analysis of Algorithms:
Basics about analysis of algorithms, worst case behavior, Order
- Some simple algorithms, stable marriages, gcd, primality, binary
- Sorting and Selection: Sorting techniques, Selection.
- Heaps and other Data Structures.
- Elementary Graph Theory.
- Graphs and search techniques: Depth first search, Breadth first search,
- Applications of Algorithms: DNA sequencing, Google, Mapquest.
- NP-completeness: What does it mean for a problem to be NP-complete?
Examples of NP-complete problems.
Algorithmics: The spirit of computing by David Harel
Other readings will be given out in class.
Course Work and Grading
Final grades will be based on homework assignments, the midterm
exams, and the comprehensive final exam. The relative weights of these
will be 20% for the homework total, 10% for a small project,
30% for the midterm,
and 40% for the final exam.
Homeworks and Handouts:
General Course Information
Notes on Sorting and Heaps
Notes on GCD, Stable Marriages and Selection
Homework 1 Due on 2/17/04 Average: 27
Homework 2 Due on 2/26/04 Average: 30
Homework 3 Due on 3/11/04 Average: 36
Homework 4 Due on 4/6/04 Average: 34
In class MIDTERM on March 16 (Tuesday). Average 38.5
Homework 5 Due on 4/20/04 Average 29
Homework 6 Due on 5/06/04 Average: 36
Final is on May 19th (Wed) 10:30-12:30am.
I WILL BE AVAILABLE ON FRI, MAY 21 11-12am to discuss the exam,
hand back project reports. You may also look over your graded exam
Projects are due on May 17th (Mon) by 4:30pm.
- Lecture 1: Course Overview, General discussion of Algorithms, Euclid's
- Lecture 2: Running time of Euclid's algorithm. Fibonacci numbers.
- Lecture 3: Stable Marriage Problem. Proofs by Induction.
- Lecture 4: Analysis of algorithms.
- Lecture 5: Order notation. Selection.
- Lecture 6: Sorting .
- Lecture 7: Heaps.
- Lecture 8: Elementary graph theory. Orienting Graphs to make them
strongly connected. DFS.
- Lecture 9: Representation of Graphs. Graph coloring. Planar Graphs.
- Lecture 10: Exam Review.
- Midterm Exam.
- Lecture 11: Matchings and their applications.
- Lecture 12: Google and pagerank. Hubs and authorities.
- Lecture 13: Hubs and authorities. BFS.
- Lecture 14: Euler tours and their applications. Hamilton tours.
- Lecture 15: Discuss projects and Euler tour algorithm.
Visit to Cryptology museum. on Fri, Apr 9.
- Lecture 16: Dynamic Programming. Knapsack problem.
- Lecture 17: Dynamic Programming. Applications to Sequence comparison.
- Lecture 18: Cake cutting (guest lecture by Dr. Gasarch).
- Lecture 19: Dynamic Programming.
- Lecture 20: Shortest paths (Bellman-Ford) and Huffman coding.
- Lecture 21: Shortest paths (Dijkstra). NP-completeness.
- Lecture 22: Guest lecture by Bobby (Algorithms in Networking).
- Lecture 23: Review for final. NP-completeness.
- Lecture 24: Elementary Cryptography.
- Lecture 25: Guest lecture by Dr. Mount (Data compression).