------------------------------------

      HONR 278J:  Under the Hood: Algorithms and their Applications
      Spring 2004

      General Information Course Overview Homeworks and Handouts Lectures Related Stuff

      ------------------------------------

      General Information

      Class Time Tue, Thu 3:30-4:45.
      Room CSIC 3118

       
      Instructor Samir Khuller
      Office A.V. Williams 3369.
      Office phone 405 6765
      Office Hours (for rest of semester) Office hours will be THURSDAY, May 13 11-12am and TUES May 18th 11-12am.
      Email samir@cs.umd.edu

       

      ------------------------------------

      Course Overview

      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.

      Syllabus

      The topics and order listed below are tentative and subject to change.
      • Analysis of Algorithms: Basics about analysis of algorithms, worst case behavior, Order notation, Asymptotics.
      • Some simple algorithms, stable marriages, gcd, primality, binary search.
      • Sorting and Selection: Sorting techniques, Selection.
      • Heaps and other Data Structures.
      • Elementary Graph Theory.
      • Graphs and search techniques: Depth first search, Breadth first search, Shortest Paths.
      • 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.

      Texts

      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 Solution 3

      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 then

      Projects are due on May 17th (Mon) by 4:30pm.

      ------------------------------------

      Lectures

      • Lecture 1: Course Overview, General discussion of Algorithms, Euclid's GCD algorithm.
      • 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).