Python coding questions

By

Question 3 (25 marks)

This question is about graphs and their algorithms (Unit 5 Section 2 and the Companion). 

Consider an ADT for undirected graphs, named UGraph, that includes these operations:
nodes, which returns a sequence of all nodes in the graph, in no particular order
has_edge, which takes two nodes and returns true only if there is an edge between those nodes
edges, which returns a sequence of node-node pairs (tuples), in no particular order. Each edge only appears once in the returned sequence, i.e. if the pair (node1, node2) is in the sequence, the pair (node2, node1) is not.

How each node is represented is irrelevant. Because the graph is undirected, has_edge(node1, node2) and has_edge(node2, node1) return the same. You can assume the graph is connected and has no edge between a node and itself.

More to Read:
Adjacency matrix
This part is about algorithmic complexity (Unit 2 Section 4.1and Companion)

The following stand-alone Python function checks if an undirected graph is complete, i.e. if each node is connected to every other node. It assumes the ADT is implemented as a Python class.

defis_complete(graph):
  nodes = graph.nodes()
  for node1 in nodes:
     for node2 in nodes:
       edge_exists = graph.has_edge(node1, node2)
       if node1 != node2 and not edge_exists:
         return False
  return True
Assume that nodeshas complexity O(n), where n is the number of nodes, and graph.has_edge has complexity O(1). State and justify a best-case scenario and a worst-case scenario for the above function. State and explain the Big-O complexity for each scenario. Assume the basic computational step is the assignment. State explicitly any other assumptions you make. (7 marks)
This part is about ADT specifications (Unit 2 Section 3.6and Companion).

In graph theory, the number of nodes in a graph is called the order of the graph. The term ‘order’ is unrelated to sorting. Specify the problem of computing the order, as a UGraph operation.

Creator / Inspector / Modifier (delete as appropriate): order
Inputs:
Preconditions:
Outputs:
Postconditions: 
Justify the kind of operation. (5 marks)
This part is about initial insights (Unit 2 Section 2.3and Companion).

Give your initial insight for an algorithm that solves the order problem. You can use any of the M269 data structures listed in the Companion’s appendix but of the ADT operations given above you may only use edges. (4 marks)

A city council is planning the city’s bus routes. It has decided which places will have a bus stop (schools, cinemas, hospital, etc.). Each bus route will start from the train station, visit a number of bus stops, and then return to the station, visiting the same bus stops in reverse order. Each bus stop has to be served by at least one bus route. The council wants to minimise the total amount of time that all buses are on the road when following their routes.

This problem can be solved by first defining a graph and then applying to it a graph algorithm to obtain the answer.

This part is about modelling with graphs (Companion).

Define a graph that is suitable for this problem, by addressing the following questions. Justify your answers. Explicitly state any assumptions you make.

What do the nodes and edges represent?
Are edges directed? If so, what does the direction represent?
Are edges weighted? If so, what do the weights represent?
Is the graph acyclic or cyclic?
Is the graph dense or sparse? (6 marks)
This question is about graph algorithms (Unit 5 Section 2and the Companion).

What algorithm(s) would you adopt or adapt to efficiently compute the bus routes according to the council’s criterion? You do not need to explain any algorithm given in M269, only how it could be used or modified to solve the problem. State explicitly any assumptions you make. (3 marks)

 

Last Updated on January 29, 2025

How to create Testimonial Carousel using Bootstrap5

Clients' Reviews about Our Services