xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

C++/Java代写-CS608

时间：2021-03-06

CS608 Algorithms & Computing Theory

Midterm Exam

Sung-Hyuk Cha

(March 13, 2019 version 1.)

Exam questions are based on materials covered in CS 608 on Spring of 2019.

Do not turn the cover page until announced.

.1. This test consists of five parts (25 pnts each) and each part has five ques-

tions (5 pnts each). 125 points in total.

.2. Students with 90 points or higher: A.

Students with 85 points or higher: A-.

Students with 80 points or higher: B+.

Students with 75 points or higher: B.

Students with 70 points or higher: B-.

Students with 65 points or higher: C+

Students with 60 points or higher: C

Students with 55 points or higher: C-

Students with 50 points or higher: D

.3. You have 2 hours and 30 minites to complete the exam. (6:15pm∼8:45pm)

.4. Only a simple calculator, pencils, and erasers are allowed.

Master Theorem: T (n) = aT (nb ) + f(n) where a ≥ 1 and b ≥ 1.

Case 1: If f(n) = O(nlogb a−) for some > 0,

T (n) = Θ(nlogb a)

Case 2: If f(n) = Θ(nlogb a logk n) for some k ≥ 0,

T (n) = Θ(nlogb a logk+1 n)

Case 3: If f(n) = Ω(nlogb a+) for some > 0

and af(n/b) ≤ cf(n) for some c < 1,

T (n) = Θ(f(n))

1

I Sum of odd numbers

Consider the problem of adding the first n odd numbers.

I.1. Formulate the problem.

I.2. Derive a closed form.

I.3. Prove the correctness of your closed form.

I.4. Derive a first order linear recurrence relation of the problem.

I.5. Devise an algorithm using inductive programming.

II Alternating permutation - checking up-down

Consider the problem of checking whether a given a sequence A1∼n of n num-

bers is a up-down alternating sequence.

Problem II.X Checking up-down sequence

Input: A sequence A of n quantifiable elements

Output:

true ∀i ∈ {1, · · · , n− 1},

