authorea.com/5532

CS344 HW #2

\(T(n) = 2T(\frac{n}{4})+n^{0.51}\)

Using Master’s Theorem \(T(n)=aT(\frac{n}{b})+f(n)\), we let \(a=2\), \(b=4\), and \(d=.51\).

\(T(n) = \theta(n^{0.51})\)

\(T(n) = 16T(\frac{n}{4}) + n!\)

We can use Case 3 that was given (\(f(n) = \Omega(n^{log_{b}a+\epsilon})\) ) to analyze the recurrence relation.

\(f(n)= n!\) and \(n^{log_{b}a+\epsilon}\) for \(\epsilon > 0\)

Case 3 states that if \(f(n)=\Omega(n^{log_{b}a+\epsilon})\), then \(T(n) = \theta(f(n))\)

Since \(n!=\Omega(n^{2}+\epsilon)\), then:

\(T(n)=\theta(n!)\)

\(T(n)= \sqrt{2}T(\frac{n}{2})+logn\)

For this problem, we can first use Case 1 to analyze the recurrence relation.

\(f(n)=log(n)\) and \(n^{log_{b}a-\epsilon}=n^{\frac{1}{2}-\epsilon}\)

We know from Case 3, that if \(f(n)=O(log_{b}a-\epsilon), then T(n) = \theta(n^{log_{b}a})\).

Since we know that a polynomial is greater than a log function, we can apply case 1, therefore:

\(T(n) = \theta(\sqrt{n})\)

\(T(n) = T(n-1) + lg(n)\)

\(T(n-1) = T(n-2) + lg(n-1)\)

\(T(n-2) = T(n-3) + lg(n-2)\)

\(T(1) = T(0) + lg(1)\)

\(T(n) + \sum_{i=1}^{n-1} T(i) = \sum_{i=1}^{n-1} T(i)\) since \(T(0) = T(1) + \sum_{k=1}^{n} lg(k)\)

Then, subtract the summation terms from both sides and:

\(T(n) = \sum_{k=1}^{n} lg(k) = lg(n!) <= \theta(nlgn)\)

\(T(n) = 5T(\frac{n}{5})+ \frac{n}{lgn}\) So if we are to look at the recursion tree this relation creates we can observe that at the jth level there will be \(5^j\) nodes. Each node will only have a problem of the size \(\frac{n}{5^j}\) so at each node the time to complete it will be \(\frac{(\frac{n}{5^j})}{log(\frac{n}{5^j})}\)

Know this if we sum over all the \(log(n)\) levels we get:

\(T(n) = \sum_{j=0}^{log(n-1)} 5^{j}\frac{\frac{n}{5^j}}{log(\frac{n}{5^j})}\)

\(T(n) = \sum_{j=0}^{log(n-1)} \frac{n}{log(n-j)}\)

\(T(n) = n\sum_{j=1}^{log(n-1)} \frac{1}{j}= \theta(nlog(log(n)))\)

Assumptions: We will be able to construct a tree where each node of the left subtree consists of easier projects, and each node of the right subtree consists of harder projects. Also we can create a tree where each node of the left subtree consists of less capable programmers and each node of the right subtree consists of more capable programmers. We know we can not directly compare the projects or porgrammers but we have an algorithm explained in part B which allows us to order these items.

In this problem, we will use the foundations of a lower bound for comparison-based sort algorithms because comparisons are the only way to figure out which job matches with the correct person. For any comparison-based sorting algorithm, it can be interpreted as a question of decision trees. For a decision tree, we can state:

A. In a tree of n nodes, for each of the n! permutations, it must appear as one of the leaves of the decision tree in order for the algorithm to sort properly.

B. For a number x, let it represent both the maximum number of comparisons in the algorithm and the maximum height of the tree. A tree with a maximum neight of x, also has at most \(2^{x}\) leaves.

Using these statements, we can induce the following:

\(n! <= 2^{x}\)

\(log(n!) <= x\)

\(log(n!) = \Theta(nlogn)\)

\(x = \Omega(nlogn)\)

No matter which alogrithm you choose to use you can see that this problem will force you to take at minimum of 2nlogn time because there are two trees we have to deal with. Therefore, any algorthim you find to solve this problem will have a worst case of \(\Omega(nlogn)\)

We will first take one person and have him/her interview for each job position. After the interviews, then we split the job positions into the 3 categories: 1 - jobs that he can do but the compensation doesn’t meet his expectations, 2 - jobs that he can’t do, and 3 - the single project he can do and the compensation matches his expecation.This takes n time.

Then, we take the other candidates and have them interview for the perfectly matched job (3), and split them into two groups 4 -programmers who can do the job, and 5 - programmers who cannot do the job. This takes n time.

Now, we pair the groups 2 and 4 and pair the groups 1 and 5 (with the numbers designated above).

People that could handle the perfect job (3) will have to do the more difficult jobs that is group 2. So that means all the people in group (4) will be matched up with some project in group (2). People that couldn’t handle the perfect job (4) will do the easier jobs in group (1). So that means people in group (1) will be matched with projects in group (5).

This algorithm is basically quicksort because the first person we choose is the pivot and we first find the job that person matches up with. Then we break both arrays into a lower half and upper half. This is quicksort except that each recursion takes 2n time instead of n time but because we don’t care about constants this does not change the run time analysis.

To sort everyone out, we will basically use quicksort on two arrays, which has an average case of \(nlogn\) which we proved in lecture.

To sort the scores of the participants for each university, we can use

**mergesort**for our comparative sorting algorithm. Our initial array will just be filled with the (unsorted) scores for every student of every university, and since the array is filled with numerical values, a simple mergesort (with no modifications) is needed to sort the scores. Disregarding space efficienecy, mergesort has a worst case of \(nlogn\).For our non-comparitive sort, we can use counting sort because we do know that there is a maximum and minimum score, so the possible values for the counting sort are bounded. Also all the values are integers so there will be no issues using this sort which will take n time.

To sort the scores of participants given k files, where each file includes the sorted scores from specific universities, we will make use of a max heap.

First we will take the first element of each array (university), and insert it into a max heap. This takes \(klogk\) time. Since these arrays are all sorted we will be inserting the largest elements, then we will pop out the largest element. Popping the largest value takes \(logk\) time. This value is the highest score in all the universities.

Then, we examine the popped element, and if the element is from array \(i\), then the next element we add to the heap will be from array \(i\). This takes \(logk\) time.

If we continue this process the max heap will give us the correct order of all the scores.

We will do all of this n times, so in total it will take \(O(2nlogk)\) time. The total time to sort is \(O(klogk + 2nlogk) = O(nlogk)\).

Given k sorted files we need to find the rth largest score and to do this without sorting the scores of the participants we will be using binary search on all the sorted files. First we will start by looking at the r/k position of each of the k arrays. If r/k is not an integer we will round up for some and round down for others to make sure if you add all the indicies of the arrays it will equal k. It is important to note that during any time during this algorithm the summation of the indices will always be k.

Next we will find the smallest value of each one of these arrays which will only take k time.

Then for the array that had the smallest value at the index r/k we know that all the values under that one cannot be the rth largest value. So we ignore the bottom half of the array. Then for all the other arrays we know that the values above the r/k index will not have the rth largest value so we can ignore the top half of all of those arrays. This just shows us that at each iteration we are able to cut our problem in half.

Now we can look at the our new smaller arrays and we continue this same process. We choose indices such that the summation of them are equal to r and then we find the smallest of these values. At each step we are on average spliting up our problem in half. So we continue this process until we are only left with one element in each array. Since the indices of these positions sum up to r the smallest value is the rth largest number.

At each step we have to do k comparisons to find the smallest number and we are basically doing binary search to each array the running time is \(k*(time of binary searches)\)

Runtime= \(\theta(k\sum_{i=1}^{k}logm_i)\)

We are not sure if we can do this in \(O(\log k (\sum_{i=1}^{k}\log m_{i}+k))\)

## Share on Social Media