DECISION

Question 1

A list of n items needs to be sorted into descending order starting at the left-hand entry. Describe how to carry out the first pass of a bubble sort on the numbers in the list.

Answer 1

-In the first pass, we compare the first number with the second and swap them if the second is larger than the first
-We now compare the second number with the third and swap them if the third number is larger than the second number
-We continue this untill we reach the end of the list

Question 2

What is the final step of a sort?

Answer 2

Writing “sort complete”

Question 3

How do you approximate time of an algorithm?
And why is it an approximation

Answer 3

Time = t x f(n2)/f(n1)

The runtime is not exactly proportional to …

Question 4

Graph

Answer 4

A set of vertices connected by edges

Question 5

Degree of a vertex

Answer 5

Number of edges coming out of it

Question 6

Isomorphic

Answer 6

Two graphs are isomorphic if there is a 1:1 correspondance between their vertices which preserve adjacency

Question 7

Subgraph

Answer 7

A graph whose edges and vertices are contained within the original graph

Question 8

Walk

Answer 8

A sequence of connecting edges

Question 9

Trail

Answer 9

A walk in which no edge is listed more than once

Question 10

Path

Answer 10

A walk in which no vertex is visited more than once

Question 11

Cycle

Answer 11

A path that finishes where it started

Question 12

Connected graph

Answer 12

A graph where there is a path between any pair of vertices

Question 13

Simple graph

Answer 13

-no edge begins and ends at the same vertex (no loops)
-no two edges connect the same pair of vertives (no repeated edges)

Question 14

Tree

Answer 14

A conected graph with no cycles

Question 15

Spanning tree

Answer 15

A subgraph that includes all the vertices of the original graph, and is also a tree

Question 16

Minimum spanning tree

Answer 16

A spanning tree with the smallest possible weight

Question 17

Complete graph

Answer 17

A simple, connected graph such that there is an edge between every pair of vertices. We use the standard notation Kn for the complete graph with n vertices
There are 0.5(n)(n-1) edges in the graph Kn

Question 18

Eularian graph

Answer 18

A connected graph with no odd vertices

Question 19

Eularian cycle

Answer 19

A cycle that contains every edge once

Every Eularian graph has an Eularian cycle

Question 20

Hamiltonian cycle

Answer 20

A cycle that passes through every vertex precisely once

Question 21

Hamiltonian graph

Answer 21

A graph that contains a Hamiltonian cyle

Question 22

For any graph…

Answer 22

-The sum of all the degrees is double the number of edges
-There is always an even number of odd vertices

Question 23

For any simple graph…

Answer 23

-The graph can have atmost 0.5n(n-1) edges
-The degree of each vertex is atmost n-1