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.
What is needed before an analysis can be analyzed?
A model of the implementation of the technology being used, including a model for the resources of that technology, and their costs.
What is the RAM model? How does the RAM model handle instructions?
Stands for random-access machine, it represents a one-processor computer. In the RAM model instructions are executed one after another, with no concurrent operations.
What are the instructions commonly found in the RAM model? What is unique about these instructions?
The RAM model contains instructions that are commonly found in real computers.
Arithmetic (such as add, subtract, multiply, divide, remainder, floor, ceiling), data movement (load, store, copy), and control (conditional and unconditional branch, subroutine call and return). Each of these instructions takes a constant amount of time.
What are the data types in the RAM model?
Integer and floating point (for storing real numbers).
When working with inputs of size n, how many bits are integers represented by?
c lg n bits, where c is some constant >= 1, so that each word can hold the value of n, enabling us to index the individual input elements, and c is restricted to a constant so that the word size does not grow arbitrarily.
Is exponentiation a constant-time instruction? Explain.
Usually no, it takes several instructions to compute x^y when x and y are real numbers. In restricted situations, however, exponentiation is a constant-time operation. Many computers have a shift left instruction which in constant-time shifts the bits of an integer by k positions to the left. In most computers shifting 1 bit to the left is equivalent to multiplication by 2, so shifting the bits by k positions to the left, is 2^k. Therefore these computers can compute 2^k in one constant-time instruction, as long as k is not longer than the number of bits in a computer word.
What does the time taken by the insertion-sort procedure depend on?
The size of the input, sorting 1000 numbers will take longer than sorting 3 numbers. Insertion-sort can also take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are.
How do you measure the input size?
The best notion for input size depends on the problem being analyzed. For many problems, the most natural measure is the number of items in the input. For other problems, such as multiplying two integers, the best measure is the total number of bits needed to represent the input in ordinary binary notation. Sometimes it is appropriate to describe the size of the input with two numbers, for instance, in a graph, the input would be described as the number of vertices and edges on the graph.
How do you measure the running time of an algorithm?
The running time on a particular input is the number of primitive operations, or “steps” executed.
