Decision

• Dijkstra's algorithm


  name this algorithm:

  1) give start vertex label 0

  2) give each vertex connected to start vertex a working value

  3) find smallest working value and give it its permanent label

  4) update working values at any unlabelled vertex that can be reached from V

  5) repeat steps 3 and 4 till destination vertex given permanent label
• Prim's algorithm


  name this algorithm:

  1) choose starting vertex

  2) choose vertex nearest to starting vertex, add that vertex and add its associated edge to the tree

  3) connect to the tree of connected vertices that vertex that is nearest to any vertex in the connected set, but to a vertex not already in the tree

  4) repeat step 3 till all vertices are connected to the tree
• Prim's algorithm with a distance matrix


  name this algorithm:

  1) start with the matrix representing the network and choose a starting vertex. Delete the row corresponding to to that vertex

  2) label with '1' the column corresponding to the start vertex, ring the smallest undeleted entry in that column

  3) delete the row corresponding to the entry you just ringed

  4) label with the next number the column corresponding to the vertex you just ringed

  5) ring the lowest undeleted entry in all labelled columns

  6) repeat steps 3, 4 and 5 till all rows are deleted. The ringed entries represent the edges in the minimum connector
• minimum spanning tree


  a spanning tree such that the total length of its arcs is as small as possible.
• Kruskal's algorithm


  name this algorithm:

  1) sort edges into ascending order of weight

  2) select the edge of least weight

  3) select from edges not previously selected, the edge of least weight that does not form a cycle

  4) repeat step 3 until selected edges form a spanning tree
• What is the purpose of floyd's algorithm


  To find the shortest path between any two vertices in a network.
• Floyd's algorithm (method)


  1. Complete initial distance table for the network. No direct route between two vertices, label with ∞ symbol.

  2. Complete an initial route table by making every entry in the columns the same as the column header.

  3. First iteration copy first row and first column into a new table and lightly shade these values.

  4. Consider each unshaded position in turn. Compare the value in this position in the previous table and the sum of the corresponding shaded values.

  5. If the added values are less than existing value, replace and put the letter of the shaded column header into the route table.

  6. For the second iteration, repeat with the second column and row, shading these values. Repeat steps 4 & 5.

  7. If there are n vertices then there will be n iterations.
• planar graph


  what do you call a graph where none of its edges cross over each other?
• isomorphic


  what do you call two graphs have the same number of vertices and the degrees of corresponding vertices are the same?
• network or weighted graph


  if a graph has a number associated with its edge, what is it called? (two names)
• complete graph


  what do you call a graph where every vertex is connected to every other vertex?
• spanning tree


  what do you call a connected graph with no cycles?
• connected


  a graph is ... if from any vertex you can get to any other vertex
• simple graph


  what do you call a graph with no loops and not more than one edge connected any pair of vertices
• subgraph


  a ... of a graph is a collection of some of the vertices from that graph and some of the edges, not all of them need be there
• Eulerian cycle


  which cycle includes every edge of the graph exactly once?
• Hamiltonian cycle


  which cycle passes through every vertex of a graph exactly once
• cycle


  what do you call a path that ends at the vertex it starts at?
• ascending


  when using a binary search algorithm, do the numbers have to be in descending or ascending order?
• first-fit decreasing algorithm


  name this algorithm:

  1) reorder the boxes in decreasing order of size using one of the sorting algorithms

  2) apply first-fit algorithm to the reordered list
• first-fit algorithm


  name this algorithm:

  taking the boxes in the order listed, place the next box to be packed in the first available bin that can take that box
• quick-sort algorithm


  name this algorithm:

  1) select the mid-point of the list to use a pivot

  2) write numbers smaller than pivot to the left, write numbers higher than pivot to the right

  3) select the mid points of each new list and use as a pivot

  4) repeat steps 2 and 3 until list is ordered
• route inspection algorithm


  name this algorithm:

  1) list all odd vertices

  2) form all possible pairings of odd vertices

  3) for each pairing find the edges that are best to repeat and find the sum of the lengths of these edges

  4) choose the pairing with the smallest sum, construct a route that repeats these edges
• traversable


  what is the other name for an Eulerian graph
• handshaking theorem


  what theorem states that the sum of the valencies, taken over all the vertices of a graph, is equal to twice the number of edges
• Dependence/presedence table


  shows which activities must be completed before the others are started
• event


  in activity networks, a node represents what?
• activities

  in activity networks, the arcs represent what?
• source node


  the ... represents the beginning of the project
• sink node


  the ... represents the end of the project
• activity network


  after you have made a precedence table, you make an ...
• event


  an ... is the completion of one or more activities
• duration


  the weight of an activity represents the ... of that activity
• Critical Activity


  Project activity for which the earliest start time and latest start time are equal. A critical activity cannot be delayed without lengthening the overall project duration.
• critical path


  the sequence of activities that determine the earliest date by which the project can be completed (contains all the critical activities)
• Dummy Activity


  shows a dependency but no passage of time. Used if activity D depends on A and B, but C depends on only B.

  There can only be one at most activities between any two events. This may require use of a dummy.

  
• float


  The amount of time a project activity may be delayed without delaying the whole project

  Float = latest finish time - duration - earliest start time
• Semi-Eulerian Graph


  If precisely two valencies are odd and rest are even. The graph is semi-traversable, meaning can be traversed if start and finish nodes are different (and they are the odd nodes).
• Simple graph


  A graph in which there are no loops and not more than one edge connecting any pair of vertices
• loop


  An edge that starts and finishes at the same vertex