These are optional exercises that I suggest you try to practice the material we've learned so far.
For each pair of functions f and g, determine whether f(n) = O(g(n)).
f(n) |
g(n) |
---|---|
10n + 4 |
4n + 10 |
1000 |
1 |
|sin(n)| |
1 |
1 |
|sin(n)| |
2^{n}^{ }^{+ 1} |
2^{n} |
2^{2}^{n} |
2^{n} |
n^{16} |
2^{n} |
log_{2}(n) |
log_{10}(n) |
`2^sqrt(n)` |
n |
[log(n)]^{10} |
n^{0.1} |
`sqrt(n)` |
n^{sin }^{n} |
n^{log }^{5} |
5^{log }^{n} |
Is it true that for all eventually positive functions f, f(n) = O(f(n)^{2})?
Prove that for all asymptotically positive functions f and g,
f(n) + g(n) = O(max(f(n), g(n)))
Give an example of two asymptotically positive continuous functions f and g for which neither f(n) = O(g(n)) nor g(n) = O(f(n)).
Write a program copy
that takes two
filenames as command-line arguments and copies the first (a text
file) to the second. If the second file already exists, it should be
overwritten. For example:
$ copy prog.pas prog2.pas
Solve Project Euler’s Problem 3.
Solve Project Euler’s Problem 7.
Solve Project Euler’s Problem 10.
Write a function that takes two strings s and t and returns an integer which is
1 if s > t
0 if s = t
-1 if s < t
where comparisons are performed in lexicographic (dictionary) order. You should treat uppercase and lowercase letters as the same, and ignore all non-alphabetic characters (i.e. act as if that they are absent from the strings). Do not use the built-in string comparison operators < or >.
Write a program that reads a string and writes a random permutation of the characters in the string. All permutations should be equally likely. Your program should run in time O(n), where n is the length of the input string.
Write a program that reads a number n as input, and prints out the first n digits of π.
Hint: `π / 4 = 1 – (1/3) + (1/5) - (1/7) + ...`
Write a program that reads four real numbers a, b, c, and d. The program should write 'overlap' if the line segments [a, b] and [c, d] touch or overlap, or 'disjoint' otherwise.
Input:
3 10 8 15
Output:
overlap