QUESTION 6

Study the following problem statement and answer the following questions:

A new student has arrived in the town. He will be studying in Faculty of Computer Engineering located nearby to the towns hall. He had settled down in an apartment at the other side of the town.

In order to commute, the student goes to the public transport office to identify way of commuting in the town. He has identified five places that he will frequently visit: his apartment, the faculty, the university main office, market and student caf. Below is list of public transport available between these places:

Transportation	Destination 1	Destination 2	Bus Fee /doIlar)
Bus Route A	Apartment	Faculty	8
	Faculty	Main Office	4
	Faculty	Student Cafe	7
	Market	Apartment	3
Bus Route B	Student Cafe	Main Office	2
	Market	Faculty	6
Bicycle	Apartment	Student Cafe	1

a) Draw a graph to represent these destinations and the travelling cost. The graph should be bidirectional. (8 marks)

b) Using Greedy ADT, find the travelling route find the travelling route to all places with minimum cost. Show your steps. State the minimum cost AND the final graph of the route. The data are not in sorted order. (7 marks)

c) Name the algorithm that being used in 6b). (1 mark)

d) What problem is solved by algorithm in 6c)? (1 mark)