Answer all questions.

1. (24 points) Consider the divide and conquer algorithm below.

D_C(Array A: size of n)

{

if (n == 1)

return;

P(A)

for (int i = 1 to a)

D_C(subarray of A with size n/b)

Q(A)

}

Suppose a = 8 and b = 2, P(A) takes k operations for an array of size k, and Q(A) takes k operations for an array of size k. We want to deduce the running time of the algorithm (without using the Recurrence Master Theorem). We use the technique of building a tree denoting the various recursive calls as discussed in class. Assume we start out with an array A of size n. We also denote recursive calls made by the initial call of the function as level-1 recursive calls; the recursive calls made by those level-1 recursive calls as level-2 recursive calls and so on.

1. How many operations does P(A) and Q(A) together take for the initial call?

For the algorithm’s initial call, the operations done by P(A) and Q(A) on an array A of size n may be estimated as follows:

P(A) performs k operations on an array of size k. In this situation, k equals n, therefore P(A) requires n operations.

Similarly, Q(A) performs n operations on an array of size n.

As a result, for the initial call, P(A) and Q(A) do n + n = 2n operations in total.

2. How many recursive call does the algorithm take for each function call?

for (int i = 1 to a)

D_C(subarray of A with size n/b)

Given a = 8 and b = 2, the algorithm makes 8 recursive calls (for i = 1 to a) in each function call, each operating on a subarray of size n/2

3. Consider the level-1 recursive calls, what is the TOTAL amount of operations on P(A) and Q(A) together for all those calls.

For level 1 recursive calls, the array is divided into subarrays of size n/b.

Based on the issue statement, a = 8 and b = 2. So, each subarray has a size of n/2, and there are eight of them.

The techniques P(A) and Q(A) both need k operations on an array of size k. As a result, for one subarray

of size n/2, P(A) and Q(A) will each need n/2 operations. That’s 2*(n/2) operations for a single subarray.

Because there are eight such subarrays, the total number of operations on P(A) and Q(A) combined for all level-1 recursive calls is 8 * 2 * (n/2) = 8n.

Thus, for all level-1 recursive calls, the total number of operations on P(A) and Q(A) is 8n.

4. Repeat that for the all the level-t recursive call. Write your answers in terms of t (if necessary).

Number of Recursive Calls at Level-t:

1. At level-1, we have 8 recursive calls (since a = 8).
2. At each subsequent level, each call spawns 8 more calls. Thus, the total number of calls at level-t is 8^t.

Size of Array at Level-t:

1. At level-1, each call works on an array of size n/2 (since b = 2).
2. At each level, the array size for each call is halved. So, at level-t, the array size for each call is n/2^t.

Operations by P(A) and Q(A) at Level-t:

1. For a single call at level-t, P(A) takes n/2^t operations, and Q(A) takes n/2^t operations.
2. So, for a single call at level-t, total operations for P(A) and Q(A) together is 2 * (n/2^t) = n/2^(t-1).

Total Operations at Level-t:

1. There are 8^t calls at level-t, and each takes n/2^(t-1) operations.
2. Total operations for all calls at level-t for P(A) and Q(A) together is 8^t * n/2^(t-1).

Therefore, the total number of operations for P(A) and Q(A) together for all the level-t recursive calls is indeed 8^t * n/2^(t-1).

5. Let s be the level where the recursive call reached the base case (n=1). Write s in terms of n.

To identify at what recursion level, called ‘s’, the algorithm ends when the array size reduces to 1, the pattern of how the array size gets smaller in each stage of recursion is observed. The algorithm cuts the array size in half at each level because b equals 2.

The array sizes through different levels start at n and go to n/2, n/(2^2), and so on with each next level. The target is to find out the level ‘s’ where this reduction leads to an array size of 1. For this, the following equation is set up:

At level ‘s’, the size is n/2 to the power of s, and this equals 1.

Solving for ‘s’: n = 2^s

Now, take the logarithm (base 2) of both sides: log2(n) = s

