CSE 2320

Documents

• Fall 2008 Syllabus PDF, doc
• email archive
• Notes 1 - Algorithmic Concepts PDF, doc (updated 08/18/08)
• Notes 2 - Growth of Functions PDF, doc (updated 08/20/08)
• Notes 3 - Summations PDF, doc (updated 08/22/08)
• Notes 4 - Recurrences PDF, doc (updated 08/27/08)
• Notes 5 - Heaps and Priority Queues PDF, doc (updated 01/26/08)
• Notes 6 - Greedy Algorithms PDF, doc (updated 02/04/08)
• Notes 7 - Dynamic Programming PDF, doc (updated 02/08/08)
• Notes 8 - Sorting PDF, doc (reviewed 02/18/08)
• Notes 9 - Linked Lists PDF, doc (updated 02/25/08)
• Notes 10 - Stacks & Queues PDF, doc (updated 03/03/08)
• Notes 11 - Rooted Trees PDF, doc (updated 03/08/08)
• Notes 12 - Red-Black Trees PDF, doc (updated 03/18/08)
• Notes 13 - Hashing PDF, doc (updated 03/25/08)
• Notes 14 - Graph Representations and Search PDF, doc (updated 04/02/08)
• Notes 15 - Minimum Spanning Trees PDF, doc (updated 04/13/08)
• Notes 16 - Shortest Paths PDF, doc (updated 04/14/08)
• Notes 17 - Network Flows and Bipartite Matching PDF, doc (updated 04/19/08)
• HW - Notes 1 through 4 PDF, doc, answers
• HW - Notes 5 through 7 PDF, doc
• HW - Notes 8 through 10 PDF, doc
• HW - Notes 11 through 13 PDF, doc
• HW - Notes 14 through 15 PDF, doc
• HW - Notes 16 through 17 PDF, doc
• HW - Notes 1 through 7 Answers PDF, zip
• HW - Notes 8 through 13 Answers PDF, zip
• HW - Notes 14 through 17 Answers PDF, zip
• PDF of old HW 1
• Old HW 1 answers PDF, doc (updated 08/20/04)
• PDF of old HW 2
• Old HW 2 answers PDF, doc (updated 11/20/04)
• PDF of old HW 3
• Old HW 3 answers PDF, doc (updated 10/22/04)
• Summer 08 exam questions PDF, doc
• Spring 08 exam questions PDF, doc
• Fall 07 exam questions PDF, doc
• Summer 07 exam questions PDF, doc
• Spring 07 exam questions PDF, doc
• Fall 06 exam questions PDF, doc
• Summer 06 exam questions PDF, doc
• Spring 06 exam questions PDF, doc
• Fall 05 exam questions PDF, doc
• Summer 05 exam questions PDF, doc
• Fall 04 exam questions PDF, doc
• Summer 04 exam questions PDF, doc
• Fall 03 exam questions PDF, doc
• PDF of Summer 03 exam questions
• PDF of Fall 02 exam questions
• PDF of Summer 02 exam questions
• PDF of Spring 02 exam questions
• PDF of Spring 01 exam questions
• PDF of Spring 00 exam questions
• PDF of Spring 99 exam questions
• Red-Black Tree Cheat Sheet PDF, doc
• Analysis of Hashing

Programming Assignments

• Lab 1 PDF, doc, lab1fall08a.dat, lab1fall08b.dat

Code - Java

• Union-Find Trees uf.java, uf1.java, uf2.java, uf3.java, ufTest.java
• Mergesort ITEM.java, mergesort.java
• Binary Search BinarySearch.java, BinarySearchTest2.java
• Java code for min heap linked to integer table of priorities intPQi.java, intPQiTest.java
• Java code for min heap minHeap.java, heapEntry.java
• Longest Increasing Subsequence BinarySearch.java, LIS.java
• Longest Strictly Increasing Subsequence BinarySearch.java, LSIS.java
• Subset Sum subsetSum.java
• Knapsack (as described in Sedgewick) knapsackTypeRS.java
• Quicksort ITEM.java, qsortRS.java, partition.java
• Circular list Java code
• Java code for free/allocated abstraction circularFree.java, cFtest.java
• Java code for top-down red-black tree ITEM.java, KEY.java, RBtest.java, myItem.java, myKey.java, topdownRB.java
• Sedgewick depth-first search on directed graph AdjList.java, dfs.java, Edge.java, Graph.java, GraphDFS.java
• Sedgewick breadth-first search on directed graph AdjList.java, bfs.java, Edge.java, EdgeQueue.java, Graph.java, GraphBFSedge.java
• Prim's Minimum Spanning Tree; Example in Notes: prim.dat Memoryless: primMemoryless.c Table: primTable.c Heap: primHeap.java (minHeap class: minHeap.java, heapEntry.java) Sedgewick Heap: AdjList.java, Edge.java, Graph.java, GraphMST.java, MSTfile.java, doublePQi.java
• Dijkstra's Shortest Path; Example in Notes: dijkstra.dat Memoryless: dijkstraMemoryless.c Table: dijkstraTable.c Heap: dijkstraHeap.java (minHeap class: minHeap.java, heapEntry.java) Sedgewick Heap: AdjList.java, Edge.java, Graph.java, GraphSPT.java, SPTfile.java, doublePQi.java
• Network Flows even.dat, AdjList.java, Edge.java, IntQueue.java, Network.java, NetworkMaxFlow.java, intPQi.java, netflowFile.java,

