1 Combinatorics
1. How many different ways are there to order a list containing 100 distinctelements?
2. A palindrome is a word that can be read in both directions, such as “madam” or “noon”. How many 7-letter palindromes can be formed using the letters of the alphabet A? Start by choosing the alphabet and write down the number of letters, e.g. the English alphabet has 26 letters. (Please only choose alphabets that have 10 and < 50 letters). Then calculate the number of palindromes.
3. A graph is complete if any pair of its vertices is connected by an edge. How many edges are there in a complete graph with 5 vertices? What about 25 vertices and n vertices?
4. How many different ways are there to order the letters contained in theword ”engineering”?
2 Asymptotic order
1. Take the following list of functions and arrange them in ascending orderof growth rate. That is, if function f(n) comes before function g(n) in your list, then it should be the case that f(n) is O(g(n)).
f1(n)
=
5n
f2(n)
=
n1.5
f3(n)
=
22n
f4(n)
=
n300
f5(n)
=
2n2
f6(n)
=
n(logn)2
f7(n)
=
nloglogn
f8(n)
=
nlogn
2. For any two functions f(n) and g(n) that immediately follow each other in your list, prove that f(n) is O(g(n)).
