The MIT Tinker-toy computer

• Practicum 3 and Writing Assignments due.
• Final on Monday, Dec 16, 2:00 to 4:30.
• Problem set 11 posted, due Dec 9.

News and Announcements for CSC517.

Dec 7

Final on Monday, Dec 16, 2:00 to 4:30.

Dec 3

Practicum and Writing Assignments: submit for final grade.
Problem set 11 posted, due Dec 9.

Nov 15

Problem set 10 posted, due Nov 20.
Practicum Project 3 posted, due Dec 3

Nov 7

Problem set 9 posted, due Nov 13.

Oct 30

Problem set 8 posted, due Nov 6.

Oct 27

Practicum Project 2 posted.

Sample midterm

Sample Midterm
Histogram

Midterm!

October 23.

Sept 18:

Problem set 4 posted.
csc401 web server up for practicum students.

August 28:

Problem set 1 posted.
Syllabus updated, info on writing credit, corrected dates.

August 22:

Welcome! Don't forget to follow twitter/csc_517
Like us on Facebook!

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.

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. Please direct questions on grading first to the grader Joe Masterjohn.
• Our grader is Joe Masterjohn, j.masterjohn@umiami.edu; office Ungar 406, 9am – 11am Wednesdays.
• No late homeworks accepted after the last day of classes, Tuesday, Dec 10.
• Midterm Wednesday October 23.
• The final will be in class at 2:00 – 4:30 pm on Wed Dec 16.
• 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 403.

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

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
• Tools of the Trade
  • Solvability: Pseudocode.
  • Correctness: Loop Invariants
  • Example of Loop Invariants: Findmin
• Examples (textbook, Problems 2-3 and 2-4)
  • Evaluating a polynomial.
    • Operation count and repeated squaring
    • Induction proof (Loop Invariants) and Horner's Method
  • Inversion numbers and insertion sort
    • Input dependence, worst and average case times.
• Recurrence Equations
  • Cheaper by Half revisited — n log n as fixed point.
  • Tree method
  • Recurrence relations.
• Big-Oh notation.
  • Big-Oh theory.
  • Substitution Method, Tree Method, Master Method
  • Max subarray problem and Strassen multiplication (integer and matrix)
• Machine models, and algorithmic thinking.
• 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

• Problem Set 1: Due Wed Sept 4.
  • 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-1, 2.1-2, and 2.1-3.
• Problem Set 2: Due Wed Sept 11.
  • Exercises 2.2-1, 2.2-2 and 2.2-4.
  • Exercises 2.3-1, 2.3-2 and 2.3-3.
  • Do Problem 2-2.
• Problem Set 3: Due Wed Sept 18.
  • Read chapter 3.
  • Exercise 3.2-1.
  • Problems 3-1 and 3-2.
  • Prove: If g₁=O(f₁), and g₂=O(f₂), then g₁ g₂ = O(f₁ f₂).
• Problem Set 4: Due Wed Sept 25.
  • Redo problem 3-2, now that we have worked many of these in class.
  • Problems 3-3 and 3-4.
  • Read section 4.1.
  • Exercises 4.1-1 and 4.1-2.
• Problem Set 5: Due Wed Oct 2.
  • Exercises 4.2-1 and 4.2-7.
• Problem Set 6: Due Wed Oct 9.
  • Exercises 4.3-1, 4.3-2, 4.3-6 and 4.3-7.
  • Exercises 4.4-1, 4.4-2, 4.4-3 and 4.4-4.
  • Exercise 4.5-1.
• Problem Set 7: Due Wed Oct 16.
  • Problem 4-3.
  • Exercises 5.2-1, 5.2-2, 5.2-3, 5.2-4 and 5.2-5.
• Problem Set 8: Due Wed Nov 6.
  • Exercises 9.1-1, 9.1-2, 9.2-1, 9.2-3, 9.3-1, 9.3-2, 9.3-3.
  • Problem 9-1.
• Problem Set 9: Due Wed Nov 13.
  • Exercises 10.1-5, 10.1-6, 10.2-2, 10.2-3.
  • Problems 10-1, 10-2.
  • Exercises 11.4-1, 11.4-2, 11.4-3.
  • Problem 11-4.
• Problem Set 10: Due Wed Nov 20.
  • Problems 12-1 and 12-2.
  • Problems 13-1, 13-3 and 13-4.
• Problem Set 11: Due Mon Dec 9.
  • Exercises 15.1-2, 15.1-3, 15.5-1, 15.5-2.
  • Problem 15-2.
  • Exercises 16.2-1, 16.2-2, 16.2-3.
  • Problem 16-1.

CSC401 is the practicum associated with CSC517.

New practicum information at the csc401 zinc server.

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.

• Project 0:
  • I am working on a public web server for students to upload their projects. Use TextWrangler on mac, or jEdit of Windows to sftp edit the files on the server. You will be given a private key, instead of a password.
  • I am getting together more specific information, but please refer to previous courses I have offered in Javascript and DHTML:
    • Five Easy Pieces (In development)
    • Web Commerce (offered Summer 1, 2007)
    • Annotated DHTML
    • Annotated DHTML as source
  • Make a web page using Javascript that converts teaspoons to gils.
  • Due Monday, September 30.
• Project 1:
  • Do an algorithm animation of insertion sort; see Partition Algorithm Animation as an example.
  • or ... See Exercise 4.1-3 and implement and animate the recursive FIND-MAXIMUM-SUBARRAY algorithm.
  • Due Monday, October 14.
• Project 2:
  • Do an algorithm animation for randomized selection, as described in our the midterm, and in the textbook, section 9.2.
  • Due Monday, November 11.
• Project 3:
  • Program a red-black tree for insert and delete.
  • Visualizing a tree: in order to keep this simple, use a text visualization. One of my favorites is a pre-order traversal where an indentation amount is collected. Write the node at that indentation then recursively do first the left then the right sub-tree, both advanced to the net indentation level.
  • Due Monday, December 2.
• Submit everything for final grading. Done with the semester!

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)