I . chp 2. Getting Started

Question 1

Objective

Answer 1

This chapter will familiarize you with the framework we shall use throughout the
book to think about the design and analysis of algorithms. We begin by examining the insertion sort algorithm to solve the sorting problem.Having specified the insertion sort algorithm, we then argue that it
correctly sorts, and we analyze its running time. The analysis introduces a notation
that focuses on how that time increases with the number of items to be sorted. Following our discussion of insertion sort, we introduce the divide-and-conquer
approach to the design of algorithms and use it to develop an algorithm called
merge sort. We end with an analysis of merge sort’s running time.

Question 2

Keys in sorting problem:

Answer 2

The numbers that we wish to sort are also known as the keys.

Question 3

Pseudo Code Vs Real Code.

Answer 3

What separates pseudocode from “real” code is that in
pseudocode, we employ whatever expressive method is most clear and concise to
specify a given algorithm. Sometimes, the clearest method is English.
Another difference between pseudocode and real code
is that pseudocode is not typically concerned with issues of software engineering.
Issues of data abstraction, modularity, and error handling are often ignored in order
to convey the essence of the algorithm more concisely.

Question 4

Insertion Sort:

Answer 4

INSERTION-SORT(A)
1 for j = 2 to A.length
2     key = A[j]
3 // Insert A[j]  into the sorted sequence A[1 ... j - 1].
4     i = j - 1
5     while i>0 and A[i] > key
6         A[i + 1] = A[i]
7          i = i - 1
8 A[i + 1] = key

Question 5

Loop Invariant? Why do we need it?

Answer 5

invariant:

a function, quantity, or property which remains unchanged when a specified transformation is applied.

We use loop invariants to help us understand why an algorithm is correct.

Question 6

Loop Invariant of Insertion Sort:

Answer 6

At the start of each iteration of the for loop of lines 1–8, the subarray
A[1 , , , j -1 ] consists of the elements originally in
A[ 1 , , , j - 1 ], but in sorted order

Question 7

What things must be shown about loop invariant:

(3)

How to show Algo is correct?

Answer 7

Initialization: It is true prior to the first iteration of the loop.
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.

When the first two properties hold, the loop invariant is true prior to every iteration
of the loop.

Question 8

Pseudocode Conventions:

1. block structure:
2. Comments?

Answer 8

1. Indentation indicates block structure.

3. // Indicates that the remainder of the line is a comment.

Question 9

2.Loop Pseudocode Conventions:

Answer 9

2.The looping constructs while, for, and repeat-until and the if-else conditional
construct have interpretations similar to those in C, ..etc.
In this book, the loop counter retains its value after exiting the loop.
keyword downto when a for loop
decrements its loop counter,
“to” when increment.
When the loop counter changes by an amount
greater than 1, the amount of change follows the optional keyword “by”

Question 10

Psedocode

j = e, i = j
different allowed assignment form.

Answer 10

4.A multiple assignment of the form i = j = e assigns to both variables i and j
the value of expression e; it should be treated as equivalent to the assignment
j = e followed by the assignment i = j

Question 11

Scope of variables in Pseudocode:

Answer 11

5. Variables (such as i, j , and key) are local to the given procedure. We shall not
   use global variables without explicit indication.

Question 12

Array Convention Pseudocode:

Answer 12

6. We access array elements by specifying the array name followed by the index in square brackets. For example, A[i] indicates the ith element of the
   array A. The notation “. .” is used to indicate a range of values within an array. Thus, A [1 . . j] indicates the subarray of A consisting of the j elements
   A[1], A[2], . . , A[j] .

Question 13

Compund data types rule, pointers to them.

Notations:

Answer 13

7. We typically organize compound data into objects, which are composed of
   attributes.
   We access a particular attribute using the syntax : the object name, followed by a dot,
   followed by the attribute name.
   Example : Array A is treated as object and its attribute length, A.length.
   We treat a variable representing an array or object as a pointer to it.
   For all attributes f of an object x, setting y = x
   causes y.f = x.f
   If x.f = 3, then y.f = 3 as well. I
   x and y point to the same object after the assignment y = x.
   Our attribute notation can “cascade.” For example, suppose that the attribute f
   is itself a pointer to some type of object that has an attribute g.
   Then the notation
   x.f.g is implicitly parenthesized as (x.f).g.
   If y = x.f , then x.f.g is the same as y.g.

When pointer refers to no object at all, it has value NIL

Question 14

Passing paramenters, Calling Convention:

Answer 14

8. We pass parameters to a procedure by value: the called procedure receives its
   own copy of the parameters, and if it assigns a value to a parameter, the change
   is not seen by the calling procedure. When objects are passed, the pointer to
   the data representing the object is copied, but the object’s attributes are not. For
   example, if x is a parameter of a called procedure, the assignment x = y within
   the called procedure is not visible to the calling procedure. The assignment
   x.f = 3, however, is visible. Similarly, arrays are passed by pointer, so that a pointer to the array is passed, rather than the entire array, and changes to
   individual array elements are visible to the calling procedure.

