CSE 5311

Documents

• Preliminary Summer 2012 Syllabus PDF, doc
• email archive
• Notes 1 - Mathematical Preliminaries PDF, doc (updated 06/03/12)
• Notes 2 - Binary Search Trees PDF, doc (updated 06/03/12)
• Notes 3 - Amortized Analysis PDF, doc (updated 06/14/12)
• Notes 4 - Self-Organizing Linear Search PDF, doc (reviewed 06/14/12)
• Notes 5 - Trees and Notes 6 - Skip Lists PDF, doc (reviewed 06/18/12)
• Notes 7a - Priority Queues PDF, doc (reviewed 06/26/12)
• Notes 7b - Priority Queues - vEB Trees PDF, doc (reviewed 06/26/12)
• Notes 8 - Disjoint Sets PDF, doc (reviewed 06/28/12)
• Notes 9 - Hashing PDF, doc (updated 07/07/12)
• Notes 10 - Medians/Selection and Notes 11 - Minimum Spanning Trees PDF, doc (reviewed 07/07/12)
• Notes 12 - Network Flows PDF, doc (reviewed 07/12/12)
• Notes 13 - Depth-First Search PDF, doc (reviewed 07/09/06, WILL NOT COVER)
• Notes 14 - Stable Marriages PDF, doc (reviewed 08/07/05, WILL NOT COVER)
• Notes 15 - Sequences PDF, doc (reviewed 07/26/12)
• Notes 16 - Matrices PDF, doc (reviewed 07/26/12)
• Notes 17 - Computational Geometry PDF, doc (reviewed 07/26/12)
• Notes 18 - NP-Completeness PDF, doc (reviewed 07/22/12)

Programming Assignments

• Lab 1 PDF, doc
• Lab 2 PDF, doc, lab2sum12.a.dat, lab2sum12.a.out, lab2sum12.b.dat, lab2sum12.b.out, lab2sum12.c.dat, lab2sum12.c.out
• Lab 3

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
• Homework 1 PDF, doc ( answers )
• Homework 2 PDF, doc ( 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
• Summer 2004 exams PDF, doc
• Summer 2005 exams PDF, doc
• Summer 2006 exams PDF, doc
• Summer 2007 exams PDF, doc
• Summer 2008 exams PDF, doc
• Summer 2009 exams PDF, doc
• Summer 2010 exams PDF, doc
• Summer 2011 exams PDF, doc
• Summer 2012 exams PDF, doc
• Link to Randomized Search Tree (Treap) Paper
• 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
• Sleator & Tarjan, Amortized Efficiency Of List Update and Paging Rules
• 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

Code

• AVL Tree Code in C
• Another Version of AVL Tree Code in C
• Markov analysis of move-to-front and transpose for lists (soList.c) (description)
• 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
• van Emde Boas Trees real.book.c, real.driver.c
• Offline LCA using union-find trees code, input, diagram
• Brent's Rehash in C
• Floyd-Warshall based algorithm for assignment problem in C ( hungarian0.dat, hungarian1.dat, hungarian2.dat, hungarian3.dat, hungarian4.dat)
• 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, Simple example, Significant example, Vertex 0 is not an articulation point, Vertex 0 is an articulation point (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
• "Countdown" code for Gusfield's fundamental string preprocessing (Gusfield's course)
• Code for KMP string search
• Code for KMP string overlaps (includes both fail link techniques)
• Code for Karp-Rabin string search
• Suffix array example
• Manber/Myer's RadixSort Suffix array construction
• Input to suffix array construction
• LCP based manipulations for suffix arrays - LCPdemo.c
• Linear space algorithm for longest common subsequence (description)
• Longest increasing subsequences monotone, strict
• Boolean matmult using Kronrod's algorithm - kronrodChar5311.c
• Code for closest points on a line
• Code for closest points in a plane
• Code for random points in a plane
• Code for vertex coloring
• Code for edge coloring
• Dynamic programming code for subset sum problem

Links

• Hungarian Method Applet
• Combinatorial Generation
• Algorithm Courses
• Fibonacci Heap Applet
• 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!