Algorithm and time complexity

Assessment 3 HIT220

cat.kutay

September 2020

1 Rubric

2 Questions

1. (6 points) Graphs and Trees

1 mark Draw three small example connected graphs, each of which has n vertices and n-1 edges. Vary the value of n for each example. What kind of graphs are these? Spanning tree

1 mark Is it possible to draw a connected graph with n vertices and n edges but no cycles? Explain your answer. In an undirected graph with the same number of edges as vertices, there will always be a loop, regardless of whether it is a self-loop or cyclic path across multiple vertices. In a directed graph it is possible.

1 mark Draw a simple Graph G, which is a Forest that has 12 vertexes and at least 8 edges. Correct graph

2 mark How many connected components does graph G have? How does this relate to the number of vertices and edges? If it is a Simple Graph, then it will have zero parallel edges or self-loops, else it is not a Simple Graph. Also, a forest is made of trees, which have no cycles. . . so no self-loops or parallel edges there either. The minimum number of edges for an undirected connected graph is (n-1) edges. So for every separate component there is at most one less edge

1 mark If the sum of the degree of all vertex is 24 in a graph with 12 vertices, what else can we say about the graph? Given that information, we can tell that the Graph will have 12 edges.

2. (6 points) Topological Sort List a topological order for the following graphs. When you have a choice of path, choose the lower alphanumeric vertex. 2 marks a. 4, 3, 5, 2, 1, 6, 7 2 marks b. e, d, a, g, b, c, f Provide pseudo code to provide a topological sort for the graphs given (this may not generalise) Using code given in lecture you need to comment and expand 2 marks

Algorithm topologicalDFS(G)

//Input dag G

1

//Output topological ordering of G

n = G.numVertices();

for i in range(1,n)

\\set each vertex then visit

setLabel(G.vertices(i), 0)

for i in range (1,n)

v=G.vertices(i)

if getLabel(v) = 0

topologicalDFS(G, v)

Algorithm topologicalDFS(G, v)

//Input graph G and a start vertex v of G

// Output labeling of the vertices of G in the connected component of vertex v

setLabel(v, 1)

for e in range (1,m)

//find G outEdges from v

if G(v,m)>0:

//outgoing edges

w = opposite(v,e)

if getLabel(w) = 0

// e is a discovery edge

topologicalDFS(G, w)

else

// e is a forward or cross edge

// Label v with topological number n

v.order=n

n = n - 1

//specify how you will story - effects efficiency

G.edges = matrix[n x m]//pos (or negative) for direction

G.vertices=[a,b,c...j] //example

topologicalDFS(G);

for i in range (1,n):

print (G.vertex(i),G.vertex(i).order)

3. (6 points) Shortest Path Apply Dijkstra’s Algorithm to each of the graphs shown below. Include the table of vertex labels at

Page 2

each stage and draw the spanning tree. Use the alphanumeric conventions for ordering of the vertices and start the algorithm at the smallest vertex.

1.5 mark

1.5 mark

Page 3

1.5 mark

Page 4

1.5 mark

4. (6 points) Matrix Graphs Use the following graph for this problem.

a) Draw both the adjacency matrix and adjacency list representations of the graph (A) and (B) above. [1 mark each]

Page 5

[1 mark each]

Page 6

b) For graph (A), what is the worst case big-O running time of the following operations (use V and E rather than N in your answers).

1 mark Operation: Find the degree of a single vertex whose graph is stored in an adjacency matrix. Explain your answer. O(v) – Accessing the row for the vertex, check each column to see if the corresponding vertex is tagged as adjacent, counting them as we go.

1 mark Operation: Find the opposite vertex of u along the edge e in a graph which is stored in an adjacency list. Explain your answer. O(v + e) – Worst Case: To find the opposite vertex of u, we must potentially check every vertex in the adjacency list, and for each of those vertices we must check their edge list looking for the edge e

5. (6 points) Sorting Use the following sequence as the list to sort: [ M,A,U,N,G,K,P,R,T,J,Y] You need to display the contents of the list during the execution of the algorithm. 2 marks

a) Sort the list using selection sort.

[ M,A,U,N,G,K,P,R,T,J,Y]

[ A,M,U,N,G,K,P,R,T,J,Y]

[ A,G,U,N,M,K,P,R,T,J,Y]

[ A,G,N,U,M,K,P,R,T,J,Y]

[ A,G,K,U,M,N,P,R,T,J,Y]

[ A,G,J,U,M,N,P,R,T,K,Y]

[ A,G,J,M,U,N,P,R,T,K,Y]

