Introduction to Algorithms Homework 1

COMP 3270 Introduction to Algorithms
Homework 1
1. (20 points) Understand the following algorithm. Simulate it mentally on the following four inputs, and
state the outputs produced (value returned) in each case: (a) A: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; (b) A: [‐1, ‐2,
‐3, ‐4, ‐5, ‐6, ‐7, ‐8, ‐9, ‐10]; (c) A: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; (d) A: [‐1, 2, ‐3, 4, ‐5, 6, 7, ‐8, 9, ‐10].
Algorithm Mystery (A:array[1..n] of integer)
sum, max: integer
1 sum = 0
2 max = 0
3 for i = 1 to n
4 sum = 0
5 for j = i to n
6 sum = sum + A[j]
7 if sum > max then
8 max = sum
9 return max
Output when input is array (a) above:
Output when input is array (b) above:
Output when input is array (c) above:
Output when input is array (d) above:
What does the algorithm return when the input array contains all negative integers?
What does the algorithm return when the input array contains all non‐negative integers?
2. (30 points) Fill out the following table w.r.t. the above algorithm Mystery with the input size n.
Step Total # of times executed
1
2
3
4
5
6
7
8
9
3. (50 points) 𝑇ሺ𝑛ሻ ൌ 7𝑇ሺ𝑛/8ሻ ൅ 𝑐𝑛; 𝑇ሺ1ሻ ൌ 𝑐. Determine the polynomial T(n) for the recursive
algorithm characterized by these two recurrence relations, using the Recursion Tree Method. Drawing
the recursion tree may help but you do not have to show the tree in your answer; instead, fill the table
below. You may need to use the following results, where a and b are constants and x<1:
𝑎
୪୭୥್ ௡ ൌ 𝑛
୪୭୥್ ௔
෍ 𝑥௜
ஶ
௜ୀ଴
ൌ 1
1െ𝑥
Level Level
number
Total # of
recursive
executions at this
level
Input size to
each recursive
execution
Work done by each
recursive execution,
excluding the
recursive calls
Total work
at this level
Root 0
1 level below 1
2 levels
below
2
The level just
above the
base case
level
Base case
level
T(n) =