Exam (elaborations)
Exam 1 prep Questions and Answers
- Course
- Institution
Exam of 4 pages for the course GFACT at GFACT (Exam 1 prep)
[Show more]
Content preview
Exam 1 prepif we modify merge sort to recursively to divide into groups of 5 instead of 2, what will be
the time complexity be ? - answer It would be same as the time complexity when we are
dividing the problem in two halves every time, only the base of log changes. But when
we divide array into two sub-arrays then two-way merge needs one comparison but 5-
way merge needs 2 comparisons. So, although by splitting array into 5 sub-arrays, we
are decreasing fewer number of passes, we are actually increasing the cost of each
pass by doing more number of comparisons.
T(n)=5T(n/5)+ O(n) = O(nlogn) with base 5.
You are given an array that has n distinct elements, so that the index of each element is
no more than k away from the index where that element belongs after the array is
sorted. Show how to sort the array in O ( n logk ) time? - answer We can also use a
Balanced Binary Search Tree instead of Heap to store K+1 elements. The insert and
delete operations on Balanced BST also take O(Logk) time. So Balanced BST based
method will also take O(nLogk) time,
You are given an array that has n distinct elements (numbers), such that the index of
each element is no more than k away from the index where that element belongs after
the array is sorted. Show how to sort the array in O(n log k) time. - answerWe can sort
such arrays more efficiently with the help of Heap data structure. Following is the
detailed process that uses Heap.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See
this GFact)
2) One by one remove min element from heap, put it in result array, and add a new
element to heap from remaining elements.
Removing an element and adding a new element to min heap will take Logk time. So
overall complexity will be O(k) + O((n-k)*logK)
You have k sorted lists, each of size n.
How fast can you sort all this data, in terms of k and n? - answerTreat each list as a leaf
in a binary tree. This tree will have O(k) nodes, and O(logk) levels. Merging the lists
pairwise in the leaf level costs Θ(n) for each pair, thus Θ(nk) overall at this level. This
time complexity holds for every level though; because we have disjoint merges, of total
size Θ(nk). This really mimics merge-sort. So over all levels, the cost is O(nk log k).
Explain the sorting lower bound for comparison sort? - answerAny decision tree sorting
n elements has height Ω(n log n). Assume elements are the (distinct) numbers 1
through n
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller julianah420. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $12.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
82871 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now