Old Notes - C/C++

• Notes 1 - Algorithmic Concepts PDF, doc (updated 08/15/06)
• Notes 2 - Growth of Functions PDF, doc (updated 08/28/06)
• Notes 3 - Summations PDF, doc (updated 08/17/06)
• Notes 4 - Recurrences PDF, doc (updated 09/19/06)
• Notes 5 - Heaps and Priority Queues PDF, doc (updated 09/09/06)
• Notes 6 - Sorting PDF, doc (updated 09/16/06)
• Notes 7 - Stacks & Queues PDF, doc (updated 09/26/06)
• Notes 8 - Linked Lists PDF, doc (updated 09/29/06)
• Notes 9 - Rooted Trees PDF, doc (updated 10/02/06)
• Notes 10 - Red-Black Trees PDF, doc (updated 10/07/06)
• Notes 11 - Hashing PDF, doc (updated 10/19/06)
• Notes 12 - Graph Representations and Search PDF, doc (updated 10/22/06)
• Notes 13 - Minimum Spanning Trees PDF, doc (updated 11/01/06)
• Notes 14 - Shortest Paths PDF, doc (updated 11/06/06)
• Notes 15 - Network Flows and Bipartite Matching PDF, doc (updated 11/12/06)
• Notes 16 - Dynamic Programming PDF, doc (updated 11/20/06)
• Notes 17 - Greedy Algorithms PDF, doc (updated 11/24/06)
• Notes 18 - KMP String Search PDF, doc (updated 12/06/06)

Old Code - C/C++

• Insertion sort code
• Shellsort code (not covered)
• Mergesort code
• Binary search code
• Binary search code - for tables with duplicate keys
• Binary search code - for tables with duplicate keys (uses bsearch())
• Binary Search Example from 1/24 code, input, output
• matmult.c
• C++ code for min heap minHeap.cpp, minHeap.h
• C code to trace quicksort partitioning routine
• C code for quicksort
• A couple of examples for using qsort()
• Input to the examples for using qsort()
• Selection problem using sorting or partitioning.
• Find k largest elements using sorting or partitioning.
• Rat in a maze - Recursive: ratDFSrec.c Stack: ratDFSstack.c Queue: ratBFSqueue.c Inputs: rat9.9.dat, rat15.15.dat, rat19.19.dat, rat39.39.dat
• Circular list C code
• C++ code for free/allocated abstraction circularFree.cpp, circularFree.h, cFtest.cpp
• Miscellaneous C code from overhead slide on hashing
• Depth-first search C code (directed)
• Input to depth-first search
• PDF of diagram for input to depth-first search
• Depth-first search C code (undirected)
• Kosaraju's Strong Components Using DFS C code (directed)
• Prim's Minimum Spanning Tree; Example in Notes: prim.dat Memoryless: primMemoryless.c Table: primTable.c Heap: primHeap.cpp (minHeap class: minHeap.h, minHeap.cpp)
• Dijkstra's Shortest Path; Example in Notes: dijkstra.dat Memoryless: dijkstraMemoryless.c Table: dijkstraTable.c Heap: dijkstraHeap.cpp (minHeap class: minHeap.h, minHeap.cpp)
• Warshall's algorithm C code (path recovery using successors)
• Warshall's algorithm C code (path recovery using predecessors)
• Warshall's algorithm C code (path recovery using transitive vertex)
• Input to Warshall code
• Floyd-Warshall algorithm C code
• Input to Floyd-Warshall code
• Ford-Fulkerson C code - adjacency matrix
• Ford-Fulkerson C code - adjacency lists
• C code for optimal matrix multiply (dynamic programming)
• C code for hotel-to-airport shuttle explicit traceback, implicit traceback
• C code for weighted interval scheduling
• Input case 1 (see Notes 16) for weighted interval scheduling
• Input case 2 for weighted interval scheduling
• Input case 3 for weighted interval scheduling
• C code for longest common subsequence (dynamic programming)
• C code for unit-time scheduling (greedy)
• Unit-time scheduling input 1
• Unit-time scheduling input 2
• C code for KMP string search

Links

• Sedgewick's Java Code for Parts 1-4
• Sedgewick's Java Code for Part 5
• Java Sorting Animation Page
• Example 1 of enumerating the red-black colorings for a tree
• Example 2 of enumerating the red-black colorings for a tree
• Example 3 of enumerating the red-black colorings for a tree
• Example 4 of enumerating the red-black colorings for a tree
• Red-Black Tree Applet - be sure to open the Java console on your browser