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 fornext 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 worstcase order of the insertion sort algorithm is _(a)__, and its averagecase order is _(b)___.

for all integers n >= 1
OR

for any real number r except 1, and any integer n >= 0
OR
1 + r + r^{2}+...r^{n = }

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, x^{2}, log_{b}x, andare arranged in order of increasing size, the result is ___.
log_{b}x < x < x log_{b }x < x^{2}

if n is a positive integer, then 1 + 1/2 +1/3 +...+1/n has order ___.
ln x or equivantly log_{2}x







Is the same as_____.





To solve a problem using a divideandconquer 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 ___.
log_{2}n, 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 log_{2}n

QuickSort
Best:
Average:
Worst:
Memory:
Stable:
 Best: n log n
 Average: n log n
 Worst: n^{2}
 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: n^{2}
 Worst: n^{2}
 Memory: 1
 Stable: yes


Recurrence for Binary Search is: T(n)=
BigO solution:
T(n/2) + O(1)
O(log n)

Recurrence for Sequential Search is: T(n) =
BigO solution:

Recurrence for Tree Traversal: T(n)
BigO solution:

Recurrence for Mergesort and Average case Quicksort: T(n) =
BigO solution:

Recurrence for Selection Sort (other n^{2} sorts): T(n) =
BigO solution:

What is the formula to calculate the balance for each node in an AVL tree with height h ?
h_{R}  h_{L }_{ }where h_{R}_{ }and h_{L}_{ }are the heights of the left and right subtrees, respectively.

A tree is called a LeftLeft tree because ___.
its root and left subtree of the root are both leftheavy

What is the Balance Property of an AVLTree for all nodes x?
 Result: height is

To balance AVLTree 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 V_{1} and V_{2} in such a way that (1) each of the m vertices in V_{1} is __(a)__ to each of the n vertices in V_{2}, no vertex in V_{1}_{ }is connected to ___(b)__, and no vertex in V_{2}_{ }is connected to __(c)__.
 (a) connected by an edge
 (b) any other vertex V_{1}
 (c) any other vertex in V_{2}

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 v_{i}_{ }(the ith vertex) to v_{j}_{ }(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 v_{i}_{ }(the ith vertex) and v_{j}_{ }(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 offdiagonal entries are all __(b)__.

if G is a graph with verticies v_{1}, v_{2}, ..., v_{m}, 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 A^{n}^{ }= ___.
the number of walks of length n from v_{i} to v_{j}

T/F? if f(n) is O(g(n)) then g(n) is
True

T/F? Mergesort and Quicksort have the same worstcase 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 jellybeans 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 worstcase running time O(n) is faster then an algorithm with a bestcase running time on any input.
False

T/F?
int sum(int n) { if ( n==0 ) return 0; else return n+sum(n1); } is tail recursive.
False

Suppose, int sum(int n) { if ( n==0 ) return 0; else return n+sum(n1); } 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 n_{i}_{ }ways (regaurdless of how previous steps were performed), then the operation as a whole can be performed in ___.
n_{1}n_{2}...n_{k}_{ }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 rpermutation of a set of n elements is ___.
an ordered selection of r of the elements of the set

the number of rpermutations of a set of n elements is denoted ___.
P(n, r)

One formula for the numner of rpermutations 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 A_{1 }, A_{2 }, ... , A_{k}_{ }, then ____.
 the number of elements in A equals N(A_{1}) + N(A_{2}) + ...+ N(A_{n})

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(AB) = N(A)  N(B)

If S is a finite sample space and A is an event in S, Then the probability of A^{c}^{ }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 onetoone

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 onetoone iff ___.
f is onto