{

ai < ai+1 if i is odd

ai > ai+1 if i is even

false otherwise

For example, isupdown(〈5, 9, 1, 4, 2〉) returns true and isupdown(〈5, 2, 1, 9, 4, 3〉)

returns false.

II.1. Derive a first order linear recurrence relation of Problem II.X.

II.2. Devise an inductive programming algorithm for Problem II.X.

II.3. Devise a dvide and conquer algorithm for Problem II.X.

II.4. Illustrate your algorithm proposed in II.3 on the following toy example:

A = 2 11 3 10 7 9 1 5 4 8 6

II.5. Provide the computational time complexity of your divide and conquer

algorithm provided in II.3.

2

III Divide recurrence relation

Consider the following recurrence in eqn (1).

T (n) =

{

1 if n = 1

2T (n/2) + 1 if n > 1

(1)

III.1. Find the equivalent closed asymptotic notation for eqn (1) using the Mas-

ter Theorem.

III.2. Prove the solution of the divide recurrence in eqn. (2) is T (n) = 2n − 1

for any positive integer n using strong induction.

T (n) =

{

1 if n = 1

T (

⌊

n

2

⌋

) + T (

⌈

n

2

⌉

) + 1 if n > 1

(2)

III.3. Devise a strong inductive programming algorithm to find T (n) in eqn. (2)

and analyze the computational time and space complexities.

III.4. Devise a memoization algorithm to find T (n) in eqn. (2) and analyze the

computational time and space complexities.

III.5. Illustrate your algorithm based on the memoization method in d) for T (61)

and analyze the computational time and space complexities. (Hint: show

the table.)

3

IV Unbounded equality knapsack minimization

There are three missiles (blue, red, and yellow) with different points gained and

energy required. The problem, V (n), is to score exactly n points using as little

energy as possible. Note that if the points gained is short or exceeds m, it is a

loss. Exactly m points earned using the least energy is a winner.

missile blue red yellow

energy E 1 3 4

point P 1 5 6

IV.1. Formulate the problem.

IV.2. Design a greedy algorithm and prove the correctness or incorrectness of

the proposed algorithm.

IV.3. Devise a strong inductive programming (conventionally known as dynamic

programming) algorithm.

Hint: A recurrence relation of the problem is given in eqn (3).

V (n) =

∞ 〈impossible〉 if n < 0

0 if n = 0

min

1≤i≤k

(V (n− pi) + ei) if n > 0

(3)

IV.4. Illustrate the algorithm proposed in IV.3 on the above toy example:

IV.5. Devise a memoization algorithm.

4

V Cycle number

Consider the problem of finding the cycle number, a.k.a., Stirling number of the

first kind, or SNF in short, as defined in eqn (4).

Problem V.1 Cycle number (Stirling number of the first kind)

Input: n, k where n, k ∈ Z

Output: S(n, k) =

1 if k = n = 0

0 if (k = 0 ∧ n > 0) ∨ k > n

S(n− 1, k − 1) + (n− 1)S(n− 1, k) if 0 < k < n

(4)

S C G R

G R

CS

S R G C S G R C

R G

C

S R

C

R S

C

S G

C

G S

C

S R

G

R S

GS

G

G

R

R

C

C

1

0 1

0 1

0 2 3 1

1

0 6 11 6

0 24 50

0 120

0 720 21 1

15 1

10 1

1

35

274 225

1624 735 175

85

1764

S(n = 4, k = 2) = 11 SNF triangle

V.1. Find the value of S(5, 2) and the number of recursive calls when the na¨ıve

recursive algorithm in eqn (4) is used. (Hint: draw the recursion tree.)

V.2. Describe a memoization algorithm to compute S(n, k).

V.3. Provide the number of recursive calls necessary to compute S(6, 3) when

the algorithm provided in V.2 is used.

V.4. Provide a strong inductive programming algorithm to compute S(n, k).

V.5. Provide the computational time and space complexities of the algorithm

provided in V.4.

5

学霸联盟

Midterm Exam

Sung-Hyuk Cha

(March 13, 2019 version 1.)

Exam questions are based on materials covered in CS 608 on Spring of 2019.

Do not turn the cover page until announced.

.1. This test consists of five parts (25 pnts each) and each part has five ques-

tions (5 pnts each). 125 points in total.

.2. Students with 90 points or higher: A.

Students with 85 points or higher: A-.

Students with 80 points or higher: B+.

Students with 75 points or higher: B.

Students with 70 points or higher: B-.

Students with 65 points or higher: C+

Students with 60 points or higher: C

Students with 55 points or higher: C-

Students with 50 points or higher: D

.3. You have 2 hours and 30 minites to complete the exam. (6:15pm∼8:45pm)

.4. Only a simple calculator, pencils, and erasers are allowed.

Master Theorem: T (n) = aT (nb ) + f(n) where a ≥ 1 and b ≥ 1.

Case 1: If f(n) = O(nlogb a−) for some > 0,

T (n) = Θ(nlogb a)

Case 2: If f(n) = Θ(nlogb a logk n) for some k ≥ 0,

T (n) = Θ(nlogb a logk+1 n)

Case 3: If f(n) = Ω(nlogb a+) for some > 0

and af(n/b) ≤ cf(n) for some c < 1,

T (n) = Θ(f(n))

1

I Sum of odd numbers

Consider the problem of adding the first n odd numbers.

I.1. Formulate the problem.

I.2. Derive a closed form.

I.3. Prove the correctness of your closed form.

I.4. Derive a first order linear recurrence relation of the problem.

I.5. Devise an algorithm using inductive programming.

II Alternating permutation - checking up-down

Consider the problem of checking whether a given a sequence A1∼n of n num-

bers is a up-down alternating sequence.

Problem II.X Checking up-down sequence

Input: A sequence A of n quantifiable elements

Output:

true ∀i ∈ {1, · · · , n− 1},

{

ai < ai+1 if i is odd

ai > ai+1 if i is even

false otherwise

For example, isupdown(〈5, 9, 1, 4, 2〉) returns true and isupdown(〈5, 2, 1, 9, 4, 3〉)

returns false.

II.1. Derive a first order linear recurrence relation of Problem II.X.

II.2. Devise an inductive programming algorithm for Problem II.X.

II.3. Devise a dvide and conquer algorithm for Problem II.X.

II.4. Illustrate your algorithm proposed in II.3 on the following toy example:

A = 2 11 3 10 7 9 1 5 4 8 6

II.5. Provide the computational time complexity of your divide and conquer

algorithm provided in II.3.

2

III Divide recurrence relation

Consider the following recurrence in eqn (1).

T (n) =

{

1 if n = 1

2T (n/2) + 1 if n > 1

(1)

III.1. Find the equivalent closed asymptotic notation for eqn (1) using the Mas-

ter Theorem.

III.2. Prove the solution of the divide recurrence in eqn. (2) is T (n) = 2n − 1

for any positive integer n using strong induction.

T (n) =

{

1 if n = 1

T (

⌊

n

2

⌋

) + T (

⌈

n

2

⌉

) + 1 if n > 1

(2)

III.3. Devise a strong inductive programming algorithm to find T (n) in eqn. (2)

and analyze the computational time and space complexities.

III.4. Devise a memoization algorithm to find T (n) in eqn. (2) and analyze the

computational time and space complexities.

III.5. Illustrate your algorithm based on the memoization method in d) for T (61)

and analyze the computational time and space complexities. (Hint: show

the table.)

3

IV Unbounded equality knapsack minimization

There are three missiles (blue, red, and yellow) with different points gained and

energy required. The problem, V (n), is to score exactly n points using as little

energy as possible. Note that if the points gained is short or exceeds m, it is a

loss. Exactly m points earned using the least energy is a winner.

missile blue red yellow

energy E 1 3 4

point P 1 5 6

IV.1. Formulate the problem.

IV.2. Design a greedy algorithm and prove the correctness or incorrectness of

the proposed algorithm.

IV.3. Devise a strong inductive programming (conventionally known as dynamic

programming) algorithm.

Hint: A recurrence relation of the problem is given in eqn (3).

V (n) =

∞ 〈impossible〉 if n < 0

0 if n = 0

min

1≤i≤k

(V (n− pi) + ei) if n > 0

(3)

IV.4. Illustrate the algorithm proposed in IV.3 on the above toy example:

IV.5. Devise a memoization algorithm.

4

V Cycle number

Consider the problem of finding the cycle number, a.k.a., Stirling number of the

first kind, or SNF in short, as defined in eqn (4).

Problem V.1 Cycle number (Stirling number of the first kind)

Input: n, k where n, k ∈ Z

Output: S(n, k) =

1 if k = n = 0

0 if (k = 0 ∧ n > 0) ∨ k > n

S(n− 1, k − 1) + (n− 1)S(n− 1, k) if 0 < k < n

(4)

S C G R

G R

CS

S R G C S G R C

R G

C

S R

C

R S

C

S G

C

G S

C

S R

G

R S

GS

G

G

R

R

C

C

1

0 1

0 1

0 2 3 1

1

0 6 11 6

0 24 50

0 120

0 720 21 1

15 1

10 1

1

35

274 225

1624 735 175

85

1764

S(n = 4, k = 2) = 11 SNF triangle

V.1. Find the value of S(5, 2) and the number of recursive calls when the na¨ıve

recursive algorithm in eqn (4) is used. (Hint: draw the recursion tree.)

V.2. Describe a memoization algorithm to compute S(n, k).

V.3. Provide the number of recursive calls necessary to compute S(6, 3) when

the algorithm provided in V.2 is used.

V.4. Provide a strong inductive programming algorithm to compute S(n, k).

V.5. Provide the computational time and space complexities of the algorithm

provided in V.4.

5

学霸联盟