这是一个美国的数据结构与算法作业代写
Instructions (please read carefully before you start!)
- This take-home exam contains 7 pages (including this cover page) and 5 questions.Total number of points is 50.
- You must work on your own,and no collaboration or help from any resources other than those made available in class (lecture notes, texts, homework problems, etc.) is permitted.
- Submit your solutions in PDF on Google Classroom before the deadline, either scanned or typeset in LATEX. Name the PDF fifile ‘<your last name> MT2.pdf’. If you choose to hand-write and scan, print out this exam sheet and write your solutions on it.Do your best to fifit your answers into the space provided, and attach extra papers only if necessary. If you typeset in LATEX, use the provided TeX fifile. No other formats are accepted.
- For problems that require you to provide, design or describe an algorithm, you must give a precise description of the algorithm in pseudocode, together with a proof of correctness and an analysis of its running time.
Grade Table (for graders’ use only)
- (10 points) Suppose that instead of each node x keeping the attribute x.p, pointing to x’s parent, it keeps x.succ, pointing to x’s successor. Give pseudocode for Search,Insert, and Delete on a binary search tree T using this representation. These proce-dures should operate in time O(h), where h is the height of the tree T. (Hint: You may wish to implement a subroutine that returns the parent of a node.)
- (10 points) Consider a connected, undirected graph G = (V, E) and a vertex u ∈ V.After we run both BFS and DFS on u, we obtain the same BFS search tree and DFS search tree T, which contains all vertices of G. Prove or refute: G = T.
- (10 points) Suppose we are given a directed graph G with weighted edges and two vertices s and t. Describe and analyze an effificient algorithm to fifind the shortest path from s to t when exactly one edge in G has negative weight.
- (10 points) Suppose we change line 4 of Dijkstra’s algorithm to the following:
4 while |Q| > 1
This change causes the while loop to execute |V| − 1 times instead of |V| times. Is this proposed algorithm correct?
- (10 points) Design an effificient algorithm for the following problem. You are given a set of n jobs to be executed on a single large machine, with a processing time ti and a weight wi for each job. Given a schedule (i.e., an ordering of the jobs), let Ci denote the fifinishing time of job i. For example, if job j is the fifirst to be done, we would have Cj = tj ; and if job j is done right after job i, we would have Cj = Ci + tj . You wish to order the jobs so as to minimize the weighted sum of the completion times, Σni=1wiCi.
Example: Suppose there are two jobs: the fifirst takes time t1 = 1 and has weight w1 = 10, while the second job takes time t2 = 3 and has weight w2 = 2. Then doing job 1 fifirst would yield a weighted completion time of 10 · 1 + 2 · 4 = 18,while doing the second job fifirst would yield the larger weighted completion time of 10 · 4 + 2 · 3 = 46.