Homework answers / question archive / Question 1:Question 2:For example, for ? = 10, ? = 4 and the following charging locations (underlined) You are given two ?-bit binary strings and your goal is to verify whether they are identical or not

Question 1:Question 2:For example, for ? = 10, ? = 4 and the following charging locations (underlined) You are given two ?-bit binary strings and your goal is to verify whether they are identical or not

Computer Science

Share With

Question 1:Question 2:For example, for ? = 10, ? = 4 and the following charging locations (underlined) You are given two ?-bit binary strings and your goal is to verify whether they are identical or not. Design an exact procedure, show its correctness, and show pseudo-code for this purpose. What is the complexity of your procedure? If you can tolerate some error, e.g., 10-4, can you design a better-than-linear-time solution and write its pseudo-code?

 Professor ? drives Tesla to travel from city ? to city ?. The distance between cities ? and ? is ? miles. The Tesla can go up to ? miles before it needs a charge and there are many charging locations along the way including those in ? and ?. Professor ? wants to minimize the number of charges needed so he can get to the destination the soonest. Assume that at any charging location there is at least another charging location within a ?-mile radius.

(?)1 2 3 4 5 6 7 8 9 10 11

(?) the numbers of charges needed is 2 (at #4 and #8).

Professor ? promises to give you an A in his class if you can design a procedure to help him to archive the goal. Does your procedure provide an optimal solution? Why or why not? show pseudo-code fr your procedure. Show its correctness and complexity. (Note: I am not Professor ? and I do not drive a Tesla).

Question 3: Amazon.com is renting local trucks to deliver packages in the early morning and afternoon shifts. Each zone of the city needs several trucks and those numbers are estimated and provided to the manager at 11:59 pm daily. The manager will then rent enough trucks for the early morning shift and reuse them for the afternoon shift. Note that each zone must be completely covered in either shift.

For examples, if the city has 4 zones and their truck requirements, in this order, are 1, 6, 11 and 5, the manager could rent 16 trucks to deliver packages in zones #3 (11 trucks) and #4 (5 trucks) in the morning shift and reuse 7 trucks to cover zones #1 (1 truck) and #2 (6 trucks) in the afternoon shift. However, he would leave 9 trucks unused in the afternoon shift. Alternatively, the manager could have rented 12 trucks to cover zones #1 (1 truck) and #3 (11 trucks) in the morning and reuse 11 trucks to deliver packages in zones #2 (6 trucks) and #4 (5 trucks). In this plan, he would only have 1 truck left unused. Note that 12 is also the minimum number of trucks needed.

You are interviewed to help the manager to rent the minimum numbers of trucks for daily delivery. Don't you want to be hired? So, what procedure would you design to help the manager? Does your procedure provide an optimal solution? Why or why not? show pseudo-code fr your procedure. Show its correctness and complexity.

Question 4: In a graph ?, an edge (?, ?) is called good if all other vertices of G are adjacent to both ? and ?, i.e., connected to both ? and ? via edges. Assume that ? is a clique of size ? (i.e., a complete graph of ? vertices), what is the least number of edges to be removed from ? so that it contains NO good edges. Present and analyze the complexity of your procedure. Does your procedure return the least edges to be deleted? Why and/or why not?