Source code online books for professionals by professionals

Appendix d
Hints for Exercises
To solve any problem, here are three questions to ask yourself: First, what could I do? Second, what 
could I read? And third, who could I ask?
— Jim Rohn
Chapter 1
1-1. As machines get faster and get more memory, they can handle larger inputs. For poor algorithms, this will 
eventually lead to disaster.
1-2. A simple and quite scalable solution would be to sort the characters in each string and compare the results. (In 
theory, counting the character frequencies, possibly using collections.Counter, would scale even better.) A really 
poor solution would be to compare all possible orderings of one string with the other. I can’t overstate how poor this 
solution is; in fact, algorithms don’t get much worse than this. Feel free to code it up and see how large anagrams you 
can check. I bet you won’t get far.
Chapter 2
2-1. You would be using the same list ten times. Definitely a bad idea. (For example, try running a[0][0] = 23; 
print(a).)
2-2. One possibility is to use three arrays of size n; let’s call them A, B, and C, along with a count of how many entries 
have been assigned yet, m. A is the actual array, and B, C, and m form the extra structure for checking. Only the first m 
entries in C are used, and they are all indices into B. When you perform A[i] = x, you also set B[i] = m and C[m] = i 
and then increment m (that is, m += 1). Can you see how this gives you the information you need? Extending this to a 
two-dimensional adjacency array should be quite straightforward.
2-3. If f is O(g), then there is a constant c so that for n > n
0
, f(n) £ cg(n). This means that the conditions for g being W(f) 
are satisfied by using the constant 1/c. The same logic holds in reverse.
2-4. Let’s see how it works. By definition, b
log
b
 n
 = n. It’s an equation, so we can take the logarithm (base a) on both 
sides and get log
a
 (b
log
b
 n
) = log
a
 n. Because log x
y
 = y log x (standard logarithm rule), we can write this as (log
a
 b)(log
b
 n) 
= log
a
 n, which gives us log
b
 n = (log
a
 n). The takeaway from this result is that the difference between log
a
 n and log
b
 n is 
just a constant factor (log
a
 b), which disappears when we use asymptotic notation.

---

Appendix d 
■
 Hints for exercises
274
2-5. We want to find out whether, as n increases, the inequality k
n
 ³ c·n
j
 is eventually true, for some constant c. For 
simplicity, we can set c = 1. We can take the logarithm (base k) on both sides (it won’t flip the inequality because it 
is an increasing function), and we’re left with finding out whether n ³ j log
k
 n at some point, which is given  
by the fact that (increasing) linear functions dominate logarithms. (You should verify that yourself.)
2-6. This can be solved easily using a neat little trick called variable substitution. Like in Exercise 1-5, we set up a 
tentative inequality, n
k
 ³ lg n, and want to show that it holds for large n. Again, we take the logarithm on both sides 
and get k lg n ³ lg(lg n). The double logarithm may seem scary, but we can sidestep it quite elegantly. We don’t care 
about how fast the exponential overtakes the polynomial, only that it happens at some point. This means we can 
substitute our variable—we set m = lg n. If we can get the result we want by increasing m, we can get it by increasing n. 
This gives us km ³ lg m, which is just the same as in Exercise 2-5!
2-7. Anything that involves finding or modifying a certain position will normally take constant time in Python lists 
because their underlying implementation is arrays. You have to traverse a linked list to do this (on average, half the 
list), giving a linear running time. Swapping things around, once you know the positions, is constant in both. (See 
whether you can implement a linear-time linked list reversal.) Modifying the list structure (by inserting or deleting 
element, except at the end) is generally linear for arrays (and Python lists) but can in many cases be done in constant 
time for linked lists.
2-8. For the first result, I’ll stick to the upper half here and use O notation. The lower half (W) is entirely 
equivalent. The sum O( f ) + O(g) is the sum of two functions, say, F and G, such that (for large enough n, and some