CO522 Algorithms, Data Structures and Complexity

Card Set Information

Author:
ianholden
ID:
212620
Filename:
CO522 Algorithms, Data Structures and Complexity
Updated:
2013-05-16 09:53:09
Tags:
Algorithms Data Structures Complexity
Folders:

Description:
Cards for CO527 - Algorithms, Data Structures and Complexity
Show Answers:

Home > Flashcards > Print Preview

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


  1. If a list is unordered, then our algorithm will be...
    Quadratic
  2. If a list is ordered, then our algorithm will be...
    Linear
  3. 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.
  4. 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.
  5. 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
  6. 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.
  7. 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.
  8. 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
  9. What are the three types of connections for graphs?
    • Connected
    • Bi-Connected
    • Unconnected
  10. Explain the difference between a connected graph and a bi-connected graph
    • Connected graph - A graph where every node can be reached by travelling along the edges of the graph consistently.
    • Bi-Connected Graph - A graph where every node can be reached and has at least two connections to other nodes.
  11. 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.
  12. Describe the Union-Find 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
  13. Which out of Quicksort and Mergesort are best at sorting Arrays?
    Quicksort
  14. Which out of Quicksort and Mergesort are best at sorting Linked Lists?
    Mergesort
  15. 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...
  16. 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.
  17. Name the three fields needed for a single Linked List object (Node).
    • ID (Value or String)
    • Data (user-defined)
    • Next (Pointing to next Node object in list)
  18. Explain the process of a mergesort algorithm.
    • Recursively halve the list into sub-lists 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.
  19. What is the answer to the equation...
    a & b where
    a = 000111
    b = 000101
    000101 = 5 (denary)
  20. What is the answer to the equation...

    a & b where
    a = 00000110
    b = 01111010
    00000010 = 2 (denary)
  21. What does left-shifting in a binary number represent?

    A) Multiplication
    B) Addition
    C) Subtraction
    D) Division
    A) Multiplication
    (this multiple choice question has been scrambled)
  22. What is the answer to this equation...

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

    a | b where
    a = 00000101
    b = 00001001
    00001101 = 13 (denary)
  24. What do these bit operators represent...

    &     |     !     ^
    • & = AND
    • |  = OR
    • !  = NOT
    • ^ = XOR
  25. 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.
  26. Describe how an Edge list looks when comapring a graph and compare your imagined image to the answer
    • AC
    • CB
    • BA
  27. 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
  28. 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
  29. 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
  30. In O-notation, 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.
  31. In O-notation, what does O(n) time scale represent?
    Linear
  32. In O-notation, what does O(n2) time scale represent?
    Quadratic
  33. In O-notation, what does O(n3) time scale represent?
    Cubic
  34. In O-notation, what does O(log(n)) time scale represent?
    Logarithmic (no base!)
  35. In O-notation, 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)
  36. 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.
  37. What is the formula to work out the actual number in a floating point number?
    m*b(e-k)

    • Where m = Mantissa
    • Where b = Base (Denary, Binary, Hex)
    • Where e = Exponent
    • Where k = Length of mantissa
  38. 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)
  39. How is breadth-first search implemented?

    a) FIFO
    b) LIFO
    a) FIFO
  40. How is depth-first search implemented?

    a) FIFO
    b) LIFO
    b) LIFO
  41. What does a spanning tree do?
    A spanning tree connects all the nodes in an undirected graph with the smallest number of edges
  42. 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.
  43. 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.

What would you like to do?

Home > Flashcards > Print Preview