CSE 3318

Office Hours

Documents

• Fall 2024 Syllabus PDF
• Notes 1 - Algorithmic Concepts PDF
• Notes 2 - Growth of Functions PDF
• Notes 3 - Summations PDF
• Notes 4 - Recurrences PDF
• Notes 5 - Heaps and Priority Queues PDF
• Notes 6 - Greedy Algorithms PDF
• Notes 7 - Dynamic Programming PDF
• Notes 8 - Sorting PDF
• Notes 9 - Linked Lists PDF
• Notes 10 - Stacks & Queues PDF
• Notes 11 - Rooted Trees PDF
• Notes 12 - Hashing PDF
• Notes 13 - Graph Representations and Search PDF
• Notes 14 - Minimum Spanning Trees PDF
• Notes 15 - Shortest Paths PDF
• Notes 16 - Network Flows and Bipartite Matching PDF
• Homework 1 problems PDF
• Homework 1 answers PDF
• Homework 2 problems PDF
• Homework 2 answers PDF
• Homework 3 problems PDF
• Homework 3 answers PDF
• Some exam answer keys
• Fall 22 exam questions PDF
• Spring 19 exam questions PDF
• Fall 18 exam questions PDF
• Summer 18 exam questions PDF
• Spring 15 exam questions PDF
• Fall 14 exam questions PDF
• Spring 14 exam questions PDF
• Fall 13 exam questions PDF
• Summer 13 exam questions PDF
• Spring 13 questions PDF
• Fall 12 exam questions PDF
• Summer 12 exam questions PDF
• Spring 12-001 exam questions PDF
• Spring 12-002 exam questions PDF
• Fall 11 exam questions PDF
• Summer 11 exam questions PDF

Programming Assignments

• Using omega.uta.edu
• Building and executing on omega.uta.edu
• Lab 1
• Lab 2
• Lab 3
• Lab 4
• Lab 5

Code

• Insertion Sort code, input, output
• Mergesort code (CLRS), input, output
• Merge code (CLRS), input, output
• Binary Search binarySearch.c, binarySearchRange.c
• LU decomposition code, input, output
• Expansion of recurrences notes04.c, notes04.out
• Heap code for Notes 05 heapsort.c, intPQi.c
• Huffman coding for Notes 06 code (probabilities), input (probabilities), output (probabilities), code (weights/frequencies)
• C code for hotel-to-airport shuttle explicit traceback, implicit traceback
• Weighted interval scheduling C code (dynamic programming), C code (powerset), input case 0 (see Notes 07), input case 1, input case 2, input case 3, output case 0, output case 1, output case 2, output case 3
• C code for optimal matrix multiply (dynamic programming)
• C code for longest common subsequence (dynamic programming)
• Longest Increasing Subsequence LIS.c
• Longest Strictly Increasing Subsequence LSIS.c
• Subset Sum subsetSum.c
• Knapsack (as described in Sedgewick) knapsackTypeRS.c
• Quicksort qsortRS.c, partition.c, partitionRS.c
• 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.
• Destructive merge of linked lists C code (mergeDummy.c)
• Circular list C code (circular.c)
• C code for free/allocated abstraction circularFree.c
• C++ code for free/allocated abstraction circularFree.cpp, circularFree.h, cFtest.cpp
• Huffman coding for Notes 10 huffman2Q.c, huffman.notes06.dat (probabilities)
• Rat-in-a-maze
• C code for unbalanced binary search trees
• C code and examples for red-black trees
• Linear probing, Notes 12 example 1, Notes 12 example 2
• Double hashing, Notes 12 example, Notes 12 example output
• Compressed Adjacency Lists
• 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
• Depth-first search C code (directed)
• Small examples from Notes 13 dfsDir.tree.dat, dfsDir.tree.out, dfsDir.back.dat, dfsDir.back.out, dfsDir.fwd.dat, dfsDir.fwd.out, dfsDir.crs.dat, dfsDir.crs.out
• Input to depth-first search
• PDF of diagram for input to depth-first search
• Depth-first search C code (undirected), dfsUnd.dat, dfsUnd.out
• Kosaraju's Strong Components Using DFS (code, input (Notes 13), output)
• Second Example of Kosaraju's Strong Components (input, output)
• Prim's Minimum Spanning Tree; Example in Notes 14: prim.dat Memoryless: primMemoryless.c Table: primTable.c Heap (C++): primHeap.cpp (minHeap class: minHeap.h, minHeap.cpp) Heap (Java): primHeap.java (minHeap class: minHeap.java, heapEntry.java) Sedgewick Heap: AdjList.java, Edge.java, Graph.java, GraphMST.java, MSTfile.java, doublePQi.java
• Union-Find Trees uf1.c, uf2.c, uf3.c
• Kruskal's MST: kruskal.c, kruskal.dat, kruskal.out
• Dijkstra's Shortest Path; Example in Notes 15: dijkstra.dat Memoryless: dijkstraMemoryless.c Table: dijkstraTable.c Heap (C++): dijkstraHeap.cpp (minHeap class: minHeap.h, minHeap.cpp) Heap (Java): dijkstraHeap.java (minHeap class: minHeap.java, heapEntry.java) Sedgewick Heap: AdjList.java, Edge.java, Graph.java, GraphSPT.java, SPTfile.java, doublePQi.java
• 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
• Network Flows (Java) even.dat, AdjList.java, Edge.java, IntQueue.java, Network.java, NetworkMaxFlow.java, intPQi.java, netflowFile.java
• C code for KMP string search

Links

• Sedgewick's C Code for Parts 1-4
• Sedgewick's C Code for Part 5
• Java Sorting Animation Page
• Sound of Sorting
• A dichromatic framework for balanced trees