The MIT Tinker-toy computer

• Final Exam: Monday 15 Dec, 8:00 to 10:30 am.
• Problem Set 12 posted, due Mon Dec 8

News and Announcements for CSC317

Dec 7:

The final will be in MM 203, Monday 15 Dec, 8:00 to 10:30 am.

Dec 3:

Problem Set 12 posted, due Mon Dec 8.

Nov 20:

Problem Set 11 posted, due Wed Nov 26 Dec 3.

Nov 12:

Problem Set 10 posted, due Wed Nov 19.

Nov 5:

Practicum project 3 posted, due Dec 9.

Nov 5:

Problem Set 9 posted, due Wed Nov 12.

Oct 29:

Problem Set 8 posted, due Wed Nov 5.

Oct 22:

Problem Set 7 posted, due Wed Oct 29.

Oct 20:

Practicum project 2 announced: double hashing.

Oct 19:

Midterm Histogram

Oct 8:

Sample Midterm

Oct 1:

Midterm is Monday, Oct 13-th

August 25:

Welcome! Don't forget to follow twitter/csc_517
Like us on Facebook!
First day of class.

This is a course on algorithmic thinking. You will learn how to think about problems from the point of view of machine procedures to solve the problem. You will be given techniques to break a problem down, to notice its combinatorial difficulties, to reason about correctness, and to measure the efficiency of a solution. You will learn how to recognized the inherent complexity of a problem – the best possible efficiency that a problem can be solved.

The course does not require programing. The course is more about thinking about code, than writing code. However, the Practicum does Javascript programming and dynamic HTML to create creative animations of the algorithms presented in the course. The Practicum is self-study, and highly recommended. In the practicum you will learn the basis of in-browser programming, and exercise your coding skills for algorithms.

Notes of 151 edition of 317: This semester the course number was changed from 517 to 317. There was no change in level or emphasis. The numbering change was entirely clerical.

However, I did make some major changes to the course for this semester:

• A lecture on complexity was added early in the course, covering the lower complexity classes, linear, etc., with an intuitive appreciation, up through BPP and NP.
• The order of hashing, trees and sorting was changed. Hashing and sorting were made separate top-bullet points, and hashing was moved forward to before sorting.
• The topic of hashing was more fully covered, including universal and perfect hashing.
• Trees, red-black trees and union-find were put under the same topic, and splay trees were re-introduced as a warm-up towards red-black trees, as well as an important example of amortized complexity (just mentioned, not studied) and "simple" adaptive data structures.
• Graph algorithms was moved forward before algorithmic paradigms, to give them more emphasis.
• A lecture on graph theory was tested, to see if it adds interesting context to the theory of graphs.

General

• The textbook is Introduction to Algorithms (3ird edition), Cormen, Leiserson, Rivest and Stein.
• Please follow us on twitter/csc_517.
• The course assigns weekly problem sets, due on Wednesdays. It is very important to do the homeworks.
• Our grader is Parul Maheshwari, p.maheshwari@umiami.edu.
• No late homeworks accepted after the last day of classes.
• Midterm: Monday, 13 October, 2014.
• Sample Midterm
• Midterm Histogram
• The final will be in MM 203, Monday 15 Dec, 8:00 to 10:30 am.
• Grades are 40% final, 30% midterm, and 30% homework.

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 401-01.

Writing Credit

Three essays, each at least 1500 words.

• 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.
• 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.

Please write me with your proposed topics, if you elect writing credit. One paper must be done before the midterm, and the other two before reading days.

Class notes

• Introduction
  • Solvability, correctness, efficiency.
  • Sorting a hand of cards, sorting a deck of cards..
  • Cheaper by Half
  • Complexity Petting Zoo
• Correctness
  • Assertions
  • Example of Loop Invariants: Findmin
  • Example of Loop Invariants: Partition
• Big-Oh notation and Recurrence Equations
  • Big-Oh theory.
  • Recurrence relations.
  • Tree method
  • Substitution Method, Tree Method, Master Method
  • Examples
