Mathematics > QUESTIONS & ANSWERS > Georgia Institute Of Technology CS 8803-GAF17midterm1soln (All)

Georgia Institute Of Technology CS 8803-GAF17midterm1soln

Document Content and Description Below

DIRECTIONS: • Do not turn over the page until you are told to do so. • This is a closed book exam. No communicating with other students, or looking at notes, or using electronic devices. You m... ay ask the professor or TA to clarify the meaning of a question but do so in a way that causes minimal disruption. • If you finish early, you may leave early but do so as quietly as possible. The exam script should be given to the professor. • There are five questions. All carry the same number of marks but some questions may be easier than others. Don’t spend too long on a problem if you’re stuck { you may find that there are other easier questions. • The front and back of the pages can be used for solutions. There are also a blank page at the end that can be used. If you are using these pages, clearly indicate which question you’re answering. Remember that the best answers are those that are clear and concise (and of course correct). Most questions can be answered in two or three sentences. 1 /10 2 /10 3 /10 4 /8+2 5 /10 Total /48+2 1Question 1. For each of the following statements, indicate whether they are TRUE or FALSE by circling the appropriate answer. No justification is required. 1. If the running time T (n) of an algorithm satisfies T (n) = O(n2) and T (n) = Ω(n2) then it also satisfies T (n) = Θ(n2). Answer: TRUE. 2. If a subset system (E; I) doesn’t satisfy the cardinality property, there exist subsets A; B 2 I such that jBj > jAj and A + e 62 I for all e 2 B − A. Answer: TRUE. 3. If the complex number z is a 4th root of unity, then it is also an 8th root of unity. Answer: TRUE. 4. Consider an undirected graph where all edges have weight at least 1. If there are exactly two edges with weight 1 then any minimum spanning tree includes both of these edges. Answer: TRUE. 5. If E consists of n elements and I consists of 2n subsets of E, then (E; I) is a matroid. Answer: TRUE. Question 2. No justification required for your answers. 1. Consider the following undirected graph. The number on an edge indicates its weight. Weight of minimum spanning tree = 7 Weight of maximum weight matching = 8 Length of shortest path between c and d = 7 Diameter of the graph = 7 a c b d 4 8 2 1 For diameter and shortest paths, you should treat the weight as the length of the edge. 2. What is the adjacency matrix of the graph considered above? You should ignore the weights on the edges. Answer: 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 3. Suppose that a divide and con [Show More]

Last updated: 2 years ago

Preview 1 out of 7 pages

Buy Now

Instant download

We Accept: