Chapter 2 - Getting Started Flashcards
What separates pseudocode from real code?
In pseudocode, whatever expressive method is most clear and concise to specify a given algorithm is used. Sometimes the clearest method is English. Pseudocode is also not typically concerned with issues of software engineering, such as data abstraction, modularity and error handling.
How does insertion sort work?
We first start by splitting the input array into two parts, the sorted portion and the unsorted portion. At the beginning, the sorted portion is just the first element, and the unsorted portion is everything else. We then go through each element in the unsorted portion, and place it in the correct position in the sorted portion, examining each element in the sorted portion from right to left, to determine the correct position for the element. When you’ve placed the last element from the unsorted portion into the correct place in the sorted portion, the array is sorted.
Describe insertion sort for the input array <5, 2, 4, 6, 1 ,3>
Sorted: <5> Unsorted: <2, 4, 6, 1, 3> Element: 2. Look through the sorted portion. 5 is greater than 2 so examine the next position to the left. We are now at the beginning of the sorted portion, so 2 must go here.
Sorted: <2, 5> Unsorted: <4, 6, 1, 3> Element: 4. Look through the sorted portion. 5 is greater than 4 so examine the next position to the left. 2 is less than 4, so place 4 right after 2.
Sorted: <2, 4, 5> Unsorted: <6, 1, 3> Element: 6. Look through the sorted portion. 5 is less than 6, so place 6 right after 5.
Sorted: <2, 4, 5, 6> Unsorted <1, 3> Element: 1. Look through the sorted portion. 6 is greater than 1 so examine the next position to the left. 5 is greater than 1 so examine the next position to the left. 4 is greater than 1 so examine the next position to the left. 2 is greater than 1 so examine the next position to the left. We are not at the beginning of the sorted portion, so 1 must go here.
Sorted: <1, 2, 4, 5, 6> Unsorted <3> Element: 3. Look through the sorted portion. 6 is greater than 3 so examine the next position to the left. 5 is greater than 3 so examine the next position to the left. 4 is greater than 3 so examine the next position to the left. 2 is less than 3, so place 3 right after 6.
Output: <1, 2, 3, 4, 5, 6>
What are loop invariants?
Loop invariants are statements that must be true about the loop of an algorithm in order to prove and help understand why an algorithm is correct.
What must a loop invariant show?
Initialization: It first must show that prior to the first iteration of the loop, the invariant is true.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
What is the loop invariant for insertion sort?
At the start of each iteration of the insertion sort loop, where the element being sorted is at position j, the subarray A[0..j - 1] consists of the elements originally in A[0..j-1], but in sorted order.
How do you prove the initialization of the insertion sort loop invariant?
In order to do this we must show that the invariant is true prior to the first iteration of the loop, where the element being sorted is at position 1. This means that there’s only 1 element in the subarray A[0..j], the element at position 0. Any array of length 1 must be in sorted order, as there is nothing else to compare it to, therefore the loop invariant holds true prior to the first iteration of the loop.
How do you prove the maintenance of the insertion sort loop invariant?
We must show that each iteration maintains the loop invariant. The for loop works by examining the positions in the subarray A[0..j], by moving from right to left. That is it examine A[j - 1], A[j - 2], A[j - 3], and so on by one position to the right until it finds the proper position for A[j], at which point it inserts the value of A[j]. Therefore the subarray A[1..j] now consists of the elements originally in A[1..j] but in sorted order. When j is incremented for the next iteration of the for loop, the loop invariant is preserved.
How do we prove the termination of the insertion sort loop invariant?
The condition causing the for loop to terminate is the j >= A.length = n. Because each loop increases j by 1, we must have j = n + 1 at that time. Substituting n + 1 for j in the loop invariant shows that the subarray A[0..n] consists of the elements originally in A[0..n], but in sorted order. Observing that the subarray A[0..n] is the entire array, we conclude that the entire array is sorted. Hence, the algorithm is correct.
In pseudocode how is block structure represented?
Indentation is used, rather than begin and end statements to avoid clutter while preserving clarity.
In pseudocode what does the line “i = j =e” represent?
i and j are both set equal to the value of e. Equivalent to j = e followed by i = j.
How would you change the insertion sort pseudocode to sort into nonincreasing order instead of nondecreasing order?
In the inner loop, change the condition where A[i] > key to A[i] < key.
Write pseudocode for linear search given the searching problem:
Input: A sequence of n numbers A = 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.
for i = 0 to A.length - 1
if A[i] = v
return i
return NIL
Write a loop invariant for linear search.
At the start of each iteration of the linear search loop, where the element being checked is at position i, the subarray A[0..i - 1] does not contain the value being searched for.
What does analyzing an algorithm means? What factors are taken into consideration?
Analyzing an algorithm means predicting the resources that the algorithm requires. Occasionally resources such as memory, communication bandwidth, or computer hardware are of primary concern, but most often the analysis is measuring computational time.
