1

COLLEGE OF ENGINEERING AND APPLIED SCIENCES
DEPARTMENT OF COMPUTER SCIENCE

ICSI403 Design and Analysis of Algorithms

Student Name: _______________

Total converted points: /100

Total points: /155
Homework 1 Created by Qi Wang
Instructions:

1. In this homework, you will practice the topics that are discussed in module I. You should study the relevant

materials before completing the homework.

2. All work is individual unless it is notified otherwise.

3. While working on the problems, you must show/explain your work for all problems to receive credit. Simply

stating the answers will result in 0 points awarded.

4. Writing is how knowledge can be retained. Here are the suggestions on how to complete the work:

1) You may print the work, complete it, and scan it with Microsoft Office Lens into a PDF file.

2) You may write with a stylus pen and save your work as a PDF file.

3) You may write on your own paper, and scan it with Microsoft Office Lens into a PDF file. If so, you must

clearly mark each question and write the solutions in order.

When scanning, you must adjust it so that it is not too dark or too bright or blurry to read. Any unreadable work

may be rejected with no credit. No matter how you complete it, you must submit the work with all pages or

solutions included in ONE PDF file on Blackboard. Absolutely NO hard copies or e-mail submissions or late work

will be accepted.

5. Two attempts will be allowed on Blackboard. Only the last attempt will be graded.

6. Work will be rejected with no credit if

a. The work is late.

b. The work is not submitted properly (Blurry, wrong files, not in required format, etc.). For example,

i. Multiple files (image files or PDF files) are submitted.

ii. The submitted PDF file can’t be opened.

iii. The submitted PDF file is too dark or bright or blurry to read.

iv. The submitted work is empty or wrong work.

v. Other issues.

c. The work is a copy or partial copy of others’ work (such as work from another person or the Internet).

2

7. The points in each question are for grading only. The converted points rounded to the ones place will be

recorded for this work.

8. Your TA will grade, and then post the feedback and the grade for this homework on Blackboard if you have

submitted it properly and on time. If you have any questions regarding the feedback or the grade, please

reach out to the TA first. You may also contact the instructor for this matter.

3

1. Use the following as a model,

illustrate the operation of INSERTION-SORT on the array A = {31, 41,59, 26, 41,58}. Rewrite the INSERTION-SORT

procedure to sort into nonincreasing instead of nondecreasing order.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points each, 20

points in total.)

4

5

2. Binary Addition of Integers: Given two integers a and b, their binary expansions are shown below.

To compute the sum of a and b in binary form, add the corresponding pairs of bits with carries when they occur.

• First add their rightmost bits. This gives

o s0 is the rightmost bit in the binary expansion of a + b and

o c0 is the carry.

• Then add the next pair of bits and the carry.

o s1 is the next bit (from the right) in the binary expansion of a + b, and

o c1 is the carry.

• Continue this process, adding the corresponding bits in the two binary expansions and the carry, to

determine the next bit from the right in the binary expansion of a + b.

• At the last stage,

an−1 + bn−1 + cn−2 = cn−1 ・ 2 + sn−1

The leading bit of the sum is sn = cn−1. This procedure produces the binary expansion of the sum,

Write pseudocode for adding two integers in binary expansions formally. Store the two binary integers and

their sum in arrays. Illustrate your algorithm using this following two integers: a = (1110)2 and b = (1011)2.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points)

6

7

3. Express the following functions in terms of Θ- notation.

(n2 + 8)(n + 1) , (n log n + n2)(n3 + 2), and (n! + 2n)(n3 + log(n2 + 1)

You must show/explain how you arrived at the answers. Simply stating the answers will result in 0 points

awarded. (5 points each, 15 points in total.)

a. (n2 + 8)(n + 1)

b. (n log n + n2)(n3 + 2)

c. (n! + 2n)(n3 + log(n2 + 1))

8

9

4. We often use a loop invariant to prove that an algorithm gives the correct answer. To use a loop invariant to

prove correctness, we must show three things about it:

1) Initialization: It is true prior to the first iteration of the loop.

2) Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.

3) Termination: When the loop terminates, the invariant (usually along with the reason that the loop

terminated) gives us a useful property that helps show that the algorithm is correct.

Let’s take a look at the following Bubble sort algorithm.

1) Bubble sort is a sorting algorithm that works by repeatedly exchanging adjacent elements that are out of

order. Let A’ denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to

prove that it terminates and that A’[1] ≤ A’[2] ≤ … ≤ A’[n], where n = A.length. In order to show that

BUBBLESORT actually sorts, what else do we need to prove?

2) State precisely a loop invariant for the for loop inner, and prove that this loop invariant holds using the

above-mentioned structure of the loop invariant.

3) Using the termination condition of the loop invariant proved in part 2), state a loop invariant for the for

loop outer that will allow you to prove A’[1] ≤ A’[2] ≤ … ≤ A’[n], where n = A.length. Prove that this

loop invariant holds using the above-mentioned structure of the loop invariant.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (5 points

for #2), 5 points for each of the three parts (Initialization, Maintenance, and Termination) in #3). 20

points in total.)

outer:
inner :

10

11

12

13

5. Suppose that a list contains integers that are in order of largest to smallest and an integer can appear repeatedly

in this list.

1) Devise an algorithm that locates all occurrences of an integer x in the list.

2) Estimate the number of comparisons used.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points each, 20

points in total.)

14

15

6. Prove that n3 – 91n2 – 7n – 14 = 𝛺𝛺(n3). You must show/explain how you arrived at the constants, and clearly

specify the positive constants c and n0. Simply stating the answers will result in 0 points awarded. (10 points)

16

7. Prove that 27n2 + 18n = 𝛩𝛩(0.5n2 – 100). You must show/explain how you arrived at the constants, and clearly

specify the positive constants c1, c2, and n0. Simply stating the answers will result in 0 points awarded. (10 points)

17

8. Write pseudocode for Strassen’s algorithm and use Strassen’s algorithm to compute the matrix product of AB.
You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points)

A = �2 1
3 2

�, B = �0 4
1 3

�.

18

19

9. (Substitution method) Show that the solution of T(n) = T(n – 1) + n is O(n2). You must show/explain your work.
Simply stating the answers will result in 0 points awarded. (10 points)

20

21

22

10. Use a recursion tree to determine a good asymptotic upper bound on the following recurrence.
T(n) = 4T(n/2 + 2) + n
Use the substitute method to verify your answer. You must show/explain your work. Simply stating the answers
will result in 0 points awarded. (10 points)

23

24

11. Use the master method to give tight asymptotic bounds for the following recurrences.
1) T(n) = 2T(n/4) + 1
2) T(n) = 2T(n/4) + √𝑛𝑛

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points each, 20
points in total.)

25