So, ‘s’ in terms of n is: s = log2(n)

This means that the level s at which the recursive call reaches the base case (n=1) is the base-2 logarithm of the original array size n.

6. Use all the information from (a) – (e) to calculate the time complexity of the algorithm. Show how you get the results for every part.

The total time complexity of the algorithm, combining both the initial call and the recursive calls, is calculated as follows:

It’s a polynomial of the third degree, so we can say that the time complexity of this algorithm

2. (24 points) Consider tracing the execution of depth first search on the following directed graph, represented as a adjacency matrix. You should use the same convention as of homework 2, with the following convention:

• We start at vertex 1
• At any stage, if there is a choice of edges to be examined (e.g: x->y, x->z), we pick the edge such that y < z.
• If the stack is empty, and there are still vertices that are unvisited, pick the vertex that has the largest number

	1	2	3	4	5	6	7
1							T
2	T
3				T		T
4					T
5	T			T
6	T
7				T	T

(all the entries without T should be viewed as F) (To read this graph, the direction of edges is from row to column, that is there is an edge from v1 to v2, but not from v2 to v1). Use the same table format as homework 2, list as below

Step 1: Examine edge 1->7. This is a tree edge. Stack: 1.

Step 2: Examine edge 7->4. This is a tree edge. Stack: 1 -> 7.

Step 3: Examine edge 4->5. This is a tree edge. Stack: 1 -> 7 -> 4.

Step 4: Backtrack from 5 to 4. Stack: 1 -> 7 -> 4.

Step 5: Backtrack from 4 to 7. Stack: 1 -> 7.

Step 6: Backtrack from 7 to 1. Stack: 1.

Step 7: Start at vertex 6 as the stack is empty and vertex 6 is unvisited. Stack: 6.

Step 8: Start at vertex 3 as the stack is empty and vertex 3 is unvisited. Stack: 3.

Step 9: Start at vertex 2 as the stack is empty and vertex 2 is unvisited. Stack: 2.

Step	Edge to be examined	Edge type	Stack (from bottom to top)
1	1->7	Tree	1
2	7->4	Tree	1 -> 7
3	4->5	Tree	1 -> 7 -> 4
4	5->4	Back	1 -> 7 -> 4
5	4->7	Back	1 -> 7
6	7->1	Back	1
7	–	Start	6
8	–	Start	3
9	–	Start	2

2. (16 points) Now suppose we traverse the graph above using breadth-first search starting at vertex 1, using the same convention as the previous question in choosing edges and vertices.
   1. List the order of the edges being examined.

Edge 1->7

Edge 7->4

Edge 7->5

2. What is the number of vertices in the FIFO queue when it is the longest?

The FIFO queue was longest with 2 vertices.

2. Now consider using the same notion of timestamps as depth first search.
   • The global timestamp starts at 1, and is incremented right after a vertex enter or exit the queue.
   • When a vertex v is inserted into/removed from the queue, the in[v]/out[v] value is assigned with the current global timestamp (after the increment is done).

List the timestamp for each vertex in your traversal.

In and Out timestamps for each vertex are as follows (Vertex: [In timestamp, Out timestamp]):

• Vertex 1: [0, 1] (Start vertex, out timestamp is when it’s dequeued)
• Vertex 2: [0, 0] (Never visited)
• Vertex 3: [0, 0] (Never visited)
• Vertex 4: [4, 6] (Timestamps for queue entry and exit)
• Vertex 5: [5, 7] (Timestamps for queue entry and exit)
• Vertex 6: [0, 0] (Never visited)
• Vertex 7: [2, 3] (Timestamps for queue entry and exit)

Note: A timestamp of 0 indicates the vertex was never in the queue. The in timestamp is when the vertex is added to the queue, and the out timestamp is when it is removed from the queue.

2. (16 points) Consider the following instance of the fractional knapsack problem. Assume weight of knapsack = 22

Object	Weight	Profit
1	8	20
2	15	30
3	5	6
4	10	32
5	1	3
6	22	33

