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 may ask the professor or
...
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 may 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]