ECE 606 W2016 Assignment 1

Answer the following questions showing all of your work and explaining your reasoning. The writeup should be written in a word processor or using LaTeX. Whatever approach you use please be as neat as possible. You must hand in your own work, there are no group assignments in this course. You may discuss with others the problem and ideas for solutions but you must work out the final solution independently and write it out yourself.

Question 1: (6 points)

Consider the following heap in both tree and array representation below:

Figure 1: Example of a heap.

1. Give the array representation of the heap.
2. Fill out the array representation for the heap after a single element 7 is added.
3. Starting from the original heap again, fill out the array representation for the heap after the element 13 is deleted. Was Heapify-Up or Heapify-Down used?

Question 2: (10 points)

Some friends of yours work on wireless networks, and they’re currently studying the properties of a network of n mobile devices. As the devices move around they define a graph at any point in time as follows: there is a node representing each of the n devices, and there is an edge between device i and device j if the physical locations of i and j are in range of each other which means they are no more than 500 metres apart.

They’d like it to be the case that the network of devices is connected at all times. So they’ve constrained the motion of the devices to satisfy the following property:

• at all times, each device i is within 500 metres of at least n/2 of the other devices.

We will assume n is even to keep it simple.

2

What they’d like to know is: Does this property by itself guarantee that the network will remain connected? Here’s a concrete way to formulate the questionsa s a claim about graphs:

• Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has degree at least n/2, then G is connected.

Decide whether you think this claim is true or false, and give a proof of either the claim or it’s negation.

Question 3: (10 points)

There’s a natural intuition that two nodes that are far apart in a communication network, (i.e. they are seperated by many hops), have a weaker connection than two nodes that are close together. There are a number of algorithmic results that are based to some extend on different ways of making this notion precise. Here’s on that involves susceptibility of paths to the deletion of nodes.

Suppose that an n-node undirected graph G = (V,E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s − t paths. In other words, the graph obtained from G by deleting node v contains no path from s to t.

Give an algorithm with running time O(m+n) to find such a node v. Prove that the algorithm will produce will always find the node v.

Question 4: (10 points)

Your friend is working as a camp counselor organizing a mini-triathalon for high school students. Each contestant must swim 20 laps of a pool, then bike 10 km and then run 3km. The plan is to send the contestants out in a staggered fashion, with the following constraint: the contestants may only use the pool one person at a time. In other words, first one contestant swims the 20 laps, gets out, and starts biking. As soon as this first person is out of the pool, a second contestant begins swimming the 20 laps. As soon as he or she is out of the pool and starts biking, a third contestant begins swimming...and so on.

Each contestant has a projected swimming time (the expected time it will take him or her to complete the 20 laps), a projected biking time (the expected time it will take him or her to complete 10 km of bicycling), and a projected running time (the time it will take him or her to complete the 3km of running). Your friend wants to decide on a schedule for the triathalon: an order in which to sequence the starts of the contestants. Let’s say that completion time of a schedule is the earliest time at which all contestants will be finished with all three legs of the triathalon, assuming they each spend exactly their projected swimming, biking and running times on the three parts. Again, note that contestants can bike and run simultaneously and possibly pass each other, but at most one person can be in the pool at any time. What’s the best order for sending people out, 3

it one wants to the whole competition to be over as early as possible? More precisely, give a description of an efficient algorithm that produces a schedule whose completion time is as small as possible. Be sure to argue what is the algorithms runtime complexity prove the algorithm is correct. To prove this is, you should be able to prove this using an exchange argument.