The flashcards below were created by user
forrest.allen57
on FreezingBlue Flashcards.
-
A rooted tree is a tree in which ______.
One vertex is distinguished from the others and is called the root
-
The level of a vertex in a rooted tree is ____.
the number of edges along the unique path between it and the root
-
The height of a rooted tree is ____.
the maximum level of any vertex of the tree
-
A binary tree is a rooted tree in which ____.
every parent has at most two children
-
A full binary tree is a rooted tree in which ____.
every parent has exactly two children
-
If k is a positive integer and T is a full binary tree with k internal verticies, then T has a total of __(a)___ verticies and ___(b)__ terminal verticies
-
If T is a binary tree that has t terminal verticies and height h, then t and h are related by the inequality ______.
 or 
-
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
-
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.
n
-
The worst-case order of the insertion sort algorithm is _(a)__, and its average-case order is _(b)___.
-
for all integers n >= 1
OR
-
for any real number r except 1, and any integer n >= 0
OR
1 + r + r2+...rn =
-
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
-
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
-
if k is an integer and  then 
k
-
If b is a real number with b > 1 and if x 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 logb x < x2
-
if n is a positive integer, then 1 + 1/2 +1/3 +...+1/n has order ___.
ln x or equivantly log2x
-
-
-
-
-
-
-
 Is the same as_____.
-
-
-
-
-
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
-
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
-
The worst case order of the binary search algorithm is ___.
log2n, where n is the length of the array
-
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.
-
The worst case order of the merge sort algorithm is ___.
n log2n
-
QuickSort
Best:
Average:
Worst:
Memory:
Stable:
- Best: n log n
- Average: n log n
- Worst: n2
- Memory: log n
- Stable: depends
-
Merge Sort
Best:
Average:
Worst:
Memory:
Stable:
- Best: n log n
- Average: n log n
- Worst: n log n
- Memory: depends; worst case is n
- Stable: yes
-
Heapsort
Best:
Average:
Worst:
Memory:
Stable:
- Best: n log n
- Average: n log n
- Worst: n log n
- Memory: 1
- Stable: no
-
Insertion Sort
Best:
Average:
Worst:
Memory:
Stable:
- Best: n
- Average: n2
- Worst: n2
- Memory: 1
- Stable: yes
-
-
Recurrence for Binary Search is: T(n)=
Big-O solution:
T(n/2) + O(1)
O(log n)
-
Recurrence for Sequential Search is: T(n) =
Big-O solution:
-
Recurrence for Tree Traversal: T(n)
Big-O solution:
-
Recurrence for Mergesort and Average case Quicksort: T(n) =
Big-O solution:
-
Recurrence for Selection Sort (other n2 sorts): T(n) =
Big-O solution:
-
What is the formula to calculate the balance for each node in an AVL tree with height h ?
hR - hL where hR and hL are the heights of the left and right subtrees, respectively.
-
A tree is called a Left-Left tree because ___.
its root and left subtree of the root are both left-heavy
-
What is the Balance Property of an AVL-Tree for all nodes x?
 - Result: height is