• 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
• Hashing
  • Elementary data structures (review)
  • O(1) access, encoding, hash function.
  • Uniform hashing assumption, blackbox hash functions.
  • Collision resolution.
  • Linear Probing (animation), double hashing.
  • Universal Hashing, Perfect Hashing
  • Hashing performance curves
  • Hashing workshop 2014
• Sorting
  • Lower bound on sort in the decision tree model
  • O(n²) sorts:
    • Selection Sort (java applet)
    • Insertion Sort (javascript)
  • O(n log n) sorts:
    • Merge Sort
    • Heapsort (code)
    • Quicksort (code)
  • Linear sorts
    • Counting sort (animation)
    • Radix sort
    • Bucket sort
• Trees
  • Binary Search Tree (my animation) (a really beautiful animation)
  • Splay trees (PDF) (animation)
  • Self balancing trees
    • Red-Black Trees
    • Red Black animation
  • Union-Find
• Graph Algorithms
  • Introduction to graph theory
  • Breadth First Search
  • Depth First Search algorithm
  • Topological Sorting
  • Strongly Connected Components
  • Mininum Spanning Tree
    • Kruskal
    • Prim
  • Single Source Shortest Paths
    • Bellman-Ford
    • via Topological sorting
    • Dijkstra
• Hashing reprise
  • Bloom Filters
• Algorithmic Paradigms
  • Dynamic Programming
    • recurrences and dynamic programming
    • Optimal binary search trees
    • Longest common subsequence
  • Greedy Algorithms
    • Huffman codes
  • Linear Programming

• Problem Set 1: Due Wed Sept 3.
  • Read chapters 1 and 2
  • Do exercises 1.1-3., 1.1-4, 1.1-5, 1.2-2 and 1.2-3.
  • Do exercises 2.1-2 and 2.1-3.
• Problem Set 2: Due Wed Sept 10.
  • Problem 1-1.
  • Problem 2.1-4, 2.2-2, 2.2-3, 2.2-4.
  • (food for thought, due in two weeks ... ) Problem 2.3-7.
• Problem Set 3: Due Wed Sept 17.
  • Problem 2.2-1, 2.3-1, 2.3-2.
  • Write loop invariants for this partition algorithm.
  • Problems 2-2 and 2-3.
  • Problem 2.3-7.
  • Food for thought, due in two weeks: Problem 2-4.
• Problem Set 4: Due Wed Sept 24.
  • Show that if g=O(f), and h=O(g), then h=O(f). (Prove this.)
  • 4.3-1, 4.3-2, 4.3-3, 4.3-6, 4.3-7, 4.3-8.
  • Problem 2-4.
  • Food for thought, due in two weeks: Problem 4-4.
• Problem Set 5: Due Wed Oct 1. (originally Oct 2 by accident)
  • Problems 4.5-1, 4.5-3, 4-1 and 4-3.
  • Problem 4-4.
  • Food for thought, due in two weeks: Problem 5.2-5.
• Problem Set 6: Due Wed Oct 8.
  • Problems 5.2-1, 5.2-2, 5.2-3.
  • Problems 9.2-3, 9.2-4, 9.3-1, 9.3-2, 9.3-6.
  • Food for thought, due in two weeks: Problem 9.1-1.
  • Problem 5.2-5
• No Problem Set week ending Oct 15.
• Problem Set 7: Due Wed Oct 29.
  • Problem 6-2.
  • Exercises 8.2-1, 8.2-4, 8.3-2, 8.3-4.
  • Exercise 11.4-2.
  • Exercise 9.1-1.
  • For for thought, due in two weeks:
    • Show by substitution method the the exact solution for the recurrence:
         T(n)=T(n-3)+n, n ≥ 3,
      with initial conditions T(0)=0, T(1)=1, T(2) = 2.
    • Solve first for the case of n being a multiple of 3.
    • Hint: We argued in class that the solution should have leading term n²/6.
    • Try n²/6 + a n + b. Remember, this should be an exact solution.
