Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS330 Midterm
Instructions • This exam is open book. You may consult your textbook, notes, slides, or other course materials, but no external sources. • You may reference and use anything without having to prove or explain in detail (e.g., algorithms, proofs, running time) discussed in lecture, lab or the textbook. • Absolutely no collaboration is allowed. You cannot discuss the contents of this exam with anyone except the instructors. • The exam consists of 3 questions. With question 1 consisting of subproblems a - e. • The exam has quite a few questions. Don’t get stuck on one, if it takes you a long time, move on to the next question and you can come back to it later. Also, the deadline is a hard deadline. It’s better to submit a not fully completed exam, than miss your deadline. • You can write your answers by hand on paper, on a tablet, or you can type your solutions. Make sure to clearly write which problem you are answering and also label your answers with the problem number and the problem part at the top of each page when you upload to Gradescope. If we cannot find or read your answers they will not be graded. • From the time you download this pdf you have exactly 120 minutes time to upload your final pdf to Gradescope. The system is set not to accept exams after your time has expired. • If you have questions, you may ask them via private post on Piazza or via the Zoom link. (This link is also posted on Piazza in @309) 1 Problem 1 Short answers (8 points) (a) (2 points) For each of the below determine whether the complexity is Θ(n2). Write True or False, no explanation needed. (a) Smallest complexity of an algorithm which finds the largest and smallest element in a list. (b) Complexity of Dijkstra’s algorithm (with the implementation discussed in class). (c) Smallest complexity of finding a minimum weight spanning tree in a graph that has n vertices and 3n many edges. (Answer this question with regard to the algorithms and implementations that we studied in class.) (d) Let G(U,W,E) be a complete bipartite graph. Suppose that |U | = |W | = √n. The number of edges in G is Θ(n2). Here is the definition of a complete bipartite graph: the nodes in G are divided in to two sets U and W that form a partition, i.e. each node is assigned to exactly one of the two. There is an edge between every pair of nodes u,w where u ∈ U and w ∈ W , but there are NO edges between pairs of nodes in the same set. (b) (3 points) Consider the graph G below. Note, that this graph is undirected. Answer both parts (a.) and (b.). In both parts there may be more than one correct answer, and you should list all the answers that are correct. No explanation needed. a b c d e f g h (a) Which of the following is NOT a possible order in which vertices of G are dis- covered when a depth-first search (DFS) on G is done? Assume that the search starts at vertex a. (A) abcdefgh (B) acfghedb (C) abceghedb (D) acefhgbd (E) None of them (b) Which of the following ARE possible orders in which the vertices of G are dis- covered when a breadth-first search (BFS) on G is done? Assume that the search starts at vertex f . (A) fchgaedb (B) fhgecabd (C) fgchabd (D) fghcaedb (E) chgebda (F) None of them 2 (c) ( 1 point) Suppose you are given an undirected, connected graph G(V,E). Suppose you run DFS on this graph started from a randomly chosen node. How can you use the outcome of DFS to assign a direction to each edge, so that the resulting directed graph is a DAG? Give a very short explanation (you should be able to do this in one or two sentences). You don’t need to describe an efficient implementation of your algorithm or prove its correctness, only state your approach clearly. (d) (1 point) Given a weighted graph where weights of all edges are unique (no two edge have same weights), there is always a unique shortest path from a source to destination in such a graph. Explain why or provide a counter example. (e) (1 point) Let G = (V,E, c) be an undirected graph with costs c(e) on each edge e and let T be a minimum weight spanning tree on G. Suppose the cost of each edge is increased by 1. Is T still an MST? Explain why or provide a counter example. 3 Problem 2 (7 points) Exam 2 In the Interval Partitioning problem we are given a set of n requests, where the ith request starts at time si and finishes at time fi, find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time. We propose the Earliest-Finish-Time-First (EFTF) algorithm to solve this problem. It works as follows; first, we sort the requests in ascending order of finish time. Then we consider requests in this order. We assign a request to one of the resources it’s compatible with at random. If a request is incompatible with all resources being used, then we choose a new resource to use for this request. (a) (3 points) Give an example of jobs, such that the EFTF algorithm does not yield an optimal solution (that is a minimum size list of resources). Note: For this part of the problem it is sufficient to draw a picture of the intervals (jobs) that are in your example as was done in our textbook. You should number the jobs and use this numbering to specify which jobs are scheduled using ESTF as well as a list of jobs which are optimal for this problem. (b) (4 points) Prove that when all jobs are of equal length, then the Earliest-Finish-Time- First algorithm does yield an optimal solution. (You may reference proofs from class if you think they are relevant.) 4 Problem 3 (7 points) A graph G(V,E) is called BIPARTITE if V can be decomposed into two disjoint sets U and W such that every edge in E joins a vertex in U to one in W . (Thus there is no edge between two nodes in the same set.) You can see an example in the picture on the right. (a) (3 points) Observe the two graphs depicted in the picture. If you look at it carefully, you can see that the two graphs are identical, just drawn in a different layout. You can also clearly see from the drawing on the right that it’s bipartite. Suppose we have a connected graph G(V,E) that we know to be bipartite, but don’t know which of the two sets U and W each node belongs to. (e.g. you would see something like the drawing on the left.) Design a simple greedy algorithm that assigns the nodes to the two sets. (Hint: start from an arbitrary node v and assign it to set U . Then consider the neighbors of v. ) Describe your algorithm and give a short explanation why it is correct in assigning the vertices (we are not expecting a rigorous formal proof here.) (b) ( 1 point) Analyze the algorithm’s running time assuming it’s stored in an adjacency list. (c) (3 points) A cycle in a graph is even length if it consists of even number of nodes (and of course the same number of edges). Based on the algorithm you designed in (a.), prove that any cycle in a bipartite graph has to be of even length. (Hint: think of which sets U or W each subsequent node along the cycle is in.) 5