Things from notes

Question 1

C(n, 2) = ?

Without any factorials

Answer 1

2

Question 2

How many comparisons does an algorithm that finds duplicates in an array?

Answer 2

C(n, 2)

Question 3

Comparisons needed to find the max value in an array?

Answer 3

n-1

Question 4

Comparisons needed in a bubble sort?

Answer 4

C(n, 2)

Question 5

Factorial notation for C(n, k)

Answer 5

k!(n-k)!

Question 6

Factorial notation for P(n, k)

Answer 6

(n-k)!

Question 7

Comparisons on n elements for search?

Answer 7

n

Question 8

Comparisons on n elements for BSearch?

Answer 8

log2n + 1

Question 9

General type of decomp recursions for:

Build a fractal like Koch snowflake

Answer 9

Bottom up

Question 10

General type of decomp recursions for:

Binary search and merge

Answer 10

Divide and conquer

Question 11

General type of decomp recursions for:

Reverse a string by moving last element to from, recurse on rest

Answer 11

Top Down

Question 12

General type of decomp recursions for:

Check if a string is a palindrome

Answer 12

edge and middle

Question 13

General type of decomp recursions for:

Calculate the factorial of n as a recursive program taking a single formal parameter.

Answer 13

Top Down

Question 14

General type of decomp recursions for:

Reverse characters in an array in place.

Answer 14

Edges and middle

Question 15

Closed form solution for the sum of n positive integers?

Answer 15

2

Question 16

Define a function C(n) as follows:
1 if n = 0
2*C(n-1) if n > 0
What is the closed form solution?

Answer 16

2^n

Question 17

Closed form solution for sum of n odd integers?

Answer 17

n^2

Question 18

Closed form solution for sum of n even numbers?

Answer 18

n*(n+1)

Question 19

Geometric proof form closed for solution of sum of n integers?

Answer 19

Draw stacks and then duplicate and flip mirror image on to top.

Question 20

Geometric proof form closed for solution of sum of n integers?

Answer 20

Draw square made of n cubes and then add a layer for each n.

Question 21

What is proof by contraposition?

Answer 21

Prove “If P, Then Q” by the method of contrapositive means to prove “If Not Q, Then Not P”

Question 22

What is generative recursion?

Answer 22

usually decomposes the original problem into sub-problems to solve it, works on newly generated data

Question 23

What is structural recursion?

Answer 23

usually decomposes on the data orignal data rather than decomposing the problem int smaller pieces, works on smaller immediate structural component of input

Question 24

What is the difference for inductive proofs when using k or k -1 as IH?

Answer 24

For k -1 k > 1 for IH, and for k, k >= 1 for IH.

Question 25

If you have n elements how many comparisons does it take to do a search in terms of n-1?

Answer 25

T(1) = 1
T(n) = T(n-1) + 1

Question 26

If you have n elements how many comparisons does it take to do a bsearch in terms of n-1?

Answer 26

T(1) = 1
T(n) = T(n/2) + 1

Question 27

How many different binary code words are there of length n?

Answer 27

2^n

Question 28

Binomial theorem

Answer 28

if j +k = n

a^h*b^k in expansion of (a+b)^n is C(n, j)

Question 29

How to approach circle problem

Answer 29

Places to break circle * 2 on each side

Question 30

A complete graph with n vertices has how many edges?

Answer 30

n choose 2