cpsc221 M2 Flashcards

The flashcards below were created by user forrest.allen57 on FreezingBlue Flashcards.

  1. A rooted tree is a tree in which ______. 
    One vertex is distinguished from the others and is called the root
  2. The level of a vertex in  a rooted tree is ____. 
    the number of edges along the unique path between it and the root
  3. The height of a rooted tree is ____.
    the maximum level of any vertex of the tree
  4. A binary tree is a rooted tree in which ____.
    every parent has at most two children
  5. A full binary tree is a rooted tree in which ____.
    every parent has exactly two children 
  6. If is a positive integer and T is a full binary tree with internal verticies, then T has a total of __(a)___ verticies and ___(b)__ terminal verticies
    • a) 2k +1
    • b) k +1  
  7. If  T is a binary tree that has terminal verticies and height h, then and are related by the inequality ______.
    Image Upload 1 or Image Upload 2
  8. When an algorithm segment contains a nested for-next loop, you can find the number of times the loob will interate by constructing a table in which each column represents ____.
    one iteration of the innermost loop
  9. In the worst case for an input array of length  n, the sequential search algorith has to look through _____ elements of the array before it terminates.
  10. The worst-case order of the insertion sort algorithm is _(a)__, and its average-case order is _(b)___.
    • a) n2
    • b) n2
  11. for all integers n >= 1
    Image Upload 3


    Image Upload 4
    Image Upload 5
  12. for any real number except 1, and any integer n >= 0
    Image Upload 6
    1 + r + r2+...rn = 
    Image Upload 7
  13. The domain of any exponential function is _(a)_, and its range is  _(b)_.
    • a) the set of all real numbers 
    • b) the set of all positive real numbers
  14. The domain of any logarithmic funcion is _(a)_, and its range is _(b)_.
    • a) the set of all positive real numbers
    • b) the set of all real numbers
  15. if is an integer and Image Upload 8 then Image Upload 9 
  16. If is a real number with b > 1 and if is a sufficiently large real number, then when the quantities x, x2, logbx, andare arranged in order of increasing size, the result is ___.
    logbx < x < x logx < x2
  17. if is a positive integer, then 1 + 1/2 +1/3 +...+1/n has order ___.
    ln x or equivantly log2x
  18. b0
  19. b-x 
    Image Upload 10
  20. Image Upload 11
    Image Upload 12
  21. Image Upload 13
    Image Upload 14
  22. Image Upload 15
    Image Upload 16
  23. Image Upload 17
    Image Upload 18
  24. Image Upload 19 Is the same as_____.
    Image Upload 20
  25. Image Upload 21
    Image Upload 22
  26. Image Upload 23
    Image Upload 24
  27. Image Upload 25
    Image Upload 26
  28. Image Upload 27
    Image Upload 28
  29. To solve a problem using a divide-and-conquer algorithm, you reduce it to a fixed number of smaller problems of the same kind, which can themselves be __(a)__, and so forth until _(b)__.
    • a) reduced to the same finite number of smaller problems of the same kind
    • b) easily resolved problems are obtained
  30. To search an array using the binary search algorithm in each step, you compare a middle element of an array to __(a)__. If the middle element is less then __(b)__, you __(c)__, and if the middle element is greater then __(d)__, you  __(e)__.
    • (a) the element uou are looking for
    • (b) the element you are looking for
    • (c) apply the binary search algorithm to the lower half of the array
    • (d) the element you are looking for
    • (e) apply the binary search algorithm to the upper half of the array
  31. The worst case order of the binary search algorithm is ___.
    log2n, where is the length of the array
  32. To sort an array using the merge sort algorithm, in each step until the last one you split the array into approximately two equal sections and sort each section using __(a)__. Then you __(b)__ the two sorted sections.
    • (a) merge sort
    • (b) merge
  33. The worst case order of the merge sort algorithm is ___.
    n log2n
  34. QuickSort
    • Best: n log n 
    • Average: n log n
    • Worst: n2
    • Memory: log n
    • Stable: depends
  35. Merge Sort
    • Best: n log n
    • Average: n log n 
    • Worst: n log n
    • Memory: depends; worst case is n 
    • Stable: yes 
  36. Heapsort
    • Best: n log n
    • Average: n log n
    • Worst: n log n 
    • Memory: 1
    • Stable: no 
  37. Insertion Sort
    • Best: 
    • Average: n2
    • Worst: n2
    • Memory: 1
    • Stable: yes
  38. Hash(n) = 
    n mod 7
  39. Recurrence for Binary Search is: T(n)=

    Big-O solution:
    T(n/2) + O(1)

    O(log n)
  40. Recurrence for Sequential Search is: T(n) = 

    Big-O solution:
    T(n-1) + O(1)

    • O(n)
  41. Recurrence for Tree Traversal: T(n)

    Big-O solution:
    2 T(n/2) + O(1)

    • O(n)
  42. Recurrence for Mergesort and Average case Quicksort: T(n) = 

    Big-O solution:
    2 T(n/2) + O(n)

    • O(n log n)
  43. Recurrence for Selection Sort (other n2 sorts): T(n) = 

    Big-O solution:
    T(n-1) + O(n)

    • O(n2)
  44. What is the formula to calculate the balance for each node in an AVL tree with height 
    hR - h where hR and hL are the heights of the left and right subtrees, respectively.
  45. A tree is called a Left-Left tree because ___.
    its root and left subtree of the root are both left-heavy
  46. What is the Balance Property of an AVL-Tree for all nodes x?
    • Image Upload 29
    • Result: height is Image Upload 30
  47. To balance AVL-Tree balance(x) = 
    height(x.left) - height(x.right)

    NB: height(NULL) = -1 
  48. Image Upload 31
    Image Upload 32
  49. A Loop Invariant is _(a)__. What are three of it's properties?
    • (a) a statement that is true before loop execution begins, at the beginning of each repetition of the loop body, and just after
    • the loop exits
    • 1) Invariant must be true before loop execution begins
    • 2)Must be true at the beginning of each repetition
    • 3) Must be true after loop exit
  50. Binary Heap Navigation:
    left_child(i) = (a)
    right_child(i) = (b)
    parent(i) = (c)
    root() = (d)
    next_free_pos() = (e)
    • (a) Image Upload 33
    • (b)Image Upload 34
    • (c) Image Upload 35
    • (d) Image Upload 36
    • (d) Image Upload 37
  51. A graph consists of two finite sets: __(a)__ and __(b)__, where each edge is associated with a set consisting of __(c)__.
    • (a) a finite, nonempty set of verticies
    • (b) a finite set of edges
    • (c) one or two verticies called its endpoints
  52. A loop in a graph is ____ 
    an edge with a single endpoint 
  53. Two distinct edges in a  graph are parallel if, and only if, ___.
    they have the same set of endpoints
  54. Two vertices are called adjacent if and only if __.
    they are connected by an edge.
  55. An edge is incident on ____.
    each of its endpoints.
  56. Two edges incident on the same endpoint are ___.
  57. A vertex on which no edges are incident is ___.
  58. In a directed graph, each edge is associated with ___.
    an ordered pair of vertices called its endpoints 
  59. a simple graph is ___.
    a graph with no loops or parallel edges
  60. A complete graph on vertices is a ___.
    simple graph with vertices whose set of edges contains exactly one edge for each pair of verticies.
  61. A complete bipartite graph on (m,n) vertices is a simple graph whose vertices can be partitioned into two disjoint sets V1 and V2 in such a way that (1) each of the vertices in V1 is __(a)__ to each of the vertices in V2no vertex in V1 is connected to ___(b)__, and no vertex in V2 is connected to __(c)__.
    • (a) connected by an edge
    • (b) any other vertex V1
    • (c) any other vertex in V2

  62. A graph is a subgraph of a graph G if, and only if, (1)__(a)__, (2)__(b)__, and (3) __(c)__.
    • (a)every vertex in H is also a vertex in G
    • (b) every edge in is also an edge in 
    • (c) every edge in has the same endpoints as it has in G. 
  63. The degree of a vertex in a graph is ___.
    the number of edges that are incident on the vertex, with an edge that is a loop counted twice.
  64. The total degree of a graph is defined as ___.
    the sum of the degrees of all the verticies of the graph
  65. The handshake theorem says that the total degree of a graph is ___. 
    equal to twice the number of edges in the graph
  66. in any graph the number of vertices of odd degree is ___.
    an even number.
  67. Let be a graph and and be vertices in G, 

    A walk from to is ____.
    a finite alternating sequence of adjacent verticies and edges of 
  68. Let G be a graph and v and w be vertices in G,

    A trail from to is ____.
    a walk that does not contain a repeated edge
  69. Let G be a graph and v and w be vertices in G,

    a path from to is ____.
    a trail that does not contain a repeated vertex
  70. Let G be a graph and v and w be vertices in G,

    a closed walk is ____. 
    a walk that starts and ends at the same vertex
  71. Let G be a graph and v and w be vertices in G,

    A circuit is ____. 
    a closed walk that contains at least one edge and does not contain a repeated edge
  72. Let G be a graph and v and w be vertices in G,

    a simple circuit is ____. 
    a circuit that does not have any repeated vertex other than the first and the last
  73. Let G be a graph and v and w be vertices in G,

    a trivial walk is ____.  
    a walk consisting of a single vertex and no edge
  74. Let G be a graph and v and w be vertices in G,

    vertices and are connected if, and only if, ____. 
    there is a walk from to w
  75. A graph is connected if, and only if, ____.
    given any two verticies in the graph, there is a walk from one to the other
  76. Removing an edge from a circuit in a graph does not ____.
    disconnect the graph
  77. An Euler circuit in a graph is ____.
    a circuit that contains every vertex and every edge of the graph 
  78. A graph has an Euler circuit if, and only if, ____.
    the graph is connected, and every vertex has positive, even degree
  79. Given verticies and in a graph, there is a Euler path from to if, and only if, ____.
    the graph is connected,  and have odd degree, and all other vertices have positive even degree
  80. A Hamiltonian circuit in a graph is ____.
    a simple circuit that includes every vertex of the graph 
  81. If a graph has a Hamiltonian circuit, then has a sub graph with the following properties: __(a)__, __(b)__, __(c)__, and __(d)__.
    • (a) contains every vertex of G
    • (b) H is connected 
    • (c) H has the same number of edges as vertices
    • (d) every vertex of has degree 2
  82. A traveling salesman problem involves finding a ____ that minimizes the total distance of traveled for a graph in which each edge is marked with a distance.
    Hamiltonian circuit
  83. In the adjacency matrix for a directed graph, the entry in the ith rowand jth colum is ____.
    the number of arrows from vi (the ith vertex) to vj (the jth vertex)
  84. In the adjacency matrix for an undirected graph, the entry in the ith row and jth column is ___.
    the number of edges connecting vi (the ith vertex) and vj (the jth vertex)
  85. An n *  n square matrix is called symmetric if, and only if, for all integers i and from to , the entry row __(a)__, and column__(b)___, equals the entry row __(c)__ and column__(d)__.
    • (a) 
    • (b) j 
    • (c) j
    • (d) i
  86. the ijth entry in the product of two matrices A and is obtained by multiplying row __(a)__ of by row __(b)__ of B 

  87. In an n * n identity matrix the entries on the main diagonal are all __(a)__ and the off-diagonal entries are all __(b)__.
    • (a) 1 
    • (b) 0
  88. if is a graph with verticies v1, v2, ..., vm, and is the adjacency matrix of G, then for each positive integer and for all integers i and with j = 1, 2, ...m, the ijth entry of An = ___.
    the number of walks of length from vi to vj
  89. T/F? if f(n) is O(g(n)) then g(n) is Image Upload 38
  90. T/F? Mergesort and Quicksort have the same worst-case running time. 
  91. T/F? Postorder traversal visits the nodes of a binary search tree (with no duplicate keys) in decreasing order of their keys.
  92. T/F? If every box of jelly-beans contains 20 to 30 beans then I only need to collect 23 boxes to be sure that three of my boxes contain teh same number of beans.
  93. T/F? Skip list nodes (with maximum height 16) are most likely to have height 1 than height 2. 
  94. T/F? For all a, b > 1, Image Upload 39
  95. T/F? An algorithm with worst-case running time O(n) is faster then an algorithm with a best-case running time Image Upload 40 on any input.
  96. T/F? 
    int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } is tail recursive.
  97. Suppose, int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } takes Image Upload 41 to complete when = 10,000 a reasonable prediction of its running time when n = 1,000,000 is : (a) Image Upload 42, (b) 105Image Upload 43, (c) Image Upload 44, (d) Image Upload 45
  98. T/F? The height of a rooted tree with nodes is at most - 1
  99. 3 % 11 = 
  100. 14 % 11 = 
  101. 13 % 11 = 
  102. 2 %  11 = 
  103. 24 % 11 = 
  104. 24 % 7 = 
  105. 14 % 7 = 
  106. 17 % 7 = 
  107. 11 % 7 =
  108. There are ____ different ways of arranging n distinct objects into a sequence, the permutations of those objects.
  109. A sample space of a random process or experiement is ___.
    the set of all outcomes of the random process or experiement
  110. An event in a sample space is ___.
    a subset of the sample space
  111. To compute the probability of an event using the equally likely probability formula, you take the ratio of the __(a)__ to the __(b)__.
    • (a) number of outcomes in the event
    • (b) total number of outcomes
  112. if  Image Upload 46, the number of integers from to inclusive is ___.
    - m + 1
  113. The multiplication rule syas that if an operation can be performed in steps and for each with Image Upload 47, the ith step can be performed in ni ways (regaurdless of how previous steps were performed), then the operation as a whole can be performed in ___.
    n1n2...nk ways
  114. A permutation of a set of elements is ___.
    an ordering of the elements of the set in a row
  115. The number of permutations of a set of elements equals ___.
  116. An r-permutation of a set of elements is ___.
    an ordered selection of of the elements of the set
  117. the number of r-permutations of a set of elements is denoted ___.
    P(n, r)
  118. One formula for the numner of r-permutations  of a set of  elements is __(a)__ and another formula is __(b)__.
    • (a) - 1 ) ( - 2 ) ... ( + 1)
    • (b)Image Upload 48
  119. The addition rule says that if a finite set equals the union of dsitinct mutally disjoint subsets A1  , A, ... , Ak , then ____.
    • the number of elements in equals N(A1) + N(A2) + ...+ N(An)
  120. The difference rule says that if is a finite set and is a subset of A, then ___.
    The number of elements in A - B is the difference between the number of elements in and the number of elements in B , that is, N(A-B) = N(A) - N(B)
  121. If is a finite sample space and is an event in S, Then the probability of Ac equals ____.
    1 - P(A)
  122. The inclusion/exclusion rule for two sets says that if  and are  any finite sets, then ____.
    Image Upload 49
  123. The inclusion/exclusion rule for three sets says if A, B, and are any finite sets, then ____.
    Image Upload 50
  124. The pigeonhole principal states that ___.
    if pigeons fly into pigeonholes and n > m , then at least two pigeons fly into the same pigeonhole. OR a funcion form one finite set to a smaller finite set cannot be one-to-one
  125. The generalized pigeonhole principal states that ___.
    if pigeons fly into pigeonholes and, for some positive integer k , k < n/m, then at least one pigeonhole contains +1 or more pigeons OR for any funcion from a finite set with elements to a finite set with elements and for any positive integer , if k < n/m, then there is some Image Upload 51 such that is the image of at least k +1 distinct elements of Y.
  126. If and are finite sets and is a function form to then is one-to-one iff ___.
    f  is onto
  127. Image Upload 52
    Image Upload 53
Card Set:
cpsc221 M2 Flashcards

CPSC 221 M2 Flashcards
Show Answers: