deletions | additions       diff --git a/q2.tex b/q2.tex  index 20424ae..3de545f 100644  --- a/q2.tex  +++ b/q2.tex 
...
\item  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}$  
...
$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 best case of $\Omega(nlogn)$  \item  We will first take one person and have him/her interview for ách job position. After the interviews, then we split the job positions into the 3 categories: 1 - jobs that he can do, 2 - jobs that he can't do, and 3 - jobs that perfectly match him (???).  Then, we take the other candidates and have them interview for the perfectly matched job (3), and split them into two groups 3 - jobs that they can do, and 4 - jobs that they can't do.  Now, we pair the groups 3 and 2 and pair the groups 1 and 4 (with the numbers designated to the above).   People that could handle the perfect job (3) will have to do the more difficult jobs that is group 2. People that couldn't handle the perfect job (4) will do the easier jobs in group (1).  To sort everyone out, we will use quicksort, which has an average case of $nlogn$.  \end{enumerate}