UNIT 2

Introduction to Algorithms

1. What is algorithm? explain

An algorithm is the finite set of English statements which are designed to accomplish the specific task. Study of any algorithm is based on the following four criteria

1.Design of algorithm : This is the first step in the creation of an algorithm. Design of algorithm includes the problem statement which tell user about the area for which algorithm is required. After problem statement next important thing required is the information about available and required resources. The last thing required in design of algorithm phase is information about the expected output.

2.Validation of algorithm : Once an algorithm is designed , it is necessary to validate it for several possible input and make sure that algorithm is providing correct output for every input. This process is known as algorithm validation. The purpose of the validation is to assure us that this algorithm will work correctly independently of the issues concerning the programming language it will eventually be written in.

3.Analysis of algorithm : Analysis of algorithms is also called as performance analysis. This phase refers to the task of determining how much computing time and storage an algorithm requires.  The efficiency is measured in best case, worst case and average case analysis.

4.Testing of algorithm :  This phase is about to testing of a program which coded as per the algorithm. Testing of such program consists of two phases:

Debugging : It is the process of executing programs on sample data sets to determine whether faulty results occur or not and if occur, to correct them.

Profiling : Profiling or performance measurement is the process of executing a correct program on data sets and measuring the time and space it takes to compute the result

Characteristics of an algorithm

Input:  Algorithm must accept zero or more inputs.

Output: Algorithm must provide at least one quantity.

Definiteness: Algorithm must consist of clear and unambiguous instruction.

Finiteness: Algorithm must contain finite set of instruction and algorithm will terminates after a finite number of steps.

Effectiveness: Every instruction in algorithm must be very basic and effective.

Uses of algorithm

Algorithm provide independent layout of the program.

It is easy to develop the program in any desired language with help of layout.

Algorithm representation is very easy to understand.

To design algorithm there is no need of expertise in programming language.

2.     What is complexities of algorithm and explain flow chart?

There are three ways to represent an algorithm. Consider the following algorithm of addition of two numbers

Step 1 :Start

Step 2 : Read a number, say x and y

Step 3 : Add  x and y

Step 4 : Display Addition

Step 5 : Stop

1.Flowcharts: A flow chart is a diagrammatic / pictorial representation of an algorithm. It is the simplest way of representation of algorithm. Initially an algorithm is represented in the form of flowchart and then flowchart is given to programmer to express it in some programming language. Logical error detection is very easy in flowchart as it shows the flow of operations in diagrammatic form. Once flowchart is ready it is very easy to write a program in terms of statements of a programming language. Following are the symbols used in designing the flowcharts.

2.Pseudo code : Pseudo code is the combination of English statements with programming methodology. In pseudo code, there is no restriction of following the syntax of the programming language. Pseudo codes cannot be compiled. It is just a previous step of developing a code for given algorithm.

3.Program: In this way of representation, complete algorithm is represented using some programming language by following the complete syntax of programming language.

Sr. No.	Name of Symbol	Symbol	Meaning / Purpose
1.	Terminal		To indicate START / STOP. Usually it is the first symbol and last symbol used in program logic.
2.	Input / Output Statement		To indicate input / output of Data
3.	Processing Statement		To indicate the processing of instructions.
4.	Decision Box		To indicate decision making and a branch to one or more alternatives.
5.	Flow Lines		To indicate the direction of flow of information.
6.	Connector		It is used when flowchart becomes long and need to be continued. Shows the continuity of the algorithm on the next page.

3.     What is Programming?

Computer Programming is defined as the step by step process of designing and developing various sets of computer programs to accomplish a specific computing outcome. The process comprises several tasks like analysis, coding, algorithm generation, checking accuracy and resource consumption of algorithms, etc.

The purpose of computer programming is to find a sequence of instructions that solve a specific problem on a computer.

These basic elements include −

• Programming Environment
• Basic Syntax
• Data Types
• Variables
• Keywords
• Basic Operators
• Decision Making
• Loops
• Numbers
• Characters
• Arrays
• Strings
• Functions
• File I/O

4.     Explain Categories of Programming Languages

Procedure Oriented Programming

• Procedure Oriented Programming divides program into small procedures.
• A procedure is a set of instructions to perform specific independent task.
• A problem is viewed as a sequence of tasks and a separate procedure is written to perform that task.
• So the main emphasis is on procedure and data is given no/ little importance.
• Mostly data is global data which is shared by functions/procedures.
• It employs top down approach.

Fig.: Structure of procedure oriented programming

• Fig. Shows how global data is accessed by all functions in a program while local data can be accessed by only that specific function.

