CPS420

W2017 Assignment 1

Ryerson University

Worth: 10%

Sequences, recursion, and induction

Due: Monday February 13


Team Size

This lab can be done in teams of 1 or 2.

Assignment Description

Part A - Question5.2.32 in textbook

You have two biological parents, four biological grandparents, eight biological grandparents, and so on...
  1. If all your ancestors were distinct, what would be the total number of your ancestors for the past 40 generation counting your parents' generation as number one.
  2. Assuming that each generation represents 25 years, how long is 40 generations? Explain your answer.
  3. The total number of people who have ever lived is approximately 10 billion, which equals 1010. Compare this fact with the answer to part 1. What do you deduce?

Part B - Based on Question 5.7.52 in textbook:

A single line divides a plane into two regions. Two lines can divide it into four regions by crossing each other. Three lines can divide it into seven regions.

When n is a non-negative integer, let Pn be the maximum number of regions into which n lines divide a plane.

  1. Derive a recurrence relation for Pk in terms for Pk-1, for all integers k greater or equal to 2.
  2. Use iteration to guess an explicit formula for Pn
  3. Prove by induction that the explicit formula is correct (i.e. that it solves the recurrence relation)

Part C - Question 5.4.25 in textbook

Imagine a situation in which eight people, numbered consecutively 1-8, are arranged in a circle. Starting from person #1, every second person in the circle is eliminated. The elimination process continues until only one person remains. In the first round the people numbered 2, 4, 6, and 8 are eliminated; in the second round the people numbered 3, and 7 are eliminated; in the third round person #5 is eliminated. So after the third round only person #1 remains.
  1. Given a set of 16 people arranged in a circle and numbered consecutively 1-16, list the numbers of the people who are eliminated in each round if every second person is eliminated and the elimination process continues until only one person remains. Assume that the starting point is person #1.
  2. Use mathematical induction to prove that for all integers n >= 1, given any set of 2n people arranged in a circle and numbered consecutively from 1 to 2n, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #1 will remain.
  3. Use the result of part 2 to prove that for any non-negative integers n and m with 2n <= 2n+m < 2n+1, if r=2n+m, then given any set of r people arranged and numbered from 1 through r, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only one person #(2m+1) will remain.
Here is some help with parts 2 and 3: docx, pdf

References

  • Textbook chapter 5.1, 5.2, 5.3, 5.4, 5.6, 5.7
  • Handouts and other references can be found in the Lecture Material

Hand In

This lab is a paper submission to be handed in at the Computer Science office.
  • Hand in your written solution with a marking sheet (docx or pdf) stapled to the front.
  • In addition to the assignment itself you will need to also submit the Assignment 1 Submission Declaration on D2L. This assignment will not be graded unless this declaration has been submitted.

Solutions


This page is maintained by Sophie Quigley (cps420@scs.ryerson.ca)
Last modified Tuesday, 21-Feb-2017 23:40:32 EST