EECE 431 Midterm

EECE 431 Design and Analysis of Algorithms
Midterm
Saturday April 24, 2009
• Do not open this booklet until you are directed to do so.

• The exam is open book. In particular, you are allowed to use: the textbook [CLRS], your class
notes, Moodle handouts, and problem sets and their solutions.
• If you are caught during the exam communicating with a person other than the exam proctors, you
will immediately get zero and you will be referred to the appropriate disciplinary committee.
• The duration of this exam is 3 hours.

• Plan your time wisely. Do not spend too much time on any one problem. Read through all of them
first and attack them in the order that allows you to make the most progress.
• Write your solutions on the provided booklet.
• Good luck!
1
Problem 1 (70 points). Short Questions
For the following questions, unless stated otherwise, you are asked to provide concise and convincing
solutions. Do not loose your time by overexplaining.
1. (10 points) Array union

We are given two arrays each consisting of distinct numbers. However, they may have common
elements. We would like to find their union, i.e., combine them in a single array while including
each element only once. Give a fast algorithm for this problem. Express the running time in terms
of the sizes of the two arrays.
2. (12 points) Ternary Merge Sort
Consider the following variation of merge sort. Rather than dividing the array into two subarrays,
we divide it into three subarrays: lower third, middle third, and upper third. Then we sort the three
subarrays recursively. Finally, we merge the three sorted subarray into a single sorted subarray.
This is the idea of Ternary Merge Sort.
Write a pseudocode of Ternary Merge Sort and analyze its worst case running time. You can use
the merge function we did in class as a black box.
3. (12 points) Randomized Select
Recall the randomized selection algorithm RandSelect we studied in class. Consider running RandS-
elect on a size-n array to find the 10’th smallest element. Assume that n ≥ 10. Find the probability
that first chosen pivot is the third smallest element of the array and the second chosen pivot is the
(desired) 10’th smallest element.
4. (12 points) Improved Predecessor and Successor in RB trees
Explain how you can augment a RB tree so that the operations Insert, Search, Delete, Max, and
Min, still take O(log n), but Predecessor and Successor take O(1) time. Explain also how you can
maintain the augmented tree after an Insert or Delete operation.
5. (12 points) Union of simple cycles
Let G be an undirected graph with the property that all the nodes have even degrees. Prove that
G is a union of simple cycles, i.e., the edges of G can be partitioned into simple cycles.
6. (12 points) Searching sorted arrays: find first and last occurrences
In this problem we are interested in sorted arrays containing possibly many duplicate elements.
Given a size-n sorted array A of numbers and a number x, we want to check whether or not x
appears A. If x appears in A, we are not satisfied with finding the index of any occurrence of x in
A; we want to find the index of the first occurrence of x in A and the index of the last occurrence
of x in A.
Design an efficient algorithm for this problem and analyze its running time. You can do it in
O(log n) time, but you will get some credit for less efficient solutions.
Problem 2 (20 points). Maximum weighted matching for trees

In this problem we are interested in trees whose edges are weighted by real numbers, i.e., weighted
acyclic undirected graphs.
Let T be a rooted weighted tree. A matching M of T is a subset of the edges of T such that no two
edges in M have a node in common. The weight of M is defined as the sum of the weights of the edges
in M .
In the “Tree Maximum Weighted Matching” problem, given T , we want to find a matching M of T
whose weight is maximal.
Assume that T is represented as a weighted undirected graph in the adjacency list representation.
Design an efficient algorithm for this problem. Express the running time in terms of the number of
edges and the number of nodes of T .
2
For simplicity, you are not asked to produce a matching whose weight is maximum, we are satisfied
with producing the weight of a maximum weight matching.
(Hint: Make T rooted by choosing a arbitrary node of T and declaring it as the root. Try to proceed
recursively starting from the root. Look at the children of the root. To make the recursion work, it is
NOT enough to have, for each child c, the weight w(c) of the maximum weight matching of the subtree
rooted at c. In addition to the w(c)’s you need other quantities ... )
Problem 3 (10 points + 20 bonus points). A partition problem

We are given a positive integer m and a list of n integers a1 , . . . , an such that −m ≤ ai ≤ m for
i = 1 . . . n.
We want to to check whether or not we can partition the list of numbers into two subsets such that
the sum of integers in each subset is positive. That is, we want to check if there exists S ⊂ {1, . . . , n}
P P def
such that i∈S ai > 0 and i∈S c ai > 0, where S c = {1, . . . , n} − S.
Design a polynomial time algorithm for this problem. Express the running time in terms of m and n.
For simplicity, you are not asked to produce such a partition if it exists, we are satisfied with a
YES/NO answer.
(Hint: Dynamic Programming.)

EECE 431 Midterm

Uploaded by

Copyright:

Available Formats

EECE 431 Midterm

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

EECE 431 Midterm

Uploaded by

Copyright:

Available Formats

EECE 431 Design and Analysis of Algorithms

Saturday April 24, 2009

• Do not open this booklet until you are directed to do so.

• The duration of this exam is 3 hours.

1. (10 points) Array union

Problem 2 (20 points). Maximum weighted matching for trees

Problem 3 (10 points + 20 bonus points). A partition problem

You might also like