• Problem Set 8: Due Wed Nov 5.
  • Exercises 12.2-3, 12.2-5, and 12.2-6.
  • Problems 12-1 and 12-2.
  • Exercises 13.2-1, 13.2-3, and 13.2-4.
  • Show by substitution method the the exact solution for the recurrence:
       T(n)=T(n-3)+n, n ≥ 3,
    with initial conditions T(0)=0, T(1)=1, T(2) = 2.
    See last week for details.
  • Food for thought, due in two weeks: Problem 13-1.
• Problem Set 9: Due Wed Nov 12.
  • Exercises 21.3-1 and 21.3-2.
  • Exercises 22.2-2 and 22.2-7.
  • Exercises 22.3-2 and 22.3-3.
  • Exercises 22.4-2 and 22.4-3.
  • Problem 22-1.
  • Problem 13-1.
  • Food for thought, due in two weeks: Problem 22-3.
• Problem Set 10: Due Wed Nov 19.
  • Exercises 22.5-2 and 22.4-5.
  • Problem 22-3 and 22-4.
  • Exercises 23.1-1, 23.1-3 and 23.2-1.
  • Exercises 24.1-1 and 24.2-1.
  • Food for thought, due in two weeks: Problem 24-3.
• Problem Set 11: Due Wed Dec 3.
  • Exercise 15.1-3.
  • Exercises 15.5-2 and 15.5-3.
  • Problem 24-3.
  • Food for thought, due in two weeks: Problem 15-1.
• Problem Set 12: Due Mon Dec 8.
  • Exercises 16.2-4, 16.2-5, 16.3-2, 16-3.3.
  • Problem 15-1.

CSC401 is the practicum associated with CSC317.

Please see the home page of the the csc401 zinc server for more information.

CSC517 is a course on algorithmic thinking. The CSC517 mainline in the course does not require programming. It is highly recommended that students enroll in CSC401 the Practicum, for experience coding algorithms, and for the experience of using dynamic HTML and Javascript to create imaginative animations of the algorithms presented in the course.

• Preliminaries:
  • Install the private key in your .ssh directory and login into the zinc server.
  • Learn to either scp or edit right onto the zinc server, your public_html directory.
  • First, arrange your index.html to make a home page for the practicum that will link to the projects.
  • Then begin the first project.
• Project 1: Do an algorithm animation of either insertion sort or selection sort.
  • See Partition Algorithm Animation as an example.
  • Due Wednesday, October 22nd.
• Project 2: Do an algorithm animation of double hashing.
  • See my linear probing animation.
  • Have the table size be 16. A table size of perfect power of 2 (2, 4, 8, 16, etc) makes the mod easy, because it can be a simple bit mask, x % 16 == x & ~(0x0f).
  • Make the secondary hash function 2(x%4)+1. This gives 4 different skip values, independent of the value of x%16, and all relatively prime to the table size.
  • Show somehow the collisions and skips, to demonstrate how double hashing works.
  • For extra credit: sample the average unsuccessful search time. Do this by simulating the 64 unsuccessful searches of an x such that (x%16,x%4) is each of the 64 different values (0,0), (0,1), (0,2), (0,3), (1,0), (1,1), etc., then dividing the total probes over all 64 searches by 64.
  • Due Wednesday, November 12th.
• Project 3: Bloom filter.
  • Watch Prof. Mitzenmacher's workshop presentation on Bloom filters.
  • Write a page which implements a Bloom filter. For the k hash functions, choose them at random from the universal family described on CLR page 267 —
    h_ab(x) = ((ax+b) mod p) mod m)
  • As an implementation idea: make a series of cells. As a hash is made, set the cells to orange, but turn them to all green before laying in the next hash (so the current hash can be seen as well as the accumulation of hashes).
  • Due Tuesday, December 9th.

Some references:

• Annotated DHTML
• Annotated DHTML as source
• Web Commerce course
• Five Easy Pieces

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 Filters and Cuckoo Hashing.