Midterm

Question 1

What is the definition of Euer’s constant?

1. N2/3
2. The error calculated during a summation series.
3. 0.57721566
4. The sum of all the errors for a Taylor Series

Answer 1

0.57721566

Question 2

What is proof by Induction?

1. A recursive definition that shows the trivial case is true.
2. Showing that that something is true for a certain number k, and then showing it is true for k+1.
3. That the alternative is false.
4. A proof that states that it must be true if no one can find where it is false.

Answer 2

Showing that that something is true for a certain number k, and then showing it is true for k+1.

Question 3

What is the definition of a recursive function or routine?

A function that calls itself.
A function that cannot call itself.
A function that can be used inside of another function.
A function that returns no values.

Answer 3

A function that calls itself

Question 4

What is the difference between a class and an object?

  A class is a definition while an object is the actual data.
  The object is the definition and the class is the actual data.
  There is no difference...they are the same thing.
  The class is the actual programming source code while the object is the executable.

Answer 4

A class is a definition while an object is the actual data.

Question 5

Complexity Analysis measures _______ and _____

Answer 5

time and memory

Question 6

____________ counts the number of operation that we expect to take the most time.

Answer 6

Operation Count

Question 7

_____________ analysis describe the rate at which execution time increases in relation to the input size.

Answer 7

Asymptotic

Question 8

The main focus of algorithmic analysis is the relationship between __________ and __________.

Answer 8

Running Time

Input Size

Question 9

What are the two methods of analyzing algorithms?

Answer 9

Experimental Analysis

Theoretical Analysis

Question 10

A type of analysis that requires algorithms to be coded and run to determine the results.

Answer 10

Experimental Analysis

Question 11

f(n) = c

Answer 11

The constant function

Question 12

Give three examples of operations defined by the constant function.

Answer 12

arithmentic Calculation, comparison operation, variable declaration, assignment statement, invoking a method or function.

Question 13

Give an example of an algorithm that can be described using the logarithmic function?

Answer 13

binary search

Question 14

Logorithmic functions grow __________ as the value of n grows?

Answer 14

Slower

Question 15

The Linear function states that f(n) =

Answer 15

n

Question 16

The size of the size of a linear function doubles when the input __________.

Answer 16

doubles

Question 17

The NlogN function is grows ________ than the linear function.

Answer 17

faster

Question 18

Give an example of an N-Log-N function.

Answer 18

merge sort

Question 19

A Quadratic function grows _________ than an N-Log-N function?

Answer 19

faster

Question 20

A nested loop represents what type of function?

Answer 20

Quadratic Function

Question 21

A bubble sort is what type of function?

Answer 21

Quadratic Function

Question 22

This notation represents the ___________ function

O(1).

Answer 22

Constant

Question 23

Assume that algorithm 1 takes
time t1(n) = 100n+n2
and algorithm 2 takes
time t2(n) = 10n2

If the function has 10 inputs which algorithm is faster?

Answer 23

t2

Question 24

Assume that algorithm 1 takes
time t1(n) = 100n+n2
and algorithm 2 takes
time t2(n) = 10n2

If the algorithm has 1000 inputs which is faster?

Answer 24

t1

Question 25

Assume algorithms with the following times
Algorithm 1: insert - n, delete - log n, lookup - 1
Algorithm 2: insert - log n, delete - n, lookup - log n

Which algorithm is faster for an application with many lookups and few inserts?

Answer 25

Algorithm 1

Question 26

What is the primary function of Asymptotic Complexity Analysis?

Answer 26

It compares the growth rate of two functions.

Question 27

What are two factors that are eliminated when performing Asymptotic Complexity?

Answer 27

constant multipliers (co-efficient)
lower-order effects

Question 28

What type of notation if described here

T(N) <= cf(N)

Answer 28

BIG O

Question 29

What type of notation if described here

T(N) >= cf(N)

Answer 29

Omega

Question 30

What type of notation if described here

T(N) = cf(N)

Answer 30

Theta

Question 31

What type of notation if described here

T(N) < cf(N)

Answer 31

Little O

Question 32

f(N) = N logN and g(N) = N^1.5

Which one grows faster??

Answer 32

g(N)

Question 33

Name the 4 steps in Complexity Analysis

Answer 33

Find the size of input n = size of the input
Find atomic operations
define f(n) as the number of atomic activities done by an input size of n.
define the complexity of the algorithm as the complexity of f(n)

Question 34

What is the complexity of the following?

for (int i = 0; i < n; ++i){
  //operation
  if( condition) break;
}

Answer 34

O(n)

Question 35

if(condition) 
	i = 0;
else
	for ( j = 0; j < n; j++)
		a[j] = j;

Answer 35

O(N)