Algorithms For Bioinformatics: Quiz 1

Front 1

what is the number of ways you can put n items in a row?

Back 1

Number of orderings of n elements is:

n!

Front 2

what is the number of ways you can pick k items out of n?

Back 2

Number of k-subsets of n elements is:

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

Front 3

What is the number of subsets of a set of size n?

Back 3

Number of subsets of n elements is:

2^n

Front 4

What is the number of ways you can assign k colors to the vertices of a graph?

Back 4

Number of k-colorings of a graph is:

k^n

Front 5

What is the number of ways you can match up n boys to n girls?

Back 5

Number of ways to match n boys to n girls is:

n!

Front 6

What is the algorithm for putting n items in a row?

Back 6

S = {s1,s2,s3....sn}

For i=1 up to n, DO
- Pick an item from set S to go in position i
- Delete that item from the set S

Front 7

What is the algorithm for the number of subsets of a set of size n?

Back 7

S = {s1,s2,s3....sn}

For i=1 up to n, DO
-Decide if you will include si

Front 8

What is the algorithm for k-coloring a graph?

Back 8

Let G have vertices v1,v2,....vn

For i=1 up to n, DO
-pick a color for vertex vi

Front 9

What is the algorithm for matching n boys and girls?

Back 9

Let the boys be B1,B2...Bn and girls be G1,G2..Gn. Initially, all girls available.

For i=1 up to n, DO
-Pick a girl for a boy Bi from the set of available girls. Remove the girl from the set of available girls.

Front 10

What is the algorithm for picking k items out of n?

Back 10

S = {s1,s2,s3....sn}

For i=1 up to n, DO
-Pick an item from S to include in set A
-Delete that item from the set S

Front 11

What is the algorithm for a two pile rock game?

Back 11

M(i,j):
-1 if M(i-1,j-1) or M(i-1,j) or M(i,j-1) is 2
-2 otherwise

Front 12

f(n) is O(g(n)) if

Back 12

f(n)≤cg(n) for all n≥C'

Front 13

Give the common order of function for Big O analysis

Back 13

from smallest to largest:
O(1) constant
O(log n) logarithmic
O((log n)^c) polylogarithmic
O(n) linear
O(n log n) loglinear
O(n^2) quadratic
O(n^c) polynomial
O(c^n) exponential
O(n!) factorial
O(n^n) n to the n

Front 14

What is the number of k-subsets of a set S=(s1,s2...sn) in which s1 and s2 are adjacent?

Back 14

2(n-1)!

Front 15

What is the number of k-subsets of a set S=(s1,s2...sn) in which s1 and s2 are not adjacent?

Back 15

n!-2(n-1)!