Algorithms Flashcards
What is the stop condition for a shell sort?
After final shuttle pass where INT(n/2)= 1
Travelling salesman- What is a tour?
Visits vertices once, returns back to the beginning.
What is a Eulerian cycle?
A route that travels along every edge exactly once before returning to the beginning.
For a complete graph of n vertices (Kn), what is the condition for the graph to be Eulerian.?
n must be odd
Under what conditions are the maximum number of swaps and comparisons required to sort a list of numbers using a Bubble or Shuttle sort?
Reverse ordered list
What is a connected graph?
A path exists between every pair of vertices.
Given a choice of upper bounds, how do you select which one is best?
The lowest one.
For a connected graph of n vertices (Kn), how many edges are there in a Hamiltonian cycle?
n
For a complete graph of n vertices (Kn), what is the order of a vertex?
n - 1
What is the STOP condition for a Shuttle sort?
When the end of the list is reached (n - 1 passes)
Shuttle back until no swaps occur or the start of the list is reached.
When finding a Chinese Postman route through a network, how do you find out how many times you pass through a vertex?
Add repeated edges to graph then half order (representing in and out) for that vertex.
Travelling salesman- How do you express the interval within which an optimal tour T lies?
Lower Bound
For a complete graph of n vertices (Kn), how many Hamiltonian cycles are there (assuming tours in reverse order are of the same length?
(n - 1) ! / 2
Which algorithms are greedy?
Prim: always lead to the best solution
Kruskal: always lead to best solution
Nearest Neighbour: does NOT necessarily lead to the best solution and it may not be possible to apply it.
After applying Dijkstra to find the shortest path through a network from start vertex to end vertex, how do you find the shortest path to the other vertices?
Permanent labels at each vertex give length of the shortest path from start vertex.
