CS 130B HW 2 Type up

Question 1:     Rmk:Question 2:Input:  dollars, bank  ,  , and fraction of amount kept for each bank  Output: maximum am

Question 1:

Rmk:

Question 2:

• Input: dollars, bank , , and fraction of amount kept for each bank
• Output: maximum amount of money that can be transferred.
• The algorithm is then going to be a slight modification of Dijkstra's Algorithm, with the only difference being how the weight of each vertex is calculated.
• In our algorithm, the weight of a vertex is calculated by .
• Additionally, while the classical Dijkstra pops the vertex with the minimum weight from the priority queue, here we pop the vertex with the maximum weight (because it corresponds to our remaining balance).
• return

b) The algorithm terminates because for each round, it adds a vertex to the list of vertices that has been visited. So the unvisited vertices will eventually run out and there's nothing to be added to the priority queue.

Correctness: It suffices to show our algorithm never makes a mistake (in the sense that always labels the vertex it visits--not the ones whose distance are upper bounded, but the ones that have been actually visited-- with the correct distance). The base case holds trivially. Then by induction, suppose it hasn't made a mistake on the i-th round, by the greedy nature of our algorithm, the (i+1)-th vertex it chooses to label must be correct . Since if it is not correct, then there must be some path to it that cost less the one which our algorithm has chosen, but the reason our algorithm didn't choose that path is because no unvisited vertex has cost smaller than that between our starting point and the (i+1)-th vertex (which is chosen by our algorithm at this round).

c) It should be clear that the complexity of our algorithm is the same as Dijkstra. .

Question 4:

a)Alg: ( )

• Input: numbers , distance .
• Output: number of pairs of people who live at most apart.
• Store in an array and sort it.
• Let be the counter of pairs of people that are at most distance apart
• Let (as global variables)
• Loop until :
• Increase by one each time as long as and . Then decrease by one (because it is one beyond the distance range).
• 
• if : . (this is the situation when our window of size at most cannot include any person other than the person at its left endpoint).
• else:
• Output

b) Proof:

For each loop, we start with the person and keep increasing by one until . After decreasing by one from there, we know for sure that all people that are both 1)to the right of 2) is at most distance from , has been added to our output . The people who are 1)to the left of 2) at most distance from , has been previously counted, so there's no need to count them.

In a slightly concise way, we could express the above paragraph in one sentence:

where means the th person instead of the distance.

Since the loops terminates only when , we have cover the entire range , so we have included every pair possible and have not over-counted. Therefore, the algorithm is correct.

c)

Sorting the array:

Going through loop:

Total: