University of Toronto
CSC148S--Introduction to Computer Science, Spring 1997
Assignment 2: PAVING IQALUIT

Due:  Thursday March 13, 6:00 pm
This assignment is worth 10 marks towards your final grade.

Note that the diagrams in this handout have not translated well into html. You are advised to refer to the version of the handout that was distributed in class. If you have lost yours, you can make a photocopy from the course folder in the Engineering Library, SF 2304.

Introduction

In the town of Iqaluit on Baffin Island, each of the houses has a number in the range 1 to n, where n is the number of houses. For example, if you get a taxi at the airport and say take me to house 137, the driver will know where to go.

In May, when the snow finally melts, the streets become muddy. But people would still like to visit one another without becoming dirty.

Now for the imaginary part of the story. The municipal government has heard about a new kind of paving material that can withstand the cold temperatures and wants to pave enough road segments so that anyone can visit anyone else by travelling only on paved road segments. However, being fiscally responsible, they want to do this for the minimum possible cost.

A firm of paving engineers have told the planning department how much it would cost to pave each road segment. (A road segment is a piece of road connecting two houses with no other houses along the way.) Note that the cost of a road segment depends on the terrain over which it passes as well as its length. So, a road segment may be expensive to pave even if it is short. It is now the job of the planning department to decide what road segments to pave. You, a newly hired employee of the planning department, have been given the job of writing a program to determine the best solution.

Input Specifications

The input to the program consists of the total number of houses n, the x and y coordinates of the n houses, in order from 1 to n, a list of all road segments, and the cost of paving each. Each road segment is specified by the house numbers of the two houses it connects. There is at most one road segment connecting any particular pair of houses. Two houses that are connected by a road segment are called neighbours. The units and the location of the origin of the coordinate system are not important.

For example, if Iqaluit looked like this:then here is an example of the input file:

Note that, if 4 is the first number in the file, then the next four lines are coordinates of houses 1, 2, 3, and 4, respectively.

The Paving Algorithm

One way to solve the problem is as follows: Start at one particular house, say house 1, and choose the cheapest road segment connecting house 1 to a neighbour. Pave this road segment. Now there are two houses that can be reached from one another by pavement. Next, pick the cheapest road segment among all those that connect one of these two reachable houses to some house that cannot be reached by pavement. Pave it. This increases the number of reachable houses by one. Keep doing this (paving the cheapest road segment that connects a reachable house to a house that is not yet reachable) until all houses can be reached by pavement.

There is some pseudocode describing the paving algorithm more precisely at the bottom of the page.
The variable R denotes the set of road segments the program has decided to pave so far. It is initially empty.
The variables A and B denote sets of houses. No house is in both these sets at the same time.
The houses in B are those which are connected to house 1 using only roads in R. Initially B contains only house 1.
A house is in A if it has a neighbour in B, but is not in B itself. For each house ,

• CostToB(h) is the minimum cost of all road segments between h and houses in B and
• closestBneighbour(h) is a house in B to which there is an unpaved road segment from h of cost CostToB(h).

In other words, the road segment between h and closestBneighbour(h) is the cheapest road segment connecting h to a house in B. and it has cost costToB(h).

%Initialize A.
for each neighbour h of house 1 do
	add h to A
	closestBneighbour(h) := 1
	CostToB(h) := cost of paving the road segment connecting house h and house 1
