u5

Question 1

optimisation problem

Answer 1

one in which the task is to find the best possible solution

Question 2

priority queue

Answer 2

each item has a priority and items are kept sorted with the highest priority item at the front.
•When a new item is added it is inserted at its correct position in the priority order.
•The priority of an item in the queue maybe changed, whereupon the queue will be reordered

Question 3

Graphs

Answer 3

A graph is a set of verticesor nodes, together with a set of edgesor arcs, each connecting one vertex to another. Edges may have weights.
•If V is the set of vertices in a graph, then |V| is the number of vertices.
•If E is the set of edges, then |E| is the number of edges.

Question 4

digraph or directed graph

Answer 4

a graph in which each edge has a direction

Question 5

complete graph

Answer 5

has an edge between every pair of vertices

Question 6

sparse graph

Answer 6

few edges(vertices have few neighbours)

Question 7

dense graph

Answer 7

has many edges (vertices have many neighbours).

Question 8

general tree

Answer 8

an empty tree or a root with 0 or more subtrees

Question 9

Depth-first search

Answer 9

starts at a specified vertex and explores as far as possible along each branch before backtracking.
•Depth-first search is what happens automatically by recursively iterating over neighbours.
•Vertices are marked to avoid visiting them more than once.

Question 10

Breadth-first search

Answer 10

starts at a specified vertex and explores the neighbour nodes first, before moving to the next level of neighbours.
•BFS can be implemented by keeping a “to do” list of vertices as a queue.

Question 11

The minimum distance problem/shortest path

Answer 11

Find the shortest distance from a specified source vertex v to each of the other vertices.

Question 12

Dijkstra’s algorithm

Answer 12

Solution to the shortest path
create a priority queue(with priority higher for smaller values)
set distance(v)to 0
set distance(w)to infinity for all other vertices w
add all vertices to the priority queuewith priority equal to their distance
ITERATEwhile the priority queueis not empty
remove u from the front of the queue
ITERATE over vertices wthat are neighbours of u
set new-distanceto distance(u)+ length of edge uw
IF new-distanceis less than distance(w)
set distance(w)to new-distance
change the priority of w in the priority queue to new-distance

Question 13

Spanning trees

Answer 13

a subset of the graph’s edges that connect all the vertices, without including any closed circuits.
•It contains a minimal set of edges that connect up all the nodes.The number of edges in a spanning tree is |V| –1.

Question 14

minimum spanning tree

Answer 14

a weighted graph is a spanning tree that minimises the sum of the weights along its edges.

Question 15

Prim’s algorithm

Answer 15

a greedy solution to the problem of finding a MST
•Start from an arbitrary vertex.
•Keep vertices not already in the current tree in a priority queue.
•Keeptrack of the shortest edge that could connect a vertex to the current tree.
•Use the length of these edges to order the priority queue.
•At each step, add the vertex closest to the current tree to the tree

Question 16

directed acyclic graph

Answer 16

a directed graph with no directed cycles.

•DAGs are useful for representing dependencies.

Question 17

Topological sort

Answer 17

orders the vertices of a DAG so that, for every directed edge uv, ucomes before vin the ordering.
•Identify a vertex with no incoming edges and add it to the topological sort.
•Remove that vertex and all its outgoing edges from the graph.
•Repeat until all the vertices have been removed.
Rather than literally removing vertices and edges, a dictionary records how many edges come into each vertex.