GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

Final Exam Review

Frank Handel CMPT280 - Intermediate Data Structures and Algorithms Undergraduate English 107 cards

Cards in this deck (107)

  1. 1What can be said in general about sorting-by-comparison algorithms?There is no sorting-by-comparison algorithm that can sort a sequence of elements faster than time proportional to n log n where n is the number of elements to be sorted, in other words, Ω(n log n) or Big-Omega n log n is the proven tight lower bound on the time complexity of sorting-by-comparison algorithms.
  2. 2What is the worst case time complexity of bucket sort?Question
    What is the worst case time complexity of bucket sort?
    Answer
    O(d) where d is the length of the array of buckets in the SPECIAL CASE where n (the number of elements) is less than d
  3. 3What is a limiting factor of bucket sort?Question
    What is a limiting factor of bucket sort?
    Answer
    It requires O(d) space where d is the length of the array of buckets.
  4. 4What kind of data set would one use Bucket sort for?Question
    What kind of data set would one use Bucket sort for?
    Answer
    A large sequence of integer keys that have a small range of values
  5. 5What is the algorithm for Bucket sort?Question
    What is the algorithm for Bucket sort?
    Answer
    1. Initialize an array of k lists (buckets)
    2. Each element is sorted into bucket[k] where k = element.key
    3. The contents of each bucket are concatenated together
  6. 6What is the algorithm for Radix sort?1. Begin by creating an array list of R empty lists (R is the radix)
    2. each key is appended to list[k] where k is the value of the current significant digit
    3. Repeat steps 1 and 2 recursively until the last digit been reached
    4. concatenate each list[k] as the recursion unwinds
  7. 7Why can't Bucket sort and Radix sort be used to sort floating point numbers?Because the radix and the number of buckets must be a finite number, and between any two floating point numbers there are an infinite number of real values.
  8. 8Which version of Radix sort would be used to sort integers into ascending order?LSD (least-significant digit)
  9. 9Which variation of Radix sort would be used to sort strings into alphabetical order?MSD (most-significant-digit)
  10. 10Is Radix sort stable?LSD (least-significant-digit) is, MSD (most-significant digit) is NOT
  11. 11What is the time complexity of Radix sort?O(n + R)
  12. 12What is the time complexity of Heap sort?Θ(n log n)
  13. 13Is Heap sort in-place and/or stable?in-place but not stable
  14. 14What is the Heap sort algorithm?1. Convert input array into an arrayed heap
    2. Repeatedly move the largest element into it's correct position
    3. Re-heapify the remainder of the array
    4. Output the arrayed heap in reverse order for ascending order
  15. 15What is the time complexity of Tree sort?Θ(n log n) as long as a balanced tree is used
  16. 16What is the algorithm for Tree sort?1. Insert all elements into a balanced ordered tree
    2. Traverse the tree in-order to output the sorted elements
  17. 17What is the time complexity for Selection sort?Θ(n^2) - one of the worst sorts
  18. 18What is the algorithm for Selection sort?1. Take the smallest value and put it at the front of the array
    2. Repeat step 1 recursively with the remainder of the array
  19. 19What is the algorithm for Insertion sort?1. Assume that the first k elements of the array are sorted
    2. Pick the next unsorted value in the array at offset k and place it in its correct position in the sorted array
    3. Repeat until k = n
  20. 20What is the time complexity for Insertion sort?best case O(n) when the array is already sorted, worst case O(n^2) when the array is in reverse order. Very efficient if the array is ALMOST sorted
  21. 21What is the time complexity of Quick sort?O(n log n) in general, but worst case O(n^2)
  22. 22What is the algorithm for Quick sort?1. Pick any element x to be the "pivot"
    2. Sort each element into three sequences: less than x, equal to x, greater than x
    3. Recursively sort those sequences
    4. Concatenate the sorted sequences back together as recursion unwinds
  23. 23What is the time complexity of Merge Sort?Θ(n log n)
  24. 24What is the algorithm for Merge Sort?1. Recursively divide the array in half
    2. Sort the resulting arrays as they merge back together while the recursion unwinds using a helper method
  25. 25What does in-place mean with regards to sorting algorithms?The output is stored in the same array as the input
  26. 26What does stable mean with regards to sorting algorithms?Elements with equal keys stay in the same order relative to each other
  27. 27What is a Graph data structure and what is its purpose?A representation of a mathematical relation, records which elements of a set are related to each other in some fashion
  28. 28What is indegree and outdegree of a vertex?The number of directed edges pointing in and out from the vertex
  29. 29What is a self-loop?An edge where a vertex is connected to itself
  30. 30What is the difference between a directed graph and an undirected graph?Edges in a directed graph are directional, in an undirected graph edges have no implied direction
  31. 31What is a walk?An alternating sequence of vertices and connecting edges
  32. 32What is a path?A walk that cannot travel a vertex more than once
  33. 33What is a circuit?A trail (cannot travel an edge more than once) that begins and ends on the same vertex
  34. 34What is a trail?A walk that cannot travel an edge more than once
  35. 35What is a cycle?A path (cannot travel a vertex more than once) that begins and ends on the same vertex
  36. 36What is a subgraph?A graph formed by removing any number of vertices and their incident edges from a greater graph
  37. 37What is a connected component?An undirected graph where every pair of vertices are connected and there is no larger connected subgraph containing all the same vertices
  38. 38What is a strongly connected component?A directed graph where every pair of vertices are strongly connected and there is no larger strongly connected subgraph that contains all the same vertices
  39. 39Two vertices are strongly connected ifthe edge between them is bi-directional
  40. 40What is a planar graph?A graph that can be drawn on a 2D plane with no edges crossing
  41. 41What are the typical patterns used when accessing nodes/edges in a Graph?random access pattern - access one random node/edge
    sequential access pattern - access a group of nodes/edges in a sequence
  42. 42What method of storing nodes in a Graph is more efficient for random access?An adjacency matrix
  43. 43What method of storing nodes in a Graph is more efficient for sequential access?An adjacency list
  44. 44How can you tell if a matrix is undirected by looking at how its nodes are stored?An adjacency matrix will be symmetrical about the diagonal. An adjacency list will have sub-lists with symmetrical edges (1 : 1-2, 2: 2-1)
  45. 45What are the time complexities for random access for an adjacency matrix and an adjacency list?Adjacency matrix: O(1)
    Adjacency list: O(outdegree(i))
  46. 46What are the time complexities for sequential access for an adjacency matrix and an adjacency list?Adjacency matrix: O(n^2)
    Adjacency list: O(outdegree(i))
  47. 47What are the space requirements for an adjacency matrix and an adjacency list?Adjacency matrix: Θ(n^2)
    Adjacency list: Θ(n+m)
  48. 48What is the algorithm to determine the number of walks of a specific length between two nodes and what is its time complexity?1. Perform matrix multiplication of the adjacency matrix r times, where r is the length specified
    The time complexity is Θ(rn^3)
  49. 49What is the unnamed algorithm to determine path existence and what is its time complexity?1. Add up the sum of the powers of the adjacency matrix from 1 to n-1
    2. if [i, j] of the resulting matrix is greater than zero, a path exists
    The time complexity is Θ(n^4)
  50. 50What is Warshall's algorithm?A more efficient path existence algorithm that determines whether a path exists between all pairs of nodes.
  51. 51What is the time complexity of Warshall's algorithm?Θ(n^3)
  52. 52What is the time complexity of a breadth-first search on a graph for an adjacency matrix and an adjacency list? Which is faster?Adjacency matrix: O(|V|^2)
    Adjacency list: O(|V| + |E|)
    Adjacency list BFT is only as slow as Adjacency matrix BFT in the worst possible case, so in general, it is faster to use an adjacency list.
  53. 53What is a weighted graph?A graph where each edge has an associated value
  54. 54How is the absence of an edge represented in a weighted graph?∞ (infinity)
  55. 55What is Floyd's algorithm?A shortest path algorithm that determines whether a path exists between all pairs of nodes in a weighted graph. The same as Warshall's algorithm, simply modified to find the shortest path using weights.
  56. 56What is the time complexity of Floyd's algorithm?Θ(n^3)
  57. 57What property of a weighted graph can cause Floyd's algorithm to fail?The weighted graph cannot contain any negative cycles, because the path between a pair of nodes can always be made shorter by going around the cycle again
  58. 58What is Djikstra's algorithm?A single-source shortest path algorithm.
  59. 59What three properties need to be tracked for each node in Djikstra's algorithm?tentative distance - the length of the shortest path found so far from the start node to the current node
    predecessor node - the node immediately prior to the current node on the shortest path found so far
    visited - a boolean that indicates whether the current node has been visited or not
  60. 60What are the steps of Djikstra's algorithm?1. Begin at the start vertex
    2. Set the current node to visited, and process its adjacent nodes in an arbitrary order (numerical or alphabetical)
    3. Record the path cost and predecessor in each of its adjacent nodes if the current path cost is less than the stored path cost
    4. After all the adjacent nodes has been processed, move to the unvisited node with the smallest tentative distance and recurse
  61. 61What property of a weighted graph will cause Djikstra's algorithm to fail?The weighted graph cannot have any negative weights.
  62. 62What is the time complexity of Djikstra's algorithm?O(|V|^2) - linear search implementation
    O(|V|+|E|log|V|) - priority queue/arrayed heap implementation
    O(|V|log|V|+|E|) - fibonacci heap implementation
  63. 63What is a range search?A search that returns all the items within a query range of k parameters
  64. 64What is a k-D tree? What is it used for?A k-D tree is a tree with k dimensions where the coordinate of a node used to split the tree at a given depth is (depth mod k) + 1. It is used for ranged search.
  65. 65What are the characteristics of a dictionary?searchable dispenser, allows arbitrary manipulation of a cursor and linear iteration
  66. 66What data structures studied in class are dictionaries?Linked list, Bilinked list, Hash tables, 2-3 Trees, B+ Trees and B trees
  67. 67What is hashing?Using a keyed data items key to compute its location in a hash table array
  68. 68What is a collision?When a hash function hashes two different keys to the same index
  69. 69What is folding?Interpreting every j characters in a string as an integer, adding those numbers together and taking modulus n to get the hash table array position
  70. 70What is collision resolution?Finding an alternative index in the event of a collision
  71. 71What is open addressing?When a collision occurs, probe the array for an unused index according to a function
  72. 72What is a probe increment?The offset from the original hashed index
  73. 73Describe linear probing.The probe increment is a linear function and probes forwards or backwards through the array at a fixed interval
  74. 74Describe quadratic probing.The probe increment is a quadratic function that calculates a non-fixed probing interval
  75. 75Describe double hashing.Linear probing but the probe increment depends on the key being hashed
  76. 76Describe separate chaining.Each position in the hash table contains a linked list of all the items hashed to that position
  77. 77What is clustering?Large contiguous clusters of used indices in a hash table
  78. 78How do you fix an RR imbalance?A left rotation of the critical node
  79. 79How do you fix an LL imbalance?A right rotation of the critical node
  80. 80How do you fix an RL imbalance?A double left rotation: a right rotation of the right subtree, followed by a left rotation of the critical node
  81. 81How do you fix an LR imbalance?A double right rotation: a left rotation of the left subtree, followed by a right rotation of the critical node
  82. 82What is the in-order successor?The node containing the smallest element in the right subtree
  83. 83What is the algorithm for deletion from an ordered binary tree?deletion by copying: recursively find the in-order successor, replace the node being deleted with the in-order successor, and delete the in-order successor
  84. 84What are the properties of a dispenser?A collection, has a current item that is always determined by the structure and cannot be manipulated by the user. Does not allow iteration over all the elements
  85. 85What data structures studied in class are dispensers?Stack, Queue, Heap
  86. 86What are the properties of a searchable dispenser?Can examine items other than the current item by using search to move the cursor, but users have no control over where new data is inserted
  87. 87What is a depth-first search?A search that visits the children of a node before its siblings, once a node is visited, every node in its subtree is visited before its sibling
  88. 88What is a breadth-first search?A search that always visits all the nodes on the current level before visiting the nodes on the next level
  89. 89What order are nodes visited in a pre-order traversal?VLR
  90. 90What order are nodes visited in an in-order traversal?LVR
  91. 91What order are nodes visited in a post-order traversal?LRV
  92. 92What does coupling refer to?The degree to which two separate modules (not components within a single module) depend on each other
  93. 93What does cohesion refer to?The degree to which the components of a module of code belong together or are related to a singular purpose
  94. 94What is the ideal level of cohesion and coupling?high cohesion, low coupling
  95. 95mutabledata that can be changed after it is created
  96. 96immutabledata that can't be changed after it is created
  97. 97shallow clonereferences are copied
  98. 98deep clonereferences are cloned recursively
  99. 99Big-Theta (Θ)tight-upper bounds on time complexity
  100. 100Big-Omega (Ω)tight-lower bounds on time complexity
  101. 101black-box testinggenerate tests without looking at the code (can look at function headers, listed exceptions)
  102. 102white-box testinggenerate tests based on the code (test loops, conditionals), test all paths through the code
  103. 103What possible cases should be tested when testing exceptions?If an exception is expected, test if it occurs, no exception occurs, and a different exception occurs. If no exception is expected, test if an exception occurs, and if no exception occurs.
  104. 104When a split is forced on a B+ tree node, which key is chosen as the parent?the (b // 2)+ 1th node
    (ex. 5 // 2 + 1 = 3)
  105. 105When a split is forced on a B tree node, which keyed data item is chosen as the parent?If b is odd, the median is chosen, if b is even, the largest item from the left half of the split is chosen
  106. 106what happens when an array of integers is sorted by MSD radix sort265,28,42,614,7,83,916,95
  107. 107what happens when an array of strings are sorted by LSD radix sortis, or, die, win, you, you, coming, winter

Information

Description
Undergraduate CMPT280 - Intermediate Data Structures and Algorithms Flashcards on Final Exam Review, created by Frank Handel on 20/04/2023.
Created by
Frank Handel
Views
4
Rating

More on Sorting and Searching Algorithms

Feedback

What is it about?

What do you think of the new look?

How do you like it?