-
To balance AVL-Tree balance(x) =
height(x.left) - height(x.right)
NB: height(NULL) = -1
-
-
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
-
Binary Heap Navigation:
left_child(i) = (a)
right_child(i) = (b)
parent(i) = (c)
root() = (d)
next_free_pos() = (e)
-
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
-
A loop in a graph is ____
an edge with a single endpoint
-
Two distinct edges in a graph are parallel if, and only if, ___.
they have the same set of endpoints
-
Two vertices are called adjacent if and only if __.
they are connected by an edge.
-
An edge is incident on ____.
each of its endpoints.
-
Two edges incident on the same endpoint are ___.
adjacent
-
A vertex on which no edges are incident is ___.
isolated
-
In a directed graph, each edge is associated with ___.
an ordered pair of vertices called its endpoints
-
a simple graph is ___.
a graph with no loops or parallel edges
-
A complete graph on n vertices is a ___.
simple graph with n vertices whose set of edges contains exactly one edge for each pair of verticies.
-
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 m vertices in V1 is __(a)__ to each of the n vertices in V2, no 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
-
A graph H 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 H is also an edge in G
- (c) every edge in H has the same endpoints as it has in G.
-
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.
-
The total degree of a graph is defined as ___.
the sum of the degrees of all the verticies of the graph
-
The handshake theorem says that the total degree of a graph is ___.
equal to twice the number of edges in the graph
-
in any graph the number of vertices of odd degree is ___.
an even number.
-
Let G be a graph and v and w be vertices in G,
A walk from v to w is ____.
a finite alternating sequence of adjacent verticies and edges of G
-
Let G be a graph and v and w be vertices in G,
A trail from v to w is ____.
a walk that does not contain a repeated edge
-
Let G be a graph and v and w be vertices in G,
a path from v to w is ____.
a trail that does not contain a repeated vertex
-
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
-
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
-
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
-
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
-
Let G be a graph and v and w be vertices in G,
vertices v and w are connected if, and only if, ____.
there is a walk from v to w
-
A graph is connected if, and only if, ____.
given any two verticies in the graph, there is a walk from one to the other
-
Removing an edge from a circuit in a graph does not ____.
disconnect the graph
-
An Euler circuit in a graph is ____.
a circuit that contains every vertex and every edge of the graph
-
A graph has an Euler circuit if, and only if, ____.
the graph is connected, and every vertex has positive, even degree
-
Given verticies v and w in a graph, there is a Euler path from v to w if, and only if, ____.
the graph is connected, v and w have odd degree, and all other vertices have positive even degree
-
A Hamiltonian circuit in a graph is ____.
a simple circuit that includes every vertex of the graph
-
If a graph G has a Hamiltonian circuit, then G has a sub graph H with the following properties: __(a)__, __(b)__, __(c)__, and __(d)__.
- (a) H contains every vertex of G
- (b) H is connected
- (c) H has the same number of edges as vertices
- (d) every vertex of H has degree 2
-
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
-
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)
-
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)
-
An n * n square matrix is called symmetric if, and only if, for all integers i and j from 1 to n , the entry row __(a)__, and column__(b)___, equals the entry row __(c)__ and column__(d)__.
-
the ijth entry in the product of two matrices A and B is obtained by multiplying row __(a)__ of A by row __(b)__ of B
(a) i
(b) j
-
In an n * n identity matrix the entries on the main diagonal are all __(a)__ and the off-diagonal entries are all __(b)__.
-
if G is a graph with verticies v1, v2, ..., vm, and A is the adjacency matrix of G, then for each positive integer n and for all integers i and j with i , j = 1, 2, ...m, the ijth entry of An = ___.
the number of walks of length n from vi to vj
-
T/F? if f(n) is O(g(n)) then g(n) is 
True
-
T/F? Mergesort and Quicksort have the same worst-case running time.
False
-
T/F? Postorder traversal visits the nodes of a binary search tree (with no duplicate keys) in decreasing order of their keys.
False
-
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.
True
-
T/F? Skip list nodes (with maximum height 16) are most likely to have height 1 than height 2.
True
-
T/F? For all a, b > 1, 
True
-
T/F? An algorithm with worst-case running time O(n) is faster then an algorithm with a best-case running time  on any input.
False
-
T/F?
int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } is tail recursive.
False
-
Suppose, int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } takes  to complete when n = 10,000 a reasonable prediction of its running time when n = 1,000,000 is : (a)  , (b) 105  , (c)  , (d) 
(c)
-
T/F? The height of a rooted tree with n nodes is at most n - 1
True
-
-
-
-
-
-
-
-
-
-
There are ____ different ways of arranging n distinct objects into a sequence, the permutations of those objects.
n!
-
A sample space of a random process or experiement is ___.
the set of all outcomes of the random process or experiement
-
An event in a sample space is ___.
a subset of the sample space
-
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
-
if  , the number of integers from m to n inclusive is ___.
n - m + 1
-
The multiplication rule syas that if an operation can be performed in k steps and for each i with  , 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
-
A permutation of a set of elements is ___.
an ordering of the elements of the set in a row
-
The number of permutations of a set of n elements equals ___.
n!
-
An r-permutation of a set of n elements is ___.
an ordered selection of r of the elements of the set
-
the number of r-permutations of a set of n elements is denoted ___.
P(n, r)
-
One formula for the numner of r-permutations of a set of n elements is __(a)__ and another formula is __(b)__.
- (a) n ( n - 1 ) ( n - 2 ) ... ( n - r + 1)
- (b)
-
The addition rule says that if a finite set A equals the union of k dsitinct mutally disjoint subsets A1 , A2 , ... , Ak , then ____.
- the number of elements in A equals N(A1) + N(A2) + ...+ N(An)
-
The difference rule says that if A is a finite set and B is a subset of A, then ___.
The number of elements in A - B is the difference between the number of elements in A and the number of elements in B , that is, N(A-B) = N(A) - N(B)
-
If S is a finite sample space and A is an event in S, Then the probability of Ac equals ____.
1 - P(A)
-
The inclusion/exclusion rule for two sets says that if A and B are any finite sets, then ____.
-
The inclusion/exclusion rule for three sets says if A, B, and C are any finite sets, then ____.
-
The pigeonhole principal states that ___.
if n pigeons fly into m 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
-
The generalized pigeonhole principal states that ___.
if n pigeons fly into m pigeonholes and, for some positive integer k , k < n/m, then at least one pigeonhole contains k +1 or more pigeons OR for any funcion f from a finite set X with n elements to a finite set Y with m elements and for any positive integer k , if k < n/m, then there is some  such that y is the image of at least k +1 distinct elements of Y.
-
If X and Y are finite sets and f is a function form X to Y then f is one-to-one iff ___.
f is onto
-
|
|