Object Oriented Programming

• Program is divided into number of objects.
• Objects are considered as real life entities that contain data and functions. 
• Data is given more importance than functions.
• Data is not accessible to functions of other classes and hence data security is ensured.
• It employs bottom up approach.

Fig. : Structure of Object Oriented Programming

• Fig.  shows how objects can communicate with other objects with the help of functions. Here data is not accessible to external functions which ensure data security.

Modular Programming

• Modular programming divides program into distinct independent units called as modules.
• Each module is a separate software component that is programmed and tested independently.
• Modular programming leads to effective development and maintenance of large programs.

Generic Programming Technique

• Usually codes or programs are tied to specific types. If we are writing program for stack it is written for a specific data type like stack of integer values.
• If we want to create stack of characters, then we need to rewrite code taking ‘char’ as a data type.
• This rewriting same code for a specific data type can be avoided by generic programming technique.
• Generic programs create software components that can be used for any data type.
• Thus we will write generic program for stack which will work on any data type.
• In C++, class and templates are generic programming components.

5.     What is Program Design?

C is a procedural programming language. It was initially developed by Dennis Ritchie in the year 1972. It was mainly developed as a system programming language to write an operating system. The main features of C language include low-level access to memory, a simple set of keywords, and clean style, these features make C language suitable for system programming’s like an operating system or compiler development.
Many later languages have borrowed syntax/features directly or indirectly from C language. Like syntax of Java, PHP, JavaScript, and many other languages are mainly based on C language. C++ is nearly a superset of C language (There are few programs that may compile in C, but not in C++).

Beginning with C programming:

1. Structure of a C program
   After the above discussion, we can formally assess the structure of a C program. By structure, it is meant that any program can be written in this structure only. Writing a C program in any other structure will hence lead to a Compilation Error.

The structure of a C program is as follows:

The components of the above structure are:

1. Header Files Inclusion: The first and foremost component is the inclusion of the Header files in a C program.
   A header file is a file with extension .h which contains C function declarations and macro definitions to be shared between several source files.

Some of C Header files:

• Stddef.h – Defines several useful types and macros.
• Stdint.h – Defines exact width integer types.
• Stdio.h – Defines core input and output functions
• Stdlib.h – Defines numeric conversion functions, pseudo-random network generator, memory allocation
• String.h – Defines string handling functions
• Math.h – Defines common mathematical functions

Syntax to include a header file in C:

#include

2.     Main Method Declaration: The next part of a C program is to declare the main() function. The syntax to declare the main function is:

Syntax to Declare main method:

Int main()

{}

3.     Variable Declaration: The next part of any C program is the variable declaration. It refers to the variables that are to be used in the function. Please note that in the C program, no variable can be used without being declared. Also in a C program, the variables are to be declared before any operation in the function.

Example:

Int main()