Question 15

Return Statements:

Answer 15

9.A return statement immediately transfers control back to the point of call in
the calling procedure. Most return statements also take a value to pass back to
the caller. Our pseudocode differs from many programming languages in that
we allow multiple values to be returned in a single return statement.

Question 16

Boolean Operators:

Answer 16

The boolean operators “and” and “or” are short circuiting. That is, when we
evaluate the expression “x and y” we first evaluate x. If x evaluates to FALSE,
then the entire expression cannot evaluate to TRUE, and so we do not evaluate y.
If, on the other hand, x evaluates to TRUE, we must evaluate y to determine the
value of the entire expression. Similarly, in the expression “x or y” we evaluate the expression y only if x evaluates to FALSE. Short-circuiting operators
allow us to write boolean expressions such as “x != NIL and x.f = y” without
worrying about what happens when we try to evaluate x.f when x is NIL.

Question 17

error keyword:

Answer 17

The keyword error indicates that an error occurred because conditions were
wrong for the procedure to have been called. The calling procedure is responsible for handling the error, and so we do not specify what action to take

Question 18

Analysing an Algorithm:

Answer 18

Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communication bandwidth, or computer hardware are of primary concern, but most often it is computational time that we want to measure.

Question 19

Random Acssess Machine(RAM) model:

Define this model briefly

Answer 19

The RAM model contains instructions 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 such instruction takes a constant amount of time.

The data types in the RAM model are integer and floating point (for storing real
numbers).

Question 20

size of each word of data?

I DONT UNDERSTAND THISS!!

What is a word?

Answer 20

In computing, a word is the natural unit of data used by a particular processor design. A word is a fixed-sized piece of data handled as a unit by the instruction set or the hardware of the processor. The number of bits in a word (the word size, word width, or word length) is an important characteristic of any specific processor design or computer architecture.

We also assume a limit on the size
of each word of data.
For example, when working with inputs of size n, we typically assume that integers are represented by
c lg n bits for some constant c >= 1.
We require c >= 1 so that each word can hold the value of n, enabling us to index the
individual input elements, and we restrict c to be a constant so that the word size
does not grow arbitrarily. (If the word size could grow arbitrarily, we could store
huge amounts of data in one word and operate on it all in constant time—clearly
an unrealistic scenario.)

Question 21

exponentiation instruction:

Answer 21

it takes several instructions to compute x^y
when x and y are real numbers.
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 the bits of an integer by one position to the left is equivalent
to multiplication by 2, so that shifting the bits by k positions to the left is equivalent to multiplication by 2^k. Therefore, such computers can compute 2^k in one
constant-time instruction by shifting the integer 1 by k positions to the left, as long
as k is no more than the number of bits in a computer word. We will endeavor to
avoid such gray areas in the RAM model, but we will treat computation of 2^k as a
constant-time operation when k is a small enough positive integer

Question 22

Gray Area in RAM model:

Answer 22

Real computers contain instructions not listed above, and such instructions represent a gray area in the RAM model.

Question 23

memory hierarchy and RAM model:

Answer 23

In the RAM model, we do not attempt to model the memory hierarchy that is
common in contemporary computers. That is, we do not model caches or virtual
memory.
Models that include
the memory hierarchy are quite a bit more complex than the RAM model, and so
they can be difficult to work with. Moreover, RAM-model analyses are usually
excellent predictors of performance on actual machines.

Question 24

Even though we typically select only one machine model to analyze a given algorithm, we still face many choices in deciding how to express our analysis.

Answer 24

We
would like a way that is simple to write and manipulate, shows the important characteristics of an algorithm’s resource requirements, and suppresses tedious details.

Question 25

Why we need to define running time and input size?

Answer 25

In general, the time taken
by an algorithm grows with the size of the input, so it is traditional to describe the
running time of a program as a function of the size of its input. To do so, we need
to define the terms “running time” and “size of input” more carefully.

Question 26

Input Size:

3 examples

Answer 26

The best notion for input size depends on the problem being studied. For many
problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n
for sorting. For many other problems, such as multiplying two integers, the best
measure of input size is the total number of bits needed to represent the input in
ordinary binary notation. Sometimes, it is more appropriate to describe the size of
the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and
edges in the graph. We shall indicate which input size measure is being used with
each problem we study.

Question 27

Running TIme:

Assumptions?

Answer 27

The running time of an algorithm on a particular input is the number of primitive
operations or “steps” executed. It is convenient to define the notion of step so
that it is as machine-independent as possible.

A constant amount of time is required to execute each line of our
pseudocode. One line may take a different amount of time than another line, but
we shall assume that each execution of the ith line takes time ci, where ci is a
constant. This viewpoint is in keeping with the RAM model, and it also reflects
how the pseudocode would be implemented on most actual computers.

we separate the process of calling the
subroutine—passing parameters to it, etc.—from the process of executing the subroutine.
A statement that calls a subroutine takes constant time,
though the subroutine, once invoked, may take more.

