Jeremy Ting

and 2 more

QUESTION #1 A. First, we will put all of the S(ui, uj) values into an array that keeps track of the two people and their similarity level. If there is n people, the number of connections will be on the order of n². Now, we can use counting sort to sort all of these values from the largest to smallest. To use counting sort, we have to make sure these two assumptions are satisfied first: 1. The values must be an integer (we know this because of how the problem is set up). 2. We must know the range of the numbers. We can find the range of these numbers in linear time by looking through every single value, and keeping track of the max number (at the time). So, in linear time, we can find the max value. Then, we can use counting sort which also costs LINEAR TIME, so in total, the time for the sort is n² (to find the max)+ n²(to do the sort) = O(n²). Although it looks like it’s not, the efficiency is still linear. Now, we take the largest value in our list and place those users into the same group. WE will use a graph data structure ot keep track of which nodes are connected to each other. This data structure will be explained in part b. The runtime for using this data structure is O(log*(n)). So when we find the max value from the list, we put these two values into the same group, and update the data structre. THen, we find the next highest value, and check if they are in the same group. If they are, move on to the next one, and if they aren’t, put them in the same group. We also have a counter that starts at n (number of users), and decrements each time, the two nodes are connected. WE stop once that counter equals k, because that will mean we have k groups. So that means this program runs n − k times, before we get k groups, and then we can stop. Runtime: To sort this last of satisfaction levels: O(n²). Using the data structure to keep track of which nodes are connected: O(log*n). We need to do this n − k times. Total Runtime: O(n² + (n − k)log*n)=O(n²) B. Explanation of the data structure sto keep track of which nodes are connected: Now to keep track of the users that are in a connected component together, we will use a grpah. INitially, each user will have its own individual node and it will have one edge that points to itself. Then each node will have a rep value. If two nodes ahve the same rep value, it is part of the same connected compoenent. To find a node’s rep value, you have to follow the edges that leave the node, and when you searched all the edges, the node you get to, will be the rep value. So in the initial case, all the nodes point to themselves, so node A has rep value A. So all the nodes have different rep values, and they all start in their own connected components. Now when you want to join to connected components you take the pointer from one node and point it to the other one. Example: If you want to put A and B in the same component. Make A’s pointer point to B, instead of itself. Before the change: Rep(A)=A, Rep(B)=B After the change: Rep(A)=B, Rep(B)=B So now, they are in the same component. Now we can create an optimization for this data structure. Assume A and B are in the same group and C and D are in a different group. Rep(A)=Rep(B)=B Rep(C)=Rep(D)=C Now, we want ot join A and D: Normally we would just make the Rep(D) point to A and that would make all the Rep values B. But the problem with this is that if you want to check the Rep(D) you would have to search through a whole tree which could take a good amount of time so instead we will perform an optimization. What we do is we find the Rep(A), which is B. We save the Rep(D) value, which is C. Then we make both D and Rep(D) (assuming they are different) point directly to B. So if we do this every time then when you are looking for the rep value of any node it only takes one move which makes this a very efficient algorithm. Correctness: We know this algo will give us k groups because we first start with n groups (each person is it own group) Then we connect two nodes which decreases the number of groups by 1. Continue this process until you are only left with k. So that is n − k iterations. Now that means we can only connect n − k users together if we want exactly k groups. So we order all of these similarity values and order them. Then we make sure the n-k highest ones are grouped together. We can’t connect any more nodes so the (n − k − 1)th highest one will be largest value given those two people aren’t already in the same group. We can’t add anymore edges in this graph or we will have less than k groups. And since we took out the highest values we are sure to minimize the the similarity of the most similar pair of users that have been assigned to different groups.

Jeremy Ting

and 2 more

QUESTION #1 PART A: If the problem has a solution, then there are no dead ends and no intersections with an odd degree. If we have a solution, it is obvious that there cannot be any dead ends because you only traverse a road once. However, if you have a dead end, you have to traverse it twice. This is because, since you have to go down the dead end to check if there are any power shortages, to get out of that street, you have to turn around and traverse the same road. Therefore, if there is a solution, then there are no dead ends. In addition, if there is a solution, all the intersections must be even. This is because, every time you go to an intersection, you need to take an unused path to get out. Therefore, this means that there must be an even number of paths leading to the intersection. If there is an odd number, then that means on the last path toward the intersection, there will not be a corresponding path to leave the intersection. Which means, you must traverse a path you have already taken and therefore, this would not have a solution. In conclusion, if you have a solution, then all intersections must have an even degree. If there are no dead ends and no intersections with an odd degree, then there is a solution. Since there are no dead ends, or odd degree intersections, you will never be stuck at a node. This means that whenever you go on a road (edge) to a node, there will always be a path that you can take to leave that node. Since all the intersections have even degrees, this means that for every node and each edge that goes into that node, there will be one edge you can take to leave it. So this means that you will always have a new path to take, and that the only time you run out of paths is when you return to teh beginning. Therefore, if there are no dead ends or odd intersections, then there exists a solution. PART B: The algorithm for this problem is quite simple. Since any path you choose will work, we will use Depth First Search to traverse through the whole graph. However, instead of keeping track of the nodes we visited, we will keep track of the edges we traversed through. Then, we will continue along the graph until we hit all the edges, and the path provided will take linear time. If we ever get to a point where you must revisit an old edge and all the edges haven’t already been visited that means there is no solution.

