Things from notes Flashcards
C(n, 2) = ?
Without any factorials
2
How many comparisons does an algorithm that finds duplicates in an array?
C(n, 2)
Comparisons needed to find the max value in an array?
n-1
Comparisons needed in a bubble sort?
C(n, 2)
Factorial notation for C(n, k)
k!(n-k)!
Factorial notation for P(n, k)
(n-k)!
Comparisons on n elements for search?
n
Comparisons on n elements for BSearch?
log2n + 1
General type of decomp recursions for:
Build a fractal like Koch snowflake
Bottom up
General type of decomp recursions for:
Binary search and merge
Divide and conquer
General type of decomp recursions for:
Reverse a string by moving last element to from, recurse on rest
Top Down
General type of decomp recursions for:
Check if a string is a palindrome
edge and middle
General type of decomp recursions for:
Calculate the factorial of n as a recursive program taking a single formal parameter.
Top Down
General type of decomp recursions for:
Reverse characters in an array in place.
Edges and middle
Closed form solution for the sum of n positive integers?
2
Define a function C(n) as follows:
1 if n = 0
2*C(n-1) if n > 0
What is the closed form solution?
2^n
Closed form solution for sum of n odd integers?
n^2
Closed form solution for sum of n even numbers?
n*(n+1)
Geometric proof form closed for solution of sum of n integers?
Draw stacks and then duplicate and flip mirror image on to top.
Geometric proof form closed for solution of sum of n integers?
Draw square made of n cubes and then add a layer for each n.
What is proof by contraposition?
Prove “If P, Then Q” by the method of contrapositive means to prove “If Not Q, Then Not P”
What is generative recursion?
usually decomposes the original problem into sub-problems to solve it, works on newly generated data
What is structural recursion?
usually decomposes on the data orignal data rather than decomposing the problem int smaller pieces, works on smaller immediate structural component of input
What is the difference for inductive proofs when using k or k -1 as IH?
For k -1 k > 1 for IH, and for k, k >= 1 for IH.
If you have n elements how many comparisons does it take to do a search in terms of n-1?
T(1) = 1 T(n) = T(n-1) + 1
If you have n elements how many comparisons does it take to do a bsearch in terms of n-1?
T(1) = 1 T(n) = T(n/2) + 1
How many different binary code words are there of length n?
2^n
Binomial theorem
if j +k = n
a^h*b^k in expansion of (a+b)^n is C(n, j)
How to approach circle problem
Places to break circle * 2 on each side
A complete graph with n vertices has how many edges?
n choose 2
