Algorithm and complexity questions

 Hello there, I have done the first question but stuck in other. Could you please help me?

Thank you

Assessment 3 HIT220

cat.kutay

September 2020

1

Rubric

1. Pseudo code should be written according to guidelines supplied at
https://www.geeksforgeeks.org/how-to-write-a-pseudo-code/.
If there is no structure or the explanation is at too high a level to implement directly in code your
pseud code is not sufficient.

2. This document is available https://www.overleaf.com/read/jmczmkhsnfzc

3. Submit as a pdf on Learnline

4. Hand drawings can be scanned and inserted

5. Marking rubric for each question:
Marks will be awarded for accuracy, completeness, and well communicated reasoning which demon-
strates your depth of understanding of the subject matter.
Unless otherwise divided up marking is:

• Half marks will be given for right answer
• Half marks will be given for working shown with verbal explanation of working

Note: For proving and disproving include an example where you look at how the claim works with
a specific set

All question totals are shown

2 Questions

1. (6 points) Graphs and Trees

a) 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?

b) Is it possible to draw a connected graph with n vertices and n edges but no cycles? Explain your
answer.

c) Draw a simple Graph G, which is a Forest that has 12 vertexes and at least 8 edges.

d) How many connected components does graph G have? How does this relate to the number of
vertices and edges?

e) 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?

1

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.
Provide pseudo code to provide a topological sort for the graphs given (this may not generalise)

3. (6 points) Shortest Path
Apply Dijkstra’s Algorithm to each of the graphs shown below. Include the table of vertex labels at
each stage and draw the spanning tree. Use the alphanumeric conventions for ordering of the vertices
and start the algorithm at the smallest vertex.

Page 2

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.

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).

A. Operation: Find the degree of a single vertex whose graph is stored in an adjacency matrix.
Explain your answer.

B. Operation: Find the opposite vertex of u along the edge e in a graph which is stored in an
adjacency list. Explain your answer.

Page 3

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.

a) Sort the list using selection sort.
Provide the pseudo code

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.
Provide the pseudo code

c) What is the worst-case runtime complexity of selection sort?

d) What is the worst-case runtime complexity of heap sort?

Page 4