Jeremy Ting

and 2 more

QUESTION 1 We will have two variables relating with the distance DIST and MIN_D, which are initialized to 0. For the first step of Takeshi’s Castle, we will first assign the minimum distance value between the starting points (lets call the points, r₀ and b₀), to a variable called DIST. To find the minimum distance, we calculate the three possible distance values that correspond with the three possible travel methods: 1. The distance between r₁ and b₁ (if both players jump at the same time). 2. The distance between r₁ and b₀ (if only player one jumps). 3. The distance between r₀ and b₁ (if only player two jumps). After finding the 3 possible values, we find the miminimum of the 3, and assign it to the MIN_D variable. Now we will compare the two values MIN_D and DIST. We already know that we need a rope with length DIST because that is the initial distance between the two contestants. The question is whether we need a longer rope for the contestants to complete the first jump. If MIN_D is larger than DIST set DIST equal to MIN_D. If MIN_D is smaller than DIST nothing needs to be done because the initial rope length will be long enough to complete the first jump. Then, we make the contestants do the next iteration of the jump, do the same as above, and find the smallest distance value of the 3 jumps: 1. The distance between ri + 1 and bk + 1 (if both players jump at the same time). 2. The distance between ri + 1 and bk (if only player one jumps). 3. The distance between ri and bk + 1 (if only player two jumps). Again, once we find the smallest distance value of the 3 jumps (MIN_D), compare it to the DIST variable, and update dist if necessary. We do this until both contestants reach the end, and dist’s value is the smallest the rope can be, for the two contestants to finish the challenge. In the worst case, we have to analyze m + n jumps because in the worst case at each jump, only one contestant can jump at a time. Also, there needs to be 3 checks and 3 comparisons for each iteration, to calculate the new value of mind. So in total, there are 6 * (m + n) operations, and the run time is O(m + n).
QUESTION 1 We will have two variables relating with the distance DIST and MIN_D, which are initialized to 0. For the first step of Takeshi’s Castle, we will first assign the minimum distance value between the starting points (lets call the points, r₀ and b₀), to a variable called DIST. To find the minimum distance, we calculate the three possible distance values that correspond with the three possible travel methods: 1. The distance between r₁ and b₁ (if both players jump at the same time). 2. The distance between r₁ and b₀ (if only player one jumps). 3. The distance between r₀ and b₁ (if only player two jumps). After finding the 3 possible values, we find the miminimum of the 3, and assign it to the MIN_D variable. Now we will compare the two values MIN_D and DIST. We already know that we need a rope with length DIST because that is the initial distance between the two contestants. The question is whether we need a longer rope for the contestants to complete the first jump. If MIN_D is larger than DIST set DIST equal to MIN_D. If MIN_D is smaller than DIST nothing needs to be done because the initial rope length will be long enough to complete the first jump. Then, we make the contestants do the next iteration of the jump, do the same as above, and find the smallest distance value of the 3 jumps: 1. The distance between ri + 1 and bk + 1 (if both players jump at the same time). 2. The distance between ri + 1 and bk (if only player one jumps). 3. The distance between ri and bk + 1 (if only player two jumps). Again, once we find the smallest distance value of the 3 jumps (MIN_D), compare it to the DIST variable, and update dist if necessary. We do this until both contestants reach the end, and dist’s value is the smallest the rope can be, for the two contestants to finish the challenge. In the worst case, we have to analyze m + n jumps because in the worst case at each jump, only one contestant can jump at a time. Also, there needs to be 3 checks and 3 comparisons for each iteration, to calculate the new value of mind. So in total, there are 6 * (m + n) operations, and the run time is O(m + n).

Jeremy Ting

and 2 more

QUESTION 1 1. $T(n) = 2T({4})+n^{0.51}$ Using Master’s Theorem $T(n)=aT({b})+f(n)$, we let a = 2, b = 4, and d = .51. T(n)=θ(n0.51) 2. $T(n) = 16T({4}) + n!$ We can use Case 3 that was given (f(n)=Ω(nlogba + ϵ) ) to analyze the recurrence relation. f(n)=n! and nlogba + ϵ for ϵ > 0 Case 3 states that if f(n)=Ω(nlogba + ϵ), then T(n)=θ(f(n)) Since n!=Ω(n² + ϵ), then: T(n)=θ(n!) 3. $T(n)= T({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^{{2}-\epsilon}$ We know from Case 3, that if f(n)=O(logba − ϵ),thenT(n)=θ(nlogba). Since we know that a polynomial is greater than a log function, we can apply case 1, therefore: $T(n) = \theta()$ 4. 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) + ^{n-1} T(i) = ^{n-1} T(i)$ since $T(0) = T(1) + ^{n} lg(k)$ Then, subtract the summation terms from both sides and: $T(n) = ^{n} lg(k) = lg(n!) <= \theta(nlgn)$ 5. $T(n) = 5T({5})+ {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 5j nodes. Each node will only have a problem of the size ${5^j}$ so at each node the time to complete it will be ${5^j})}{log({5^j})}$ Know this if we sum over all the log(n) levels we get: $T(n) = ^{log(n-1)} 5^{j}{5^j}}{log({5^j})}$ $T(n) = ^{log(n-1)} {log(n-j)}$ $T(n) = n^{log(n-1)} {j}= \theta(nlog(log(n)))$