1 Fundamental Principles of Algorithm and Recursion

DOI: 10.1201/9781003105800-1

1.1 Algorithm, Its Pseudo-Code Representation and FlowChart

1.1.1 Algorithm Definition

An algorithm is a step-by-step procedure for solving a problem. A sequential solution to any program that is scripted in any natural language is called as an algorithm. The algorithm is the first step of the solving process. After the problem analysis, the developer writes the algorithm for this problem. It is largely used for data processing, computing and other related computer and mathematical operations.

The algorithm must satisfy the following five conditions:

1. Input: Zero, one or more quantities are externally provided.
2. Output: The algorithm produces at least one output as a result.
3. Definiteness: Each statement must be clear, specific, and unambiguous.
4. Finite: The algorithm should conclude after a limited number of steps.
5. Effectiveness: Every statement must be very fundamental so that it can be carried out by any individual using only paper and pencil.

1.1.2 Pseudo-Code Representation

The word “pseudo” means “fake,” so “pseudo-code” means “fake code”. Pseudo-code is an informal language used by programmers to develop algorithms. Pseudo-code describes how you would implement an algorithm without getting into syntactical details. It uses the structural conventions of a formal programming language but is proposed for human reading rather than machine reading. It is used to create an overview or outline of a program. System designers write pseudo-code to make sure the programmer understands a software project’s requirements and aligns the code accordingly. The pseudo-code contains no variable declaration.

The pseudo-code follows certain standard loop structures as follows:

1. FOR… ENDFOR
2. WHILE… ENDWHILE

Certain terms also exist for standard conditional clauses:

1. IF… ENDIF
2. WHILE… ENDWHILE (this is both a loop and a conditional clause by the way)
3. CASE… ENDCASE

The pseudo-code cannot be compiled within an executable program.

Example in C code:

if (I < 10)
{
I++;
}

Therefore, its respective pseudo-code is:

If I is less than 10, increment I by 1.

Benefits of pseudo-code:

1. Pseudo-code is understood by every programming language developer like Java or C#. Net developer, etc.
2. Programming languages are difficult to read for most people, but pseudo-code permits non-programmers, such as business analysts, end user or customer to review the steps to approve the projected pseudo-code that matches the coding specifications.
3. By drafting the code in human language first, the programmer protects from omitting an important step.

Example 1.1: Algorithm for Identifying the Area of a Triangle

1. Step 1: Start
2. Step 2: Take input as the base and the height of the user
3. Step 3: Area = (base * height)/2
4. Step 4: Print area of triangle
5. Step 5: Stop.

Example 1.2: An Algorithm Used to Determine Number Is Odd or Even

1. Step 1: Start
2. Step 2: Enter any input number
3. Step 3: Reminder = number mod 2
4. Step 4: If reminder = 0, then

     Print "number is even"
   Else
     Print "number is odd"
   End if
   

5. Step 5: Stop.

1.1.3 Flowchart

The graphical representation of any program is referred to as flowcharts. A flowchart is a kind of diagram that represents an algorithmic program, a workflow or operations. A flowchart aims to provide people with a common language to understand a project or process. Developers often use it as a program-planning tool for troubleshooting a problem. Each flowchart provides the solution to a specific problem. There are a few standard graphics symbols, which are used in the flowchart as follows:

1. Start and Stop or Terminal

   The circular rectangles or oval symbol indicates where the flowchart starts and ends.

2. Input and Output

   The parallelogram symbol denotes input or output operations in the flowchart.

3. Process or Instruction

   The rectangle represents a process like computations, a mathematical operation or a variable assignment operation, etc.

4. Arrows or Direction of Flow

   Arrows or direction of flow represents the flow of the sequence of steps and direction of a process.

5. Question or Decision

   The diamond symbol is used as a representation of the true or false statement tested in a decision symbol.

6. Connector

   A flowchart is divided into two or more smaller flowcharts, consistent with project requirements. This connector is most often used when a flowchart does not fit on a single page or has to be split into sections. A connector symbol, which is a small circle called an On-Page Connector, with a number inside it, allows you to connect two flowcharts on the same page.

   A connector symbol that looks like a pocket on a shirt, called off-page connector allows you to connect to a flow diagram on another page.

