2.1.md

Exercises 2.1-1

---

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = [31, 41, 59, 26, 41, 58].

Answer

Exercises 2.1-2

---

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

Answer

Exercises 2.1-3

---

Consider the searching problem:

• Input: A sequence of n numbers A = [a1, a2, . . . , an] and a value v.
• Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Answer

Exercises 2.1-4

---

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers.

Answer

C = Array[A.length+1]
carry <- 0,
for i <- A.length to 1
    C[i+1] <- (A[i] + B[i] + carry) % 2;
    carry = (A[i] + B[i] + carry)/2;
C[1] <- carry;
return C

---

Follow @louis1992 on github to help finish this task.