Define control abstraction.

• By control abstraction, we mean “procedure whose major operations are by other procedures whose specific meanings are left unspecified.”
• Control abstraction is a procedure that has this flow of control.
• Create an abstraction of control for the divide-and-conquer strategy.

Write control abstraction for Divide and Conquer

Algorithm DC(P)
// P is the problem to be solved

if P is small enough then
     return Solution of P 
else
     divide larger problem P into k smaller subproblems P1, P2, …, Pk
     solve each small subproblem Pi using DC strategy
     return combined solution (DC(P1), DC(P2), …, DC(Pk))
end

Write control abstraction for greedy approach

Algorithm GREEDY_APPROACH(L, n)
// Description : Solve the given problem using a greedy approach
// Input : 
L : List of possible choices, 
n: the size of the solution 
// Output : Set Solution containing the solution of the given problem

Solution ← ∅
for i ← 1 to n do
    Choice ← Select(L)
    if (feasible(Choice ∪ Solution)) then
        Solution ← Choice ∪ Solution
    end
end
return Solution

Write control abstraction for Dynamic Programming

Algorithm DYNAMIC_PROGRAMMING (P)

if solved(P) then
    return lookup(P)
else
    Ans ← SOLVE(P)
    store (P, Ans)
end

FUNCTION SOLVE(P)
    if sufficiently small(P) then
        solution(P)	// Find solution for sufficiently small problem
    else

        Divide P into smaller sub problems P1, P2, ..., Pn
        Ans1 ← DYNAMIC_PROGRAMMIN(P1)
        Ans2 ← DYNAMIC_PROGRAMMIN(P2)
                .
                .
        Ansn ← DYNAMIC_PROGRAMMIN(Pn)
        return (combine(Ans1, Ans2 ..., Ansn))
    end

Name some basic Efficiency classes

Following are some of the common efficiency classes:

• Constant
• Logarithmic
• Linear
• nlogn
• Quadratic
• Cubic
• Exponential
• Factorial

What is an Activation frame?

It is a storage area for an invocation of recursive program (parameters, local variables, return address/value etc.). Activation frame allocated from frame stack pointed by frame pointer.

Define order of an algorithm

Measuring the performance of an algorithm in relation to the input size n is known as the order of growth.

What is recursive call?

• When an algorithm makes many calls to itself, this type of interaction is referred to as a recursive call.
• Direct recursion describes an algorithm that repeatedly invokes itself.
• If algorithm A calls another algorithm, and that second algorithm then calls A, then we say that algorithm A is an indirect recursive algorithm.

What do you mean by stepwise refinement?

In top-down design methodology the problem is solved in sequence (step by step) is known as stepwise refinement.

What do you mean by the time complexity and space complexity of an algorithm?

• The time complexity of an algorithm describes how quickly it can be executed.
• The space complexity refers to the additional memory that it needs.
• The time efficiency of a process can be evaluated by counting the number of times the fundamental operation is performed and plotting that data against the amount of the input.
• The basic operation is the one that has the most impact on the total amount of time it takes for the algorithm to complete.
• The amount of time that an algorithm takes to run is determined by the function that is based on the number of steps (or the amount of memory) that are needed to solve input instances that are size n.