Question 28

How to find running time:

Answer 28

The running time of the algorithm is the sum of running times for each statement executed; a statement that takes ci steps to execute and executes n times will
contribute cin to the total running time.6

Question 29

Linear Function of n:

Answer 29

(best case)
T (n) = c1n + c2(n - 1) + c4(n - 1) + c5(n - 1) + c8(n - 1)
= (c1 + c2 + c4 + c5 C c8)n - (c2 + c4 + c5 + c8)

We can express this running time as an + b for constants a and b that depend on
the statement costs ci; it is thus a linear function of n

Question 30

Insertion Sort:

Best case and worst case:

Answer 30

Best : Already sorted.
For each j = 2, 3, .. ,n, we then find
that A[i] key in line 5 when i has its initial value of j - 1. Thus tj = 1 for
j = 2, 3,…, n.

Worst: Reverse Sorted.
Compare A[j] with each element of subarray so
tj = j.

Question 31

Quadratic Function of n:

Answer 31

T(n) = (c5/2 + c6/2 + c7/2)n^2 +
(c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8)n
- (c2 + c4 + c5 + c8)

We can express this worst-case running time as
an^2 + bn + c for constants a, b,
and c that again depend on the statement costs ci; it is thus a quadratic function
of n.

Question 32

Why are we concentrating on finding worst case:

Answer 32

1. The worst-case running time of an algorithm gives us an upper bound on the
   running time for any input. Knowing it provides a guarantee that the algorithm
   will never take any longer. We need not make some educated guess about the
   running time and hope that it never gets much worse.
2. For some algorithms, the worst case occurs fairly often.
3. The “average case” is often roughly as bad as the worst case.

Question 33

Considering Average Case

consequences and what to consider:

Answer 33

In some particular cases, we shall be interested in the average-case running time
of an algorithm; we shall see the technique of probabilistic analysis applied to
various algorithms throughout this book. The scope of average-case analysis is
limited, because it may not be apparent what constitutes an “average” input for
a particular problem. Often, we shall assume that all inputs of a given size are
equally likely. In practice, this assumption may be violated, but we can sometimes
use a randomized algorithm, which makes random choices, to allow a probabilistic
analysis and yield an expected running time. We explore randomized algorithms
more in Chapter 5 and in several other subsequent chapters.

Question 34

Order of growth and Abstraction:

Answer 34

We used some simplifying abstractions to ease our analysis of the INSERTIONSORT procedure. First, we ignored the actual cost of each statement, using the
constants ci to represent these costs. This gave us more detail so we expressed the worst-case running time
as an^2 + bn + c for some constants a, b, and c that depend on the statement
costs ci. We thus ignored not only the actual statement costs, but also the abstract
costs ci.

We shall now make one more simplifying abstraction: it is the rate of growth,
or order of growth, of the running time that really interests us.

We consider only leading term, lower order term are relatively insignificant for large values of n.
We also ignore the leading term’s constant coefficient, since constant factors are less significant than the rate of growth
in determining computational efficiency for large inputs.

Question 35

Whats u can say a disadvantage of considering order of growth:

Answer 35

Due to constant factors and lowerorder terms, an algorithm whose running time has a higher order of growth might
take less time for small inputs than an algorithm whose running time has a lower order of growth. But for large enough inputs, a Theta(n^2) algorithm, for example, will
run more quickly in the worst case than a theta(n^3) algorithm.

Question 36

Selection Sort:

Answer 36

Consider sorting n numbers stored in array A by first finding the smallest element
of A and exchanging it with the element in AŒ1. Then find the second smallest
element of A, and exchange it with AŒ2. Continue in this manner for the first n1
elements of A. Write pseudocode for this algorithm, which is known as selection
sort. What loop invariant does this algorithm maintain? Why does it need to run
for only the first n 1 elements, rather than for all n elements? Give the best-case
and worst-case running times of selection sort in ‚-notation.

Question 37

Designing Algo, what technique did we use in Insertion Sort, explain.

Answer 37

For insertion
sort, we used an incremental approach: having sorted the subarray A[ . . j - 1],
we inserted the single element A[j ] into its proper place, yielding the sorted
subarray A[. . j].

Question 38

recursive in structure:

Answer 38

to solve a given problem, they

call themselves recursively one or more times to deal with closely related subproblems.

Question 39

Just say about divide n conquer:

Answer 39

Recursive algorithms typically follow a divide-and-conquer approach: they
break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these
solutions to create a solution to the original problem.

Question 40

The divide-and-conquer paradigm involves three steps at each level of the recursion:

Answer 40

Divide the problem into a number of subproblems that are smaller instances of the
same problem.

Conquer the subproblems by solving them recursively. If the subproblem sizes are
small enough, however, just solve the subproblems in a straightforward manner.

Combine the solutions to the subproblems into the solution for the original problem.

Question 41

The Merger Sort Algo Divide and Conquer steps:

Answer 41

Divide: Divide the n-element sequence to be sorted into two subsequences of n=2
elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.