Exams

• Midterm: Tuesday, October 15. Chapters up to 9. (In First Edition, Chapters up to 10.)
• Midterm Histogram
• Final: Tuesday, December 17. 2:00-4:30 in MM 215

• Homework due 10 Oct will be available, corrected, Monday before the midterm. Email grader.
• You are encouraged to sign up for Csc 401, the lab component of this course.

Notes

• Introduction, Background.
  • How to sort a pack of cards. (Insertion, Selection)
  • Big-Oh notation
  • Series with Applications
• Heaps and Heapsort
  • Heapsort Java code
• Sorting
  • Quicksort
  • Lower bounds for sorting, comparison model.
  • Linear time sorts, Counting, Radix and Bucket sort.
• Linear time selection, median
• Hashing
  • Double Hashing (Java code)
  • Deletion (Java code)
  • Check sum to hash "good" card numbers.
  • Universal Hashing
• Binary Search Trees
  • Basics
  • Red-Black Trees
• Dynamic Programming
  • Matrix Chain Multiplication, Java.
  • Longest Common Subsequence
  • Optimal Polygon Triangulation (convex polygons)
• Greedy Algorithms
  • Activity Selection
  • Huffman codes
  • Greedy versus Dynamic Programing.
• Network algorithms: Foundation
  • Breadth First Search (BFS)
  • Depth First Search (DFS)
  • DFS edge types: Tree, Forward, Back and Cross.
  • Topological Sort
  • Strongly Connected Components (SCC)
• Network algorithms: Minimum Spanning Tree
  • Safe edges, Greedy algorithm.
  • Prim's Algorithm
  • Union-Find Algorithm
  • Kruskal's Algorithm
• Network algorithms: Shortest Path (single source)
  • Relaxation, Dynamic programming and Greedy algorithm.
  • Bellman-Ford: relaxation for general graphs and weights.
  • Relaxation for DAG's
  • Dijstra: relaxation for non-negative edge weights.
• NP-Completeness and Approximation Algorithms
  • Quick description of NP and NP completeness
  • Vertex cover problem. Approximation algorithm (factor of 2).
  • Traveling salesman problem. Approximation algorithm (factor of 2).

Projects Csc401 students only.

1. Write merge-sort. See heapsort for a model.
2. Write quick-sort. See heapsort for a model.
3. Write a hashing program. Hash on strings (say, people's names). Use the open-chaining method. Support Find, Insert and Delete operations.
   Above projects due by midterm
4. Write a tree search program. Use a hash of a string (say, a person's name) as the key. Resolve hash collisions by continuing the tree search. Support Find, Insert, Delete and PrintTree operations.
5. Write a program solving Problem 15-1 (16-1 in 1-st edition). You input should be a sequence of integer pairs (the point coordinates as integers) taken from a file.
   Above projects due 1 week before last class

1. Problems 3-2 and 3-3.
   (In First Edition, these are problems 2-2 and 2-3.)
   Due Sept 24.
2. Exercises 6.2-1, -3, -4 and -5. Exercises 6.3-1, -2 and -3.
   (In First Edition, these are exercises 7.2 all except -5, 7.3 all.)
   Due Oct 3.
3. Problems 7-1, 7-3, 7-4.
   (In First Edition, Problems 8-2, 8-3, 8-4.)
   Due Oct 10.
4. Exercises 11.2-4, 11.4-1 and 11.4-4
   (In First Edition, Exercises 12.2-5, 12.4-1 and 12.4-4.)
   Due Oct 29.
5. Exercises 12.1-2, 12.1-3 and 12.1-5, and Problems 13-1, 13-2.
   (In First Edition, Exercises 13.1-2, 13.1-3, and 13.1-5, and Problems 14-1 and 14-2.)
   Due Nov 5.
6. Exercise 15.4-5, Problems 15-1, 16-1 (Exercise 16.3-5, Problems 16-1, 17-1, 1-st Edition)
   Due Nov 19.
7. Exercises 22.2-1, 22.2-2 and 22.2-8, 22.3-3, 22.3-7. (Exercises 23.2-1, 23.2-2 and 23.2-8, 23.3-2, 23.3-6 in 1-st Edition)
   Due Dec 3.