Homework answers / question archive / COSC 336 Assignment 03 Instructions: Turn in a PDF report with images/screenshots of your work in detail

COSC 336 Assignment 03 Instructions: Turn in a PDF report with images/screenshots of your work in detail

Computer Science

Share With

COSC 336 Assignment 03 Instructions: Turn in a PDF report with images/screenshots of your work in detail. Submission: Include everything in a folder, zip and name it _HW0304.zip and submit to Blackboard. Part A 1. 8.2-2(p196), 8.3-3(p200), 11.2-5 (p261), 12.1-3 (p289), 13.1-3 (p311), 23.1 (p629), 24.3-2 (p663) Part B (B1). Implement a Red-Black tree with only operation Insert(). Your program should read from a file that contain positive integers and should insert those numbers into the RB tree in that order. Note that the input file will only contain distinct integers. Print your tree by level using positive values for Black color and negative values for Red color. Do not print out null nodes. Format for a node: (, ). For example, the following tree is represented as (12, null) (5, 12) (15, 12) (3, 5) (-10, 5) (13, 15) (17, 15) (-4, 3) (7, -10) (11, -10) (-14, 13) (-6, 7) (-8, 7) (B2). Implement a randomized Skip-List with operations Insert(), Delete() and Search(). Your program should read from the input file just like in (B1). Print out the skip-list using the format given below 16 16 71 91 2 16 71 89 91 2 10 15 16 31 71 86 89 91 96 (B3). Implement Dijkstra’s algorithm on an undirected graph. The input file would contain (1) the pair of source and destination “u v” in the first row, and (2) the edge list with the associated weight (of type double) for each edge in the graph. Output the sequence of nodes that are on the shortest path from “u” to “v” with the total weight. Provide your own test cases. Turn in your code and test cases (i.e., “.java” or “.c/.cpp” and test files) only. Note: RECURSION is NOT allowed at all. Your implementation can only contain iterative methods. 8.3-3 Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable? 8.2-2 Prove that COUNTING-SORT is stable. 11.2-5 Suppose that we are storing a set of n keys into a hash table of size m. Show that if the keys are drawn from a universe U with |U| > nm, then U has a subset of size n consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is (n). 12.1-3 Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but ele- gant, solution uses no stack but assumes that we can test two pointers for equality.) 23.1-1 Let (u, v) be a minimum-weight edge in a connected graph G. Show that (u, v) belongs to some minimum spanning tree of G. 24.3-2 Give a simple example of a directed graph with negative-weight edges for which Dijkstra's algorithm produces incorrect answers. Why doesn't the proof of Theo- rem 24.6 go through when negative-weight edges are allowed? 13.1-3 Let us define a relaxed red-black tree as a binary search tree that satisfies red- black properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed red-black tree T whose root is red. If we color the root of T black but make no other changes to T, is the resulting tree a red-black tree? 12.1-3 Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but ele- gant, solution uses no stack but assumes that we can test two pointers for equality.)