Announcements

• Textbook: Introduction to Algorithms (3ird edition), Cormen, Leiserson, Rivest and Stein.
• New media: announcements on twitter/csc_517 (enable SMS - very low traffic) and the class blog.
• Syllabus: similar to year's version is CSC517.101 and to many previous years.
• Practicum: The mainline of the course will have no programming. The optional practicum will assign you the task of implementing some of the algorithms using Javascript, CSS, and DHTML. If you would like to take the practicum, enroll in CSC 402.
• Grading: There are homeworks, one or two midterms, and a final. Weekly homework is assigned most Wednesdays. It is very important to do the homeworks!
• Grader: The grader is Nan Wu, nan.wu _at_ cs.miami.edu.
• Midterm: Wednesday, October 27
• Midterm Histogram
• No late homeworks accepted after Monday, December 6.
• Final: Friday, December 10, in class, from 2:00-4:30 PM.

Class notes

• Introduction
  • Machine models, solvability, correctness, efficiency.
  • Sorting a hand of cards, sorting a deck of cards..
  • Cheaper by Half
• Tools of the Trade
  • Solvability: Pseudocode,
  • Correctness: Loop Invariants
  • Example of Loop Invariants: Findmin
  • Efficiency: Step counting (PDF)
  • Big-Oh notation
• Recurrence Equations
  • Substitution Method, Tree Method, Master Method
  • Max subarray problem and Strassen multiplication (integer and matrix)
• Randomized algorithms
  • Probability theory, see notes.
    • Probability spaces and axioms,
    • Random variables and expectation
    • Conditional probability, independence, and Bayes
  • Hiring problem (number of maxima)
  • Generating a random permutation.
  • Selection in Random Linear Time
  • The power of randomness: Median Find in Deterministic Linear Time
• Making and breaking lower bounds
  • Lower bound on sort in the decision tree model
  • n-squared sorts:
    • Selection Sort (java applet)
    • Insertion Sort
  • n log n sorts:
    • Merge Sort
    • Heapsort
    • Quicksort
    • Partition algorithm (animation)
  • Linear sorts
    • Counting sort (animation)
    • Radix sort
    • Bucket sort
• Hashing
  • Elementary data structures (review)
  • O(1) access, encoding, hash function.
  • Collision resolution.
  • Linear Probing (animation), double hashing.
  • Universal Hashing, Perfect Hashing
• Midterm
• Search Trees
  • Binary Search Tree
  • Beautiful animated BST example
  • Red-Black Trees
  • Red Black animation
  • Splay trees (PDF) (applet)
  • Augmenting data structures
    • Dyanmic order statistics
    • Interval trees
