MCS-177, Intro. to Computer Science I, Fall 2007
Homework Assignment 4
Due: Monday, Oct. 15

Do exercise 4.11 on pages 99-100.
Do exercise 4.14 on pages 101-102.
Do exercise 4.15 on pages 103-104.
Where possible, fill in the blanks so as to make the statement true (and to make it match the definitions.) When it is impossible, put a question mark in the blank and explain why it can't be filled in. In cases which aren't obvious, be sure to show your work.

3n is Theta(n) because for any n > __, we know that __*n <= 3n <= __.
3n - 20 is Theta(n) because for any n >=__, we know that __*n <= 3n-20 <=__*n.
n^3+6n^2 is Theta(n^3) because for any n >=__, we know that __* n^3 <= n^3+6n^2 <= __*n^3.
n^3+6n^2 is Theta(n) because for any n >=__, we know that __* n <= n^3+6n^2 <= __*n.
n^2+2n+1 is Theta(__) because for any n >=__, we know that __* __ <= n^3+6n^2 <= __*__.

Suppose n, m are integers. The index of n mod m is the smallest integer power i such that i>0 and n^i mod m = 1. For example the index of 2 mod 7 is 3, since 2^1 mod 7 = 2, 2^2 mod 7 = 4, and 2^3 mod 7 = 8 mod 7 = 1. Write a procedure that, given positive integers, n and m, will find the index of n mod m. Be sure to use mod*.