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)| |
|
2n + 1 |
2n |
|
22n |
2n |
|
n16 |
2n |
|
log2(n) |
log10(n) |
|
`2^sqrt(n)` |
n |
|
[log(n)]10 |
n0.1 |
|
`sqrt(n)` |
nsin n |
|
nlog 5 |
5log 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