Solving Algorithms

1. (Total: 8 pts) A grad student comes up with the following algorithm to sort an array A[1..n] that
works by first sorting the first 2/3rds of the array, then sorting the last 2/3rds of the (resulting) array,
and finally sorting the first 2/3rds of the new array.
1: function G-SORT(A, n) . takes as input an array of n numbers, A[1..n]
2: G-sort-recurse(A, 1, n)
3: end function
4: function G-SORT-RECURSE(A, `, u)
5: if u − ` ≤ 0 then
6: return . 1 or fewer elements already sorted
7: else if u − ` = 1 then . 2 elements
8: if A[u] < A[`] then . swap values
9: temp ← A[u]
10: A[u] ← A[`]
11: A[`] ← temp
12: end if
13: else . 3 or more elements
14: size ← u − ` + 1
15: twothirds ← d(2 ∗ size)/3e
16: G-sort-recurse(A, `, ` + twothirds − 1)
17: G-sort-recurse(A, u − twothirds + 1, u)
18: G-sort-recurse(A, `, ` + twothirds − 1)
19: end if
20: end function
1
a (4 pts). First, prove that the algorithm correctly sorts the numbers in the array (in increasing order).
After showing that it correctly sorts 1 and 2 element intervals, you may make the (incorrect) assumption that the number of elements being passed to G-sort-recurse is always a multiple of 3 to simplify
the notation (and drop the floors/ceilings).
Solution.
2
b (1 pts). Next, Derive a recurrence for the algorithm’s running time (or number of comparisons
Solution.
3
c (3 pts). Finally, obtain a good asymptotic upper bound (big-O) for your recurrence.
Solution.
4
2. (Total: 3 pts) Least counterexample: Give a proof by contradiction using the least counterexample
method that:
Xn
i=0
i =
n(n + 1)
2
for all n ≥ 0.
Solution.
5
3. (Total: 8 pts) Define the sequence Tn = (n − 1) + n−1
n2 ·
Pn−1
k=1 Tk. Prove, by induction, for all n ≥ 1,
that Tn ≤ 2n.
Solution.
6
4. (Total: 14 pts) Let S(n) be defined, for n ≥ 2, as S(n) = 2S(d
n
2
e) + nlog2
(n). For n = 1, the value
is S(n) = 1.
(a) (4 pts) Can you apply Master Theorem on S(n)? If no, precisely state why not. If yes, apply the
theorem and derive the bound.
Solution.
7
(b) (10 pts) Now use a method, besides Master Theorem, to prove that S(n) ∈ O(n(log2n)
2
).
Solution.
8
5. (5 points) You are presented with two sorting algorithms. You have to select one of them. The
documentation provided states that both of these algorithms perform Ω(n
3
) comparisons in the worst
case. You want to build a fast program and therefore want to optimise speed. Does it matter which
algorithm you select? How would you make the decision?
Solution.
9
6. (Total: 12 pts)You are interested in building a coffeeshop and charging station beside a freeway running between two cities. Let n be the number of interchanges between the cities, and number them
consecutively so that interchange 0 is at the first city, 1 is the next interchange, and so on, with n − 1
being the interchange at the other city. We say each interchange i is adjacent to interchanges i−1 and
i + 1 (only).
Each interchange i has a cost c(i) to construct a coffee shop/charging station. Call an interchange
i a local minimum if (and only if) the cost of building there is less than the costs of building at the
adjacent interchanges, i.e. both c(i) < c(i + 1) and c(i) < c(i − 1). You want to ensure that you
build at a local minimum so that no one can build a coffeeshop/charging station more cheaply at an
You can assume that:
• n ≥ 3, so there is at least one interchange between the cities.
• The costs at the cities c(0) and c(n−1) are both known to be the same large number (say 100n).
• The other costs are all different and are all strictly less than c(0) (and thus also less than c(n−1)).
The difficulty is that the c(i) values are not known ahead of time (except for c(0) and c(n − 1)) and it
is expensive to determine the cost of building at any interchange.
The goal is to create a divide and conquer algorithm that finds any interchange k that is a local
minimum while examining relatively few of the c(i) values. Although there may be many local
minimums, your algorithm need only find one of them.
(a) (2 points) First, prove that a local minimum exists.
Solution.
10
(b) (5 points) Clearly describe a divide and conquer algorithm for the problem.
Two pages have been left blank for this question. If you do not need both the page, please leave
the second page blank.
Solution.
11
12
(c) (3 points) Prove that your algorithm is correct.
Solution.
13
(d) (2 points) Analyze the (worst case) number of interchange costs (i.e. c(i) values) examined by
your algorithm as a function of n.
Solution.
14

The post Solving Algorithms first appeared on COMPLIANT PAPERS.

Pages (550 words)
Approximate price: -

High Quality Papers

We always make sure that writers follow all your instructions precisely. You can choose your academic level or professional level, and we will assign a writer who has a respective degree.

Experienced Writers

We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.

Free Revisions

If you think we missed something, send your order for a free revision. You have 10 days to submit the order for review after you have received the final document.

Timely Delivery

All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension.A 100% refund is guaranteed.

100% Confidential

We use several writing tools checks to ensure that all documents you receive are free from plagiarism. Our editors carefully review all quotations in the text.

Tutorpro support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.

Try it now!

Calculate the price of your order

Total price:
\$0.00

How it works?

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

Tutorpro Homework Help Services

At Tutorpro, we have top rated masters and PhD writers who will help you tacke that homework and score A+ grade. Tutorpro services covers all levels of education : high school, college, university undergraduate, masters and PhD academic level.

Essay Writing

No matter what kind of academic paper you need and how urgent you need it, you are welcome to choose your academic level and the type of your paper at an affordable price. We take care of all your paper needs and give a 24/7 customer care support system.