CSE 5311

Documents

• Summer 2004 Syllabus PDF, doc
• Notes 1 - Mathematical Preliminaries PDF, doc (updated 05/29/04)
• Notes 2 - Binary Search Trees PDF, doc (reviewed 05/22/04)
• Notes 3 - Amortized Analysis PDF, doc (reviewed 05/22/04)
• Notes 4 - Self-Organizing Linear Search PDF, doc (updated 05/22/04)
• Notes 5 - Trees and Notes 6 - Skip Lists PDF, doc (updated 06/08/04)
• Notes 7 - Priority Queues PDF, doc (updated 06/12/04)
• Notes 8 - Disjoint Sets and Notes 9 - Hashing PDF, doc (update 06/18/04)
• Notes 10 - Medians/Selection and Notes 11 - Minimum Spanning Trees PDF, doc
• Notes 12 - Network Flows PDF, doc
• Notes 13 - Depth-First Search PDF, doc
• Notes 14 - Stable Marriages PDF, doc
• Notes 15 - Sequences PDF, doc
• Notes 16 - Matrices and Notes 17 - Computational Geometry PDF, doc
• Notes 18 - NP-Completeness PDF, doc

Handouts

• desJardins: How to Be a Good Graduate Student/Advisor
• Towards a Discipline of Experimental Algorithmics
• A Theoretician's Guide to the Experimental Analysis of Algorithms
• PDF of Homework 1 ( answers )
• PDF of Homework 2 ( answers )
• PDF of 1998 exams
• PDF of 1999 exams
• PDF of 2002 exams
• PDF of Spring 2003 exams
• PDF of Summer 2003 exams
• Spring 2004 exams PDF, doc
• Link to Randomized Search Tree (Treap) Paper
• PDF of Move-to-front (MTF) to Optimal Off-line (OPT) Handout
• PDF of Albers & Westbrook - Self-Organizing Data Structures
• Link to ACM Digital Library for PDF of Hester & Hirschberg Self-Organizing Linear Search Paper
• Link to ACM Digital Library for PDF of Rivest Self-Organizing Sequential Search Paper
• PDF of Optimal Binary Search Tree Slides
• PDF of Splay Tree Slides
• Link to ACM Digital Library for PDF of Sleator & Tarjan Splay Tree Paper
• Link to ACM Digital Library for PDF of Fredman & Tarjan Fibonacci Heap Paper
• Link to ACM Digital Library for PDF of Pugh's Skip List paper
• Link to ACM Digital Library for PDF of Tarjan & van Leeuwen Analysis of Set Union Algorithms
• Link to ACM Digital Library for PDF of Brent's Rehash Paper
• An Empirical Assessment of Algorithms for Constructing a MST
• Link to ACM Digital Library for PDF of Rivest's Optimal Hash Arrangement Paper
• Link to ACM Digital Library for PDF of Fredman, Komlos, Szemeredi Perfect Hashing Paper
• Local Copy of Mark Nelson's Dr. Dobb's Suffix Tree Article
• PDF of Theoretical Computer Science Cheat Sheet

Programming Assignments

• Programming Assignment 1 PDF, doc

Code

• AVL Tree Code in C
• Another Version of AVL Tree Code in C
• Optimal Binary Search Tree in C - Lecture (Knuth) Version
• Optimal Binary Search Tree in C - CLRS Version
• Skip Lists in C
• Splay Tree Code in C
• Offline LCA using union-find trees code, input, diagram
• Brent's Rehash in C
• Hungarian algorithm for assignment problem in C
• Minimum Spanning Tree Using Warshall-Like Algorithm
• Kruskal's MST
• Kruskal's MST with detection of non-unique MST
• Boruvka's MST
• Ford-Fulkerson with adjacency matrix
• Ford-Fulkerson with adjacency lists
• Elementary FIFO Preflow-push Algorithm for Network Flows
• Elem. FIFO Preflow-push Alg. with Saturated/Unsaturated edges Separated (description) (input file)
• Input File for Network Flows
• Biconnected components using DFS (other DFS code)
• Stable Marriages Code
• Sedgewick's Stable Marriages Example
• Gusfield and Irving's Page 12 Stable Marriages Example
• Stable Roommates Code
• Stable roommates instance with n=4 and no solution
• Stable roommates instance with n=4 and a solution
• Stable roommates instance with n=10
• Code for Gusfield's fundamental string preprocessing - 3 examples from lecture
• Code for Gusfield's fundamental string preprocessing - applications
• Code for KMP string search
• Code for KMP string overlaps (includes both fail link techniques)
• Code for Karp-Rabin string search
• Suffix array example
• Suffix array construction
• Input to suffix array construction
• Linear space algorithm for longest common subsequence (description)
• Longest increasiing subsequences monotone, strict
• Code for closest points on a line
• Code for closest points in a plane
• Code for random points in a plane
• Dynamic programming code for subset sum problem

Links

• Combinatorial Generation
• Algorithm Courses
• Minnesota Graph Partitioning
• Electronic Colloquium on Computational Complexity
• AT&T Graph Visualization
• National Resident Matching Program (NRMP)
• National Matching Services Inc.
• LEDA - Library of Efficient Datatypes and Algorithms
• IBM Research
• DIMACS - Center for Discrete Mathematics & Theoretical CS
• Stony Brook Algorithm Repository
• Red-Black Tree Applet
• Applet for Fortune's Sweep-line Voronoi Diagram Construction
• VoroGlide - Fun Voronoi Applet - Try Dragging Around a Point!