CSE 5311

CSE 5311 students - Please submit email survey to spal@uta.edu by June 9.

Documents

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

Programming Assignments

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
• Summer 2004 exams PDF, doc
• Summer 2005 exams PDF, doc
• Summer 2006 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 (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
• 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
• 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 increasing subsequences monotone, strict
• Code for closest points on a line
• Code for closest points in a plane
• Code for random points in a plane
• Code for edge coloring
• Dynamic programming code for subset sum problem

Links

• Hungarian Method Applet
• 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!