Guidelines for developing flowcharts:

Here are a couple of things to keep in mind when designing and developing a flowchart:

1. The arrows should not intersect during the design of a flowchart.
2. Processes or activities take place from top to bottom or from left to right in general.
3. The on-page connectors are referenced using digits in general.
4. Off-page connectors are referenced using alphabets generally.
5. The flowchart may have only one beginning symbol and a one-stop symbol.
6. The shapes, lines and texts of a flowchart need to be consistent.

Pros and cons of flowcharts:

Advantages of flowchart:

1. Flowcharts are one of the best ways of documenting programs.
2. Flowcharts are easier to understand compared to algorithms and pseudo-codes.
3. It helps us to debug and analyze processes.
4. It helps us understand how to think or make decisions to formulate the problem.

Disadvantages of flowchart:

1. Manual tracking is needed to verify the accuracy of the paper flowchart.
2. Modification of the flowchart is sometimes time-consuming.
3. It is difficult to display numerous branches and create loops in the flowchart.
4. A simple modification of the problem logic can result in a complete redesign of the flowchart.
5. It is very difficult to draw a flowchart for huge and complicated programs.

Example: Draw a flowchart to find area of triangle and odd or even number:

1.2 Abstract Data Type

Abstract data type (ADT) is a type or class of objects whose behavior is determined by a set of values and a set of functions. The definition of ADT only refers to the transactions that need to be performed, but not the way these transactions will be implemented. It does not specify how the data will be organized in memory and what algorithms will be used for the implementation of those operations. It is called “abstract” because it provides an independent perspective from the implementation. The process of supplying only the essentials and concealing details is known as abstraction.

The programmer who has used the data type may not know that how data type is implemented, for example, we have been using different built-in data types such as int, long, float, double, char only with the knowledge that which values we can store in that particular data types and operations that can be performed on them without any idea of how these data types are implemented. Therefore, a programmer just needs to know what a kind of data can do, but not how it’s going to do it. ADT may be considered a black box that hides the internal structure and design of the data type. We are now going to define three ADTs: List ADT, Stack ADT, Queue ADT.

1.2.1 List ADT

A list contains items of the same type organized in sequence, and the following operations can be carried out on the list.

1. Get () – Returns an element of the list to a specific position.
2. Insert () - Insert an item in any position on the list.
3. Remove () – Remove the first instance of an item in a non-empty list.
4. RemoveAt () – Removes the element at a specified location from a non-empty list.
5. Replace () – Replace an item at any position with a different item.
6. Size () – Returns the number of items within the list.
7. IsEmpty () – Returns true if the list is empty, else returns false.
8. IsFull () - Returns true if the list is full, otherwise it returns false.

1.2.2 Stack ADT

A stack contains elements of the same type arranged in sequential order and push and pop operations occur at one end at the top of the stack. The following operations may be carried out on the stack:

1. Push () – Insert an item on one end of the stack called the top.
2. Pop () – Removes and returns the item to the top of the stack, if it is not empty.
3. Top () – Returns the element to the top of the stack without deleting it, if the stack is not empty.
4. Size () – Returns the number of items within the stack.
5. IsEmpty () – Returns true if it is empty, otherwise returns false.
6. IsFull () – Returns true if the stack is full or returns false.

1.2.3 Queue ADT

A queue contains similar items organized in a sequential order. The operations take place at both ends, which is at the front and rear, the insertion is done at the rear and the deletion is done at the front. The following operations may be carried out in the queue:

1. Enqueue () – Insert an element at the end of the queue that is the rear end.
2. Dequeue () – Delete the first item from the front end of the queue, if the queue is not empty.
3. Size () – Returns the number of items within the queue.
4. IsEmpty () - Returns true if the queue is empty, otherwise return false.
5. IsFull () – Returns true if the queue is full or returns false.

From these descriptions of ADTs, we can see that the descriptions do not specify how these ADTs will be represented and how the operations will be carried out. There can be alternative ways to implement ADTs using an array or linked list, for example, the list ADT can be implemented using arrays as statically, or singly linked list or doubly linked list as dynamically. Likewise, stack ADT and Queue ADT or other ADTs can be implemented using related arrays or linked lists.

