CSC 225 Midterm 1

Question 1

What is a permutation?

Answer 1

Number of possible linear combinations where we count all different orderings of elements

Question 2

Permutation Formula

Answer 2

n!/(n-r)!

Question 3

What is a combination?

Answer 3

Number of possible linear combinations where we dont count separate orderings of elements.

Question 4

Combination Formula

Answer 4

n!/[k!(n-k)!]

Question 5

Binomial Formula

Answer 5

Formula:

Question 6

What is the Pigeonhole Principle

Answer 6

If m pigeons occupy n pigeonholes then and m > n, then at least 1 pigeonhole has 2 pigeons in it.

Question 7

simplify

Answer 7

Question 8

simplify

Answer 8

Question 9

simplify

Answer 9

Question 10

simplify

Answer 10

Question 11

memorize logarithm bullshit

Answer 11

Question 12

Formal Definition of Big - Oh

Answer 12

let f: N+ -> R and g: N+ -> R

f(n) is O(g(n)) IFF there exists a constant c > 0 and n_o > 0 such that

f(n) <= c g(n) for all n > n_o

[f(n) curve must fit under cg(n) curve]

Question 13

What is Stirlings Formula?

(approx for n!)

Answer 13

Question 14

How does a stack work?

Answer 14

Stacks follow a LIFO principle.

Question 15

What methods does stack have

Answer 15

push

pop

isEmpty

top

size

Question 16

Worst case and Best case time of selection sort

Answer 16

O(n^2), O(n^2)

Question 17

Worst Case / Best Case Insertion Sort

Answer 17

O(n^2), O(n)

Question 18

Worst Case / Best Case Bubble Sort

Answer 18

O(n^2), O(n)

Question 19

Worst Case / Best Case Quicksort

Answer 19

O(n^2), O(nlogn)

Question 20

Worst Case / Best Case Heap Sort

Answer 20

O(nlogn), O(nlogn)

Question 21

Worst Case / Best Case Merge Sort

Answer 21

O(nlogn), O(nlogn)