{

    int a;

.

.

4.     Body: Body of a function in C program, refers to the operations that are performed in the functions. It can be anything like manipulations, searching, sorting, printing, etc.

Example:

Int main()

{

    int a;

    printf("%d", a);

.

.

5.     Return Statement: The last part in any C program is the return statement. The return statement refers to the returning of the values from a function. This return statement and return value depend upon the return type of the function. For example, if the return type is void, then there will be no return statement. In any other case, there will be a return statement and the return value will be of the type of the specified return type.

Example:

Int main()

{

    int a;

    printf("%d", a);

    return 0;

}

6.     Write a program in C

Following is first program in C

Let us analyze the program line by line.
Line 1: [ #include <stdio.h> ] In a C program, all lines that start with # are processed by preprocessor  which is a program invoked by the compiler. In a very basic term, preprocessor  takes a C program and produces another C program. The produced program has no lines starting with #, all such lines are processed by the preprocessor. In the above example, preprocessor copies the preprocessed code of stdio.h to our file. The .h files are called header files in C. These header files generally contain declaration of functions. We need stdio.h for the function printf() used in the program.

Line 2 [ int main(void) ] There must to be starting point from where execution of compiled C program begins. In C, the execution typically begins with first line of main(). The void written in brackets indicates that the main doesn’t take any parameter  main() can be written to take parameters also. We will be covering that in future posts.
The int written before main indicates return type of main(). The value returned by main indicates status of program termination.

Line 3 and 6: [ { and } ] In C language, a pair of curly brackets define a scope and mainly used in functions and control statements like if, else, loops. All functions must start and end with curly brackets.

Line 4 [ printf(“GeeksQuiz”); ] printf() is a standard library function to print something on standard output. The semicolon at the end of printf indicates line termination. In C, semicolon is always used to indicate end of statement.

Line 5 [ return 0; ] The return statement returns the value from main(). The returned value may be used by operating system to know termination status of your program. The value 0 typically means successful termination.

How to excecute the above program:
Inorder to execute the above program, we need to have a compiler to compile and run our programs.

7.     Write Programming Paradigms

Paradigm is a method used to solve a problem or to do some task. Though there are many programming languages all of them need to follow some strategy for implementation and this methodology is paradigm. Programming paradigm is an approach used to solve problem using some programming language or a method to solve problem using tools and techniques.

                                                            Figure 1. Programming Paradigm

Programming paradigm is classified into

Imperative Paradigm and Declarative Paradigm

Imperative programming paradigm:

• Imperative programming is one of the oldest programming paradigms. It works by changing the program state through assignment statements. It performs step by step task by changing state.
• The focus is how to achieve the goal It consists of several statements and after execution all the result is stored.

Advantage:

1. Easy to implement
2. It contains loops, variables etc.

Disadvantage:

1. Complex problem cannot be solved
2. Less efficient and less productive
3. Parallel programming is not possible

8.     Write an Example of programming paradigm and explain Imperative programming and its categories in detail

// average of five number in C

Int marks [5] = { 12, 32, 45, 13, 19 } int sum = 0;

Float average = 0.0;

For (int i = 0; i < 5; i++) {

Sum = sum + marks[i];

}

Average = sum / 5;

Imperative programming is divided into three broad categories:

• Procedural
• OOP
• Parallel processing.

These paradigms are as follows:

Procedural programming paradigm –
This paradigm emphasizes on procedure in terms of under lying machine model. There is no difference in between procedural and imperative approach. It has the ability to reuse the code.

#include <iostream>

Using namespace std;

Int main ()

{

Int i, fact = 1, num;

Cout << "Enter any Number: ";

Cin >> number.

For (i = 1; i <= num; i++) {

Fact = fact * i;

}

Cout << "Factorial of " << num << " is: " << fact << endl;

Return 0;

}

Object oriented programming –
The program is written as a collection of classes and object which are meant for communication. The smallest and basic entity is the object. All kind of computation is performed on objects only.

Here emphasis is on data rather procedure.

Advantages:

• Data security
• Inheritance
• Code reusability
• Flexible and abstraction is also present

Parallel processing approach –
Parallel processing is the processing of program instructions by dividing them among multiple processors. A parallel- processing system consists of numbers of processor with the objective of running a program in less time by dividing them.

This approach can be like divide and conquer.

Examples are NESL (one of the oldest one) and C/C++ also supports because of some library function.

Declarative programming paradigm:
Declarative is divided as Logic, Functional, Database.

• The declarative programming is a style of building programs that expresses logic of computation but does not provide the control flow.
• Here it considers on theories of some logic. The focus is on what needs to be done rather how it should be done basically emphasize on what code is doing.
• It shows the result rather than showing how it is produced. This is the only difference between imperative (how to do) and declarative (what to do) programming paradigms.

Logic programming paradigms –
Logic programming paradigms can be termed as abstract model of computation. It would solve logical problems like puzzles, series etc.

In normal programming languages, such concept of knowledge base is not available but the concept of artificial intelligence, machine learning we have some models like Perception model mechanism.
In logical programming the main emphasize is on knowledge base and the problem. The execution of the program is very much like proof of mathematical statement,

For example,

Sum of two number in prolog:

  predicates

  sumoftwonumber(integer, integer)

Clauses

  sum(0, 0).

   sum(n, r):-

        n1=n-1,

        sum(n1, r1),

        r=r1+n

9.     Explain OOPS

• Program is divided into number of objects.
• Objects are considered as real life entities that contain data and functions. 
• Data is given more importance than functions.
• Data is not accessible to functions of other classes and hence data security is ensured.
• It employs bottom up approach.

Fig. Structure of Object Oriented Programming

Fig shows how objects can communicate with other objects with the help of functions. Here data is not accessible to external functions which ensure data security.

Advantages of OOP

• Real world complex problems can be modelled very well using OOP as OOP consists of object that represents real life entity.
• Using Inheritance class can reuse code of another class. This leads to faster software development and saves coding efforts and time.
• OOP ensures data security by making members of class private. Private members are accessible to same class hence data is not invaded by external functions.
• We can perform variety of tasks with the help of single function or operator by function or operator overloading.
• OOP provides better software development productivity than traditional programming languages due to data hiding, inheritance, polymorphism and templates.

10. Difference between Procedure Oriented Programming VS object oriented Programming