Homework #8

Due in lecture, Thursday May 9 (with homework #7). Please do the homework in a workbook.

In all cases, you can leave your answer in terms of factorials or \(C(n,r)\). No need to calculate: just simplify as much as you can with algebra.

From the Text

Complete the following questions from the text:


  1. How many strictly increasing sequences of positive integers are there that have 1 as the first term and \(n\) as the last term? [For example, for \(n=4\) there are four possible sequences: \(1,4; 1,2,4;1,3,4;1,2,3,4\).]
  2. If we analyze selection sort, we would come up with a recurrence \(a_n=a_{n-1}+(n-1)\) for the number of comparisons used to sort \(n\) elements, with \(a_0=0\). Solve this recurrence using the method discussed in lecture. Hint: guess that there is a quadratic particular solution.