Rucurrence running time

Give asymptotic upper and lower running time bounds for T(n) for each of the recurrences. Assume that T(n) is constant for n <= 2. Make bounds as tight as possible, and justify solutions. a) T(n) = 2*T(n/2) + n^3 b) T(n) = T(9n/10) + n c) T(n) = 16*T(n/4)+n^2 d) T(n) = 7*T(n/3) + n^2 e) T(n) = 7*T(n/2) + n^2

Solving a recurrence

Using the same method in attachment #1, solve the recurrence in attachment #2. I increased the bid to 6 credits, but also could you repost the Rucurrence running time problem (MasterTheorem.doc) in PDF format (as well as the solution to this problem) because the .doc says it is corrupt when I try to open it.

Design the unit testing framework for the ATM machine

Design the unit testing framework for the ATM machine in the style of JUnit Test Infected: with the following functionalities: check balance, deposit cash, and withdraw cash. The framework could be developed in pseudo-code

DATA COMMUNICATIONS QUESTION - MULTIPLEXING

Suppose I have a multiplexer that is connected to a high-speed digital transmission system that can transfer 1,536,000 information bits per second. How many standard voice channels is the high-speed transmission system capable of carrying and how do you figure this out? What is the transmission efficiency of t ...continues

Sum of 2 numbers problem: create a O(n log n) algorithm that determines whether or not there exist two elements in S whose sum is exactly z

I need help creating a O(n log n) algorithm that determines whether or not there exists two elements in S whose sum is exactly z. Additionally, the problem indicates that sorting is somehow related to the solution.

Merging Sorted Lists using Heaps

I need help figuring out an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists. I believe we are supposed to use a Heap for k-way merging.

radix sort

Attached is a problem asking if radix sort would be appropriate. I think it would not be appropriate. Can you help give me reasons why? One of the reasons why I think radix sort is not better then the other is because radix is linear, and the other one is n log n (which I believe is faster?).

sorting an array of integers in linear time

How can I sort an array of integers in O(n) time, where different integers may have different numbers of digits, but the total number of digits over ALL the integers in the array is n? My assumption is that radix sort is somehow involved.

explanation of solution

The solution seems to be the the following, but I need a more in-depth explanation, particularly on why we should use merge sort and binary sort. Here is the problem at a high level (you can look at the attachment for more detail): Describe a (n log_2 n) time algorithm that, given a set S of n real numbers and another rea ...continues

Min heap problem: merge k sorted lists into one sorted list in O(n lg k) time

Recall this problem -- define an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists... My question is why do we define a comparison that states the following: "We shall also need to define comparison with empty lists, and so we define it ...continues