CS 2420 – Fall 2006
Assignment 5 – 20 points
Due Oct 11, 2006
Railroad Tycoon – Part II
Story Line:
It’s still a wild frontier out there, in the Australian Outback (see the previous assignment). And you still need to get a set of railroad lines in place. And because money is still an important thing in your life, you want to make your railroad lines for as little money as possible.
Designing railroads with Prim’s Algorithm using a linear search to find the min-cost edge to add to the tree is a somewhat time-expensive operation, though. That’s why you are going to employ your new secret weapon: Priority Queues.
Objective:
Given a set of towns, their locations, and their elevations, write a function that designs a railroad network designed to service each town at minimum cost, using a min-cost spanning tree algorithm based on priority queues. For this assignment, you must write your own priority queue code. Thou shalt borrow not from the book, nor from the standard template library, nor from any other source, save your brain(s).
Details, details:
You are to read from standard input a list of towns, followed by three integers describing an x and y coordinate (in kilometers), and an elevation (also in kilometers):
<town name> <x coordinate> <y coordinate> <elevation>
The last town in the list is always called “Zaboonaboon.”
You may assume a maximum number of 50 towns, if you wish.
The cost to create a railroad between two points can be determined by the following equation:
cost(k$) = distance + (10 * distance * sine(elevation_angle) )
For example, two towns 1km from each other on the same elevation could be joined by a railroad for a cost of 1 Australian kilodollar, but two towns 1km from each other with a height different of 100 meters would cost roughly 1.995 Australian kilodollars.
Your function should be given an array of coordinates and elevations, plus an (empty) adjacency array (plus whatever else you need). It should fill in the adjacency array with the designed railroad system and return the cost needed to build it. Your program should print to standard output the resulting adjacency array.
Following the list of towns is a set of town pairs, coming from standard input. Your program should read in each pair and print out to standard output the distance along your railroad system from one to the other, along with the names of the cities visited along the way. The last destination in the list of town pairs is always “Zaboonaboon,” which appears nowhere else in the list.
Questions:
1. Draw the binary expression tree for the expression
2. What is the maximum number of nodes in a binary tree that has n nodes?
3. Execute the following sequence of operations on an initially empty binary search showing the tree after each operation:
Insert(10); Insert(100); Insert(30); Insert(80); Insert(50); Delete(10); Insert(60); Insert(70); Insert(40); Delete(80); Insert(90); Insert(20); Delete(30); Delete(70);
4. The nodes of a binary tree are labeled a–h. The preorder listing is abcdefgh, and the inorder listing is cdbaghef. Draw the binary tree. Also, list the nodes of your binary tree in postorder and level order.
What to turn in:
Include a short narrative of your program in with your report, including the questions, and describe one set of results garnered from it. Turn in your source code along with your report in a zipped archive.
Examples:
For the following set of towns, locations, and elevations:
Boongalla 1383 886 777
Coocoobyrnie 915 1793 2335
Wangalawa 1386 492 2649
Fangbooboo 1421 362 1027
Stubbyhand 690 59 1763
Sheilaville 1926 540 426
Plax 1172 1736 1211
Gatorcreek 1368 567 429
Yangboola 1782 1530 1862
Billabong 1123 67 1135
Chikamakagalwallawalla 1929 1802 2022
X 1058 1069 1167
Flitcairn 1393 456 2011
Walkaboutcanyon 42 229 2373
Killdunnen 421 919 1784
Mercy 537 1198 2324
Millpick 315 370 413
Zoe 1526 91 980
Cawbillabilla 1956 1873 1862
Zaboonaboon 1170 996 2281
My program (which has not been independently verified) came up with:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0
Total cost: 22445.9 kiloDollars
And for the set of pairs:
Sheilaville Billabong
Wangalawa Fangbooboo
Walkaboutcanyon Fangbooboo
Sheilaville Yangboola
Mercy Cawbillabilla
Fangbooboo Walkaboutcanyon
Chikamakagalwallawalla Plax
Killdunnen Walkaboutcanyon
Sheilaville Coocoobyrnie
Boongalla Fangbooboo
Walkaboutcanyon Zaboonaboon
My program found:
Sheilaville -> Gatorcreek -> Wangalawa -> Flitcairn -> Fangbooboo -> Billabong
Wangalawa -> Flitcairn -> Fangbooboo
Walkaboutcanyon -> Mercy -> Zaboonaboon -> X -> Billabong -> Fangbooboo
Sheilaville -> Gatorcreek -> Wangalawa -> Flitcairn -> Chikamakagalwallawalla -> Cawbillabilla -> Yangboola
Mercy -> Zaboonaboon -> X -> Billabong -> Fangbooboo -> Flitcairn -> Chikamakagalwallawalla -> Cawbillabilla
Fangbooboo -> Billabong -> X -> Zaboonaboon -> Mercy -> Walkaboutcanyon
Chikamakagalwallawalla -> Flitcairn -> Fangbooboo -> Billabong -> X -> Plax
Killdunnen -> Yangboola -> Cawbillabilla -> Chikamakagalwallawalla -> Flitcairn -> Fangbooboo -> Billabong -> X -> Zaboonaboon -> Mercy -> Walkaboutcanyon
Sheilaville -> Gatorcreek -> Wangalawa -> Flitcairn -> Fangbooboo -> Billabong -> X -> Zaboonaboon -> Mercy -> Coocoobyrnie
Boongalla -> Zaboonaboon -> X -> Billabong -> Fangbooboo
Walkaboutcanyon -> Mercy -> Zaboonaboon
CS 2420 – Assignment 5 Page 1