Answer the following questions

Algorithmic Problem Solving

Specification and Abstraction

Part II

Very Short Answers

1. Define an algorithm.

Answer: An algorithm is a sequence. of instructions to accomplish a task or solve a problem.

2. Distinguish between an algorithm and a process.

Answer:

Algorithm

(i) An algorithm is a step-by-step sequence of statements to solve a problem.

(iii) As an algorithm is executed, a process evolves which solves the problem.

Process

(i) An instruction describes an action.

(ii) When the instructions are executed, a process evolves which accomplishes the intended task or solves the given problem.

3. Initially,

farmer, goat, grass, wolf = L, L, L, L

and the farmer crosses the river with goat. Model the action with an assignment statement.

Answer:

(i) -- farmer, goat, grass, wolf = L, L, L, L

(ii) farmer, goat := R, R

(iii) -- farmer, goat, grass , wolf = R, R, L, L

(iv) farmer := L

(v) farmer, goat, grass, wolf = L, R, L, L

(vi) farmer, grass := R, R

(vii) -- farmer , goat, grass , wolf = R, R, R, L

(viii) famer, goat := L, L

(ix) -- farmer, goat, grass, wolf = L, L, R, L

(x) farmer, wolf := R, R

(xi) -- farmer, goat, grass, wolf = R, L, R, R

(xii) farmer : = L

(xiii) -- farmer , goat, grass , wolf = L, L, R, R

(xiv) farmer, goat: = R, R

(xv) - farmer, goat, grass, wolf = R, R, R, R

4. Specify a function to find the minimum of two numbers.

Answer:

(i) Minimum (A, B)

(ii) -- inputs : A an B are integers or real numbers.

(iii) -- outputs : A is minimum, (A < B)

B is minimum, (B <A)

5.  If √2 = 1.414, and the square_root() function returns -1.414, does it violate the following specification?

 - - square_root (x)

- -  inputs: x is a real number , x ≥ 0

- -  outputs: y is a real number such that y2=x

Answer: Yes, it violate the specification.

Part III

Short Answers

1. When do you say that a problem is algorithmic in nature?

Answer: We usually say that a problem is algorithmic in nature when its solution involves the construction of an algorithm. Some types of problems can be immediately recognized as algorithmic.

2. What is the format of the specification of an algorithm?

Answer: Let P be the required property of the inputs and Q the property of the desired outputs. Then the algorithm

 S is specified as

1. algorithm_name (inputs)

 2. -- inputs : P

3. -- outputs: Q

3. What is abstraction?

Answer: A problem can involve a lot of details. Several of these details are unnecessary for solving the problem. Only a few details are essential. Ignoring or hiding unnecessary details and modeling an entity only by its essential properties is known as abstraction.

4. How is state represented in algorithms?

Answer: (i) State is a basic and important abstraction.

(ii) Computational processes have state. A computational process starts with an initial state.

As actions are performed, its state changes. Its ends with a final state.

(iii) The state at any point of execution is simply the values of the variables at that point.

5. What is the form and meaning of assignment statement?

Answer: Assignment statement is used to store a value in a variable. It is written with the variable on the left side of the assignment operator and a value on the right side.

Format / Form :

variable := value

Example : m : = 2

When this assignment is executed, the value on the right side is stored in the variable on the left side.

6. What is the difference between assignment operator and equality operator?

Answer: Assignment operator is used to assign the right hand side value into left hand side variable.

Example : A = 5, B = 10

Equality operator is used compare the values of both right hand side variable and left hand side variable and results in either true or false.

Example : A == B (a = 5, b = 5) True

 A≠B (a = 5, b = 0) True.

Part IV

Explain

1. Write the specification of an algorithm hypotenuse whose inputs are the lengths of the two shorter sides of a right angled triangle, and the output is the length of the third side.

Answer: (i) Let us name the algorithm hypotenuse.

(ii) It takes the number as the input. Let us name the input S1, S2 should not be negative.

(iii) It produces the Hypotenuse of S1, S2 as the output. Let us name the output l. Then S1, S2 should be the square of l.

Now the specification of the algorithm is Hypotenuse (S1,S2)

- inputs : S1 and S2 are real numbers or integers.

- outputs : l is a real number such that l² = S1² + S2²

2. Suppose you want to solve the quadratic equation ax2 + bx + c = 0 by an algorithm.

 quadratic_solve (a, b, c)

-- inputs : ?

-- outputs: ?

You intend to use the formula and you are prepared to handle only real number roots.

Write a suitable specification.

x = (- b ± √[b2 - 4ac ] ) / 2a

Answer: Quadratic_solve (a, b, c)

-- inputs : a, b, c are real numbers, a ≠ 0

-- outputs : x is a real number, the quadration equation ax² + bx + c = 0 is satisfied by exactly two values fx, namely

x₁ = ( −b + √[b²−4ac] ) /  2a

and

x₁ = ( −b − √[b²−4ac] ) /  2a

3. Exchange the contents: Given two glasses marked A and B. Glass A is full of apple drink and glass B is full of grape drink. For exchanging the contents of glasses A and B, represent the state by suitable variables, and write the specification of the algorithm.

Answer: (i) Let us name the algorithm exchange.

(ii) It takes the number as the input. Let us name the input a, b. a,b should not be zero.

(iii) It produces the exchange of a,b by using third variable t as the output. Let us name the output. Then a, b, t should be exchange of the drinks.

Now the specification of the algorithm is Exchange (a, b)

-- inputs : a, b are integers, a≠ 0, b ≠ 0

 -- outputs : a, b are integers,

t: = a

 a : = b

 b:=t