Exams:

• Midterm: Wed Oct. 19.
  Example midterm
  Histogram
• Final: Monday Dec 12, in class.
  All material from midterm until the class of Friday, Dec. 9.
  • Hashing
  • Binary Search Trees
  • Dynamic Programming and Greedy Algorithms
  • Graph Algorithms
  • Mininum Spanning Trees
  • Shortest Paths

• Introduction to Algorithms, 2nd ed. Cormen, Leiserson, Rivest, Stein.

• You are encouraged to sign up for Csc 401, the lab component of this course.
• See last year's homepage for more information.
• The grader is Wei Zhou at weizhou@students.cs.miami.edu>

Workbook:

• Introduction
  • Pseudocode, ADT's.
  • Correctness: Assertions, Loop Invariants
  • Efficiency
  • Selection Sort, Insertion Sort , Merge Sort
• Mathematical Preliminaries
  • Merge Sort recurrence
  • Big-Oh notation
  • Series with Applications
• Sorting and Selection
  • Heapsort
  • Quicksort
  • Randomized Algorithms and Probabilistic Analysis (review of prob.) (See Grinstead and Snell for a (free) book on probability.
  • Lower bounds for sorting.
  • Linear time sorting.
  • Randomized and deterministic median find.
• Hashing
  • Resolution by chaining
  • Hash functions
  • Open addressing
  • Universal and Perfect hashing
  • Deletion in Hash tables
• Binary Search Trees
  • Binary Search Tree
  • Red-Black Trees
  • Splay Trees
  • Skip Lists (PDF)
    • MIT lecture notes
    • Additional math
• Algorithm techniques and paradigms
  • Dynamic Programming
    • A scheduling problem
    • Matrix chain multiplication
    • Longest Common Subsequence
    • Optimal binary search trees
  • Greedy Algorithms
    • Activity Selection
    • Greedy versus Dynamic Programing.
    • Huffman codes
  • Amortized Analysis (optional material)
    • aggreate, accounting and potential methods
    • Dynamic tables
  • Linear Programming (special topic)
• Graph Algorithms
  • Breadth-first search
  • Depth-first search
  • Topological Sort
  • Strongly Connected Components
  • Union-Find and Kruskal MST
  • Prim MST.
  • Bellman-Ford single-source Shortest Paths
  • Dijkstra's algorithm;

Exercises:

1. Exercises 2.1-1 through 2.1-4; Exercises 2.2-1 through 2.2-4.
   Due: Wed 7 Sept
2. Exercises 2.3-1 through 2.3-5 and Problem 2-2 (page 38).
   Due: Friday Sept 16.
3. Problems 3-1 through 3-4. Problems 4-1 through 4-4.
   Due: Friday Sept 23.
4. Exercisess 6.1-1 through 6.1-5; 6.2-1 through 6.2-4; 6.4-1 through 6.4-4.
   Due: Friday Sept 30.
5. Exercises 7.1-1, -2 and -3; 7.2-1, -2, and -3; 7.3-1 and -2.
   Due: Monday Oct 10.
6. Problems 6-2 (page 143); 7-1 and 7-2 (pages 159, 161); 8-2 and 8-4 (pages 178-179).
   Due: Monday Oct 17.
7. Exercises 11.2-1, 11.2-2, 11.2-3; 11.3-1, 11.3-2, 11.3-3, 11.3-4; 11.4-1, 11.4-2.
   Due: Friday Oct 28.
8. Exercises 12.1-1 through -5; 12.2-1 though -3; 12.3-1 through -5.
   Due: Wed Nov 9.
9. Exercises 13.2-1 through -4; 13.3-1 through -3; and 13.4-1 through -3.
   Due: Fri Nov 18.
10. Exercises 15.1-1 through -3; 15.2-1 through -3; and 15.5-1 through -3.
    Due: Wed Nov 30
    Happy Thanksgiving
11. Exercises 16.1-2, 16.1-3; 16.3-1, 16.3-2; and problem 16-1 (page 402).

Practicum assignments:

1. Using C on Unix of Windows, write Insertion Sort and Merge Sort. Test them on data sets of increasing size and plot the run time, verifying that Insertion Sort is quadratic and Merge Sort is n log n. Give the cross over point, if any, when Merge Sort is faster than Insertion Sort in actual run time.
   Due: Monday Oct 3.
2. Use the qsort libc function to sort a large data set of words. You will have to master function pointers. Compare speed to your implementations of Insertion and Merge Sort. How does qsort avoid bad run times?
   Due: Monday Nov 11.
3. Implement a Skip List. Operations should be find, insert, and delete.
   Due: Monday Dec 5.