Special Announcements

• Demonstration of redirecting input in Java for Dimitris' csc517.131.

Announcements

• Textbook: Introduction to Algorithms (3ird edition), Cormen, Leiserson, Rivest and Stein.
• Emails to me concerning the class should be sent to the tagged email address burt+csc517@cs.miami.edu. (Note: tags might not be working. If I don't respond at the tagged address, send without the tag.)
• New media: announcements on twitter/csc_517 (enable SMS - very low traffic) and the class blog.
• Syllabus: similar to year's version is CSC517.111 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 403.
• 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!
• No late homeworks accepted after the last day of class, Friday, Dec 2.
• Home work grades: mean and std dev.
• Grader: Fu Huansong, a.k.a. Fu, fuhuansong at gmail.
• Office hours: I am available Fridays, 1:30 to 3:00, and by appointment.
• Midterm: Wednesday, Oct 26.
• Midterm Histogram
• Final: Monday, December 12, in class, from 2:00-4:30 PM.

• No class on Monday Nov 14th.

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
  • Partition algorithm (animation)
  • The power of randomness: Median Find in Deterministic Linear Time
• Making and breaking lower bounds
  • Lower bound on sort in the decision tree model
  • Linear sorts
    • Counting sort (animation)
    • Radix sort
    • Bucket sort
  • Review of O(n²) and O(n log n) sorts:
    • Selection Sort (java applet)
    • Insertion Sort (javascript)
    • Merge Sort
    • Heapsort (code)
    • Quicksort (code)
• Searching
  • Hashing
    • Elementary data structures (review)
    • O(1) access, encoding, hash function.
    • Collision resolution.
    • Linear Probing (animation), double hashing.
    • Universal Hashing, Perfect Hashing
  • Trees
    • Binary Search Tree
    • Beautiful animated BST example
• Midterm
• Advanced data structures
  • Self balancing trees
    • Red-Black Trees
    • Red Black animation
  • Augmenting data structures
    • Dynamic order statistics
    • Interval trees. Proof of correctness (blog entry)
  • Skip lists Skip Lists: probabilistic alternative to balanced trees, (PDF)
  • Union-Find
• Algorithmic Paradigms
  • Dynamic Programming
    • recurrences and dynamic programming
    • Matrix chain multiplication
    • Longest common subsequence
  • Greedy Algorithms
    • Huffman codes
  • Linear Programming
• 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

Assignments

• Problem Set 1; due Wed, Sept 7.
  • Read chapters 1 and 2.
  • Exercises 1.1-3., 1.1-4, 1.1-5, 1.2-2 and 1.2-3.
  • Exercises 2.1-3, 2.1-4, 2.2-1, 2.2-2, 2.2-3 and 2.2-4.
  • Problem 2-1.
• Problem Set 2; due Wed, Sept 14.
  • Read chapter 3
  • Problem 2-2 and 2-3.
  • Exercises 3.1-1, 3.1-2, 3.1-3, 3.1-4 and 3.1-5.
• Problem Set 3: due Wed, Sep 21.
  • Problems 3-1, 3-2, 3-3 and 3-4.
  • Read chapter 4
  • Exercises 4.3-1, 4.3-2, 4.3-3, 4.3-7 and 4.3-8.
• Problem Set 4: due Wed, Sep 28.
  • Exercises 4.1-1, 4.1-2, 4.1-5;
  • Exercises 4.4-1, 4.4-2, 4.4-3, 4.4-4, 4.4-5;
  • Exercise 4.5-1.
• Problem Set 5: due Wed, Oct 5.
  • Problems 4-1 and 4-3.
  • Read chapter 5.
  • Exercises 5.3-2, 5.3-3, 5.3-4 and 5.3-7.
  • Problem 5-1.
• Problem Set 6: due Wednesday, Oct 12.
  • Read chapters 8 and 9.
  • Exercises 8.2-1, 8.2-2, 8.3-1, 8.3-2, 8.4-1, 8.4-2, 8.4-3.
  • Exercises 9.3-3, 9.3-5, 9.3-6, 9.3-7, 9.3-8.
• Problem Set 7: due Wednesday, Oct 19.
  • Read chapter 6, 7, 10 and 11.
  • Exercises 6.3-2, 6.3-3, 6.4-3, 6.4-4, 6.5-5, 6.5-7. 6.5-8.
  • Problem 6-2.
  • Exercises 11.1-2, 11.1-3, 11.2-1, 11.4-1, 11.4-2, 11.4-3.
• Problem Set 8: due Wednesday, Oct 26.
  • Read chapter 12.
  • Exercises 12.1-1, 12.1-2, 12.1-4, 12.1-5;
  • Exercises 12.2-3, 12.2-5, 12.2-6;
  • Exercises 12.3-1, 12.3-2, 12.3-3;
• Midterm, Wednesday, Oct 26.
• Problem Set 9: due Wednesday, Nov 9.
  • Read chapters 13, 14 and 21.
  • Exercises 13.3-2, 13.3-3, 13.4-3;
  • Problem 13-1;
  • Exercises 14.1-1, 14.1-2, 14.1-3, 14.2-1, 14.3-1;
  • Exercise 21.3-3, 21.3-3, 21.3-4;
  • Problem 21-1.
• Problem Set 10: due Wednesday, Nov 16.
  • Read chapters 15 and 16.
  • Exercises 15.4-1, 15.4-2 and 15.4-5.
  • Exercises 15.5-1, 15.5-2 and 15.5-3;
  • Problems 15-1, 15-4 and 15-7;
  • Exercises 16.1-2, 16.1-3, 16-1.4 and 16-1.5.
• Problem Set 11: due Wednesday, Nov 30.
  • Read chapters 29, 22 and 23.
  • Exercises 29.1-4, 29.1-5, 29.1-6, 29.1-7 and 29.1-8.
  • Exercises 29.5-5, 29.5-6 and 29.5-7.
  • Exercises 22.2-7, 22.2-8 and 22.2-9.
  • Exercises 22.3-1, 22.3-2 and 22.3-3.
• Material on final.
  • Please look over the exercises in chapter 23 for the final.

Practicum

• Project 0:
  • Email me for your class account login and password. You will be working on the lab machines. You can login remotely using lee.cs.miami.edu. Your webpages are placed in the public_html subdirectory of your directory and will appear at http://web.cs.miami.edu/home/loginname, example: http://web.cs.miami.edu/home/burt
• Project 1: due Wed., Oct. 5.
  • 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, Oct 19.
  • 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 3: due Wed., Nov 9.
  • 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 collisions, 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 4: due Wed, Nov 30.
  • 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 need to break military codes drove forward the construction of computers during World War II. Among the early computers were the Colossus designed by Tommy Flowers, to break German Navel Codes (Tunny) and Turing's Bomb, to break army and high command codes (Enigma). These were really the first computers ever built. there were code breaking computers.
• 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

• Lucida Sans: A typeface by Charles Bigelow and Kris Holmes. This year's default font. For its lightness, given that the actual subject matter is heavy.
• Futura: On Macs, set in Futura. Futura is not a font for the web, because it features low readability. Despite that, I used it as the default font in previous years.
• Verdana: IKEA booted Futura for Verdana font, creating a scandal in the design world. Probably my favorite font for this page, but I went with Lucida.
• Trebuchet MS: Set in Trebuchet MS, a font by Microsoft font designer Vincent_Connare. This font was meant to be "Microsoft's Verdana". Every nation-state has a national font. When the Franks invaded Gaul they brought with them the Frankish hand. And what else ... (I'm making this up, you know.)