Year 1 - Decision Flashcards
1.1 How can algorithms be written?
Code, flowcharts, or a set of instructions
1.1 What can be used to implement an algorithm?
A trace table
1.2 What does the shape of each box in a flowchart tell you about the function?
Oval - Start/End
Rectangle - Instruction
Diamond - Decision
1.3 Describe a bubble sort
Compare adjacent items in a list:
- If they are in order, leave them
- If they are not in order, swap them
- After the first pass, the last item will be in the correct place
- When a pass is completed with no swaps, the sort is complete
1.3 What is the expression for the maximum number of comparisons in a bubble sort?
(n(n -1))/2
1.4 Describe quick sort
Select a pivot and split the items into 2 sub-lists:
- One contains the items less than the pivot
- The other contains the items greater than the pivot
- Select further pivots from within each sub-list and repeat the process
1.5 What are the 3 bin packing algorithms? Describe them
First-fit: Items in order listed, place each item in the first available bin
First-fit descending: Sort into descending order, then apply the first-fit algorithm
Full-bin: Use inspection to select items that will fill a bin first. Remaining items packed with first-fit
1.5 What are the advantages and disadvantages of first-fit?
+ve - Quick to implement
-ve - Unlikely to lead to an optimal solution
1.5 What are the advantages and disadvantages of first-fit descending?
+ve - Usually an optimal solution, easy to implement
-ve - May not find optimal solution, takes a long time
1.5 What are the advantages and disadvantages of full-bin?
+ve - Usually an optimal solution
-ve - Difficult especially when numbers are large/awkward
1.6 What is the order of an algorithm?
If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the run time by a factor of approximately f(m)/f(n)
1.6 What order does bubble sort have? Explain how you get this
A list has n items, the first pass will require (n-1) comparisons, a second pass will require (n-2) comparisons, in the worse case this continues, the total number of comparisons would be:
1+2+3+…+(n-3)+(n-2)+(n-1) = (1/2)(n-1)n = (1/2)n^2 - (1/2)n
Since this is a quadratic expression, bubble sort is taken to have quadratic order
1.6 What are the rules for linear, quadratic, and cubic order?
If the size of a problem is increased by some factor k then:
- an algorithm of linear order will take approximately k times as long to complete
- an algorithm of quadratic order will take approximately k^2 times as long to complete
- an algorithm of quadratic order will take approximately k^3 times as long to complete
2 What is a graph?
A finite number of vertices (or nodes) connected by edges (or arcs)
2 What is a weighted graph? What is it also known as?
A graph that has numbers assigned to each edge, also called a network
2 What is a tree?
A connected graph with no cycle
2 What is a subgraph?
A graph whose vertices and edges belong to another graph but it is only part of the original
2 What is a walk?
A route through a graph along edges from one vertex to another
2 What is a path?
A walk in which no vertex is visited more than once
2 What is a trail?
A walk in which no edge is visited more than once
2 What is a cycle? What is it also known as?
A walk in which the end vertex is the same as the starting vertex (also a closed path)
2 What is a Hamiltonian Cycle?
A cycle in which all vertices are visited
2 What does it mean if a graph is connected?
If all the vertices are joined to the graph
2 What is a loop?
An edge that starts and finishes at the same vertex
2 What is a simple graph?
A graph with no loops and where there is at most one edge connecting any pairs of vertices
2 What is a digraph?
A graph where edges have a direction
2 What is a spanning tree?
A subgraph which includes all original vertices that is also a tree
2 What is the expression for the number of edges in a spanning tree for a connected graph of n vertices?
n-1
2 What is a complete graph?
Every vertex is connected to each other by a single edge (think k1, k2, k3, …)
2 What is the expression for the number of Hamiltonian cycles in a complete graph with n vertices?
((n-1)!)/2
2 What is an isomorphic graph?
A pair of graphs which shows the same information but are drawn differently
2 What is an adjacency matrix?
A table describing the number of arcs joining the corresponding vertices
2 What is a distance matrix?
A table in which the entries represent the weight of each arc, not the number of arcs
2 What is the degree/valency/order of a vertex?
The number of edges coming out of the vertex
2 What is the Handshake Lemma?
In any undirected graph, the sum of the degrees of vertices is equal to 2x the number of edges - therefore the number of odd vertices must be even
3.1-3.2 What do Kruskal and Prim’s algorithms do?
They find the minimum spanning tree (MST) of a network
3.1 Describe Kruskal’s algorithm
- Sort the arcs in ascending order of weight
- Select the arc of least weight to start the tree
- Consider the next arc of least weight:
i) If it would form a cycle, reject it
ii) If it would not form a cycle, add it to the tree (if arcs are of equal weight consider each in turn) - Repeat (3) until all vertices are connected
3.2 Describe Prim’s algorithm
- Select any vertex to start the tree from (often given to you in the question)
- Choose an arc of least weight connecting to the starting vertex that joins a vertex not currently in the tree (if there are a choice of equal arcs then choose randomly)
- Repeat (2) until all vertices are connected
3.3 Describe how you can apply Prim’s algorithm to a distance matrix
- Choose any vertex to start the tree
- Cross out the row containing that vertex
- Number the column in the matrix for the chosen vertex
- Ring the lowest remaining entry in the column (if equal, choose randomly)
- The ringed entry becomes the next arc added to the tree
- Repeat 2, 3, 4, & 5 until all rows are deleted
3.3 What order is Prim’s algorithm?
n^3
3.4 What is Dijkstra’s algorithm used for?
Dijkstra’s (‘Dike-stra’) algorithm is used to find the shortest path through a network
3.4 Describe Dijkstra’s algorithm
- Above every vertex there is a vertex label, order of labelling, final value, and working values
- Label the starting vertex with a 1 and a final value of 0
- Record a working value at every vertex that is connected to the vertex chosen
- If this value is smaller than the current working value, cross the old value out
- Look at the working values at all vertices without final labels, select the smallest working value and make it the final label
- Repeat until the destination receives a final label
3.4 How do you find the shortest path between 2 points on a network?
Work backwards, whichever arc equals the next vertex when you subtract the arc value is the correct path
4.1 What is an Eulerian graph?
A network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph whose vertices are all even is Eulerian.
4.1 What is a semi-Eulerian graph?
A network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph with two odd vertices is semi-Eulerian (one odd vertex is the start and the other is the end of the trail)
4.2 What does the route inspection algorithm do?
Finds the length of the shortest route in a network that transverses every arc at least once, and returns to its starting point
4.2 If a network is Eulerian, what can you say about the length of its shortest route that transverses every arc?
length of the shortest route = total weight of the network
4.2 If a network is semi-Eulerian, what can you say about the length of its shortest route that transverses every arc?
length of the shortest route = total weight of the network plus the length of the shortest path between the two odd vertices
4.2 Describe how to implement the route inspection algorithm
- Identify any odd vertices
- Consider all possible pairings of these pairings
- Select the complete pairing that has the least sum
- Add a repeat of the arcs indicated by this pairing to the network
6.1 How do you formulate a linear programming problem?
- Define the decision variables (x, y, z, etc)
- State the objective (maximise/minimise, together with an algebraic expression called the objective function)
- Write the constraints as inequalities
6.2 What is the name of the region of a graph that satisfies all the constraints of a linear programming problem? How should you label this?
Feasible Region (generally marked with an ‘R’ and everywhere not in the region is shaded)
6.3 How do you solve a linear programming problem after drawing the feasible region?
Locate the optimal point with objective method or ruler method.
Obj. method: Find the coords of each vertex of the feasible region and select the vertex that gives the optimal value of the objective function
Ruler method: Sketch parallel lines with the same gradient as the objective function, for a max. point look for the last point covered by the lines as it leaves the feasible region, for a min. point look for the first point covered by the lines as it enters the feasible region
6.4 How do you find the optimal vertex of a linear programming problem if the solution does not have integer values?
- Consider the four integer coords in a square around the optimal vertex
- See which point obeys all the constraints
- If there are multiple, select the point that has the more optimal solution for the objective function
8.1 What is a precedence table?
A table which shows which activities must be completed before others are started
8.1 How do you draw an arc network for a critical path analysis problem?
- Activities represented by arcs & completion of activities shown as nodes
- Each arc labelled with an activity letter, convention is straight lines for arcs
- Nodes are numbered starting from 0 for the first node which is also called the source node
- Number each node as it is added to the network
- Final node is the sink node
8.2 What is a dummy activity?
- An activity that has no time or cost
- Its purpose is to show dependencies between activities
8.2 What is special about the relationship between two activities in a critical path analysis problem?
- Every activity must be uniquely represented
- There can be at most one activity between any two nodes
8.3 What is duration of an activity? How is it denoted?
- How long it takes to complete
- Denoted in brackets as the ‘weight’ of each arc
8.3 What is an early event time? What is a late event time?
- The earliest time that an activity can start/finish
- The latest time that an activity can start/finish
8.3 How are early and late event times shown?
Nodes are replaced by two boxes: top is the early event time, bottom is the late event time
8.3 How do you find the early event time of a node?
- Do a forward pass
- Whichever activity preceding it takes the longest to finish
- Think ‘forward high’
8.3 How do you find the late event time of a node?
- Do a backward pass
- Whichever activity after it takes the shortest time to start
- Think ‘backward low’
8.4 What is a critical activity?
An activity when any increase in its duration results in an increase in the duration of the whole project
8.4 What is a critical path?
- A path from the source node to the sink node which entirely follows critical activities
- A critical path is the longest path contained in the network
- An activity connecting two critical events isn’t necessarily a critical activity
8.4 How do you identify a critical event node?
The early event time is equal to the late event time
8.5 What is the float of an activity?
The amount of time that its start may be delayed without affecting the duration of the project
8.5 How do you calculate the float of an activity?
Total float = latest finish time - duration - earliest start time
8.5 What is the total float of a critical activity?
0
8.6 What is a Gantt chart? How do you draw one?
- Graphical way of representing possible start and finish time for all activities in a project
- Critical activities are across the top marked by solid lines
- Each subsequent activity is marked with solid lines starting at their early event time and spanning their duration
- An activity’s float is marked on the end with dotted lines
8.6 What do these questions mean?
- Determine how many activities MUST be happening at midday on day x
- Determine how many activities MAY be happening at midday on day x
What must you also remember when answering these questions?
- MUST: An activity is definitely happening on the day either because its float is too small or because it is critical
- MAY: An activity may be happening depending on the length of its float
- IMPORTANT: If asked how many activities MAY be happening, do not also include those that MUST be happening
- Also, always consider the fencepost problem when marking the day on the Gantt Chart
