MTH 231 Study Guide - Final Guide: Natural Number
11 Oct 2018
School
Department
Course
Professor
Math 231 Final Practice Problems Not Solved In Class
(1) Consider the algorithm:
Input: a∈R,n∈N.
Output: b∈R.
Prod(a, n)
(1) If n= 1, return a.
(2) Set m=¥n
2¦.
(3) Return Prod(a, m)+ Prod(a, n −m).
(a) Explain in detail how this algorithm calculates Prod(2,5).
(1) is skipped, (2) sets m= 2, (3) executes Prod(2,2)+Prod(2,3). Each of these skip (1), sets
m= 1, and respectively executes Prod(2,1)+Prod(2,1) and Prod(2,1)+Prod(2,2), from which
the second term executes Prod(2,1)+Prod(2,1). At this stage, each Prod(2,1) returns 2 (a
total of five of them to be added – representing multiplication by five).
(b) For any a∈R, find a recurrence relation for µn, defined as the number of times an addition
occurs in calculating Prod(a, n). Solve it in the case where n= 2kfor k∈N, given the initial
condition µ1= 0. Use this to determine a “big oh” notation for µnin the case where n= 2k.
Let kbe a non-negative integer. µ2k= 1 + 2µ2k−1. By iteration, µ2k= 1 + 2[1 + µ2k−2] =
1 + 2[1 + 2[1 + ···2[1 + 2µ1]· ··]].
Hence µ2k=
k−1
X
i=0
2i.
Since for n= 2k, 1 + 2 + · · · + 2k−1≤n+n+· · · +n=nk =n·lg(n). Hence µnis “big oh” of
n·lg(n) when n= 2kfor some non-negative integer k.
Document Summary
Final practice problems not solved in class (1) consider the algorithm: Prod(a, n) (cid:165) (cid:166) (1) if n = 1, return a. (2) set m = (3) return prod(a, m)+ prod(a, n m). n. 2 (a) explain in detail how this algorithm calculates prod(2, 5). (1) is skipped, (2) sets m = 2, (3) executes prod(2, 2)+prod(2, 3). Each of these skip (1), sets m = 1, and respectively executes prod(2, 1)+prod(2, 1) and prod(2, 1)+prod(2, 2), from which the second term executes prod(2, 1)+prod(2, 1). Solve it in the case where n = 2k for k n, given the initial condition 1 = 0. Use this to determine a big oh notation for n in the case where n = 2k. By iteration, 2k = 1 + 2[1 + 2k 2] = 1 + 2[1 + 2[1 + 2[1 + 2 1] ]]. k 1(cid:88) i=0.