end for
while A is not empty do
	%pick the next road segment to pave
	remove a house h from A that has the smallest value of CostToB(h)
	add h to B
	add the road segment connecting houses h and closestBneighbour(h) to R
	for each neighbour h' of h
		if h' is not in B then
			c := cost of paving the road segment between h and h'
			if h' is not in A then
				add h' to A
				closestBneighbour(h') := h
				CostToB(h') := c
			else if c < CostToB(h') then
				%update closestBneighbour(h') and CostToB(h') if necessary
				closestBneighbour(h') := h
				CostToB(h') := c
			end if
		end if
	end for
end while

An Abstract Data Type for Information About Iqaluit

The program will have to store information about the town of Iqaluit, such as the number of houses and which houses have road segments between them. It will also have to perform operations on this data. Some of these operations will be general purpose, for example, returning the coordinates of a given house. Other operations are particularly useful for implementing the paving algorithm, for example ``given a house h, consider each neighbour h' of h in turn and find the cost of paving the road segment between h and h'''. The following abstract data type describes this data, properties of it, and operations performed on it.

DATA AND PROPERTIES OF THE DATA:
houses

• Each house has a number, an x coordinate, and a y coordinate.
• House numbers are positive integers.
• x and y coordinates are integers.
• Each house has a different number in the set , where n is the number of houses.
• No two houses have both the same x coordinate and the same y coordinate.

road segments

• Each road segment is a set of two houses.
• For each road segment r, the nonnegative integer cost(r) is the cost to pave road segment r.

OPERATIONS:

GetAnotherNeighbour(h,h',c)

Given a house h, return a neighbour h' of h that has not been returned (since the operation BeginGettingNeighbours(h) was last performed). If there is no such neighbour, h' is the dummy house with number 0. When h' is not the dummy house, the cost c of paving the road segment connecting h and h' is also returned.

BeginGettingNeighbours(h)

This has to be called before GetAnotherNeighbour(h,h',c) is called for the first time. It can also be called if you want to go through the complete set of neighbours of h again.

ReadInfo

Initializes the data structure by reading information about Iqaluit from a file.

HouseCoords(h, x, y)

Given a house h, return its x and y coordinates.

NumberOfHouses

Returns the number of houses in Iqaluit.

Cost(h,h')

Returns the cost of paving the road segment between houses h and h'.

Free

Frees any memory that was created by Iqaluit. It is good practice to include such an operation in your ADT and to perform it when you are completely finished using the data.

Your Tasks

1. (Implement the ADT for Information about Iqaluit) Consider a data structure that consists of a positive integer n and an array of n records. The ith record contains the x and y coordinates of house number i and an unsorted singly linked list containing information about all of its neighbours. Each element of this linked list contains the house number of one neighbour and the cost of paving the road segment to that neighbour. An example of this data structure is illustrated at the top of page 4.

   Write a module using this data structure to implement the abstract data type described above. We would also suggest that, for debugging purposes, you write a subprogram to print out the information about Iqaluit stored in the data structure.

   

2. (Describe the ADT for A) Write an abstract data type that describes A and the operations that must be performed on it for use by the paving algorithm given on page 2. Specifically, list the data, properties of the data, and the operations. Be sure NOT to describe how it is going to be implemented.
3. (A simple implementation of your ADT for A) Design a simple data structure for implementing your abstract data type in part 2. Do not be concerned about efficiency. Write a module to implement your data structure.
4. (A more efficient implementation of your ADT for A) The following data structure, although more complicated, leads to a faster implementation of the paving algorithm. It consists of a binary tree T, an integer a, and an array H of size n, where n is the number of houses in Iqaluit. There is one node in T for each house in A. The integer a denotes the number of houses in A, which is equal to the number of nodes in the binary tree T. The array H is used to quickly access the node in T corresponding to a particular house in A. Specifically, if i is the number of a house in A, then H[i] is a pointer to the node in T containing the house with number i; otherwise H[i] is nil.

   Each node in the binary tree T contains pointers to its parent node, its left child node, and its right child node, if they are present. The node corresponding to house h contains the following information: the house number of h, the house number of closestBneighbour(h), and CostToB(h).
   Furthermore, the binary tree T must satisfy the following properties:

   (i)

   For every pair of nodes h and h', if node h is an ancestor of node h',
   then .

   (ii)

   The depths of any two leaves differ by at most one.

   (iii)

   If h is not a leaf, then all nodes at depth less than h have two children.

   (iv)

   If h is not a leaf, then all nodes at the same depth as h, but further left, have two children.

   Here is an illustration of this data structure. Note that, in this small example, the binary tree T doesn't look much like a tree, because it only contains two nodes.

   

   Write a module using this data structure to implement your ADT in part 2 .

   HINTS:

   • Draw some pictures of binary trees that satisfy the four properties and draw some pictures of binary trees that do not.
   • This data structure is quite different from the binary search tree discussed in class. Don't confuse them.
   • How can you determine from the value of a how many nodes are in T's left subtree and how many are in T's right subtree?
   • How can you determine which subtree contains the rightmost leaf in the bottom level?
   • To make the problem simpler (but for a small reduction in marks), at each node of T, you can store a count of the number of nodes in the subtree rooted at that node. You might start by including this extra information at each node and then later removing it, thereby making your data structure more space efficient.
5. (Implement the Paving Algorithm) Implement the paving algorithm given above, using the modules you have written above. As part of this implementation, you must decide what data structures to use to represent B and R. You are not required to use modules to implement them, but you may if you wish.

   Note that you can implement the paving algorithm before implementing the data structure described in part 4. However, the signature of your modules in parts 3 and 4 must be the same so that you can use them interchangeably.

   HINT: you should try running the paving algorithm by hand on a number of examples to make sure you understand what it is doing before you try to write ANY code.

6. (BONUS) Write a subprogram that uses graphics to draw a map of Iqaluit indicating the roads that the program determined should be paved. Identify and justify the decisions you make in designing your subprogram and designing the way the output is presented.

What to Hand In

A written solution for part 2
A written description of your data structure and algorithms for part 3
A written description of the algorithms used in part 4
A written description of the data structures used to represent B and R in part 5
A written discussion of design decisions made in the bonus question
For your modules in parts 1, 3, and 4, the program in part 5, and the bonus question:

• printouts of your code
• input and output for all your test cases
• explanation of the testing you have performed
• description of any limitations

Make sure that your comments include good English descriptions of all subprograms and their parameters. Also, for each module, you should put its signature and its implementation in different files.

Tentative Grading scheme

Below is the tentative grading scheme. Although we reserve the right to change it somewhat, it should give you an idea of where to focus your efforts.