CSE 2320
is the introductory course in algorithms and data structures. This page
provides access to documents and code for the course.
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
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
Last Updated: 09/04/08