2. Find the optimal solution using the algorithms described. Show your work. (Assume we CANNOT take more than one copy of each object).

Profit-to-weight ratio for each object, backpack weight = 22

Object 1: Profit = 20, Weight = 8, Ratio = 20/8 = 2.5

Object 2: Profit = 30, Weight = 15, Ratio = 30/15 = 2.0

Object 3: Profit = 6, Weight = 5, Ratio = 6/5 = 1.2

Object 4: Profit = 32, Weight = 10, Ratio = 32/10 = 3.2

Object 5: Profit = 3, Weight = 1, Ratio = 3/1 = 3.0

Object 6: Profit = 33, Weight = 22, Ratio = 33/22 = 1.5

Sort these objects based on their profit-to-weight ratio in descending order:

Object 4: Ratio = 3.2

Object 5: Ratio = 3.0

Object 1: Ratio = 2.5

Object 2: Ratio = 2.0

Object 6: Ratio = 1.5

Object 3: Ratio = 1.2

Then we take the items in this order until the backpack weight limit (22) is reached.

Object 4: Weight = 10, Remaining capacity = 22 – 10 = 12, Total Profit = 32

Object 5: Weight = 1, Remaining capacity = 12 – 1 = 11, Total Profit = 32 + 3 = 35

Object 1: Weight = 8, Remaining capacity = 11 – 8 = 3, Total Profit = 35 + 20 = 55

Now the next object in the sorted list is Object 2, but its weight (15) exceeds the remaining capacity (3), so it cannot be taken in its entirety. However, since this is a fractional backpack problem, we can take part of it.

The fraction of object 2 that can be taken is calculated by dividing the remaining capacity of the backpack by the weight of object 2: fraction of object 2 = remaining volume / weight of object 2 = 3 / 15

The profit from this share of Object 2 is calculated by multiplying the share by the total profit of Object 2: Profit from the share of Object 2 = Share of Object 2 * Total profit of Object 2 = 3/15 * 30 = 6.0

Adding this to total profit: Total Profit = 55 + 6 = 61

So the optimal solution is to take all of Object 4, all of Object 5, all of Object 1 and 1/5 of Object 2 for a total profit of 61.

2. Now assume the profit of object 1 is x. (and assume nothing else has changed). Find the range of x such that the whole of object 1 will be selected in the final solution.

To determine the range x (Profit of Object 1) for which all of Object 1 will be included in the final solution of the fractional knapsack problem, it is necessary to determine when the ratio of profit to weight of Object 1 exceeds the ratio of other objects that were selected earlier.

Based on the prior decision, the items were chosen in the following order according to the profit-to-weight ratio: Object 4, Object 5, and finally Object 1. The remaining capacity after these items permitted just a fraction of Object 2 to be accepted.

The profit-to-weight ratio of Object 1 is 8/x​.

The ratio of Object 4 (the highest in the original selection) is 32/10 = 3.2

The ratio of Object 5 (the second-highest in the original selection) is 3/1 =3.0

To make sure object 1 is selected:

For Object 1 to be chosen before Object 5, its ratio must be at least equal to 3.0. We find the minimum value of x for this condition: x/8 > 3.0.

x = 8 * 3.0 = 24.0

For Object 1 to be chosen at least before Object 5, the profit x must be greater than or equal to 24.0.

This means x >= 24.0 ensures that Object 1 has a higher profit-to-weight ratio than Object 5.

For Object 1 to be chosen before Object 4, its ratio must exceed 3.2. We find the minimum value of x for this condition: x/8 > 3.2.

X = 8 * 3.2 = 25.6

For Object 1 to be chosen before Object 4 (and thereby be the first choice), �x must be greater than 25.6. Thus, x > 25.6 ensures that Object 1 is selected first.

In conclusion, if x >= 24.0, then Object 1 definitely will be a part of the final solution. x must be greater than 25.6 in order for it to be selected as the first item.