CSE 5311

Office Hours

Notes

• Spring 2022 Syllabus PDF, doc
• Notes 0 - Review of Dynamic Programming PDF, doc (reviewed 01/15/18)
• Notes 1 - Mathematical Preliminaries PDF, doc (updated 01/20/18)
• Notes 2 - Binary Search Trees PDF, doc (reviewed 01/26/18, .doc has problems)
• Notes 3 - Amortized Analysis PDF, doc (reviewed 02/02/18)
• Notes 4a - Priority Queues PDF, doc (updated 01/12/21)
• Notes 4b - vEB Trees PDF, doc (reviewed 09/14/16, not in current use)
• Notes 5 - Hashing PDF, doc (updated 02/12/21)
• Notes 6 - Medians/Selection PDF, doc (reviewed 02/18/18)
• Notes 7 - Disjoint Sets PDF, doc (reviewed 02/21/18)
• Notes 8 - Minimum Spanning Trees PDF, doc (reviewed 02/25/18)
• Notes 9 - Maximum Flows PDF, doc (reviewed 02/28/18)
• Notes 10 - Matching Under Preferences PDF, doc (updated 01/12/21)
• Notes 11 - Intractability PDF, doc (reviewed 03/26/18)
• Notes 11 - Reduction Exercises PDF
• Notes 12 - Matrices PDF, doc (reviewed 04/11/18)
• Notes 13 - Computational Geometry PDF, doc (reviewed 04/23/18)
• Notes 14 - Sequences PDF, doc (reviewed 04/09/18)

Programming Assignments

• Lab 1
• Lab 2
• Lab 3

Handouts

• Homework 1 PDF, doc ( answers )
• Homework 2 PDF, doc ( answers )
• Some exam answer keys
• 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
• Summer 2014 exams PDF, doc
• Guibas & Sedgewick - A Dichromatic Framework for Balanced Trees
• 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
• Optimal Binary Search Tree in C - Lecture (Knuth) Version
• Optimal Binary Search Tree in C - CLRS Version
• Markov analysis of move-to-front and transpose for lists (soList.c) (description)
• Splay Tree Code in C
• van Emde Boas Trees Code and Test Problems
• Offline LCA using union-find trees code, input, diagram
• Brent's Rehash in C
• Code for comparing Brent's Rehash, Binary Tree Hashing, and Perfect Hashing
• Code for Bloom Filter
• 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
• MST Examples using Answer Set Programming
• 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
• Network Flow Examples using Answer Set Programming
• 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
• Can you find the 5 matchings for this stable roommates instance?
• Preference Matching Examples using Answer Set Programming
• 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
• 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
• JavaScript for Jarvis March
• 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
• 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
• Smallest Enclosing Disc
• DT/Voronoi Diagram/EMST in JavaScript
• Fortune's Sweepline Voronoi