1 Combinatorics
- How many different ways are there to order a list containing 100 distinctelements?
- 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.
- 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?
- How many different ways are there to order the letters contained in theword engineering?
2 Asymptotic order
- 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 |
- 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)).
1
Reviews
There are no reviews yet.