Announcements

• Semester number is 101, first semester of 2010 year.
• Required textbook: Introduction to Algorithms (3ird edition), Cormen, Leiserson, Rivest and Stein.
• Programming and CSC401: let's suppose you would like to program in Javascript and DHTML. Then you will be happy to sign up for CSC 401, the practicum associated with 517. If you do, then you will be happy to learn that it will be using javascript and DHTML, you will get one unit of credit, and studies show that you will learn the material more effectively. Those not enrolled in 401 will most probably not have programming.
• Content: for an idea of the course's contents, you can follow this web page, as it develops. Also last year's version is CSC517.091 and previous years can be found back to 2001.
• Grading: There are homeworks, one or two midterms, and a final. It is very important to do the homeworks!
• Grader: is Sourav Jana, sourav at cs.miami.edu.
• Twitter is: twitter/csc_517. For the courtsey of people who follow with SMS enabled, I will keep this very low traffic.
• Midterm: Wed 28 Oct.
  • A sample midterm: Here.
  • There might be a bit more on the math this year:
  • more about Big-Oh (perhaps finding a c and x_o),
  • recurrence equations (showing by substitution a result).
• Midterm histogram
• Homework statistics
• Fri, Dec 4 is the last day of class.
• Final is scheduled for Monday, Dec 14, 11:00-1:30.

Class notes

• Introduction
  • Machine models, solvability, correctness, efficiency.
  • Sorting a hand of cards, sorting a deck of cards..
• Tools of the Trade
  • Solvability: Pseudocode,
  • Correctness: Loop Invariants
  • Example of Loop Invariants: Findmin
  • Efficiency: Big-Oh notation
• The Sorting Zoo
  • Selection Sort (java applet)
  • Insertion Sort
  • Merge Sort
    • Cheaper by Half
  • Heapsort
  • Quicksort
    • Partition algorithm (animation)
• Making and breaking lower bounds
  • Lower bound on sort in the decision tree model
  • Counting sort (animation)
  • Radix sort
  • Bucket sort
• Recurrence Equations
  • Substitution Method, Tree Method, Master Method
  • Sorting algorithms, again.
  • Selection in Random Linear Time
  • Median Find in Deterministic Linear Time
• Probability and Probabilistic Analysis
  • Probability spaces and axioms, see notes.
  • Random variables and expectation
  • Conditional probability, independence, and Bayes
  • Hiring problem (number of maxima)
  • Generating a random permutation.
• 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
  • Splay trees, an applet
  • Augmenting data structures
• Algorithmic Paradigms
  • Dynamic Programming
  • recurrences and dynamic programming
  • Greedy Algorithms
  • Linear Programming
• Graph Algorithms
  • Breadth First Search
  • Depth First Search
  • Topological Sorting
  • Strongly Connected Components

Assignments

• Problem Set 1; due Monday, Sep 14.
  • Read chapters 1 and 2.
  • See attached problems
• Problem Set 2; due Monday, Sep 21.
  • Read chapters 3, 6 and 7.
  • Read class notes on Big-Oh
  • Exercises 6.1-1, 6.1-2, 6.1-7.
  • 6.2-1, 6.2-3, 6.2-4, 6.2-5.
  • 6.3-1, 6.3-2.
  • 6.4-2, 6.4-3, 6.4-4.
• Problem Set 3: due Wednesday, Sep 30 (new date)
  • Read chapters 4, 8 and 9.
  • 7.3-1, 7.3-2, 7-1, 7-4, 7-5.
  • 8.2-1, 8.2-2, 8.2-3, 8.2-4.
  • 8.3-1, 8.3-2, 8.3-4.
• Problem Set 4: due Wednesday, Oct 7 (note extended deadline)
  • Either: (third edition) 4.3-2, 4.3-3, 4.3-6; 4.4-1, 4.4-6, 4.4-7; 4.5-1.
  • Or: (second edition) 4.1-1, 4.1-2, 4.1-5; 4.2-1, 4.2-2, 4.2-3; 4.3-1.
  • And: Problem 4-1 (both editions, although the problems differ slightly).
• Problem Set 5: due Monday, Oct 12.
  • Read chapter 5.
  • Exercises 5.2-1, 5.2-2, 5.2-3, 5.2-4, 5.2-5;
  • Problem 5-1.
• Problem Set 6: due Monday, Oct 19.
  • Read chapters 10 and 11.
  • Exercises 10.2-1, 10.2-2, 10.2-3, 10.2-4 and 10.2-7;
  • Problem 10-1;
  • Exercises 11.3-1, 11.3-2, 11.3-3, and 11.3-4.
• Problem Set 7: due Monday, Oct 26.
  • Exercises 11.1-1, 11.1-2.
  • Exercises 11.2-1, 11.2-2.
  • Exercises 11.4-1, 11.4-2, 11.4-3 (3-ird edition) or 11.4-4 (2-nd edition).
  • Problem 11-4 (somewhat difficult, but interesting).
• Problem Set 8: due Monday, Nov 9
  • 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;
  • Problems 12-1 and 12-2.
• Problem Set 9: due Monday, Nov 23.
  • Exercises 13.3-2, 13.3-3, 13.4-3;
  • Problems 13-1, 13-2;
  • Exercises 14.1-1, 14.1-2, 14.1-3, 14.2-1, 14.3-1.
• Problem Set 10: due Monday, Nov 30.
  • In Third Edition:
    • Exercises 15.5-1, 15.5-2 15.5-3;
    • Problems 15-1, 15-4, 15-6, 15-7;
    • Exercises 16.2-2, 16.2-3, 16-2.4;
    • Exercises 16.3-2, 16.3-3, 16.3-6;
    • Problems 16-1, 16-4.
  • Or in Second Edition:
    • Exercises 15.5-1, 15.5-2, 15.5-3;
    • Problems 15-2, 15-4, 15-5, 15-6,
    • Exercises 16.2-2, 16.2-3, 16-2.4;
    • Exercises 16.3-1, 16.3-2, 16.3-5;
    • Problems 16-1, 16-4.
• Problem Set 11: due Friday, Dec 4.
  • In Third Edition:
    • Exercises 22.2-1, 22.2-2, 22.2-4, 22.2-7, 22.2-9;
    • Exercises 22.3-1, 22.3-2, 22.3-3, 22.3-5, 22.3-12.
  • Or in Second Edition:
    • Exercises 22.2-1, 22.2-2, 22.2-3, 22.2-6, 22.2-8;
    • Exercises 22.3-1, 22.3-2, 22.3-3, 22.3-4, 22.3-11.
  No late homeworks accepted after Dec 11

Practicum

• Project 1: due Wed, Sep 30.
  • 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 7.
  • Write one of the n log n sorting routines in JavaScript. The starting point is webpage on insertion sort.
• Project 3: due Wed, Oct 21.
  • See RANDOMIZE-IN-PLACE algorithm in chapter 5.3, page 103 on the second 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 4.
  • 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, Dec 2.
  • A dynamic programming algorithm of your choice, e.g. the five in the book (counting both 2-nd and 3-ird editions). I would like you to provide a nice visual, but I understand that DHTML can be a bit awkward. Tables are not too bad; I have examples of dynamically generated tables, using document.getElement().innerHTML in the body onload method.

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
• Deletion in hash tables.
• Cuckoo Hashing
• Bloom Filter (Supplemental topic)

Typography

• Set in Futura font on Macs. Futura is not a font for the web, because it features low readability. However it's nice, and it is now involved in a scandal involving Ikea. (See page in Ikea's new choice, Verdana.)
• Set in Trebuchet MS on Microsoft. (On Firefox/OSX, see page in Trebuchet MS.)