[ A,G,J,N,U,M,P,R,T,K,Y]

[ A,G,J,K,U,M,P,R,T,N,Y]

[ A,G,J,K,M,U,P,R,T,N,Y]

[ A,G,J,K,N,U,P,R,T,M,Y]

[ A,G,J,K,M,P,U,R,T,N,Y]

[ A,G,J,K,M,N,U,R,T,P,Y]

Page 7

[ A,G,J,K,M,N,R,U,T,P,Y]

[ A,G,J,K,M,N,P,U,T,R,Y]

[ A,G,J,K,M,N,P,T,U,R,Y]

[ A,G,J,K,M,N,P,R,U,T,Y]

[ A,G,J,K,M,N,P,R,T,U,Y]

Provide the pseudo code 1 mark

def selectionSort(list):

//run through list and swap right side if < left hand side

size= length (list)

//find number of steps

for i from 0 to size:

// step through the list with left of list[i] sorted

for j from i+1 to size:

//find an item to the right that is < and swap

min=list[j]

if list[j]<list[i]:

swap(list[i], list[j])

//when swapped, the swapped item is the new min

b) Sort the list using heap sort. You do not need to draw the heap diagram unless you find it helpful, but you must still show the contents on the list during execution. 2 marks

//reheap from bottom

[ M,A,U,N,G,K,P,R,T,J,Y]

[ M,A,U,N,Y,K,P,R,T,J,G]

[ M,A,U,T,Y,K,P,R,N,J,G]

[ M,Y,U,T,A,K,P,R,N,J,G]

[ M,Y,U,T,G,K,P,R,N,J,A]

[ Y,M,U,T,G,K,P,R,N,J,A]

[ Y,T,U,M,G,K,P,R,N,J,A]

[ Y,T,U,R,G,K,P,M,N,J,A]

//swap top value and sort down

[ A,T,U,R,G,K,P,M,N,J|Y]

[ U,T,A,R,G,K,P,M,N,J|Y]

[ U,T,P,R,G,K,A,M,N,J|Y]

//swap and reheap

[ J,T,P,R,G,K,A,M,N|U,Y]

[ T,J,P,R,G,K,A,M,N|U,Y]

[ T,R,P,J,G,K,A,M,N|U,Y]

[ T,R,P,N,G,K,A,M,J|U,Y]

[ J,R,P,N,G,K,A,M|T,U,Y]

[ R,J,P,N,G,K,A,M|T,U,Y]

[ R,N,P,J,G,K,A,M|T,U,Y]

[ R,N,P,M,G,K,A,J|T,U,Y]

[ J,N,P,M,G,K,A|R,T,U,Y]

[ P,N,J,M,G,K,A|R,T,U,Y]

Page 8

[ P,N,K,M,G,J,A|R,T,U,Y]

[ A,N,K,M,G,J|P,R,T,U,Y]

[ N,A,K,M,G,J|P,R,T,U,Y]

[ N,M,K,A,G,J|P,R,T,U,Y]

[ J,M,K,A,G|N,P,R,T,U,Y]

[ M,J,K,A,G|N,P,R,T,U,Y]

[ G,J,K,A|M,N,P,R,T,U,Y]

[ K,J,G,A|M,N,P,R,T,U,Y]

[ A,J,G|K,M,N,P,R,T,U,Y]

[ J,A,G|K,M,N,P,R,T,U,Y]

[ G,A|J,K,M,N,P,R,T,U,Y]

[ A|G,J,K,M,N,P,R,T,U,Y]

[ A,G,J,K,M,N,P,R,T,U,Y]

Provide the pseudo code\\

1 mark\\

heapsort(data[])

//sort largest to top of tree

from i= = n / 2 - 1 to 0:

restore max heap (data[i:n];

head = data[0]

for i from length (data.length-1) to 2

swap (data[i],head);

//max element is now on right of array, so sorted

//sort rest of array

restore max heap (data[0:i-1])

restore max heap(data[]):

{

largest = data[0];

for i = length(data)-1 to 0:

//while child > parent

while heap[i] > heap[i/2]:

heap[i], heap[i/2] = heap[i/2], heap[i]

// Recursively heapify the affected sub-tree

restore max heap(data[n, i/2]);

}

.5 mark What is the worst-case runtime complexity of selection sort? O(n2) n=11, so O = 121 Worse case occurs when series in reverse order

.5 mark What is the worst-case runtime complexity of heap sort? O(n log n) as for all divide and conquer=11 do O=11 x 3.5 approx

Page 9