1.3 Data Structure

1.3.1 Definition

The data structure is a collection of data elements organized in a specific manner and functions is defined to store, retrieve, delete and search for individual data elements.

All data types, including built-in such as int and float; derived such as array and pointer; or user defined such as structure and union, are nothing but data structures. A data structure is a specialized format for organizing and storing data, with features for recovering, removing and search for data items. General data structure includes array, list, stack, tree, graph, etc. Each data structure is designed to organize data with particular intention so that it can be accessed and used appropriately.

The data structure study covers the following topics:

1. Amount of storage needed.
2. Amount of time required to process the data.
3. Data representation of the primary memory.
4. Operations carried out with such data.

1.3.2 Types of Data Structures or Their Classification

1.3.3 Difference in Abstract Data Types and Data Structures

The ADT is the interface. It is defined by what operations it will support. It does not specify how the data structure or algorithmic technique will be used to perform these operations.

For example, many different ideas can be used to implement a queue: it could be a circular queue, linear queue, doubly ended queue and priority queue. Queue implemented using arrays or linked lists. As a result, the data structure is an implementation of the ADT.

ADT is a logical picture of data and data manipulation operations. The data structure is the genuine representation of the data during implementation and the algorithms for manipulating the data elements. ADT is the logical level, and the data structure is an implementation level.

ADT is a representation of a data type in terms of possible values and not how the values are stored in memory, operations permissible without concerning its implementation details.

So stack when implemented using a programming language like C, would be a data structure, but describing it in terms of things like its behavior such as last in, first out (LIFO), a possible set of values, operations permissible such as push, pop, etc. would be considered as an ADT for stack.

1.4 Algorithm Efficiency or Performance Analysis of an Algorithm

The effectiveness of the algorithm or the analysis of the performance of an algorithm mainly concerns two things: the complexity of space and the complexity of time.

1.4.1 Space Complexity

Space complexity is defined as the total amount of primary memory a program needs to run to its completion.

1.4.1.1 Components of Program Space

Program space covers instruction space, data space and stack space depicted as follows:

Program space = Instruction space + data space + stack space.

1. Instruction space is dependent on several factors:
   1. A compiler that generates the machine or binary code
   2. Target computer
2. Data space:
   1. Heavily dependent on computer’s architecture and compiler.
   2. Magnitude of data that program works.

      In programming languages, there are different kinds of data and different number of bytes to store particular data are required. Such that the character data type requires 1 byte of memory, integer requires 4 bytes, float requires 4 bytes, double requires 8 bytes, etc. This varies from one compiler to another. Choosing a “smaller” data type will affect the overall use of space in the program. Choose the appropriate type when working with arrays.

3. Stack space:

   Each time a function is called, the following data are recorded in the stack.

   1. The return address.
   2. Value of all local variables and value of formal parameters.
   3. Bindings of all references and constant reference parameters.

   A few points to make efficient use of space:

   1. Always select the smallest data type that you need.
   2. Go through the compiler in detail.
   3. Discover the effects of various compilation settings.
   4. Choose a non-recursive algorithm, if applicable.

Space (p) requirements for any p algorithm can therefore be written as,

1. S (p) = c + Sp (instance characteristics)
2. C = fixed part: this includes instruction space, space for single and fixed-size variables, constants, etc.
3. Sp = variable part: space needed for referenced variables, which depends on instance characteristics and recursion state space.

Examples:

1. Non-recursive algorithm sum(a, n)

   {
   S = 0.0;
   for i =1 to n do
   S = S + a[i] ;
   return S;
   }
   

   Here the space complexity of non-recursive sum algorithm is as follows:

   Ssum(n) >= (n+3)
   

   where Ssum (n) means the space complexity of non-recursive algorithm sum having size of array elements n.

   And (n+3) means n for array element a[], one each for n, i and s.