• Algorithmic Paradigms
  • Dynamic Programming
    • recurrences and dynamic programming
    • Matrix chain multiplication
    • Longest common subsequence
  • Greedy Algorithms
    • Huffman codes
  • Fibonacci heaps (Wikipedia)
  • Union-Find (not presented at this time, presented with MST's)
• Graph Algorithms
  • Breadth First Search
  • Depth First Search
  • Topological Sorting
  • Strongly Connected Components
  • Mininum Spanning Tree
    • Kruskal
    • Prim
  • Single Source Shortest Paths
    • Bellman-Ford
    • via Topological sorting
    • Dijkstra
• Linear Programming

Assignments

• Problem Set 1; due Wed, Sept 8.
  • Read chapters 1 and 2.
  • Problem 1-1.
  • Exercises 2.1-3, 2.1-4.
  • Problems 2-1, 2-2, 2-3.
• Problem Set 2; due Wed, Sept 15.
  • Read chapter 3
  • Exercises 3.1-1, 3.1-2, 3.1-3, 3.1-4 and 3.1-5.
  • Problems 3-1, 3-2, 3-3 and 3-4.
• Problem Set 3: due Wed, Sep 22.
  • Read chapter 4
  • Exercises 4.3-1, 4.3-2, 4.3-3, 4.3-7 and 4.3-8.
  • Exercises 4.4-1, 4.4-2, 4.4-3 and 4.4-4.
  • Exercise 4.5-1.
• Problem Set 4: due Wednesday, Sep 29.
  • Read chapter 5.
  • Exercises 5.3-2, 5.3-3, 5.3-4 and 5.3-7.
  • Problem 5-1.
• Problem Set 5: due Wednesday, Oct 6.
  • Read chapter 9.
  • Exercises 9.1-1, 9.2-4, 9.3-1, 9.3-3, 9.3-5, 9.3-6, 9.3-6, 9.3-7, 9.3-8.
• Problem Set 6: due Wednesday, Oct 13.
  • Read chapter 6.
  • Exercises 6.2-1, 6.3-1, 6.3-2, 6.3-3, 6.4-1, 6.4-2, 6.4-3, 6.4-4, 6.5-1, 6.5-2, 6.5-5, 6.5-7. 6.5-8.
  • Extra credit: 6.5-9.
• Problem Set 7: due Wednesday, Oct 20.
  • Read chapters 7 and 8.
  • Exercises 8.2-1, 8.2-2, 8-3-1, 8.3-2, 8.3-3, 8.4-1, 8.4-2, 8.4-3.
  • Problems 8-4 and 8-6.
• Problem Set 8: due Wednesday, Oct 27.
  • Read chapters 10 and 11.
  • Exercises 11.1-1, 11.1-2, 11.1-3.
  • Exercises 11.2-1, 11.2-2, 11.2-3.
  • Exercises 11.4-1, 11.4-2, 11.4-3.
  • Problem 11-3 and 11-4.
• Midterm, Wednesday, Oct 27.
• Problem Set 9: due Wednesday, Nov 3.
  • Read chapters 12 and 13.
  • Exercises 12.1-1, 12.1-2, 12.1-4, 12.1-5;
  • Exercises 12.2-3, 12.2-5, 12.2-6;
  • Problems 12-1 and 12-2;
  • Exercises 13.3-2, 13.3-3, 13.4-3;
  • Problems 13-1, 13-2.
• Problem Set 10: due Wednesday, Nov 10.
  • Read chapters 14, 15 and 19 (except 19.4).
  • Exercises 14.1-1, 14.1-2, 14.1-3, 14.2-1, 14.3-1.
  • Exercise 19.2-1.
  • Exercises 15.5-1, 15.5-2 15.5-3;
  • Problems 15-1, 15-4, 15-6, 15-7;
• No homework for the week of Nov 11-17.
• Problem Set 11: due Wednesday, Nov 24.
  • Read chapters 16 and 22.
  • Exercises 16.3-2, 16.3-3, 16.3-6;
  • Exercises 22.2-1, 22.2-2, 22.2-4, 22.2-7;
  • Exercises 22.3-1, 22.3-2, 22.3-3, 22.3-5.
• Problem Set 12: due Wednesday, Dec 3. Last problem set, Yay!
  • Read chapters 23 and 24 (except 24.4 and 24.5).
  • Exercises 22.5-1 and 22.5-2.
  • Exercises 23.2-1, 23.2-2, 23.2-4. Problem 23-4.
  • Exercises 24.1-1, 24.2-1, 24.2-4, 24.3-1, 24.3-2.

Practicum

• Project 1: due Wed., Sept. 15.
  • Look over the code of Enter Name.
  • Make a web page using Javascript that converts teaspoons to gils.
  • Look over the code of Number Build.
  • Make a web page using Javascript like Number Build, except that rather than powers of 2 only, the user can select from powers of 2, 3, 4, up to 7.
• Project 2: due Wed., Sept. 29.
  • Write one of the n log n sorting routines in JavaScript. The starting point is webpage on insertion sort.
• Project 3: due Wed, Oct 13.
  • See RANDOMIZE-IN-PLACE algorithm in chapter 5.3, page 126 on the third edition. Implement it. Start with an array of 12 cells, and a button "Randomize" that applies the algorithm with each click.
• Project 4: due Wed, Nov 3.
  • Implement perfect hashing. Accept as input a set of numbers.
  • Randomly select primary and a collection of secondary hash functions as required in the book.
  • Select and reselect the primary until the sum of the squares of the number of items per primary bucket is less than 4n.
  • Select and reselect hash functions for each bucket until there are no collissions, when the secondary hash table is of size a square the bucket size.
  • Display the parameters and an image of the hash table(s).
  • Then show the lookup for an input value (successful or unsuccessful).
• Project 5: due Wed, Nov 24. Last project, Yay!
  • Write a web page for the Longest Common Subsequence program. Implement the dynamic programming algorithm for LCS in javascript in your web page. It should take two inputs and show the dynamic programming table and the result. Note: Try to make a nice presentation.

Writing Credit

• The origin of algorithms. A historical paper. There is actually a book, History of Algorithms ... that might guide you.
• The developement of the computer during WWII. Among the things developed were the Collissus and Turing's Bomb, there were code breaking computers. I think a guy by the name of Flowers was the person who built some of America's code breaking computers during the war.
• A science fiction short story about algorithms, computers, etc. If not original, you can do an analysis of some Sci-Fi books like The Diamond Age, or Snow Crash.

References

• Algorithms in the classical world.
• You can also take this course at MIT
• Dynamic programming examples
• Introduction to Probability by Grinstead and Snell
• Animated algorithms.
• Fast Fourier Transform (PDF notes)
• Skip lists
• Cuckoo Hashing
• Deletion in hash tables.
• Bloom Filter (Wikipedia)

Typography

• Futura: On Macs, set in Futura. Futura is not a font for the web, because it features low readability.
• Verdana: IKEA booted Futura for Verdana font, creating a scandal in the design world.
• Trebuchet MS: Set in Trebuchet MS on Microsoft.