Home > Flashcards > Print Preview
The flashcards below were created by user
ianholden
on FreezingBlue Flashcards. What would you like to do?

If a list is unordered, then our algorithm will be...
Quadratic

If a list is ordered, then our algorithm will be...
Linear

List the Disadvantages of a Binary Search Tree
 Slower to insert nodes than other algorithms
 It can be very slow to search through if the tree has a large height.

List the Advantages of a Binary Search Tree
 Very fast search (If the height of the tree is small).
 Orders nodes when they are added to the tree.

List the disadvantages of a Hash Table
 A hash code may be inaccurate in grouping nodes dependant on the hashing algorithm used.
 Entities in the table are unordered
 Can become inefficient when there are many hash collisions

List the advantages of a Hash Table
 Very fast when working with large amounts of data!
 Groups similar hash codes together which immediately eliminates large portions of the data to search through.

Explain the specification that makes a tour an Euler Tour?
 Every edge must be used once and only once.
 The graph is connected (All nodes are connected)
 You must finish at the same node as you started.
 Each node must have an even number of edges connected to it.

Describe Hierholzers
algorithm for finding a Euler Tour
 If G is not connected, or if G has any node with odd degree then FAIL
 Choose a node and construct any closed trail around that node
 Repeat until the trail is a Euler Tour:
 Choose a node in the visited set that has unvisited edges and construct a closed trail using unvisited edges
 Add that trail to the larger trail, by inserting it into the correct place
 Finaltrail is our Euler Tour

What are the three types of connections for graphs?
 Connected
 BiConnected
 Unconnected

Explain the difference between a connected graph and a biconnected graph
 Connected graph  A graph where every node can be reached by travelling along the edges of the graph consistently.
 BiConnected Graph  A graph where every node can be reached and has at least two connections to other nodes.

Explain the difference between an unconnected graph and a connected graph
 Connected graph  A graph where every node can be reached by travelling along the edges of a graph consistently.
 Unconnected graph  A graph where only some nodes can be reached by travelling along the edges of a graph consistently.

Describe the UnionFind data structure
 Union  adding a new edge to the graph, and the data structure
 –If the nodes share the same root do nothing
 –Otherwise, attach the root of one as a child of the root of the other
 Find  test if two nodes are connected
 –Two nodes are connected if they share the same root
 –If they share different roots they are unconnected

Which out of Quicksort and Mergesort are best at sorting Arrays?
Quicksort

Which out of Quicksort and Mergesort are best at sorting Linked Lists?
Mergesort

Describe the process of a quicksort algorithm.
 Partition the array, placing higher figures at the end and lower figures at the front (based on a pivot)
 Recursively call this on the two new divisions and their divisions after etc...

How can you improve the quicksort algorithm?
 Sort shorter partitions (< 5 say)
 Remove recursion
 Use the median of the first last and middle elements as the pivot.

Name the three fields needed for a single Linked List object (Node).
 ID (Value or String)
 Data (userdefined)
 Next (Pointing to next Node object in list)

Explain the process of a mergesort algorithm.
 Recursively halve the list into sublists until we are left with many pairs of Nodes.
 Swap the values of these lists into the correct order.
 Merge the lists back together again.

What is the answer to the equation...
a & b where
a = 000111
b = 000101
000101 = 5 (denary)

What is the answer to the equation...
a & b where
a = 00000110
b = 01111010
00000010 = 2 (denary)

What does leftshifting in a binary number represent?
A) Multiplication
B) Addition
C) Subtraction
D) Division
A) Multiplication (this multiple choice question has been scrambled)

What is the answer to this equation...
a  b where
a = 00100100
b = 01101010
01101110 = 110 (denary)

What is the answer to this equation...
a  b where
a = 00000101
b = 00001001
00001101 = 13 (denary)

What do these bit operators represent...
&  ! ^
 & = AND
  = OR
 ! = NOT
 ^ = XOR

What is graph isomorphism?
 Isomorphism is graph equality.
 For them to be equal, they must have the same number of nodes and edges, and they must be connected in the same way.

Describe how an Edge list looks when comapring a graph and compare your imagined image to the answer

Describe how an Adjacency Matrix looks when displaying a graph and compare your imagined image to the answer
  1 2 3 4
 
 1  0 1 1 0
 2  1 0 0 0
 3  0 0 1 0
 4  1 0 0 0

Describe how an Object Model looks when displaying a graph and compare your imagined image to the answer
 Nodes Edges
 n1:A e1:n1 n2 label X
 n2:B e2:n2 n3 label Y
 n3:C e3:n3 n4 label X
 n4:D e4:n4 n1 label Q

Describe how a set based schema looks when displaying a graph and compare you imagined image to the answer
 G = (N,E)
 N = {1,2,3,4}
 E = {(1,2),(1,3),(2,3),(3,4),(4,1)}
 w: E > Integers
 w(1,2) = 3
 w(1,3) = 4
 w(2,3) = 1
 w(3,4) = 4
 w(4,1) = 1

In Onotation, what does O(1) time scale represent?
Constant time
i.e, the time never changes. No matter how large or small the program, no matter how complex or simple the architecture, the time is always the same.

In Onotation, what does O(n) time scale represent?
Linear

In Onotation, what does O(n^{2}) time scale represent?
Quadratic

In Onotation, what does O(n^{3}) time scale represent?
Cubic

In Onotation, what does O(log(n)) time scale represent?
Logarithmic (no base!)

In Onotation, when do we use multiplication to represent the time for a program or group of statements to run?
When a loop is present (iterative function)

What is the difference between a fixed point number and a floating point number?
 A fixed point number looks like this: 765.34
 A Floating point number looks like: 7.6534e2
 A fixed point number has a general mantissa (sequence of numbers) and then arbitrary information as to where that decimal point belongs.
 A floating point number has a mantissa and an exponent. The exponent dictates where exactly the decimal point belongs.

What is the formula to work out the actual number in a floating point number?
m*b ^{(ek)}
 Where m = Mantissa
 Where b = Base (Denary, Binary, Hex)
 Where e = Exponent
 Where k = Length of mantissa

How do you go about performing an add or subtract statement on two floating point numbers
 Line up points by shifting
 Perform the operation (Add or Subtract)
 Round the answer to the required number of digits
 Shift, if necessary (normalise)

How is breadthfirst search implemented?
a) FIFO
b) LIFO
a) FIFO

How is depthfirst search implemented?
a) FIFO
b) LIFO
b) LIFO

What does a spanning tree do?
A spanning tree connects all the nodes in an undirected graph with the smallest number of edges

What is a minimum spanning tree?
A MST is a spanning tree of a weighted graph with the smallest sum of edge weights of all the possible spanning trees.

How would we go about finding a minimum spanning tree using Kruskal's algorithm?
 Sort all the edges from smallest weight to largest.
 Work down the list adding edges that do not form a cycle!
 End when you have (N  1) edges where 'N' is the number of nodes.