2. Recursive algorithm Rsum(a, n)

   {
   if (n<=0) then return 0.0;
   else return Rsum (a, n-1) + a[n];
   }
   

   Space required for the recursive Rsum algorithm is:

   Each call to Rsum requires at least three words such as each for n, return address and a pointer to array a []. Recursion call occurs (n+1) times so the recursive state space needed is ≥ 3 (n+1).

   That means the space complexity of SRsum (n) ≥ 3 (n+1) where SRsum (n) means the space complexity of recursive algorithm Rsum having size of array elements n.

1.4.2 Time Complexity

The amount of time it takes for an algorithm to run is called as time complexity.

Absolute time complexity is defined as follows:

Absolute time complexity =number of instructions×time taken to execute one instruction

However, the time taken to execute one instruction, this quantity varies from system to system or computer to computer. Therefore, we only consider the number of instructions in an algorithm to be a time complexity.

For most algorithms, running time depends on the size of the input. Run time is expressed in T (n) for a function T on input size n. Suppose there is if….. else statement that may execute or not, then in that situation variable running time.

In general, algorithm time complexity is calculated in the following ways:

1. Worst case: The maximum time required to execute the program. The time complexity of the worst case is represented by the big Oh notation, O.
2. Average case: The average time required to execute the program. The time complexity of the average case is represented by the Theta notation, θ.
3. Best case: The minimum time required to execute the program. The time complexity of the best case is represented by Omega notation, Ω.

The efficiency or analysis of an algorithm involves two phases:

1. Prior estimate:

   Prior estimates concern theoretical or mathematical calculations. Theoretical or mathematical calculations use the asymptotic notation for representation.

2. Posterior estimate or testing:

   The designed algorithm is implemented on a machine. It deals with the writing of a program and thus depends on the operating system, compiler, etc.

Performance analysis: The primary goal is to determine the time and space required to run the program to its completion in terms of system time and system memory.

Prior analysis: Deals with computations of count of statement in a given algorithm. The count indicates how often each instruction is executed.

1. Example 1

   1. Algorithm add (a, n)
   2. {
   3. S=0;
   4. for (i=1 to n) do
   5. S = S + a[i];
   6. return s;
   7. }
   

   Line Number	Step per Execution	Frequency	Total Steps
   1.	0	0	0
   2.	0	0	0
   3.	1	1	1
   4.	1	n+1	n+1
   5.	1	N	N
   6.	1	1	1
   7.	0	0	0
   			2n+3 step count

2. Example 2:

   1. Algorithm add(a,b,c,m,n)
   2. {
   3. for (i=1 to m) do
   4. for (j=1 to n) do
   5. C[i, j]=a[i, j]+b[i, j]
   6. }
   

   Line Number	Total Steps
   1.	0
   2.	0
   3.	m+1
   4.	m(n+1)
   5.	Mn
   6.	0
   	2mn+2m+1 step count

   In examples 1 and 2, the number of steps carried out is shown.

   There are three types of step count:

   1. Best case: Minimum number of steps that can be executed for given inputs.
   2. Worst case: Maximum number of steps that can be executed for given inputs.
   3. Average case: Average number of steps that can be executed for given inputs.

1.5 Recursion and Design of Recursive Algorithms with Appropriate Examples

The recursive function is a function that is invoked by itself. Similarly, an algorithm is said recursive if the same algorithm is called within the body.

Recursive algorithms can be divided into the following types:

1. Direct recursive algorithm: An algorithm is said to direct recursive algorithm if the same algorithm is called within the body.

   Example:

   #include<stdio.h<
   int main()     // main function is called as direct
   recursive function.
   {
           printf("Hello\n");
           main();        // call to the main function
           return 0;
   }
   

   Output:

   Print Hello infinite times.

   In the above program, the main () function is invoked by itself is called as direct recursive function.

2. Indirect recursive algorithm: Algorithm A is considered an indirect recursive algorithm if it calls another algorithm B that in turn calls A.

   Example:

   #include<stdio.h>
   void demo();
   int main()   //main function is called as indirect
   recursive function.
   {
   printf("Hello\n");
   demo();
   return 0;
   }
   void demo()
   {
   main();   // call to the main function inside demo
   function and demo function is called by // main
   function
   }
   

   Output:

   Print Hello infinite times.

   In the above program, the demo () function is invoked by the main () function and the main function is again invoked inside the body of the demo () function is called as indirect recursive function.

