Clarifications on the theoretical part of the 2nd assignment of Data Structures and Algorithms

Questions about the master theorem. Here is a copy from Cormen's book (Cormen et al.; Introduction to Algorithms; MIT Press):

As you can see, there is no statement limiting f(x) to polynomial functions. Another thing is about the comparison between f(x) and n^log_b a. See the text below from the same book:

Finally, some students googled about the cases and found subcases 2b, 2c, etc. We are using in this course Cormen's book since it is a trustful source used by top universities and has been revised several times. If these "subcases" are not in there, there is a reason for such. Let's stick to the book.

Questions about dynamic programming. There are several ways of solving the problem in the given assignment. Probably most of the doubts are about how to describe each step. So here is a summary:

• For the algorithm, either top-down with memoization or bottom-up method are acceptable.
• For proving the correctness of the algorithm, a small paragraph with an explanation of your induction (in English) is fine. I know that you know how to prove using induction!
• For step 6: You can provide the recurrence "T(n) = ... which leads to O(something) applying the master theorem (case X)" or a similarly simple explanation. No need for showing the entire mathematical proof.
• Update: step 5 - you can provide the pseudocode; no programming language required.
• Update: step 5 - your algorithm must use one of the two methods: top-down with memoization or bottom-up
• Update: the price of the tickets are non-negative.
• Update: the minimum cost from one station to itself is zero. In fact, the only aspect that is contra-intuitive in the given problem is cheaper tickets to further destinations. Everything else should make sense. But I am glad that you asked anyway. :)

I will enter more items to the list above as I receive more questions. Stay tuned.