Exams:

• Midterm: Wednesday, October 22, 2003.
  Midterm distribution
• Final: Friday December 12, 8:00-10:30 am.

• Grader: Yuan Zhang. yuan@mail.cs.miami.edu
• You are encouraged to sign up for Csc 401, the lab component of this course.
• See the syllabus for grading policy for the practicum.
• Last day of class: Friday December 5.

Notes:

• Introduction, Background.
  • How to sort a pack of cards. (Insertion, Selection)
  • Merge Sort recurrence
  • Big-Oh notation
  • Series with Applications
• Heaps and Heapsort
  • Heapsort Java code
• Sorting
  • Loop Invariants
  • Selection Sort (DEMO)
  • Insertion Sort Java code
  • Quicksort Java code
• Linear time Sorting
  • Lower bounds for sorting, comparison model.
  • Counting, Radix and Bucket sort.
• Order Statistics
  • Randomized algorithms, review of probability
  • Expected linear time Median-Find.
  • (deterministic) Median-Find algorithm
• Data Structures (review)
• Hashing
  • Hash functions; linear probing.
  • Double Hashing (Java code)
  • Deletion (Java code)
  • Universal Hashing
• Binary Search Trees
  • Basics
  • Red-Black Trees
• Dynamic Programming
  • A scheduling problem
  • Longest Common Subsequence
  • Optimal binary search trees
• Greedy Algorithms
  • Activity Selection
  • Greedy versus Dynamic Programing.
  • Huffman codes
• String Matching
  • Naive algorithm
  • Integers mod q, for q a prime
  • Rabin Karp
  • Finite state automata and matching
• Computational Geometry
  • Points
  • Affine linear combination of points:
    • line segments
    • triangles
  • Cross products
  • Intersection of lines
  • Convex hulls
  • Nearest neighbors
• Fast Fourier Transforms
  • Motivation I: Multiplication of polynomials, and of large integers.
  • Motivation II: Represention of functions by sum of sin's.
  • Euler's identity, roots of unity.
  • Vector space of functions, scalar (hermitian) product.
  • Discrete Fourier Transform; Fast Fourier Transform. (Notes
  • Butterfly networks.

Projects:
CSC 401: Practicum assignments

1. See homework 3 for directions on writing Selection and Insertion sort.
2. Write media-find algorithm. Use large data sets, generated by a program, to test.
   Due: before midterm.
3. 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.
4. Write a program solving Optimal binary search trees.

1. Problems 3-2 and 3-3.
   Due Sept 10.
2. Exercises 6.2-1, -3, -4 and -5. Exercises 6.3-1, -2 and -3.
   Due Sept 19.
3. Homework 3
   Due Sept 26.
4. Problems 7-1, 7-3, 7-4. Exercises 8.2-1, 8.3-1, 8.4-1.
   Due Oct 10.
5. Exercises 11.2-4, 11.4-1 and 11.4-4
   Due Oct 20.
6. Exercises 12.1-2, 12.1-3 and 12.1-5, and Problems 13-1, 13-2.
   Due Nov 7.
7. Exercise 15.4-5, Problems 15-1, 16-1
   Due Nov 14.
8. Exercises 32.1-1, 32-1.2, 32.2-1, 32.3-1, 32.3-2; 33.1-1.
   Due December 8