1.5.1 Example 1: Implementing a Factorial Program Using Non-recursive Functions

#include <stdio.h>
long factorial(int);
int main()
{
int number;
long fact = 1;
printf("Enter a number to calculate its factorial\n");
scanf("%d", &number);
printf("%d! = %ld\n", number, factorial(number));
return 0;
}
long factorial(int n)
{
int c;
long fact = 1;
for (c = 1; c <= n; c++)
{
fact = fact * c;
}
return fact;
}

Output:

Enter a number to calculate its factorial

4

4! = 24

1.5.2 Example 2: Implementing a Factorial Program Using Recursive Functions

#include<stdio.h>
long factorial(int);
int main()
{
int n;
long f;
printf("Enter an integer to find its factorial\n");
scanf("%d", &n);
if (n < 0)
printf("Factorial of negative integers isn't defined.\n");
else
{
f = factorial(n);
printf("%d! = %ld\n", n, f);
}
return 0;
}
long factorial(int n)
{
if (n == 0)
return 1;
else
return(n * factorial(n-1));
}

Output:

Enter an integer to find its factorial

4

4! = 24

1.5.3 Example 3: Implementing a Program That Displays the Sum of Digits in a Number Using Non-recursive Functions

#include<stdio.h>
int sum_of_digit(int n)
{
int r,sum =0;
r = n % 10;   // separate first digit of a number
sum = sum + r;   // add the separated digit in the intermediate variable
n = n/10;     // delete first digit of a number
}
int main()
{
int num = 123;
int result = sum_of_digit(num);
printf("Sum of digits in %d is %d\n", num, result);
return 0;
}

Output:

The sum of digits in 123 is 6.

1.5.4 Example 4: Implementing a Program That Displays the Sum of Digits in a Number Using Recursive Functions

#include<stdio.h>
int sum_of_digit(int n)
 {
if (n == 0)
return 0;
return (n % 10 + sum_of_digit(n / 10));
}
int main()
{
int num = 123;
int result = sum_of_digit(num);
printf("Sum of digits in %d is %d\n", num, result);
return 0;
}

Output:

Sum of digits in 123 is 6

1.5.5 Example 5: Implementation of the Sum of n First Natural Numbers by Means of Non-recursive Functions

#include <stdio.h>
int addNumbers(int n);
int main()
{
int num;
printf("Enter a positive integer: ");
scanf("%d", &num);
printf("Sum = %d",addNumbers(num));
return 0;
}
int addNumbers (int n)
{
int i, sum=0;
for(i=1; i<=n; i++)
{
sum = sum + i;
}
return sum;
}

Output:

Enter a positive integer: 5

Sum = 15

1.5.6 Example 6: Implementation of the Sum of n First Natural Numbers by Means of Recursive Functions

#include <stdio.h>
int addNumbers(int n);
 int main()
{
int num;
printf("Enter a positive integer: ");
scanf("%d", &num);
printf("Sum = %d",addNumbers(num));
return 0;
}
int addNumbers (int n)
{
if(n != 0)
return n + addNumbers(n-1);
else
return n;
}

Output:

Enter a positive integer: 5

Sum = 15

1.5.7 Example 7: Implementation of the Prime Number Program Using Non-recursive Functions

#include<stdio.h>
int isPrime(int,int);
int main()
{
int num, prime;
printf("Enter a positive number: ");
scanf("%d",&num);
prime = isPrime(num, num/2);
if(prime==1)
       printf("%d is a prime number",num);
else
      printf("%d is not a prime number",num);
return 0;
}
int isPrime(int num, int n)
{
    int i;
       for(i=n; i>=2 ; i--)
    {
       if(num % i==0)
       {
       return 0;   // if number is not prime
       }
}
      return 1;   // if number is prime
}

Output:

Enter a positive number: 7

7 is a prime number

1.5.8 Example 8: Implementation of the Prime Number Program Using Recursive Functions

#include<stdio.h>
int isPrime(int,int);
int main()
{
int num, prime;
printf("Enter a positive number: ");
scanf("%d",&num);
prime = isPrime(num, num/2);
if(prime==1)
       printf("%d is a prime number",num);
else
     printf("%d is not a prime number",num);
return 0;
}

int isPrime(int num, int i)
{
if( i==1 )
{
        return 1;
}else{
       if(num % i ==0)
         return 0;
       else
         isPrime(num, i-1);
        }
}

Output:

Enter a positive number: 21

21 is not a prime number

1.5.9 Example 9: Implementation of the Reverse Number Program Using Non-recursive Functions

#include<stdio.h>
int reverse_function(int num);
int main()
{
    int num, reverse_number;
    printf("\nEnter any number:");
    scanf("%d",&num);
   reverse_number=reverse_function(num);
    printf("\nAfter reverse, the number is
:%d",reverse_number);
    return 0;
}
int rev=0, rem;
int reverse_function(int num)
{
   while(num!=0)
   {
      rem=num % 10;    // separate first digit of a number
      rev=(rev * 10 )+ rem;         //multiply each intermediate
number (rev) by 10 and add separated //digit into it gives you
reverse number
      num = num / 10; // delete first digit of a number
    }
      return rev;
}

Output:

Enter any number: 546

After reverse, the number is: 645

1.5.10 Example 10: Implementation of the Reverse Number Program Using Recursive Functions

#include<stdio.h>
int reverse_function(int num);
int main()
{
   int num, reverse_number;
   printf("\nEnter any number:");
   scanf("%d",&num);
   reverse_number=reverse_function(num);
   printf("\nAfter reverse, the number is
:%d",reverse_number);
   return 0;
}
int sum=0, rem;
int reverse_function(int num)
{
   if(num)
   {
      rem=num%10;
      sum=sum*10+rem;
      reverse_function(num/10);
   }
   else
      return sum;
}

Output:

Enter any number: 123

After reverse, the number is: 321

1.6 Interview Questions

1. What is an algorithm and flowchart explain with suitable example?
2. Explain pseudo-code representation in detail.
3. Write an algorithm to read three different numbers from the user and then find the largest between that three numbers.
4. Draw the flowchart to check whether a number is a prime number.
5. Write an algorithm and flowchart for finding the sum of all odd numbers from 100 to 500.
6. Write an algorithm and flowchart to calculate even numbers between 0 and 500.
7. Write an algorithm and flowchart to find the middle number by giving three numbers.
8. What is an ADT in data structure?
9. What is the difference between an ADT and a data structure?
10. Explain data structure with suitable examples?
11. What are the applications of data structures?
12. What are the different types of data structures?
13. What are the different advantages and disadvantages of flowchart?
14. What is the performance analysis of an algorithm?
15. What are the two main measures for the efficiency of an algorithm?
16. Explain the different symbols used in the flowchart.

1.7 Multiple Choice Questions

1. Which of the following issues cannot be resolved by recursion?
   1. Factorial of a number
   2. Finding of a prime number
   3. Problems without base case
   4. Finding of sum of digits in any number

      Answer: (C)

      Explanation:

      Problems having a base case should be solved using recursion. However, problems without base case lead to infinite recursion call and cannot be resolved using recursion.

2. The recursion process is identical with which of the following construct?
   1. Switch case
   2. If else
   3. Loop
   4. if else if ladder

      Answer: (C)

      Explanation:

      The recursion process is like a loop and all recursive calls are kept in the memory area of the stack.

3. What will be the output of the following code?

   #include<stdio.h>
   void recursion(int n)
   {
      if(n == 0)
      return;
      printf("%d",n);
      recursion(n-2);
   }
   int main()
   {
      recursion(6);
      return 0;
   }
   

   1. 642
   2. 654321
   3. 662
   4. 6420

      Answer: (A)

      Explanation:

      Recursion function’s first call print value 6, second call print value 4, third call print value 2 and the fourth call will execute return statement when the value becomes 0, so the output of the program is 642.

4. Which of the following data structure used to implement recursion in the main memory?
   1. Stack
   2. Array
   3. Linked list
   4. Tree

      Answer: (A)

      Explanation:

      Stack is a data structure that is used to implement recursion into the main memory.

5. What will be the output of the following C code?

   #include<stdio.h>
   int main()
   {
       printf("Hello students");
       main();
       return 0;
   }
   

   1. Hello students is printed once
   2. Hello students is printed infinite times
   3. Hello students is printed till the stack overflows occur
   4. None of the above

      Answer: (C)

      Explanation:

      In the above code, the main () function itself, calling main () is called as recursion. In the above code, there is no termination condition to exit from the program. Hence, “Hello students” will be printed an infinite number of times. However, practically, when the stack memory partition is overflowing, the printing of “Hello students” will be stopped.

6. A sequential solution of any program that is written in any natural language is called as:
   1. Flowchart
   2. Algorithm
   3. Method
   4. A and B both

      Answer: (B)

      Explanation:

      A sequential solution of any program that wrote in any natural language is called as an algorithm.

7. Which of the following code describes how you would implement an algorithm without getting into syntactical details.
   1. Program code
   2. Pseudo-code
   3. Machine-level code
   4. Binary code

      Answer: (B)

      Explanation:

      Pseudo-code describes how you would implement an algorithm without getting into syntax details.

8. Which of the following is true for ADT that is ADT?
   1. ADT is a type or class for objects whose behavior is defined by a set of values and a set of functions.
   2. ADT is only stating that what operations are to be carried out.
   3. ADT does not mention how data will be organized in memory.
      1. I and II are correct
      2. Only I is correct
      3. II and III are correct
      4. I, II and III are correct

         Answer: (D)

         Explanation:

         ADT is a type or class for objects whose behavior is defined by a set of values and a set of functions. ADT only mentions what operations are to be performed, but not how these operations will be implemented.

9. Algorithm efficiency or performance analysis of an algorithm is concerned with which of the following things.
   1. Time complexity
   2. Space complexity
   3. Both A and B
   4. None of the above

      Answer: (C)

      Explanation:

      The effectiveness of the algorithm or the analysis of the performance of an algorithm is measured in terms of time and space complexity.

10. Elements of program space within space complexity include which of the following.
    1. Instruction space
    2. Data space
    3. Stack space
    4. All the above

       Answer: (D)

       Explanation:

       Program space = Instruction space + data space + stack space.

11. Which of the following statements is false or true?
    1. Pseudo-code is an informal language used by programmers to develop algorithms.
    2. The pseudo-code contains no variable declaration.
       1. Statement 1 is false
       2. Statement 2 is false
       3. Statements 1 and 2 both are false
       4. Statements 1 and 2 both are true

          Answer: (D)

12. Which of the following statements is false or true?
    1. A flowchart is a kind of diagram which represents an algorithmic program, a workflow or operations.
    2. A sequential solution of any program that is scripted in any natural language is called as an algorithm.
       1. Statement 1 is false
       2. Statement 2 is false
       3. Statements 1 and 2 both are false
       4. Statements 1 and 2 both are true

          Answer: (D)

13. Which of the following statements is false or true?
    1. Space complexity is defined as the total amount of secondary memory a program needs to run to its completion.
    2. The amount of time required for a program to compile is called as its time complexity.
       1. Statement 1 is false
       2. Statement 2 is false
       3. Statements 1 and 2 both are false
       4. Statements 1 and 2 both are true

          Answer: (C)

14. Which of the following statements is false or true?
    1. Minimum number of steps that can be executed for given inputs is called as best case.
    2. Maximum number of steps that can be executed for given inputs is called as worst case.
       1. Statement 1 is false
       2. Statement 2 is false
       3. Statements 1 and 2 both are false
       4. Statements 1 and 2 both are true

          Answer: (D)

15. Which of the following statements is false or true?
    1. The recursive function is a function that is invoked by itself.
    2. Algorithm A is considered direct recursive algorithm if it calls another algorithm B that in turn calls A.
       1. Statement 1 is false
       2. Statement 2 is false
       3. Statements 1 and 2 both are false
       4. Statements 1 and 2 both are true

          Answer: (B)