LECTURE NOTE

on
PROGRAMMING IN “C”

&

DATA STRUCTURE

2
SYLLABUS (PROGRAMMING IN “C” )

PART 1
Module –I
C Language Fundamentals.
Character set, Identifiers, keyword, data types, Constants and variables, statements,
expression, operators, precedence of operators, Input-output, Assignments, control structures
decision making and branching.

Module -II
Arrays, Functions and Strings: Declaration, manipulation and String – handling
functions, monolithic vs. Modular programs, user defined vs. standard functions, formal vs. actual
arguments, function – category, function prototypes, parameter passing, recursion, and storage classes:
auto, extern, global, static.

Module –III
Pointers, Structures, Unions, File handling:
Pointer variable and its importance, pointer arithmetic, passing parameters, Declaration of structures,
pointer to pointer, pointer to structure, pointer to function, union, dynamic memory allocation, file
managements.

3
CONTENTS
Module: 1
Lecture 1: Introduction to C
Lecture 2: Structure of C, compilation, execution Lecture 3:character set, identifiers, keywords
Lecture 4: constants, variables
Lecture 5: expression, operators
Lecture 6: operators continue…
Lecture 7: loops: do while, while
Lecture 8: for loop, break, continue statement
Lecture 9: control Statements
Lecture 10: nesting of if else…, if else ladder
Lecture 11: arrays
Lecture 12: 2-diamensional array

Module: 2

Lecture 13: String library functions

Lecture 14: functions, categories
Lecture 15: functions categories cont..
Lecture 16: Actual arguments and Formal arguments, call by value call by reference
Lecture 17:local, global, static variable
Lecture 18: monolithic vs modular programming, Storage classes Lecture 19:storage class cont.., pointer
Lecture 20: pointer comparison, increment decrement
Lecture 21: precedence level of pointer, pointer comparison
Lecture 22: pointer to pointer, pointer to structure
Lecture 23: pointer initialization, accessing elements

Module: 3
Lecture 24: size of Structure in, array vs structure, array within structure
Lecture 25: passing structure to function, Nested Structure
Lecture 26: Union
Lecture 27: nesting of unions, dynamic memory allocation
Lecture 28: dynamic memory allocation conti…
Lecture 29: dynamic array, file
Lecture 30: file operation
Lecture 31: file operation on string

4
SYLLABUS (DATA STRUCTURE)

PART 2

Module – I
Introduction to data structures: storage structure for arrays, sparse matrices, Stacks and
Queues: representation and application. Linked lists: Single linked lists, linked list
representation of stacks and Queues. Operations on polynomials, Double linked list,
circular list.

Module – II
Dynamic storage management-garbage collection and compaction, infix to post fix
conversion, postfix expression evaluation. Trees: Tree terminology, Binary tree, Binary
search tree, General tree, B+ tree, AVL Tree, Complete Binary Tree representation,
Tree traversals, operation on Binary tree-expression Manipulation.

Module –III
Graphs: Graph terminology, Representation of graphs, path matrix, BFS (breadth first
search), DFS (depth first search), topological sorting, Warshall‘s algorithm (shortest
path algorithm.) Sorting and Searching techniques – Bubble sort, selection sort,
Insertion sort, Quick sort, merge sort, Heap sort, Radix sort. Linear and binary search
methods, Hashing techniques and hash functions.

Text Books:
1. Gilberg and Forouzan: ―Data Structure- A Pseudo code approach with C‖ by
Thomson publication
2. ―Data structure in C‖ by Tanenbaum, PHI publication / Pearson publication.
3. Pai: ‖Data Structures & Algorithms; Concepts, Techniques & Algorithms ‖Tata
McGraw Hill.

Reference Books:
1. ―Fundamentals of data structure in C‖ Horowitz, Sahani & Freed, Computer Science
Press.
2. ―Fundamental of Data Structure‖ ( Schaums Series) Tata-McGraw-Hill.
 CONTENTS

Lecture-01 Introduction to Data structure

Lecture-02 Search Operation
Lecture-03 Sparse Matrix and its representations
Lecture-04 Stack
Lecture-05 Stack Applications
Lecture-06 Queue
Lecture-07 Linked List
Lecture-08 Polynomial List
Lecture-09 Doubly Linked List
Lecture-10 Circular Linked List
Lecture-11 Memory Allocation
Lecture-12 Infix to Postfix Conversion
Lecture-13 Binary Tree
Lecture-14 Special Forms of Binary Trees
Lecture-15 Tree Traversal
Lecture-16 AVL Trees
Lecture-17 B+-tree
Lecture-18 Binary Search Tree (BST)
Lecture-19 Graphs Terminology
Lecture-20 Depth First Search
Lecture-21 Breadth First Search
Lecture-22 Graph representation
Lecture-23 Topological Sorting
Lecture-24 Bubble Sort
Lecture-25 Insertion Sort
Lecture-26 Selection Sort
Lecture-27 Merge Sort
Lecture-28 Quick sort
Lecture-29 Heap Sort
Lecture-30 Radix Sort
Lecture-31 Binary Search
Lecture-32 Hashing
Lecture-33 Hashing Functions
 PART 1
(PROGRAMMING IN “C” )
 Lecture Note: 1

Introduction to C

C is a programming language developed at AT & T‘s Bell Laboratories of USA

in 1972. It was designed and written by a man named Dennis Ritchie. In the late
seventies C began to replace the more familiar languages of that time like PL/I,
ALGOL, etc

ANSI C standard emerged in the early 1980s, this book was split into two
titles: The original was still called Programming in C, and the title that covered
ANSI C was called Programming in ANSI C. This was done because it took
several years for the compiler vendors to release their ANSI C compilers and for
them to become ubiquitous. It was initially designed for programming UNIX
operating system. Now the software tool as well as the C compiler is written in C.
Major parts of popular operating systems like Windows, UNIX, Linux is still
written in C. This is because even today when it comes to performance (speed of
execution) nothing beats C. Moreover, if one is to extend the operating system to
work with new devices one needs to write device driver programs. These
programs are exclusively written in C. C seems so popular is because it is reliable,
simple and easy to use. often heard today is – “C has been already superceded
by languages like C++, C# and Java.

Program
There is a close analogy between learning English language and learning C
language. The classical method of learning English is to first learn the alphabets
used in the language, then learn to combine these alphabets to form words, which
in turn are combined to form sentences and sentences are combined to form
paragraphs. Learning C is similar and easier. Instead of straight-away learning how
to write programs, we must first know what alphabets, numbers and special
symbols are used in C, then how using them constants, variables and keywords are
constructed, and finally how are these combined to form an instruction. A group
of instructions would be combined later on to form a program. So

a computer program is just a collection of the instructions necessary to solve a

specific problem. The basic operations of a computer system form what is known
as the computer‘s instruction set. And the approach or method that is used to solve
the problem is known as an algorithm.

So for as programming language concern these are of two types.

1) Low level language

2) High level language

Low level language:

 Low level languages are machine level and assembly level language. In
machine level language computer only understand digital numbers i.e. in the form
of 0 and 1. So, instruction given to the computer is in the form binary digit, which
is difficult to implement instruction in binary code. This type of program is not
portable, difficult to maintain and also error prone. The assembly language is on
other hand modified version of machine level language. Where instructions are
given in English like word as ADD, SUM, MOV etc. It is easy to write and
understand but not understand by the machine. So the translator used here is
assembler to translate into machine level. Although language is bit easier,
programmer has to know low level details related to low level language. In the
assembly level language the data are stored in the computer register, which varies
for different computer. Hence it is not portable.

High level language:

These languages are machine independent, means it is portable. The language in

this category is Pascal, Cobol, Fortran etc. High level languages are understood by
the machine. So it need to translate by the translator into machine level. A
translator is software which is used to translate high level language as well as low
level language in to machine level language.

Three types of translator are there:

Compiler

Interpreter

Assembler

Compiler and interpreter are used to convert the high level language into machine
level language. The program written in high level language is known as source
program and the corresponding machine level language program is called as object
program. Both compiler and interpreter perform the same task but there working is
different. Compiler read the program at-a-time and searches the error and lists
them. If the program is error free then it is converted into object program. When
program size is large then compiler is preferred. Whereas interpreter read only one
line of the source code and convert it to object code. If it check error, statement by
statement and hence of take more time.
Integrated Development Environments (IDE)

The process of editing, compiling, running, and debugging programs is often

managed by a single integrated application known as an Integrated Development
Environment, or IDE for short. An IDE is a windows-based program that allows us
to easily manage large software programs, edit files in windows, and compile, link,
run, and debug programs.

On Mac OS X, CodeWarrior and Xcode are two IDEs that are used by many
programmers. Under Windows, Microsoft Visual Studio is a good example of a
popular IDE. Kylix is a popular IDE for developing applications under Linux.
Most IDEs also support program development in several different programming
languages in addition to C, such as C# and C++.
 Lecture Note: 2

Structure of C Language program

1) Comment line

2) Preprocessor directive

3) Global variable declaration

4) main function( )

Local variables;

Statements;

User defined function

Comment line

It indicates the purpose of the program. It is represented as

/*……………………………..*/

Comment line is used for increasing the readability of the program. It is useful in
explaining the program and generally used for documentation. It is enclosed within
the decimeters. Comment line can be single or multiple line but should not be
nested. It can be anywhere in the program except inside string constant & character
constant.

Preprocessor Directive:
#include<stdio.h> tells the compiler to include information about the standard
input/output library. It is also used in symbolic constant such as #define PI
3.14(value). The stdio.h (standard input output header file) contains definition
&declaration of system defined function such as printf( ), scanf( ), pow( ) etc.
Generally printf() function used to display and scanf() function used to read value

Global Declaration:

This is the section where variable are declared globally so that it can be access by
all the functions used in the program. And it is generally declared outside the
function :

main()

It is the user defined function and every function has one main() function from
where actually program is started and it is encloses within the pair of curly braces.

The main( ) function can be anywhere in the program but in general practice it is
placed in the first position.

Syntax :

main()

……..

……..

……..

The main( ) function return value when it declared by data type as

int main( )

return 0

13
}

The main function does not return any value when void (means null/empty) as

void main(void ) or void main()

printf (―C language‖);

Output: C language

The program execution start with opening braces and end with closing brace.

And in between the two braces declaration part as well as executable part is
mentioned. And at the end of each line, the semi-colon is given which indicates
statement termination.

/*First c program with return statement*/

#include <stdio.h>

int main (void)

printf ("welcome to c Programming language.\n");

return 0;

Output: welcome to c programming language.

Steps for Compiling and executing the Programs

A compiler is a software program that analyzes a program developed in a particular

computer language and then translates it into a form that is suitable for execution

14
on a particular computer system. Figure below shows the steps that are involved in
entering, compiling, and executing a

computer program developed in the C programming language and the typical Unix
commands that would be entered from the command line.

Step 1: The program that is to be compiled is first typed into a file on the
computer system. There are various conventions that are used for naming files,
typically be any name provided the last two characters are “.c” or file with
extension .c. So, the file name prog1.c might be a valid filename for a C program.
A text editor is usually used to enter the C program into a file. For example, vi is a
popular text editor used on Unix systems. The program that is entered into the file
is known as the source program because it represents the original form of the
program expressed in the C language.

Step 2: After the source program has been entered into a file, then proceed to have
it compiled. The compilation process is initiated by typing a special command on
the system. When this command is entered, the name of the file that contains the
source program must also be specified. For example, under Unix, the command to
initiate program compilation is called cc. If we are using the popular GNU C
compiler, the command we use is gcc.

Typing the line

gcc prog1.c or cc prog1.c

In the first step of the compilation process, the compiler examines each program

statement contained in the source program and checks it to ensure that it conforms
to the syntax and semantics of the language. If any mistakes are discovered by the
compiler during this phase, they are reported to the user and the compilation
process ends right there. The errors then have to be corrected in the source program
(with the use of an editor), and the compilation process must be restarted. Typical
errors reported during this phase of compilation might be due to an expression that
has unbalanced parentheses (syntactic error), or due to the use of a variable that is
not ―defined‖ (semantic error).

15
Step 3: When all the syntactic and semantic errors have been removed from the
program, the compiler then proceeds to take each statement of the program and
translate it into a ―lower‖ form that is equivalent to assembly language program
needed to perform the identical task.

Step 4: After the program has been translated the next step in the compilation
process is to translate the assembly language statements into actual machine
instructions. The assembler takes each assembly language statement and converts it
into a binary format known as object code, which is then written into another file
on the system. This file has the same name as the source file under Unix, with the
last letter an ―o‖ (for object) instead of a ―c‖.

Step 5: After the program has been translated into object code, it is ready to be
linked. This process is once again performed automatically whenever the cc or gcc
command is issued under Unix. The purpose of the linking phase is to get the
program into a final form for execution on the computer.

If the program uses other programs that were previously

processed by the compiler, then during this phase the programs are linked together.
Programs that are used from the system‘s program library are also searched and
linked together with the object program during this phase.

The process of compiling and linking a program is often called building.

The final linked file, which is in an executable object code format, is stored in
another file on the system, ready to be run or executed. Under Unix, this file is
called a.out by default. Under Windows, the executable file usually has the same
name as the source file, with the c extension replaced by an exe extension.

16
 Step 6: To subsequently execute the program, the command a.out has the effect
of loading the program called a.out into the computer‘s memory and initiating its
execution.
When the program is executed, each of the statements of the program is sequentially executed in turn.
If the program requests any data from the user, known as input, the program temporarily suspends its
execution so that the input can be entered. Or, the program might simply wait for an event, such as a
mouse being clicked, to occur. Results that are displayed by the program, known as output, appear in
a window, sometimes called the console. If the program does not produce the desired results, it is
necessary to go back and reanalyze the program‘s logic. This is known as the debugging phase,
during which an attempt is made to remove all the known problems or bugs from the program. To do
this, it will most likely be necessary to make changes to original source program.

17
/* Simple program to add two numbers ................................ */

18
 #include <stdio.h>

int main (void)

int v1, v2, sum; //v1,v2,sum are variables and int is data type declared

v1 = 150;

v2 = 25;

sum = v1 + v2;

printf ("The sum of %i and %i is= %i\n", v1, v2, sum);

return 0;

Output:

The sum of 150 and 25 is=175

Lecture Note: 3

Character set

A character denotes any alphabet, digit or special symbol used to represent

information. Valid alphabets, numbers and special symbols allowed in C are

19
The alphabets, numbers and special symbols when properly combined form
constants, variables and keywords.

Identifiers

Identifiers are user defined word used to name of entities like variables, arrays,
functions, structures etc. Rules for naming identifiers are:
1) name should only consists of alphabets (both upper and lower case), digits
and underscore (_) sign.
2) first characters should be alphabet or underscore
3) name should not be a keyword
4) since C is a case sensitive, the upper case and lower case considered
differently, for example code, Code, CODE etc. are different identifiers.
5) identifiers are generally given in some meaningful name such as value,
net_salary, age, data etc. An identifier name may be long, some implementation
recognizes only first eight characters, most recognize 31 characters. ANSI
standard compiler recognize 31 characters. Some invalid identifiers are 5cb, int,
res#, avg no etc.

Keyword

20
 There are certain words reserved for doing specific task, these words
are known as reserved word or keywords. These words are predefined and always
written in lower case or small letter. These keywords cann‘t be used as a variable
name as it assigned with fixed meaning. Some examples are int, short, signed,
unsigned, default, volatile, float, long, double, break, continue, typedef, static,
do, for, union, return, while, do, extern, register, enum, case, goto, struct,
char, auto, const etc.

data types

Data types refer to an extensive system used for declaring variables or functions of
different types before its use. The type of a variable determines how much space it
occupies in storage and how the bit pattern stored is interpreted. The value of a
variable can be changed any time.

C has the following 4 types of data types

basic built-in data types: int, float, double, char

Enumeration data type: enum

Derived data type: pointer, array, structure, union

Void data type: void

A variable declared to be of type int can be used to contain integral values

only—that is, values that do not contain decimal places. A variable declared to be
of type float can be used for storing floating- point numbers (values containing
decimal places). The double type is the same as type float, only with roughly twice
the precision. The char data type can be used to store a single character, such as the
letter a, the digit character 6, or a semicolon similarly A variable declared char can
only store character type value.

There are two types of type qualifier in c

Size qualifier: short, long

Sign qualifier: signed, unsigned

21
 When the qualifier unsigned is used the number is always positive, and when
signed is used number may be positive or negative. If the sign qualifier is not
mentioned, then by default sign qualifier is assumed. The range of values for
signed data types is less than that of unsigned data type. Because in signed type,
the left most bit is used to represent sign, while in unsigned type this bit is also
used to represent the value. The size and range of the different data types on a 16
bit machine is given below:

Basic data type Data type with type Size Range

qualifier (byte)
char char or signed char 1 -128 to 127
Unsigned char 1 0 to 255
int int or signed int 2 -32768 to 32767
unsigned int 2 0 to 65535
short int or signed short int 1 -128 to 127
unsigned short int 1 0 to 255
long int or signed long int 4 -2147483648 to 2147483647
unsigned long int 4 0 to 4294967295
float float 4 -3.4E-38 to 3.4E+38
double double 8 1.7E-308 to 1.7E+308
Long double 10 3.4E-4932 to 1.1E+4932

22
 Lecture Note: 4

Constants

Constant is a any value that cannot be changed during program execution. In C,

any number, single character, or character string is known as a constant. A constant
is an entity that doesn‘t change whereas a variable is an entity that may change.
For example, the number 50 represents a constant integer value. The character
string "Programming in C is fun.\n" is an example of a constant character string. C
constants can be divided into two major categories:
Primary Constants
Secondary Constants

These constants are further categorized as

Numeric constant
Character constant
String constant

23
Numeric constant: Numeric constant consists of digits. It required minimum size
of 2 bytes and max 4 bytes. It may be positive or negative but by default sign is
always positive. No comma or space is allowed within the numeric constant and it
must have at least 1 digit. The allowable range for integer constants is -32768 to
32767. Truly speaking the range of an Integer constant depends upon the compiler.
For a 16-bit compiler like Turbo C or Turbo C++ the range is –32768 to 32767.
For a 32-bit compiler the range would be even greater. Mean by a 16-bit or a 32-
bit compiler, what range of an Integer constant has to do with the type of compiler.

It is categorized a integer constant and real constant. An integer constants are

whole number which have no decimal point. Types of integer constants are:
Decimal constant: 0 ------ 9(base 10)
Octal constant: 0 ------ 7(base 8)
Hexa decimal constant: 0----9, A ----- F(base 16)

In decimal constant first digit should not be zero unlike octal constant first digit
must be zero(as 076, 0127) and in hexadecimal constant first two digit should be
0x/ 0X (such as 0x24, 0x87A). By default type of integer constant is integer but if
the value of integer constant is exceeds range then value represented by integer
type is taken to be unsigned integer or long integer. It can also be explicitly
mention integer and unsigned integer type by suffix l/L and u/U.

Real constant is also called floating point constant. To construct real constant we
must follow the rule of ,
-real constant must have at least one digit.
-It must have a decimal point.
-It could be either positive or negative.
-Default sign is positive.
-No commas or blanks are allowed within a real constant. Ex.: +325.34
426.0
-32.76

To express small/large real constant exponent(scientific) form is used where

number is written in mantissa and exponent form separated by e/E. Exponent can
be positive or negative integer but mantissa can be real/integer type, for example
3.6*105=3.6e+5. By default type of floating point constant is double, it can also be
explicitly defined it by suffix of f/F.

Character constant

24
 Character constant represented as a single character enclosed within a single
quote. These can be single digit, single special symbol or white spaces such as
‗9‘,‘c‘,‘$‘, ‗ ‘ etc. Every character constant has a unique integer like value in
machine‘s character code as if machine using ASCII (American standard code for
information interchange). Some numeric value associated with each upper and
lower case alphabets and decimal integers are as:

A ------------ Z ASCII value (65-90)

a ------------ z ASCII value (97-122)

0-------------9 ASCII value (48-59)

; ASCII value (59)

String constant

Set of characters are called string and when sequence of characters are
enclosed within a double quote (it may be combination of all kind of symbols) is a
string constant. String constant has zero, one or more than one character and at the
end of the string null character(\0) is automatically placed by compiler. Some
examples are ―,sarathina‖ , ―908‖, ―3‖,‖ ‖, ―A‖ etc. In C although same characters
are enclosed within single and double quotes it represents different meaning such
as ―A‖ and ‗A‘ are different because first one is string attached with null character
at the end but second one is character constant with its corresponding ASCII value
is 65.

Symbolic constant
Symbolic constant is a name that substitute for a sequence of characters and,
characters may be numeric, character or string constant. These constant are
generally defined at the beginning of the program as

#define name value , here name generally written in

upper case for example

25
 #define MAX 10

#define CH ‗b‘

#define NAME ―sony‖

Variables

Variable is a data name which is used to store some data value or symbolic names
for storing program
computations and results. The value of the variable can be change during the
execution. The rule for naming the variables is same as the naming identifier.
Before used in the program it must be declared. Declaration of variables specify its
name, data types and range of the value that variables can store depends upon its
data types.

Syntax:

int a;

char c;

float f;

Variable initialization

When we assign any initial value to variable during the declaration, is called
initialization of variables. When variable is declared but contain undefined value
then it is called garbage value. The variable is initialized with the assignment
operator such as

Data type variable name=constant;

Example: int a=20;

Or int a;

a=20;

26
statements

Lecture Note: 5

Expressions

An expression is a combination of variables, constants, operators and function call.

It can be arithmetic, logical and relational for example:-

int z= x+y // arithmatic expression

a>b //relational

a==b // logical
func(a, b) // function call
Expressions consisting entirely of constant values are called constant expressions.
So, the expression
121 + 17 - 110
is a constant expression because each of the terms of the expression is a constant
value. But if i were declared to be an integer variable, the expression
180 + 2 – j
would not represent a constant expression.

Operator

This is a symbol use to perform some operation on variables, operands or with the
constant. Some operator required 2 operand to perform operation or Some
required single operation.

Several operators are there those are, arithmetic operator, assignment, increment ,
decrement, logical, conditional, comma, size of , bitwise and others.

1. Arithmatic Operator

This operator used for numeric calculation. These are of either Unary arithmetic
operator, Binary arithmetic operator. Where Unary arithmetic operator required

27
only one operand such as +,-, ++, --,!, tiled. And these operators are addition,
subtraction, multiplication, division. Binary arithmetic operator on other hand
required two operand and its operators are +(addition), -(subtraction),
*(multiplication), /(division), %(modulus). But modulus cannot applied with
floating point operand as well as there are no exponent operator in c.

Unary (+) and Unary (-) is different from addition and subtraction.

When both the operand are integer then it is called integer arithmetic and the result
is always integer. When both the operand are floating point then it is called floating
arithmetic and when operand is of integer and floating point then it is called mix
type or mixed mode arithmetic . And the result is in float type.

2. Assignment Operator

A value can be stored in a variable with the use of assignment operator. The
assignment operator(=) is used in assignment statement and assignment expression.
Operand on the left hand side should be variable and the operand on the right hand
side should be variable or constant or any expression. When variable on the left
hand side is occur on the right hand side then we can avoid by writing the
compound statement. For example,

int x= y;

int Sum=x+y+z;

3. Increment and Decrement

The Unary operator ++, --, is used as increment and decrement which acts upon
single operand. Increment operator increases the value of variable by one
.Similarly decrement operator decrease the value of the variable by one. And these
operator can only used with the variable, but cann't use with expression and
constant as ++6 or ++(x+y+z).

28
It again categories into prefix post fix . In the prefix the value of the variable is
incremented 1st, then the new value is used, where as in postfix the operator is
written after the operand(such as m++,m--).

EXAMPLE

let y=12;

z= ++y;

y= y+1;

z= y;

Similarly in the postfix increment and decrement operator is used in the operation .
And then increment and decrement is perform.

EXAMPLE

let x= 5;

y= x++;

y=x;

x= x+1;

4. Relational Operator

It is use to compared value of two expressions depending on their relation.

Expression that contain relational operator is called relational expression.

Here the value is assign according to true or false value.

a.(a>=b) || (b>20)

b.(b>a) && (e>b)

c. 0(b!=7)

5. Conditional Operator

29
It sometimes called as ternary operator. Since it required three expressions as
operand and it is represented as (? , :).

SYNTAX

exp1 ? exp2 :exp3

Here exp1 is first evaluated. It is true then value return will be exp2 . If false then
exp3.

EXAMPLE

void main()

int a=10, b=2

int s= (a>b) ? a:b;

printf(―value is:%d‖);

Output:

Value is:10

6. Comma Operator

Comma operator is use to permit different expression to be appear in a situation

where only one expression would be used. All the expression are separator by
comma and are evaluated from left to right.

EXAMPLE

int i, j, k, l;

for(i=1,j=2;i<=5;j<=10;i++;j++)

30
 7. Sizeof Operator

Size of operator is a Unary operator, which gives size of operand in terms of byte
that occupied in the memory. An operand may be variable, constant or data type
qualifier.

Generally it is used make portable program(program that can be run on different

machine) . It determines the length of entities, arrays and structures when their size
are not known to the programmer. It is also use to allocate size of memory
dynamically during execution of the program.

EXAMPLE

main( )

int sum;

float f;

printf( "%d%d" ,size of(f), size of (sum) );

printf("%d%d", size of(235 L), size of(A));

31
 Lecture Note: 6

8. Bitwise Operator

Bitwise operator permit programmer to access and manipulate of data at bit level.
Various bitwise operator enlisted are

one's complement (~)

bitwise AND (&)

bitwise OR (|)

bitwise XOR (^)

left shift (<<)

right shift (>>)

These operator can operate on integer and character value but not on float and
double. In bitwise operator the function showbits( ) function is used to display the
binary representation of any integer or character value.

In one's complement all 0 changes to 1 and all 1 changes to 0. In the bitwise OR its
value would obtaining by 0 to 2 bits.

As the bitwise OR operator is used to set on a particular bit in a number. Bitwise

AND the logical AND.

It operate on 2operands and operands are compared on bit by bit basic. And hence
both the operands are of same type.

Logical or Boolean Operator

Operator used with one or more operand and return either value zero (for false) or
one (for true). The operand may be constant, variables or expressions. And the
expression that combines two or more expressions is termed as logical expression.
C has three logical operators :

32
 Operator Meaning

&& AND
|| OR
! NOT
Where logical NOT is a unary operator and other two are binary operator. Logical
AND gives result true if both the conditions are true, otherwise result is false. And
logial OR gives result false if both the condition false, otherwise result is true.

Precedence and associativity of operators

Operators Description Precedence level Associativity

() function call 1 left to right

[] array subscript

 arrow operator
. dot operator

+ unary plus 2 right to left

- unary minus
++ increment
-- decrement
! logical not
~ 1‘s complement
* indirection
& address
(data type) type cast
sizeof size in byte
* multiplication 3 left to right
/ division
% modulus

+ addition 4 left to right

33
 - subtraction

<< left shift 5 left to right

>> right shift

<= less than equal to 6 left to right

>= greater than equal to
< less than
> greater than

== equal to 7 left to right

!= not equal to

& bitwise AND 8 left to right

^ bitwise XOR 9 left to right

| bitwise OR 10 left to right

&& logical AND 11
|| logical OR 12
?: conditional operator 13

=, *=, /=, %= assignment operator 14 right to left

&=, ^=, <<=
>>=

, comma operator 15

Lecture Note: 7

Control Statement

Generally C program statement is executed in a order in which they appear

in the program. But sometimes we use decision making condition for execution
only a part of program, that is called control statement. Control statement defined
34
how the control is transferred from one part to the other part of the program. There
are several control statement like if...else, switch, while, do. ..while, for loop,
break, continue, goto etc.

Loops in C

Loop:-it is a block of statement that performs set of instructions. In loops

Repeating particular portion of the program either a specified number of time or

until a particular no of condition is being satisfied.

There are three types of loops in c

1. While loop

2. do while loop

3. for loop

While loop

Syntax:-

while(condition)

Statement 1;

Statement 2;

Or while(test condition)
Statement;

35
The test condition may be any expression .when we want to do something a fixed
no of times but not known about the number of iteration, in a program then while
loop is used.

Here first condition is checked if, it is true body of the loop is executed else, If
condition is false control will be come out of loop.

Example:-

/* wap to print 5 times welcome to C‖ */

#include<stdio.h>

void main()

int p=1;

While(p<=5)

printf(―Welcome to C\n‖);

P=p+1;

Output: Welcome to C

Welcome to C

Welcome to C

Welcome to C

Welcome to C

36
 So as long as condition remains true statements within the body of while loop will
get executed repeatedly.

do while loop

This (do while loop) statement is also used for looping. The body of this loop may
contain single statement or block of statement. The syntax for writing this
statement is:

Syntax:-

Do

Statement;

while(condition);

Example:-

#include<stdio.h>

void main()

int X=4;

do

Printf(―%d‖,X);

X=X+1;

37
 }whie(X<=10);

Printf(― ‖);

Output: 4 5 6 7 8 9 10

Here firstly statement inside body is executed then condition is checked. If the
condition is true again body of loop is executed and this process continue until the
condition becomes false. Unlike while loop semicolon is placed at the end of
while.

There is minor difference between while and do while loop, while loop test the
condition before executing any of the statement of loop. Whereas do while loop
test condition after having executed the statement at least one within the loop.

If initial condition is false while loop would not executed it‘s statement on other
hand do while loop executed it‘s statement at least once even If condition fails for
first time. It means do while loop always executes at least once. Notes:

Do while loop used rarely when we want to execute a loop at least once.

Lecture Note: 8

for loop

In a program, for loop is generally used when number of iteration are known in
advance. The body of the loop can be single statement or multiple statements. Its
syntax for writing is:

Syntax:-

38
 for(exp1;exp2;exp3)

Statement;

Or

for(initialized counter; test counter; update counter)

Statement;

Here exp1 is an initialization expression, exp2 is test expression or condition and

exp3 is an update expression. Expression 1 is executed only once when loop
started and used to initialize the loop variables. Condition expression generally
uses relational and logical operators. And updation part executed only when after
body of the loop is executed.

Example:-

void main()

int i;

for(i=1;i<10;i++)

39
Printf(― %d ‖, i);

Output:-1 2 3 4 5 6 7 8 9

Nesting of loop

When a loop written inside the body of another loop then, it is known as nesting of
loop. Any type of loop can be nested in any type such as while, do while, for. For
example nesting of for loop can be represented as :

void main()

int i,j;

for(i=0;i<2;i++)

for(j=0;j<5; j++)

printf(―%d %d‖, i, j);

Output: i=0

j=0 1 2 3 4

i=1

j=0 1 2 3 4

40
Break statement(break)

Sometimes it becomes necessary to come out of the loop even before loop
condition becomes false then break statement is used. Break statement is used
inside loop and switch statements. It cause immediate exit from that loop in which
it appears and it is generally written with condition. It is written with the keyword
as break. When break statement is encountered loop is terminated and control is
transferred to the statement, immediately after loop or situation where we want to
jump out of the loop instantly without waiting to get back to conditional state.

When break is encountered inside any loop, control automatically passes to the
first statement after the loop. This break statement is usually associated with if
statement.

Example :

void main()

int j=0;

for(;j<6;j++)

if(j==4)

break;

Output:

0123

Continue statement (key word continue)

41
Continue statement is used for continuing next iteration of loop after skipping
some statement of loop. When it encountered control automatically passes
through the beginning of the loop. It is usually associated with the if statement. It is
useful when we want to continue the program without executing any part of the
program.

The difference between break and continue is, when the break encountered loop is
terminated and it transfer to the next statement and when continue is encounter
control come back to the beginning position.

In while and do while loop after continue statement control transfer to the test
condition and then loop continue where as in, for loop after continue control
transferred to the updating expression and condition is tested.

Example:-

void main()

int n;

for(n=2; n<=9; n++)

if(n==4)

continue;

printf(―%d‖, n);

Printf(―out of loop‖);

Output: 2 3 5 6 7 8 9 out of loop

42
 Lecture Note: 9

if statement

Statement execute set of command like when condition is true and its syntax is

If (condition)

Statement;

The statement is executed only when condition is true. If the if statement body is
consists of several statement then better to use pair of curly braces. Here in case
condition is false then compiler skip the line within the if block.

void main()

int n;

printf (― enter a number:‖);

scanf(―%d‖,&n);

If (n>10)

Printf(― number is grater‖);

Output:

Enter a number:12

Number is greater

43
if…..else ... Statement

it is bidirectional conditional control statement that contains one condition & two
possible action. Condition may be true or false, where non-zero value regarded as
true & zero value regarded as false. If condition are satisfy true, then a single or
block of statement executed otherwise another single or block of statement is
executed.

Its syntax is:-

if (condition)

Statement1;

Statement2;

else

Statement1;

Statement2;

Else statement cannot be used without if or no multiple else statement are allowed
within one if statement. It means there must be a if statement with in an else
statement.

Example:-

/* To check a number is eve or odd */

44
void main()

int n;

printf (―enter a number:‖);

sacnf (―%d‖, &n);

If (n%2==0)

printf (―even number‖);

else

printf(―odd number‖);

Output: enter a number:121

odd number

Lecture Note: 10

Nesting of if …else

When there are another if else statement in if-block or else-block, then it is called
nesting of if-else statement.

Syntax is :-

if (condition)

45
 If (condition)

Statement1;

else

statement2;

Statement3;

If….else LADDER

In this type of nesting there is an if else statement in every else part except the last
part. If condition is false control pass to block where condition is again checked
with its if statement.

Syntax is :-

if (condition)

Statement1;

else if (condition)

statement2;

else if (condition)

statement3;

else

statement4;

This process continue until there is no if statement in the last block. if one of the
condition is satisfy the condition other nested ―else if‖ would not executed.

46
But it has disadvantage over if else statement that, in if else statement whenever
the condition is true, other condition are not checked. While in this case, all
condition are checked.

Lecture Note: 11

ARRAY

Array is the collection of similar data types or collection of similar entity stored in
contiguous memory location. Array of character is a string. Each data item of an
array is called an element. And each element is unique and located in separated
memory location. Each of elements of an array share a variable but each element
having different index no. known as subscript.

An array can be a single dimensional or multi-dimensional and number of

subscripts determines its dimension. And number of subscript is always starts with
zero. One dimensional array is known as vector and two dimensional arrays are
known as matrix.

ADVANTAGES: array variable can store more than one value at a time where
other variable can store one value at a time.

Example:

int arr[100];

47
 int mark[100];

DECLARATION OF AN ARRAY :

Its syntax is :

Data type array name [size];

int arr[100];

int mark[100];

int a[5]={10,20,30,100,5}

The declaration of an array tells the compiler that, the data type, name of the array,
size of the array and for each element it occupies memory space. Like for int data
type, it occupies 2 bytes for each element and for float it occupies 4 byte for each
element etc. The size of the array operates the number of elements that can be
stored in an array and it may be a int constant or constant int expression.

We can represent individual array as :

int ar[5];

ar[0], ar[1], ar[2], ar[3], ar[4];

Symbolic constant can also be used to specify the size of the array as:

#define SIZE 10;

INITIALIZATION OF AN ARRAY:

After declaration element of local array has garbage value. If it is global or static
array then it will be automatically initialize with zero. An explicitly it can be
initialize that

Data type array name [size] = {value1, value2, value3…}

Example:

in ar[5]={20,60,90, 100,120}

48
Array subscript always start from zero which is known as lower bound and upper
value is known as upper bound and the last subscript value is one less than the size
of array. Subscript can be an expression i.e. integer value. It can be any integer,
integer constant, integer variable, integer expression or return value from
functional call that yield integer value.

So if i & j are not variable then the valid subscript are

ar [i*7],ar[i*i],ar[i++],ar[3];

The array elements are standing in continuous memory locations and the
amount of storage required for hold the element depend in its size & type.

Total size in byte for 1D array is:

Total bytes=size of (data type) * size of array.

Example : if an array declared is:

int [20];

Total byte= 2 * 20 =40 byte.

ACCESSING OF ARRAY ELEMENT:

/*Write a program to input values into an array and display them*/

#include<stdio.h>

int main()

int arr[5],i;

for(i=0;i<5;i++)

printf(―enter a value for arr[%d] \n‖,i);

scanf(―%d‖,&arr[i]);

49
printf(―the array elements are: \n‖);

for (i=0;i<5;i++)

printf(―%d\t‖,arr[i]);

return 0;

OUTPUT:

Enter a value for arr[0] = 12

Enter a value for arr[1] =45

Enter a value for arr[2] =59

Enter a value for arr[3] =98

Enter a value for arr[4] =21

The array elements are 12 45 59 98 21

Example: From the above example value stored in an array are and occupy its
memory addresses 2000, 2002, 2004, 2006, 2008 respectively.

a[0]=12, a[1]=45, a[2]=59, a[3]=98, a[4]=21

ar[0] ar[1] ar[2] ar[3] ar[4]

12 45 59 98 21
2000 2002 2004 2006 2008

Example 2:

50
 /* Write a program to add 10 array elements */

#include<stdio.h>

void main()

int i ;

int arr [10];

int sum=o;

for (i=0; i<=9; i++)

printf (―enter the %d element \n‖, i+1);

scanf (―%d‖, &arr[i]);

for (i=0; i<=9; i++)

sum = sum + a[i];

printf (―the sum of 10 array elements is %d‖, sum);

OUTPUT:

Enter a value for arr[0] =5

Enter a value for arr[1] =10

Enter a value for arr[2] =15

Enter a value for arr[3] =20

51
Enter a value for arr[4] =25

Enter a value for arr[5] =30

Enter a value for arr[6] =35

Enter a value for arr[7] =40

Enter a value for arr[8] =45

Enter a value for arr[9] =50

Sum = 275

while initializing a single dimensional array, it is optional to specify the size of

array. If the size is omitted during initialization then the compiler assumes the size
of array equal to the number of initializers.

For example:-

int marks[]={99,78,50,45,67,89};

If during the initialization of the number the initializers is less then size of array,
then all the remaining elements of array are assigned value zero .

For example:-

int marks[5]={99,78};

Here the size of the array is 5 while there are only two initializers so After this
initialization, the value of the rest elements are automatically occupied by zeros
such as

Marks[0]=99 , Marks[1]=78 , Marks[2]=0, Marks[3]=0, Marks[4]=0

Again if we initialize an array like

int array[100]={0};

Then the all the element of the array will be initialized to zero. If the number of
initializers is more than the size given in brackets then the compiler will show an
error.

52
For example:-

int arr[5]={1,2,3,4,5,6,7,8};//error

we cannot copy all the elements of an array to another array by simply assigning it
to the other array like, by initializing or declaring as

int a[5] ={1,2,3,4,5};

int b[5];

b=a;//not valid

(note:-here we will have to copy all the elements of array one by one, using for
loop.)

Single dimensional arrays and functions

/*program to pass array elements to a function*/

#include<stdio.h>

void main()

int arr[10],i;

printf(―enter the array elements\n‖);

for(i=0;i<10;i++)

scanf(―%d‖,&arr[i]);

check(arr[i]);

53
void check(int num)

if(num%2=0)

printf(‖%d is even \n‖,num);

else

printf(‖%d is odd \n‖,num);

Lecture Note: 12

Two dimensional arrays

Two dimensional array is known as matrix. The array declaration in both the array
i.e.in single dimensional array single subscript is used and in two dimensional
array two subscripts are is used.

Its syntax is

Data-type array name[row][column];

Or we can say 2-d array is a collection of 1-D array placed one below the other.

54
Total no. of elements in 2-D array is calculated as row*column

Example:-

int a[2][3];

Total no of elements=row*column is 2*3 =6

It means the matrix consist of 2 rows and 3 columns

For example:-

20 2 7

8 3 15

Positions of 2-D array elements in an array are as below

00 01 02
10 11 12

a [0][0] a [0][0] a [0][0] a [0][0] a [0][0] a [0][0]

20 2 7 8 3 15

2000 2002 2004 2006 2008

Accessing 2-d array /processing 2-d arrays

For processing 2-d array, we use two nested for loops. The outer for loop
corresponds to the row and the inner for loop corresponds to the column.

For example

int a[4][5];

for reading value:-

55
 for(i=0;i<4;i++)

for(j=0;j<5;j++)

scanf(―%d‖,&a[i][j]);

For displaying value:-

for(i=0;i<4;i++)

for(j=0;j<5;j++)

printf(―%d‖,a[i][j]);

Initialization of 2-d array:

2-D array can be initialized in a way similar to that of 1-D array. for example:-

int mat[4][3]={11,12,13,14,15,16,17,18,19,20,21,22};

These values are assigned to the elements row wise, so the values of
elements after this initialization are

Mat[0][0]=11, Mat[1][0]=14, Mat[2][0]=17 Mat[3][0]=20

Mat[0][1]=12, Mat[1][1]=15, Mat[2][1]=18 Mat[3][1]=21

Mat[0][2]=13, Mat[1][2]=16, Mat[2][2]=19 Mat[3][2]=22

56
While initializing we can group the elements row wise using inner braces.

for example:-

int mat[4][3]={{11,12,13},{14,15,16},{17,18,19},{20,21,22}};

And while initializing , it is necessary to mention the 2nd dimension where 1st
dimension is optional.

int mat[][3];

int mat[2][3];

int mat[][];

int mat[2][]; invalid

If we initialize an array as

int mat[4][3]={{11},{12,13},{14,15,16},{17}};

Then the compiler will assume its all rest value as 0,which are not defined.

Mat[0][0]=11, Mat[1][0]=12, Mat[2][0]=14, Mat[3][0]=17

Mat[0][1]=0, Mat[1][1]=13, Mat[2][1]=15 Mat[3][1]=0

Mat[0][2]=0, Mat[1][2]=0, Mat[2][2]=16, Mat[3][2]=0

In memory map whether it is 1-D or 2-D, elements are stored in one

contiguous manner.

We can also give the size of the 2-D array by using symbolic constant

Such as

#define ROW 2;

57
 #define COLUMN 3;

int mat[ROW][COLUMN];

String

Array of character is called a string. It is always terminated by the NULL

character. String is a one dimensional array of character.

We can initialize the string as

char name[]={‗j‘,‘o‘,‘h‘,‘n‘,‘\o‘};

Here each character occupies 1 byte of memory and last character is always NULL
character. Where ‘\o‘ and 0 (zero) are not same, where ASCII value of ‗\o‘ is 0
and ASCII value of 0 is 48. Array elements of character array are also stored in
contiguous memory allocation.

From the above we can represent as;

J o h N ‗\o‘

The terminating NULL is important because it is only the way that the
function that work with string can know, where string end.

String can also be initialized as;

char name[]=‖John‖;

Here the NULL character is not necessary and the compiler will assume it
automatically.

String constant (string literal)

58
 A string constant is a set of character that enclosed within the double quotes
and is also called a literal. Whenever a string constant is written anywhere in a
program it is stored somewhere in a memory as an array of characters terminated
by a NULL character (‗\o‘).

Example – ―m‖

―Tajmahal‖

―My age is %d and height is %f\n‖

The string constant itself becomes a pointer to the first character in array.

Example-char crr[20]=‖Taj mahal‖;

1000 1001 1002 1003 1004 1005 1006 1007 100 1009
T a j M A H a l \o

It is called base address.

Lecture Note: 13

String library function

There are several string library functions used to manipulate string and the
prototypes for these functions are in header file ―string.h‖. Several string functions
are

strlen()

This function return the length of the string. i.e. the number of characters in the
string excluding the terminating NULL character.

It accepts a single argument which is pointer to the first character of the string.

59
For example-

strlen(―suresh‖);

It return the value 6.

In array version to calculate legnth:-

int str(char str[])

int i=0;

while(str[i]!=‘\o‘)

i++;

return i;

Example:-

#include<stdio.h>

#include<string.h>

void main()

char str[50];

print(‖Enter a string:‖);

60
 gets(str);

printf(―Length of the string is %d\n‖,strlen(str));

Output:

Enter a string: C in Depth

Length of the string is 8

strcmp()

This function is used to compare two strings. If the two string match, strcmp()
return a value 0 otherwise it return a non-zero value. It compare the strings
character by character and the comparison stops when the end of the string is
reached or the corresponding characters in the two string are not same.

strcmp(s1,s2)

return a value:

<0 when s1<s2

=0 when s1=s2

>0 when s1>s2

The exact value returned in case of dissimilar strings is not defined. We only know
that if s1<s2 then a negative value will be returned and if s1>s2 then a positive
value will be returned.

For example:

61
/*String comparison… ............................ */

#include<stdio.h>

#include<string.h>

void main()

char str1[10],str2[10];

printf(―Enter two strings:‖);

gets(str1);

gets(str2);

if(strcmp(str1,str2)==0)

printf(―String are same\n‖);

else

printf(―String are not same\n‖);

strcpy()

62
This function is used to copying one string to another string. The function
strcpy(str1,str2) copies str2 to str1 including the NULL character. Here str2 is the
source string and str1 is the destination string.

The old content of the destination string str1 are lost. The function returns a pointer
to destination string str1.

Example:-

#include<stdio.h>

#include<string.h>

void main()

char str1[10],str2[10];

printf(―Enter a string:‖);

scanf(―%s‖,str2);

strcpy(str1,str2);

printf(―First string:%s\t\tSecond string:%s\n‖,str1,str2);

strcpy(str,‖Delhi‖);

strcpy(str2,‖Bangalore‖);

printf(―First string :%s\t\tSecond string:%s‖,str1,str2);

strcat()

63
This function is used to append a copy of a string at the end of the other string. If
the first string is ―‖Purva‖ and second string is ―Belmont‖ then after using this
function the string becomes ―PusvaBelmont‖. The NULL character from str1 is
moved and str2 is added at the end of str1. The 2nd string str2 remains unaffected.
A pointer to the first string str1 is returned by the function.

Example:-

#include<stdio.h>

#include<string.h>

void main()

char str1[20],str[20];

printf(―Enter two strings:‖);

gets(str1);

gets(str2);

strcat(str1,str2);

printf(―First string:%s\t second string:%s\n‖,str1,str2);

strcat(str1,‖-one‖);

printf(―Now first string is %s\n‖,str1);

Output

Enter two strings: data

Base

64
 First string: database second string: database

` Now first string is: database-one

Lecture Note: 14

FUNCTION

A function is a self contained block of codes or sub programs with a set of

statements that perform some specific task or coherent task when it is called.

It is something like to hiring a person to do some specific task like, every six
months servicing a bike and hand over to it.

Any ‗C‘ program contain at least one function i.e main().

There are basically two types of function those are

1. Library function

2. User defined function

The user defined functions defined by the user according to its requirement

System defined function can‘t be modified, it can only read and can be used.
These function are supplied with every C compiler

Source of these library function are pre complied and only object code get used by
the user by linking to the code by linker

Here in system defined function description:

Function definition : predefined, precompiled, stored in the library

65
 Function declaration : In header file with or function prototype.

Function call : By the programmer

User defined function

Syntax:-

Return type name of function (type 1 arg 1, type2 arg2, type3 arg3)

Return type function name argument list of the above syntax

So when user gets his own function three thing he has to know, these are.

Function declaration

Function definition

Function call

These three things are represented like

int function(int, int, int); /*function declaration*/

main() /* calling function*/

function(arg1,arg2,arg3);

int function(type 1 arg 1,type2 arg2,type3, arg3) /*function definition/*

Local variable declaration;

Statement;

Return value;

66
Function declaration:-
Function declaration is also known as function prototype. It inform the compiler
about three thing, those are name of the function, number and type of argument
received by the function and the type of value returned by the function.

While declaring the name of the argument is optional and the function prototype
always terminated by the semicolon.

Function definition:-

Function definition consists of the whole description and code of the function.

It tells about what function is doing what are its inputs and what are its out put

It consists of two parts function header and function body

Syntax:-

return type function(type 1 arg1, type2 arg2, type3 arg3) /*function header*/

Local variable declaration;

Statement 1;

Statement 2;

Return value

The return type denotes the type of the value that function will return and it is
optional and if it is omitted, it is assumed to be int by default. The body of the
function is the compound statements or block which consists of local variable
declaration statement and optional return statement.

67
The local variable declared inside a function is local to that function only. It can‘t
be used anywhere in the program and its existence is only within this function.

The arguments of the function definition are known as formal arguments.

Function Call

When the function get called by the calling function then that is called, function
call. The compiler execute these functions when the semicolon is followed by the
function name.

Example:-

function(arg1,arg2,arg3);

The argument that are used inside the function call are called actual argument

Ex:-

int S=sum(a, b); //actual arguments

Actual argument

The arguments which are mentioned or used inside the function call is knows as
actual argument and these are the original values and copy of these are actually
sent to the called function

It can be written as constant, expression or any function call like

Function (x);

Function (20, 30);

Function (a*b, c*d);

Function(2,3,sum(a, b));

Formal Arguments

The arguments which are mentioned in function definition are called formal
arguments or dummy arguments.

68
These arguments are used to just hold the copied of the values that are sent by the
calling function through the function call.

These arguments are like other local variables which are created when the function
call starts and destroyed when the function ends.

The basic difference between the formal argument and the actual argument are

1) The formal argument are declared inside the parenthesis where as the
local variable declared at the beginning of the function block.

2). The formal argument are automatically initialized when the copy of actual
arguments are passed while other local variable are assigned values through the
statements.

Order number and type of actual arguments in the function call should be match
with the order number and type of the formal arguments.

Return type

It is used to return value to the calling function. It can be used in two way as

return

Or return(expression);

Ex:- return (a);

return (a*b);

return (a*b+c);

Here the 1st return statement used to terminate the function without returning any
value

Ex:- /*summation of two values*/

int sum (int a1, int a2);

main()

69
 {

int a,b;

printf(―enter two no‖);

scanf(―%d%d‖,&a,&b);

int S=sum(a,b);

printf(―summation is = %d‖,s);

int sum(intx1,int y1)

int z=x1+y1;

Return z;

Advantage of function

By using function large and difficult program can be divided in to sub programs
and solved. When we want to perform some task repeatedly or some code is to be
used more than once at different place in the program, then function avoids this
repeatition or rewritten over and over.

Due to reducing size, modular function it is easy to modify and test

Notes:-

C program is a collection of one or more function.

A function is get called when function is followed by the semicolon.

A function is defined when a function name followed by a pair of curly braces

70
Any function can be called by another function even main() can be called by other
function.

main()
{

function1()

function1()

Statement;

function2;

function 2()

So every function in a program must be called directly or indirectly by the main()

function. A function can be called any number of times.

A function can call itself again and again and this process is called recursion.

A function can be called from other function but a function can‘t be defined in
another function

Lecture Note: 15
Category of Function based on argument and return type

i) Function with no argument & no return value

71
 Function that have no argument and no return value is written as:-

void function(void);

main()

void function()

Statement;

Example:-

void me();

main()

me();

printf(―in main‖);

void me()

printf(―come on‖);

Output: come on

inn main

72
ii) Function with no argument but return value

Syntax:-

int fun(void);

main()

int r;

r=fun();

int fun()

reurn(exp);

Example:-

int sum();

main()

int b=sum();

printf(―entered %d\n, b‖);

int sum()

int a,b,s;

73
 s=a+b;

return s;

Here called function is independent and are initialized. The values aren‘t passed by
the calling function .Here the calling function and called function are
communicated partly with each other.

Lecture Note: 16

iii) function with argument but no return value

Here the function have argument so the calling function send data to the called
function but called function dose n‘t return value.

Syntax:-

void fun (int,int);

main()

int (a,b);

void fun(int x, int y);

Statement;

74
Here the result obtained by the called function.

iv) function with argument and return value

Here the calling function has the argument to pass to the called function and the
called function returned value to the calling function.

Syntax:-

fun(int,int);

main()

int r=fun(a,b);

int fun(intx,inty)

return(exp);

Example:

main()

int fun(int);

int a,num;

printf(―enter value:\n‖);

scanf(―%d‖,&a)

75
 int num=fun(a);

int fun(int x)

++x;

return x;

Call by value and call by reference

There are two way through which we can pass the arguments to the function such
as call by value and call by reference.

1. Call by value

In the call by value copy of the actual argument is passed to the formal argument
and the operation is done on formal argument.

When the function is called by ‗call by value‘ method, it doesn‘t affect content of
the actual argument.

Changes made to formal argument are local to block of called function so when the
control back to calling function the changes made is vanish.

Example:-

main()

int x,y;

change(int,int);

76
 printf(―enter two values:\n‖);

scanf(―%d%d‖,&x,&y);

change(x ,y);

printf(―value of x=%d and y=%d\n‖,x ,y);

change(int a,int b);

int k;

k=a;

a=b;

b=k;

Output: enter two values: 12

23

Value of x=12 and y=23

2. Call by reference

Instead of passing the value of variable, address or reference is passed and the
function operate on address of the variable rather than value.

Here formal argument is alter to the actual argument, it means formal arguments
calls the actual arguments.

Example:-

void main()

77
 {

int a,b;

change(int *,int*);

printf(―enter two values:\n‖);

scanf(―%d%d‖,&a,&b);

change(&a,&b);

printf(―after changing two value of a=%d and b=%d\n:‖a,b);

change(int *a, int *b)

int k;

k=*a;

*a=*b;

*b= k;

printf(―value in this function a=%d and b=%d\n‖,*a,*b);

Output: enter two values: 12

32

Value in this function a=32 and b=12

After changing two value of a=32 and b=12

So here instead of passing value of the variable, directly passing address of the
variables. Formal argument directly access the value and swapping is possible even
after calling a function.

78
 Lecture Note: 17

Local, Global and Static variable

Local variable:-

variables that are defined with in a body of function or block. The local
variables can be used only in that function or block in which they are declared.
Same variables may be used in different functions such as

function()

int a,b;

function 1();

function2 ()

int a=0;

b=20;

Global variable:-

79
the variables that are defined outside of the function is called global variable. All
functions in the program can access and modify global variables. Global variables
are automatically initialized at the time of initialization.

Example:

#include<stdio.h>

void function(void);

void function1(void);

void function2(void);

int a, b=20;

void main()

printf(―inside main a=%d,b=%d \n‖,a,b);

function();

function1();

function2();

function()

Prinf(―inside function a=%d,b=%d\n‖,a,b);

function 1()

80
 prinf(―inside function a=%d,b=%d\n‖,a,b);

function 2()

prinf(―inside function a=%d,b=%d\n‖,a,);

Static variables: static variables are declared by writing the key word static.

-syntax:-

static data type variable name;

static int a;

-the static variables initialized only once and it retain between the function call. If
its variable is not initialized, then it is automatically initialized to zero.

Example:

void fun1(void);

void fun2(void);

void main()

fun1();

fun2();

void fun1()

81
 int a=10, static int b=2;

printf(―a=%d, b=%d‖,a,b);

a++;

b++;

Output:a= 10 b= 2
a=10 b= 3

Recursion

When function calls itself (inside function body) again and again then it is
called as recursive function. In recursion calling function and called function are
same. It is powerful technique of writing complicated algorithm in easiest way.
According to recursion problem is defined in term of itself. Here statement with in
body of the function calls the same function and same times it is called as circular
definition. In other words recursion is the process of defining something in form of
itself.

Syntax:

main ()

rec(); /*function call*/

rec();

rec();

Ex:- /*calculate factorial of a no.using recursion*/

int fact(int);

void main()

82
 {

int num;

printf(―enter a number‖);

scanf(―%d‖,&num);

f=fact(num);

printf(―factorial is =%d\n‖f);

fact (int num)

If (num==0||num==1)

return 1;

else

return(num*fact(num-1));

Lecture Note: 18

Monolithic Programming

The program which contains a single function for the large program is called
monolithic program. In monolithic program not divided the program, it is huge
long pieces of code that jump back and forth doing all the tasks like single thread
of execution, the program requires. Problem arise in monolithic program is that,
when the program size increases it leads inconvenience and difficult to maintain

83
such as testing, debugging etc. Many disadvantages of monolithic programming
are:

1. Difficult to check error on large programs size.

2. Difficult to maintain because of huge size.

3. Code can be specific to a particular problem. i.e. it cannot be reused.

Many early languages (FORTRAN, COBOL, BASIC, C) required one huge

workspace with labelled areas that may does specific tasks but are not isolated.

Modular Programming

The process of subdividing a computer program into separate sub-programs such

as functions and subroutines is called Modular programming. Modular
programming sometimes also called as structured programming. It
enables multiple programmers to divide up the large program and debug
pieces of program independently and tested.
. Then the linker will link all these modules to form the complete program. This
principle dividing software up into parts, or modules, where a module can be
changed, replaced, or removed, with minimal effect on the other software it works
with. Segmenting the program into modules clearly defined functions, it can
determine the source of program errors more easily. Breaking down program
functions into modules, where each of which accomplishes one function and
contains all the source code and variables needed to accomplish that function.
Modular program is the solution to the problem of very large program that are
difficult to debug, test and maintain. A program module may be rewritten while its
inputs and outputs remain the same. The person making a change may only
understand a small portion of the original program.

Object-oriented programming (OOP) is compatible with the modular programming

concept to a large extent.
. , Less code has to be written that makes shorter.

84
  A single procedure can be developed for reuse, eliminating the need to
retype the code many times.
 Programs can be designed more easily because a small team deals with only
a small part of the entire code.
 Modular programming allows many programmers to collaborate on the same
application.
 The code is stored across multiple files.
 Code is short, simple and easy to understand and modify, make simple to
figure out how the program is operate and reduce likely hood of bugs.
 Errors can easily be identified, as they are localized to a subroutine or
function or isolated to specific module.
 The same code can be reused in many applications.
 The scoping of variables and functions can easily be controlled.

Disadvantages
However it may takes longer to develop the program using this technique.

Storage Classes

Storage class in c language is a specifier which tells the compiler where and how to
store variables, its initial value and scope of the variables in a program. Or
attributes of variable is known as storage class or in compiler point of view a
variable identify some physical location within a computer where its string of bits
value can be stored is known as storage class.

The kind of location in the computer, where value can be stored is either in the
memory or in the register. There are various storage class which determined, in
which of the two location value would be stored.

Syntax of declaring storage classes is:-

storageclass datatype variable name;

There are four types of storage classes and all are keywords:-

1) Automatic (auto)

85
2) Register (register)

3) Static (static)

4) External (extern)

Examples:-

auto float x; or float x;

extern int x;

register char c;

static int y;

Compiler assume different storage class based on:-

1) Storage class:- tells us about storage place(where variable would be stored).

2) Intial value :-what would be the initial value of the variable.

If initial value not assigned, then what value taken by uninitialized variable.

3) Scope of the variable:-what would be the value of the variable of the program.

4) Life time :- It is the time between the creation and distribution of a variable
or how long would variable exists.

1. Automatic storage class

The keyword used to declare automatic storage class is auto.

Its features:-

Storage-memory location

Default initial value:-unpredictable value or garbage value.

86
Scope:-local to the block or function in which variable is defined.

Life time:-Till the control remains within function or block in which it is defined.
It terminates when function is released.

The variable without any storage class specifier is called automatic variable.

Example:-

main( )

auto int i;

printf(―i=‖,i);

Lecture Note: 19

2. Register storage class

The keyword used to declare this storage class is register.

The features are:-

Storage:-CPU register.

Default initial value :-garbage value

Scope :-local to the function or block in which it is defined.

Life time :-till controls remains within function or blocks in which it is defined.

Register variable don‘t have memory address so we can‘t apply address operator
on it. CPU register generally of 16 bits or 2 bytes. So we can apply storage classes
only for integers, characters, pointer type.

87
Variable stored in register storage class always access faster than,which is always
stored in the memory. But to store all variable in the CPU register is not possible
because of limitation of the register pair.

And when variable is used at many places like loop counter, then it is better to
declare it as register class.

Example:-

main( )

register int i;

for(i=1;i<=12;i++)

printf(―%d‖,i);

3 Static storage class

The keyword used to declare static storage class is static.

Its feature are:-

Storage:-memory location

Default initial value:- zero

Scope :- local to the block or function in which it is defined.

Life time:- value of the variable persist or remain between different function call.

Example:-

main( )

88
{

reduce( );

reduce( );

reduce ( );

reduce( )

static int x=10;

printf(―%d‖,x);

x++;

Output:-10,11,12

External storage classes

The keyword used for this class is extern.

Features are:-

Storage:- memory area

Default initial value:-zero

Scope :- global

Life time:-as long as program execution remains it retains.

89
Declaration does not create variables, only it refer that already been created at
somewhere else. So, memory is not allocated at a time of declaration and the
external variables are declared at outside of all the function.

Example:-

int i,j;

void main( )

printf( ―i=%d‖,i );

receive( );

receive ( );

reduce( );

reduce( );

receive( )

i=i+2;

printf(―on increase i=%d‖,i);

reduce( )

i=i-1;

printf(―on reduce i=%d‖,i);

90
 Output:-i=0,2,4,3,2.

When there is large program i.e divided into several files, then external variable
should be preferred. External variable extend the scope of variable.

Lecture Note: 20

POINTER

A pointer is a variable that store memory address or that contains address of

another variable where addresses are the location number always contains whole
number. So, pointer contain always the whole number. It is called pointer because
it points to a particular location in memory by storing address of that location.

Syntax-

Data type *pointer name;

Here * before pointer indicate the compiler that variable declared as a pointer.

e.g.

int *p1; //pointer to integer type

float *p2; //pointer to float type

char *p3; //pointer to character type

When pointer declared, it contains garbage value i.e. it may point any value in the
memory.

91
Two operators are used in the pointer i.e. address operator(&) and indirection
operator or dereference operator (*).

Indirection operator gives the values stored at a particular address.

Address operator cannot be used in any constant or any expression.

Example:

void main()

int i=105;

int *p;

p=&i;

printf(―value of i=%d‖,*p);

printf(―value of i=%d‖,*/&i);

printf(―address of i=%d‖,&i);

printf(―address of i=%d‖,p);

printf(―address of p=%u‖,&p);

Pointer Expression

Pointer assignment

int i=10;

int *p=&i;//value assigning to the pointer

92
Here declaration tells the compiler that P will be used to store the address of
integer value or in other word P is a pointer to an integer and *p reads the value at
the address contain in p.

P++;

printf(―value of p=%d‖);

We can assign value of 1 pointer variable to other when their base type and data
type is same or both the pointer points to the same variable as in the array.

Int *p1,*p2;

P1=&a[1];

P2=&a[3];

We can assign constant 0 to a pointer of any type for that symbolic constant
‗NULL‘ is used such as

*p=NULL;

It means pointer doesn‘t point to any valid memory location.

Pointer Arithmetic

Pointer arithmetic is different from ordinary arithmetic and it is perform relative to

the data type(base type of a pointer).

Example:-

If integer pointer contain address of 2000 on incrementing we get address of 2002

instead of 2001, because, size of the integer is of 2 bytes.

Note:-

When we move a pointer, somewhere else in memory by incrementing or

decrement or adding or subtracting integer, it is not necessary that, pointer still
pointer to a variable of same data, because, memory allocation to the variable are
done by the compiler.

93
 But in case of array it is possible, since there data are stored in a consecutive
manner.

Ex:-

void main( )

static int a[ ]={20,30,105,82,97,72,66,102};

int *p,*p1;

P=&a[1];

P1=&a[6];

printf(―%d‖,*p1-*p);

printf(―%d‖,p1-p);

Arithmetic operation never perform on pointer are:

addition, multiplication and division of two pointer.

multiplication between the pointer by any number.

division of pointer by any number

-add of float or double value to the pointer.

Operation performed in pointer are:-

/* Addition of a number through pointer */

Example

int i=100;

int *p;

94
p=&i;

p=p+2;

p=p+3;

p=p+9;

ii /* Subtraction of a number from a pointer‘*/

Ex:-

int i=22;

*p1=&a;

p1=p1-10;

p1=p1-2;

iii- Subtraction of one pointer to another is possible when pointer variable point to
an element of same type such as an array.

Ex:-

in tar[ ]={2,3,4,5,6,7};

int *ptr1,*ptr1;

ptr1=&a[3]; //2000+4

ptr2=&a[6]; //2000+6

Lecture Note: 21

95
Precedence of dereference (*) Operator and increment operator and
decrement operator

The precedence level of difference operator increment or decrement operator

is same and their associatively from right to left.

Example :-

int x=25;

int *p=&x;

Let us calculate int y=*p++;

Equivalent to *(p++)

Since the operator associate from right to left, increment operator will applied to
the pointer p.

i) int y=*p++; equivalent to *(p++)

p =p++ or p=p+1

ii) *++p;→*(++p)→p=p+1

y=*p

iii) int y=++*p

equivalent to ++(*p)

p=p+1 then *p

iv) y=(*p)++→equivalent to *p++

y=*p then

P=p+1 ;

Since it is postfix increment the value of p.

Pointer Comparison

96
Pointer variable can be compared when both variable, object of same data type
and it is useful when both pointers variable points to element of same array.

Moreover pointer variable are compared with zero which is usually expressed as
null, so several operators are used for comparison like the relational operator.

==,!=,<=,<,>,>=, can be used with pointer. Equal and not equal operators used to
compare two pointer should finding whether they contain same address or not and
they will equal only if are null or contains address of same variable.

Ex:-

void main()

static int arr[]={20,25,15,27,105,96}

int *x,*y;

x=&a[5];

y=&(a+5);

if(x==y)

printf(―same‖);

else

printf(―not‖);

Lecture Note: 22

97
Pointer to pointer

Addition of pointer variable stored in some other variable is called pointer to

pointer variable.

Or

Pointer within another pointer is called pointer to pointer.

Syntax:-

Data type **p;

int x=22;

int *p=&x;

int **p1=&p;

printf(―value of x=%d‖,x);

printf(―value of x=%d‖,*p);

printf(―value of x=%d‖,*&x);

printf(―value of x=%d‖,**p1);

printf(―value of p=%u‖,&p);

printf(―address of p=%u‖,p1);

printf(―address of x=%u‖,p);

printf(―address of p1=%u‖,&p1);

printf(―value of p=%u‖,p);

printf(―value of p=%u‖,&x);

P 2000

X 1000

p1 22

96
 3000

Pointer vs array

Example :-

void main()

static char arr[]=‖Rama‖;

char*p=‖Rama‖;

printf(―%s%s‖, arr, p);

In the above example, at the first time printf( ), print the same value array and
pointer.

Here array arr, as pointer to character and p act as a pointer to array of

character . When we are trying to increase the value of arr it would give the error
because its known to compiler about an array and its base address which is always
printed to base address is known as constant pointer and the base address of array
which is not allowed by the compiler.

printf(―size of (p)‖,size of (ar));

size of (p) 2/4 bytes

size of(ar) 5 byes

97
Sructure

It is the collection of dissimilar data types or heterogenous data types grouped

together. It means the data types may or may not be of same type.

Structure declaration-

struct tagname

Data type member1;

Data type member2;

Data type member3;

………

………

Data type member n;

};

OR

struct

Data type member1;

Data type member2;

98
Data type member3;

………

………

Data type member n;

};

OR

struct tagname

struct element 1;

struct element 2;

struct element 3;

………

………

struct element n;

};

Structure variable declaration;

struct student

int age;

char name[20];

char branch[20];

99
}; struct student s;

Initialization of structure variable-

Like primary variables structure variables can also be initialized when they are
declared. Structure templates can be defined locally or globally. If it is local it can
be used within that function. If it is global it can be used by all other functions of
the program.

We cant initialize structure members while defining the structure

struct student

int age=20;

char name[20]=‖sona‖;

}s1;

The above is invalid.

A structure can be initialized as

struct student

int age,roll;

char name[20];

} struct student s1={16,101,‖sona‖};

struct student s2={17,102,‖rupa‖};

If initialiser is less than no.of structure variable, automatically rest values are taken
as zero.

100
Accessing structure elements-

Dot operator is used to access the structure elements. Its associativety is from left
to right.

structure variable ;

s1.name[];

s1.roll;

s1.age;

Elements of structure are stored in contiguous memory locations. Value of

structure variable can be assigned to another structure variable of same type using
assignment operator.

Example:

#include<stdio.h>

#include<conio.h>

void main()

int roll, age;

char branch;

} s1,s2;

printf(―\n enter roll, age, branch=‖);

scanf(―%d %d %c‖, &s1.roll, &s1.age, &s1.branch);

s2.roll=s1.roll;

printf(― students details=\n‖);

printf(―%d %d %c‖, s1.roll, s1.age, s1.branch);

printf(―%d‖, s2.roll);

101
}

Unary, relational, arithmetic, bitwise operators are not allowed within structure
variables.

Lecture Note:24

Size of structure-

Size of structure can be found out using sizeof() operator with structure variable
name or tag name with keyword.

sizeof(struct student); or

sizeof(s1);

sizeof(s2);

Size of structure is different in different machines. So size of whole structure may

not be equal to sum of size of its members.

Array of structures

When database of any element is used in huge amount, we prefer Array of

structures.

Example: suppose we want to maintain data base of 200 students, Array of

structures is used.

#include<stdio.h>

#include<string.h>

struct student

102
char name[30];

char branch[25];

int roll;

};

void main()

struct student s[200];

int i;

s[i].roll=i+1;

printf("\nEnter information of students:");

for(i=0;i<200;i++)

printf("\nEnter the roll no:%d\n",s[i].roll);

printf("\nEnter the name:");

scanf("%s",s[i].name);

printf("\nEnter the branch:");

scanf("%s",s[i].branch);

printf("\n");

printf("\nDisplaying information of students:\n\n");

for(i=0;i<200;i++)

printf("\n\nInformation for roll no%d:\n",i+1);

103
printf("\nName:");

puts(s[i].name);

printf("\nBranch:");

puts(s[i].branch);

In Array of structures each element of array is of structure type as in above

example.

Array within structures

struct student

char name[30];

int roll,age,marks[5];

}; struct student s[200];

We can also initialize using same syntax as in array.

Nested structure

When a structure is within another structure, it is called Nested structure. A

structure variable can be a member of another structure and it is represented as

struct student

104
{

element 1;

element 2;

………

………

struct student1

member 1;

member 2;

}variable 1;

……….

……….

element n;

}variable 2;

It is possible to define structure outside & declare its variable inside other
structure.

struct date

int date,month;

};

struct student

105
char nm[20];

int roll;

struct date d;

}; struct student s1;

struct student s2,s3;

Nested structure may also be initialized at the time of declaration like in above
example.

struct student s={―name‖,200, {date, month}};

{―ram‖,201, {12,11}};

Nesting of structure within itself is not valid. Nesting of structure can be

extended to any level.

struct time

int hr,min;

};

struct day

int date,month;

struct time t1;

};

struct student

106
{

char nm[20];

struct day d;

}stud1, stud2, stud3;

Lecture Note: 25

Passing structure elements to function

We can pass each element of the structure through function but passing individual
element is difficult when number of structure element increases. To overcome this,
we use to pass the whole structure through function instead of passing individual
element.

#include<stdio.h>

#include<string.h>

void main()

struct student

char name[30];

char branch[25];

int roll;

}struct student s;

printf(―\n enter name=‖);

107
gets(s.name);

printf("\nEnter roll:");

scanf("%d",&s.roll);

printf("\nEnter branch:");

gets(s.branch);

display(name,roll,branch);

display(char name, int roll, char branch)

printf(―\n name=%s,\n roll=%d, \n branch=%s‖, s.name, s.roll. s.branch);

Passing entire structure to function

#include<stdio.h>

#include<string.h>

struct student

char name[30];

int age,roll;

};

display(struct student); //passing entire structure

void main()

108
{

struct student s1={‖sona‖,16,101 };

struct student s2={‖rupa‖,17,102 };

display(s1);

display(s2);

display(struct student s)

printf(―\n name=%s, \n age=%d ,\n roll=%d‖, s.name, s.age, s.roll);

Output: name=sona

roll=16

Lecture Note: 26

UNION

Union is derived data type contains collection of different data type or dissimilar
elements. All definition declaration of union variable and accessing member is
similar to structure, but instead of keyword struct the keyword union is used, the
main difference between union and structure is

109
 Each member of structure occupy the memory location, but in the unions
members share memory. Union is used for saving memory and concept is useful
when it is not necessary to use all members of union at a time.

Where union offers a memory treated as variable of one type on one occasion
where (struct), it read number of different variables stored at different place of
memory.

Syntax of union:

union student

datatype member1;

datatype member2;

};

Like structure variable, union variable can be declared with definition or separately
such as

union union name

Datatype member1;

}var1;

Example:- union student s;

Union members can also be accessed by the dot operator with union variable and if
we have pointer to union then member can be accessed by using (arrow) operator
as with structure.

110
Example:- struct student

struct student

int i;

char ch[10];

};struct student s;

Here datatype/member structure occupy 12 byte of location is memory, where as in

the union side it occupy only 10 byte.

Lecture Note:27

Nested of Union

When one union is inside the another union it is called nested of union.

Example:-

union a

int i;

int age;

};

union b

111
{

char name[10];

union a aa;

}; union b bb;

There can also be union inside structure or structure in union.

Example:-

void main()

struct a

int i;

char ch[20];

};

struct b

int i;

char d[10];

};

union z

struct a a1;

struct b b1;

112
}; union z z1;

z1.b1.j=20;

z1.a1.i=10;

z1.a1.ch[10]= ― i―;

z1.b1.d[0]=‖j ―;

printf(― ―);

Dynamic memory Allocation

The process of allocating memory at the time of execution or at the runtime, is

called dynamic memory location.

Two types of problem may occur in static memory allocation.

If number of values to be stored is less than the size of memory, there would be
wastage of memory.

If we would want to store more values by increase in size during the execution on
assigned size then it fails.

Allocation and release of memory space can be done with the help of some library
function called dynamic memory allocation function. These library function are
called as dynamic memory allocation function. These library function prototype
are found in the header file, ―alloc.h‖ where it has defined.

Function take memory from memory area is called heap and release when not
required.

Pointer has important role in the dynamic memory allocation to allocate memory.

malloc():

113
This function use to allocate memory during run time, its declaration is
void*malloc(size);

malloc ()

returns the pointer to the 1st byte and allocate memory, and its return type is void,
which can be type cast such as:

int *p=(datatype*)malloc(size)

If memory location is successful, it returns the address of the memory chunk that
was allocated and it returns null on unsuccessful and from the above declaration a
pointer of type(datatype) and size in byte.

And datatype pointer used to typecast the pointer returned by malloc and this
typecasting is necessary since, malloc() by default returns a pointer to void.

Example int*p=(int*)malloc(10);

So, from the above pointer p, allocated IO contigious memory space address of 1st
byte and is stored in the variable.

We can also use, the size of operator to specify the the size, such as
*p=(int*)malloc(5*size of int) Here, 5 is the no. of data.

Moreover , it returns null, if no sufficient memory available , we should always

check the malloc return such as, if(p==null)

printf(―not sufficient memory‖);

Example:

/*calculate the average of mark*/

void main()

int n , avg,i,*p,sum=0;

114
printf("enter the no. of marks ‖);

scanf(―%d‖,&n);

p=(int *)malloc(n*size(int));

if(p==null)

printf(―not sufficient‖);

exit();

for(i=0;i<n;i++)

scanf(―%d‖,(p+i));

for(i=0;i<n;i++)

Printf(―%d‖,*(p+i));

sum=sum+*p;

avg=sum/n;

printf(―avg=%d‖,avg);

Lecture Note: 28

calloc()

Similar to malloc only difference is that calloc function use to allocate multiple
block of memory .

two arguments are there

1st argument specify number of blocks

115
2nd argument specify size of each block.

Example:-

int *p= (int*) calloc(5, 2);

int*p=(int *)calloc(5, size of (int));

Another difference between malloc and calloc is by default memory allocated by

malloc contains garbage value, where as memory allocated by calloc is initialised
by zero(but this initialisation) is not reliable.

realloc()

The function realloc use to change the size of the memory block and it alter the
size of the memory block without loosing the old data, it is called reallocation of
memory.

It takes two argument such as;

int *ptr=(int *)malloc(size);

int*p=(int *)realloc(ptr, new size);

The new size allocated may be larger or smaller.

If new size is larger than the old size, then old data is not lost and newly allocated
bytes are uninitialized. If old address is not sufficient then starting address
contained in pointer may be changed and this reallocation function moves content
of old block into the new block and data on the old block is not lost.

Example:

#include<stdio.h>

#include<alloc.h>

void main()

int i,*p;

116
p=(int*)malloc(5*size of (int));

if(p==null)

printf(―space not available‖);

exit();

printf(―enter 5 integer‖);

for(i=0;i<5;i++)

scanf(―%d‖,(p+i));

int*ptr=(int*)realloc(9*size of (int) );

if(ptr==null)

printf(―not available‖);

exit();

printf(―enter 4 more integer‖);

for(i=5;i<9;i++)

scanf(―%d‖,(p+i));

for(i=0;i<9;i++)

printf(―%d‖,*(p+i));

free()

117
Function free() is used to release space allocated dynamically, the memory
released by free() is made available to heap again. It can be used for further
purpose.

Syntax for free declaration .

void(*ptr)

Or

free(p)

When program is terminated, memory released automatically by the operating

system. Even we don‘t free the memory, it doesn‘t give error, thus lead to memory
leak.

We can‘t free the memory, those didn‘t allocated.

Lecture Note: 29

Dynamic array

Array is the example where memory is organized in contiguous way, in the

dynamic memory allocation function used such as malloc(), calloc(), realloc()
always made up of contiguous way and as usual we can access the element in two
ways as:

Subscript notation

Pointer notation

Example:

118
#include<stdio.h>

#include<alloc.h>

void main()

printf(―enter the no.of values‖);

scanf(―%d‖,&n);

p=(int*)malloc(n*size of int);

If(p==null)

printf(―not available memory‖);

exit();

for(i=0;i<n;i++)

printf(―enter an integer‖);

scanf(―%d‖,&p[i]);

for(i=0;i<n;i++)

printf(―%d‖,p[i]);

File handling

119
File: the file is a permanent storage medium in which we can store the data
permanently.

Types of file can be handled

we can handle three type of file as

(1) sequential file

(2) random access file

(3) binary file

File Operation

opening a file:

Before performing any type of operation, a file must be opened and for this
fopen() function is used.

syntax:

file-pointer=fopen(―FILE NAME ‖,‖Mode of open‖);

example:

FILE *fp=fopen(―ar.c‖,‖r‖);

If fopen() unable to open a file than it will return NULL to the file pointer.

File-pointer: The file pointer is a pointer variable which can be store the address
of a special file that means it is based upon the file pointer a file gets opened.

Declaration of a file pointer:-

FILE* var;

Modes of open

The file can be open in three different ways as

120
 Read mode ’ r’/rt

Write mode ’w’/wt

Appened Mode ’a’/at

Reading a character from a file

getc() is used to read a character into a file

Syntax:

character_variable=getc(file_ptr);

Writing acharacter into a file

putc() is used to write a character into a file

puts(character-var,file-ptr);

ClOSING A FILE

fclose() function close a file.

fclose(file-ptr);

fcloseall () is used to close all the opened file at a time

File Operation

The following file operation carried out the file

(1)creation of a new file

(3) writing a file

(4) closing a file

121
Before performing any type of operation we must have to open the file.c, language
communicate with file using A new type called file pointer.

Operation with fopen()

File pointer=fopen(―FILE NAME‖,‖mode of open‖);

If fopen() unable to open a file then it will return NULL to the file-pointer.

Lecture Note: 30

Reading and writing a characters from/to a file

fgetc() is used for reading a character from the file

Syntax:

character variable= fgetc(file pointer);

fputc() is used to writing a character to a file

Syntax:

fputc(character,file_pointer);

122
/*Program to copy a file to another*/

#include<stdio.h>

void main()

FILE *fs,*fd;

char ch;

If(fs=fopen(―scr.txt‖,‖r‖)==0)

printf(―sorry….The source file cannot be opened‖);

return;

If(fd=fopen(―dest.txt‖,‖w‖)==0)

printf(―Sorry…..The destination file cannot be opened‖);

fclose(fs);

return;

while(ch=fgets(fs)!=EOF)

fputc(ch,fd);

fcloseall();

123
 Reading and writing a string from/to a file

getw() is used for reading a string from the file

Syntax:

gets(file pointer);

putw() is used to writing a character to a file

Syntax:

fputs(integer,file_pointer);

#include<stdio.h>

#include<stdlib.h>

void main()

FILE *fp;

int word;

/*place the word in a file*/

fp=fopen(―dgt.txt‖,‖wb‖);

If(fp==NULL)

printf(―Error opening file‖);

exit(1);

word=94;

putw(word,fp);

If(ferror(fp))

124
printf(―Error writing to file\n‖);

else

printf(―Successful write\n‖);

fclose(fp);

/*reopen the file*/

fp=fopen(―dgt.txt‖,‖rb‖);

If(fp==NULL)

printf(―Error opening file‖);

exit(1);

/*extract the word*/

word=getw(fp);

If(ferror(fp))

printf(―Error reading file\n‖);

else

printf(―Successful read:word=%d\n‖,word);

/*clean up*/

fclose(fp);

Lecture Note: 31

125
Reading and writing a string from/to a file

fgets() is used for reading a string from the file

Syntax:

fgets(string, length, file pointer);

fputs() is used to writing a character to a file

Syntax:

fputs(string,file_pointer);

#include<string.h>

#include<stdio.h>

void main(void)

FILE*stream;

char string[]=‖This is a test‖;

char msg[20];

/*open a file for update*/

stream=fopen(―DUMMY.FIL‖,‖w+‖);

/*write a string into the file*/

fwrite(string,strlen(string),1,stream);

/*seek to the start of the file*/

fseek(stream,0,SEEK_SET);

126
/*read a string from the file*/

fgets(msg,strlen(string)+1,stream);

/*display the string*/

printf(―%s‖,msg);

fclose(stream);

127
 PART 2
DATA STRUCTURE
 CONTENTS

Lecture-01 Introduction to Data structure

Lecture-02 Search Operation
Lecture-03 Sparse Matrix and its representations
Lecture-04 Stack
Lecture-05 Stack Applications
Lecture-06 Queue
Lecture-07 Linked List
Lecture-08 Polynomial List
Lecture-09 Doubly Linked List
Lecture-10 Circular Linked List
Lecture-11 Memory Allocation
Lecture-12 Infix to Postfix Conversion
Lecture-13 Binary Tree
Lecture-14 Special Forms of Binary Trees
Lecture-15 Tree Traversal
Lecture-16 AVL Trees
Lecture-17 B+-tree
Lecture-18 Binary Search Tree (BST)
Lecture-19 Graphs Terminology
Lecture-20 Depth First Search
Lecture-21 Breadth First Search
Lecture-22 Graph representation
Lecture-23 Topological Sorting
Lecture-24 Bubble Sort
Lecture-25 Insertion Sort
Lecture-26 Selection Sort
Lecture-27 Merge Sort
Lecture-28 Quick sort
Lecture-29 Heap Sort
Lecture-30 Radix Sort
Lecture-31 Binary Search
Lecture-32 Hashing
Lecture-33 Hashing Functions
 Module-1
Lecture-01
Introduction to Data structures
In computer terms, a data structure is a Specific way to store and organize data in a
computer's memory so that these data can be used efficiently later. Data may be
arranged in many different ways such as the logical or mathematical model for a
particular organization of data is termed as a data structure. The variety of a particular
data model depends on the two factors -
 Firstly, it must be loaded enough in structure to reflect the actual relationships of
the data with the real world object.
 Secondly, the formation should be simple enough so that anyone can efficiently
process the data each time it is necessary.
Categories of Data Structure:
The data structure can be sub divided into major types:
 Linear Data Structure
 Non-linear Data Structure
Linear Data Structure:
A data structure is said to be linear if its elements combine to form any specific order.
There are basically two techniques of representing such linear structure within memory.
 First way is to provide the linear relationships among all the elements
represented by means of linear memory location. These linear structures are termed as
arrays.
 The second technique is to provide the linear relationship among all the elements
represented by using the concept of pointers or links. These linear structures are
termed as linked lists.
The common examples of linear data structure are:
 Arrays
 Queues
 Stacks
 Linked lists
Non linear Data Structure:
This structure is mostly used for representing data that contains a hierarchical
relationship among various elements.
Examples of Non Linear Data Structures are listed below:
 Graphs
 family of trees and
 table of contents
Tree: In this case, data often contain a hierarchical relationship among various
elements. The data structure that reflects this relationship is termed as rooted tree
graph or a tree.
Graph: In this case, data sometimes hold a relationship between the pairs of elements
which is not necessarily following the hierarchical structure. Such data structure is
termed as a Graph.
Array is a container which can hold a fix number of items and these items should be of
the same type. Most of the data structures make use of arrays to implement their
algorithms. Following are the important terms to understand the concept of Array.
 Element − Each item stored in an array is called an element.
 Index − Each location of an element in an array has a numerical index, which is
used to identify the element.
Array Representation:(Storage structure)
Arrays can be declared in various ways in different languages. For illustration, let's take
C array declaration.

Arrays can be declared in various ways in different languages. For illustration, let's take
C array declaration.

As per the above illustration, following are the important points to be considered.
 Index starts with 0.
 Array length is 10 which means it can store 10 elements.
 Each element can be accessed via its index. For example, we can fetch an
element at index 6 as 9.
Basic Operations
Following are the basic operations supported by an array.
 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by the value.
 Update − Updates an element at the given index.
In C, when an array is initialized with size, then it assigns defaults values to its
elements in following order.
Data Type Default Value

bool false
 char 0

int 0

float 0.0

double 0.0f

void

wchar_t 0
Insertion Operation
Insert operation is to insert one or more data elements into an array. Based on the
requirement, a new element can be added at the beginning, end, or any given index of
array.
Here, we see a practical implementation of insertion operation, where we add data at
the end of the array −
Algorithm
Let LA be a Linear Array (unordered) with N elements and K is a positive integer such
that K<=N. Following is the algorithm where ITEM is inserted into the Kth position of LA
–
Start
Set J = N
Set N = N+1
Repeat steps 5 and 6 while J >= K
Set LA[J+1] = LA[J]
Set J = J-1
Set LA[K] = ITEM
Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
 n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
Deletion Operation
Deletion refers to removing an existing element from the array and re-organizing all
elements of an array.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such
that K<=N. Following is the algorithm to delete an element available at the Kth position
of LA.
Start
Set J = K
Repeat steps 4 and 5 while J < N
Set LA[J] = LA[J + 1]
Set J = J+1
Set N = N-1
Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}

j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
 Lecture-02
Search Operation
You can perform a search for an array element based on its value or its index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such
that K<=N. Following is the algorithm to find an element with a value of ITEM using
sequential search.
Start
Set J = 0
Repeat steps 4 and 5 while J < N
IF LA[J] is equal ITEM THEN GOTO STEP 6
Set J = J +1
PRINT J, ITEM
Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
Update Operation
Update operation refers to updating an existing element from the array at a given index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such
that K<=N. Following is the algorithm to update an element available at the K th position
of LA.
Start
Set LA[K-1] = ITEM
Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}

LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
 Lecture-03
Sparse Matrix and its representations
A matrix is a two-dimensional data object made of m rows and n columns, therefore
having total m x n values. If most of the elements of the matrix have 0 value, then it is
called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?
 Storage: There are lesser non-zero elements than zeros and thus lesser
memory can be used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements..
Example:
00304
00570
00000
02600
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as
zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes
with non-zero elements, we only store non-zero elements. This means storing non-zero
elements with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays
#include<stdio.h>
int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
int compactMatrix[3][size];
// Making of new matrix
 int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
for (int i=0; i<3; i++)
{
for (int j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);
printf("\n");
}
return 0;
}
 Lecture-04
STACK
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of
plates, etc.

A real-world stack allows operations at one end only. For example, we can place or remove a
card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at
one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element
which is placed (inserted or added) last, is accessed first. In stack terminology, insertion
operation is called PUSH operation and removal operation is called POP operation.
Stack Representation
The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from
these basic stuffs, a stack is used for the following two primary operations −
 push() − Pushing (storing) an element on the stack.
 pop() − Removing (accessing) an element from the stack.
When data is PUSHed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose,
the following functionality is added to stacks −
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 isEmpty() − check if stack is empty.
At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always
represents the top of the stack, hence named top. The top pointer provides top value of the
stack without actually removing it.
First we should learn about procedures to support stack functions −
peek()
Algorithm of peek() function −
begin procedure peek
return stack[top]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return stack[top];
}
isfull()
Algorithm of isfull() function −
begin procedure isfull

if top equals to MAXSIZE

return true
else
return false
endif

end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
begin procedure isempty

if top less than 1

return true
else
return false
endif

end procedure
Implementation of isempty() function in C programming language is slightly different. We
initialize top at -1, as the index in array starts from 0. So we check if the top is below zero or -1
to determine if the stack is empty. Here's the code −
Example
bool isempty() {
if(top == -1)
return true;
else
return false;
}
Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −
begin procedure push: stack, data

if stack is full
 return null
endif

top ← top + 1
stack[top] ← data

end procedure
Implementation of this algorithm in C, is very easy. See the following code −
Example
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an
array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value. But in
linked-list implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −
begin procedure pop: stack

if stack is empty
return null
endif

data ← stack[top]
top ← top - 1
return data

end procedure
Implementation of this algorithm in C, is as follows −
Example
int pop(int data) {

if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
 Lecture-05
Stack Applications

Three applications of stacks are presented here. These examples are central to many activities
that a computer must do and deserve time spent with them.
1. Expression evaluation
2. Backtracking (game playing, finding paths, exhaustive searching)
3. Memory management, run-time environment for nested language features.

Expression evaluation
In particular we will consider arithmetic expressions. Understand that there are boolean and
logical expressions that can be evaluated in the same way. Control structures can also be
treated similarly in a compiler.
This study of arithmetic expression evaluation is an example of problem solving where you solve
a simpler problem and then transform the actual problem to the simpler one.
Aside: The NP-Complete problem. There are a set of apparently intractable problems: finding
the shortest route in a graph (Traveling Salesman Problem), bin packing, linear programming,
etc. that are similar enough that if a polynomial solution is ever found (exponential solutions
abound) for one of these problems, then the solution can be applied to all problems.

Infix, Prefix and Postfix Notation

We are accustomed to write arithmetic expressions with the operation between the two
operands: a+b or c/d. If we write a+b*c, however, we have to apply precedence rules to avoid
the ambiguous evaluation (add first or multiply first?).
There's no real reason to put the operation between the variables or values. They can just as
well precede or follow the operands. You should note the advantage of prefix and postfix: the
need for precedence rules and parentheses are eliminated.
Infix Prefix Postfix
a+b +ab ab+
a+b*c +a*bc abc*+
(a + b) * (c - d) *+ab-cd ab+cd-*
b*b-4*a*c
40 - 3 * 5 + 1
Postfix expressions are easily evaluated with the aid of a stack.

Infix, Prefix and Postfix Notation KEY

Infix Prefix Postfix
a+b +ab ab+
a+b*c +a*bc abc*+
(a + b) * (c - d) *+ab-cd ab+cd-*
b*b-4*a*c -*bb **4ac bb*4a*c*-
40 - 3 * 5 + 1 = 26 + - 40 * 3 5 1 40 3 5 * - 1 +

Postfix Evaluation Algorithm

Assume we have a string of operands and operators, an informal, by hand process is
1. Scan the expression left to right
2. Skip values or variables (operands)
3. When an operator is found, apply the operation to the preceding two operands
4. Replace the two operands and operator with the calculated value (three symbols are
replaced with one operand)
5. Continue scanning until only a value remains--the result of the expression
The time complexity is O(n) because each operand is scanned once, and each operation is
performed once.
A more formal algorithm:
create a new stack
while(input stream is not empty){
token = getNextToken();
if(token instanceof operand){
push(token);
} else if (token instance of operator)
op2 = pop();
op1 = pop();
result = calc(token, op1, op2);
push(result);
}
}
return pop();
Demonstration with 2 3 4 + * 5 -

Infix transformation to Postfix

This process uses a stack as well. We have to hold information that's expressed inside
parentheses while scanning to find the closing ')'. We also have to hold information on
operations that are of lower precedence on the stack. The algorithm is:
1. Create an empty stack and an empty postfix output string/stream
2. Scan the infix input string/stream left to right
3. If the current input token is an operand, simply append it to the output string (note the
examples above that the operands remain in the same order)
4. If the current input token is an operator, pop off all operators that have equal or higher
 precedence and append them to the output string; push the operator onto the stack. The
order of popping is the order in the output.
5. If the current input token is '(', push it onto the stack
6. If the current input token is ')', pop off all operators and append them to the output string
until a '(' is popped; discard the '('.
7. If the end of the input string is found, pop all operators and append them to the output
string.
This algorithm doesn't handle errors in the input, although careful analysis of parenthesis or lack
of parenthesis could point to such error determination.
Apply the algorithm to the above expressions.

Backtracking
Backtracking is used in algorithms in which there are steps along some path (state) from some
starting point to some goal.
 Find your way through a maze.
 Find a path from one point in a graph (roadmap) to another point.
 Play a game in which there are moves to be made (checkers, chess).
In all of these cases, there are choices to be made among a number of options. We need some
way to remember these decision points in case we want/need to come back and try the
alternative
Consider the maze. At a point where a choice is made, we may discover that the choice leads
to a dead-end. We want to retrace back to that decision point and then try the other (next)
alternative.
Again, stacks can be used as part of the solution. Recursion is another, typically more favored,
solution, which is actually implemented by a stack.

Memory Management
Any modern computer environment uses a stack as the primary memory management model for
a running program. Whether it's native code (x86, Sun, VAX) or JVM, a stack is at the center of
the run-time environment for Java, C++, Ada, FORTRAN, etc.
The discussion of JVM in the text is consistent with NT, Solaris, VMS, Unix runtime
environments.
Each program that is running in a computer system has its own memory allocation containing
the typical layout as shown below.
Call and return process
When a method/function is called
1. An activation record is created; its size depends on the number and size of the local
variables and parameters.
2. The Base Pointer value is saved in the special location reserved for it
3. The Program Counter value is saved in the Return Address location
4. The Base Pointer is now reset to the new base (top of the call stack prior to the creation
of the AR)
5. The Program Counter is set to the location of the first bytecode of the method being
called
6. Copies the calling parameters into the Parameter region
7. Initializes local variables in the local variable region
While the method executes, the local variables and parameters are simply found by adding a
constant associated with each variable/parameter to the Base Pointer.
When a method returns
1. Get the program counter from the activation record and replace what's in the PC
2. Get the base pointer value from the AR and replace what's in the BP
3. Pop the AR entirely from the stack.
 Lecture-06
QUEUE
Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open
at both its ends. One end is always used to insert data (enqueue) and the other is used to
remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored
first will be accessed first.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters
first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-
stops.
Queue Representation
As we now understand that in queue, we access both ends for different reasons. The following
diagram given below tries to explain queue representation as data structure −

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional array.
Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then completely
erasing it from the memory. Here we shall try to understand the basic operations associated
with queues −
 enqueue() − add (store) an item to the queue.
 dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient. These
are −
 peek() − Gets the element at the front of the queue without removing it.
 isfull() − Checks if the queue is full.
 isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or
storing) data in the queue we take help of rear pointer.
Let's first learn about supportive functions of a queue −
peek()
This function helps to see the data at the front of the queue. The algorithm of peek() function is
as follows −
Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer
to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a
circular linked-list, the algorithm will differ. Algorithm of isfull() function −
Algorithm
begin procedure isfull

if rear equals to MAXSIZE

return true
else
return false
endif

end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
Algorithm
begin procedure isempty

if front is less than MIN OR front is greater than rear

return true
 else
return false
endif

end procedure
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence
empty.
Here's the C programming code −
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively
difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if the queue is full.
 Step 2 − If the queue is full, produce overflow error and exit.
 Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 Step 4 − Add data element to the queue location, where the rear is pointing.
 Step 5 − return success.

Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
Algorithm for enqueue operation
procedure enqueue(data)

if queue is full
return overflow
 endif

rear ← rear + 1
queue[rear] ← data
return true

end procedure
Implementation of enqueue() in C programming language −
Example
int enqueue(int data)
if(isfull())
return 0;

rear = rear + 1;
queue[rear] = data;

return 1;
end procedure
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is
pointing and remove the data after access. The following steps are taken to
perform dequeue operation −
 Step 1 − Check if the queue is empty.
 Step 2 − If the queue is empty, produce underflow error and exit.
 Step 3 − If the queue is not empty, access the data where front is pointing.
 Step 4 − Increment front pointer to point to the next available data element.
 Step 5 − Return success.

Algorithm for dequeue operation

procedure dequeue
 if queue is empty
return underflow
end if

data = queue[front]
front ← front + 1
return true

end procedure
Implementation of dequeue() in C programming language −
Example
int dequeue() {
if(isempty())
return 0;

int data = queue[front];

front = front + 1;

return data;
}
 Lecture-07
LINKED LIST
A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection
to another link. Linked list is the second most-used data structure after array. Following
are the important terms to understand the concept of Linked List.
 Link − Each link of a linked list can store a data called an element.
 Next − Each link of a linked list contains a link to the next link called Next.
 LinkedList − A Linked List contains the connection link to the first link called
First.
Linked List Representation
Linked list can be visualized as a chain of nodes, where every node points to the next
node.

As per the above illustration, following are the important points to be considered.
 Linked List contains a link element called first.
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Last link carries a link as null to mark the end of the list.
Types of Linked List
Following are the various types of linked list.
 Simple Linked List − Item navigation is forward only.
 Doubly Linked List − Items can be navigated forward and backward.
 Circular Linked List − Last item contains link of the first element as next and
the first element has a link to the last element as previous.
Basic Operations
Following are the basic operations supported by a list.
 Insertion − Adds an element at the beginning of the list.
 Deletion − Deletes an element at the beginning of the list.
 Display − Displays the complete list.
 Search − Searches an element using the given key.
 Delete − Deletes an element using the given key.
Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this
with diagrams here. First, create a node using the same structure and find the location
where it has to be inserted.
Imagine that we are inserting a node B (NewNode), between A (LeftNode)
and C (RightNode). Then point B.next to C −
NewNode.next −> RightNode;
It should look like this −

Now, the next node at the left should point to the new node.
LeftNode.next −> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

Similar steps should be taken if the node is being inserted at the beginning of the list.
While inserting it at the end, the second last node of the list should point to the new
node and the new node will point to NULL.
Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial
representation. First, locate the target node to be removed, by using searching
algorithms.

The left (previous) node of the target node now should point to the next node of the
target node −
LeftNode.next −> TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following
code, we will remove what the target node is pointing at.
TargetNode.next −> NULL;

We need to use the deleted node. We can keep that in memory otherwise we can
simply deallocate memory and wipe off the target node completely.

Reverse Operation
This operation is a thorough one. We need to make the last node to be pointed by the
head node and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall
make it point to its previous node −

We have to make sure that the last node is not the lost node. So we'll have some temp
node, which looks like the head node pointing to the last node. Now, we shall make all
left side nodes point to their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their
predecessor, making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

The linked list is now reversed.

Program:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

//display the list

void printList() {
struct node *ptr = head;
printf("\n[ ");

//start from the beginning

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;
link->data = data;

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link

struct node *tempLink = head;

//mark next to first link as first

head = head->next;

//return the deleted link

 return tempLink;
}

//is list empty

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next) {

length++;
}

return length;
}

//find a link with given key

struct node* find(int key) {

//start from the first link

struct node* current = head;

//if list is empty

if(head == NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//go to next link
current = current->next;
}
}
 //if data found, return the current Link
return current;
}

//delete a link with given key

struct node* delete(int key) {

//start from the first link

struct node* current = head;
struct node* previous = NULL;

//if list is empty

if(head == NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}

return current;
}
void sort() {

int i, j, k, tempKey, tempData;

struct node *current;
struct node *next;

int size = length();

k = size ;

for ( i = 0 ; i < size - 1 ; i++, k-- ) {

current = head;
next = head->next;

for ( j = 1 ; j < k ; j++ ) {

if ( current->data > next->data ) {

tempData = current->data;
current->data = next->data;
next->data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}

current = current->next;
next = next->next;
}
}
}

void reverse(struct node** head_ref) {

struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;

while (current != NULL) {

next = current->next;
current->next = prev;
prev = current;
current = next;
}
 *head_ref = prev;
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");

printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nRestored List: ");

printList();
printf("\n");

struct node *foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
 } else {
printf("Element not found.");
}

delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

printf("\n");
sort();

printf("List after sorting the data: ");

printList();

reverse(&head);
printf("\nList after reversing the data: ");
printList();
}
If we compile and run the above program, it will produce the following result −
Output
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[]
Restored List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1)
List after deleting an item:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data:
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
 Lecture-08
Polynomial List
A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. +
jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.
An important characteristics of polynomial is that each term in the polynomial
expression consists of two parts:
 one is the coefficient
 other is the exponent
Example:
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential value.
Points to keep in Mind while working with Polynomials:
 The sign of each coefficient and exponent is stored within the coefficient and the
exponent itself
 Additional terms having equal exponent is possible one
 The storage allocation for each term in the polynomial must be done in
ascending and descending order of their exponent

Representation of Polynomial
Polynomial can be represented in the various ways. These are:
 By the use of arrays
 By the use of Linked List
Representation of Polynomials using Arrays
There may arise some situation where you need to evaluate many polynomial
expressions and perform basic arithmetic operations like: addition and subtraction with
those numbers. For this you will have to get a way to represent those polynomials. The
simple way is to represent a polynomial with degree 'n' and store the coefficient of n+1
terms of the polynomial in array. So every array element will consists of two values:
 Coefficient and
 Exponent
Representation of Polynomial Using Linked Lists
A polynomial can be thought of as an ordered list of non zero terms. Each non zero
term is a two tuple which holds two pieces of information:
  The exponent part
 The coefficient part
Adding two polynomials using Linked List
Given two polynomial numbers represented by a linked list. Write a function that add
these lists means add the coefficients who have same variable powers.
Example:

Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st number = 5x^3 + 4x^2 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^3 + 4x^2 + 5x^1 + 7x^0
struct Node

int coeff;

int pow;

struct Node *next;

};

void create_node(int x, int y, struct Node **temp)

struct Node *r, *z;

z = *temp;

if(z == NULL)

r =(struct Node*)malloc(sizeof(struct Node));

r->coeff = x;

r->pow = y;

*temp = r;

r->next = (struct Node*)malloc(sizeof(struct Node));

r = r->next;

r->next = NULL;

else

r->coeff = x;

r->pow = y;
 r->next = (struct Node*)malloc(sizeof(struct Node));

r = r->next;

r->next = NULL;

void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly)

while(poly1->next && poly2->next)

if(poly1->pow > poly2->pow)

poly->pow = poly1->pow;

poly->coeff = poly1->coeff;

poly1 = poly1->next;

else if(poly1->pow < poly2->pow)

poly->pow = poly2->pow;

poly->coeff = poly2->coeff;

poly2 = poly2->next;

else

poly->pow = poly1->pow;

poly->coeff = poly1->coeff+poly2->coeff;
 poly1 = poly1->next;

poly2 = poly2->next;

poly->next = (struct Node *)malloc(sizeof(struct Node));

poly = poly->next;

poly->next = NULL;

while(poly1->next || poly2->next)

if(poly1->next)

poly->pow = poly1->pow;

poly->coeff = poly1->coeff;

poly1 = poly1->next;

if(poly2->next)

poly->pow = poly2->pow;

poly->coeff = poly2->coeff;

poly2 = poly2->next;

poly->next = (struct Node *)malloc(sizeof(struct Node));

poly = poly->next;

poly->next = NULL;

}
}

void show(struct Node *node)

while(node->next != NULL)

printf("%dx^%d", node->coeff, node->pow);

node = node->next;

if(node->next != NULL)

printf(" + ");

int main()

struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;

// Create first list of 5x^2 + 4x^1 + 2x^0

create_node(5,2,&poly1);

create_node(4,1,&poly1);

create_node(2,0,&poly1);

// Create second list of 5x^1 + 5x^0

create_node(5,1,&poly2);

create_node(5,0,&poly2);

printf("1st Number: ");

show(poly1);

printf("\n2nd Number: ");

show(poly2);
 poly = (struct Node *)malloc(sizeof(struct Node));

// Function add two polynomial numbers

polyadd(poly1, poly2, poly);

// Display resultant List

printf("\nAdded polynomial: ");

show(poly);

return 0;

Output:

1st Number: 5x^2 + 4x^1 + 2x^0

2nd Number: 5x^1 + 5x^0
Added polynomial: 5x^2 + 9x^1 + 7x^0
 Lecture-09
Doubly Linked List
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer,
together with next pointer and data which are there in singly linked list.

Following is representation of a DLL node in C language.

/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};
Following are advantages/disadvantages of doubly linked list over singly linked list.
Advantages over singly linked list
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is
given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get
this previous node, sometimes the list is traversed. In DLL, we can get the previous
node using previous pointer.
Disadvantages over singly linked list
1) Every node of DLL Require extra space for an previous pointer. It is possible to
implement DLL with single pointer though
2) All operations require an extra pointer previous to be maintained. For example, in
insertion, we need to modify previous pointers together with next pointers. For
example in following functions for insertions at different positions, we need 1 or 2 extra
steps to set previous pointer.
Insertion
A node can be added in four ways
1) At the front of the DLL
2) After a given node.
3) At the end of the DLL
4) Before a given node.
1) Add a node at the front: (A 5 steps process)
The new node is always added before the head of the given Linked List. And newly
added node becomes the new head of DLL. For example if the given Linked List is
10152025 and we add an item 5 at the front, then the Linked List becomes 510152025.
Let us call the function that adds at the front of the list is push(). The push() must
receive a pointer to the head pointer, because push must change the head pointer to
point to the new node

2) Add a node after a given node.: (A 7 steps process)

We are given pointer to a node as prev_node, and the new node is inserted after the
given node.

3) Add a node at the end: (7 steps process)

The new node is always added after the last node of the given Linked List. For example
if the given DLL is 510152025 and we add an item 30 at the end, then the DLL becomes
51015202530. Since a Linked List is typically represented by the head of it, we have to
traverse the list till end and then change the next of last node to new node.

4) Add a node before a given node:

Steps
Let the pointer to this given node be next_node and the data of the new node to be
added as new_data.
1. Check if the next_node is NULL or not. If it‘s NULL, return from the function
because any new node can not be added before a NULL
2. Allocate memory for the new node, let it be called new_node
3. Set new_node->data = new_data
4. Set the previous pointer of this new_node as the previous node of the next_node,
new_node->prev = next_node->prev
5. Set the previous pointer of the next_node as the new_node, next_node->prev =
new_node
6. Set the next pointer of this new_node as the next_node, new_node->next =
next_node;
7. If the previous node of the new_node is not NULL, then set the next pointer of
this previous node as new_node, new_node->prev->next = new_node
 Lecture-10
Circular Linked List
Circular linked list is a linked list where all nodes are connected to form a circle. There is
no NULL at the end. A circular linked list can be a singly circular linked list or doubly
circular linked list.

Advantages of Circular Linked Lists:

1) Any node can be a starting point. We can traverse the whole list by starting from any
point. We just need to stop when the first visited node is visited again.
2) Useful for implementation of queue. Unlike this implementation, we don’t need to
maintain two pointers for front and rear if we use circular linked list. We can maintain a
pointer to the last inserted node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example,
when multiple applications are running on a PC, it is common for the operating system
to put the running applications on a list and then to cycle through them, giving each of
them a slice of time to execute, and then making them wait while the CPU is given to
another application. It is convenient for the operating system to use a circular list so that
when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures
like Fibonacci Heap.
Insertion in an empty List

Initially when the list is empty, last pointer will be NULL.

After inserting a node T,

After insertion, T is the last node so pointer last points to node T. And Node T is first
and last node, so T is pointing to itself.
Function to insert node in an empty List,
struct Node *addToEmpty(struct Node *last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
 // Creating a node dynamically.
struct Node *last =
(struct Node*)malloc(sizeof(struct Node));

// Assigning the data.

last -> data = data;

// Note : list was empty. We link single node

// to itself.
last -> next = last;

return last;
}
Run on IDE

Insertion at the beginning of the list

To Insert a node at the beginning of the list, follow these step:

1. Create a node, say T.
2. Make T -> next = last -> next.
3. last -> next = T.

After insertion,

Function to insert node in the beginning of the List,

struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);

// Creating a node dynamically.

struct Node *temp
= (struct Node *)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;

// Adjusting the links.

temp -> next = last -> next;
last -> next = temp;

return last;
}

Insertion at the end of the list

To Insert a node at the end of the list, follow these step:

1. Create a node, say T.
2. Make T -> next = last -> next;
3. last -> next = T.
4. last = T.

After insertion,

Function to insert node in the end of the List,

struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);

// Creating a node dynamically.

 struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;

// Adjusting the links.

temp -> next = last -> next;
last -> next = temp;
last = temp;

return last;
}

Insertion in between the nodes

To Insert a node at the end of the list, follow these step:

1. Create a node, say T.
2. Search the node after which T need to be insert, say that node be P.
3. Make T -> next = P -> next;
4. P -> next = T.
Suppose 12 need to be insert after node having value 10,

After searching and insertion,

Function to insert node in the end of the List,
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
// Searching the item.
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = p -> next;
// Adding newly allocated node after p.
p -> next = temp;
// Checking for the last node.
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while (p != last -> next);

cout << item << " not present in the list." << endl;
return last;
}
 Module-2:
Lecture-11
Memory Allocation-
Whenever a new node is created, memory is allocated by the system. This memory is
taken from list of those memory locations which are free i.e. not allocated. This list is
called AVAIL List. Similarly, whenever a node is deleted, the deleted space becomes
reusable and is added to the list of unused space i.e. to AVAIL List. This unused space
can be used in future for memory allocation.
Memory allocation is of two types-
1. Static Memory Allocation
2. Dynamic Memory Allocation

1. Static Memory Allocation:

When memory is allocated during compilation time, it is called ‗Static Memory
Allocation‘. This memory is fixed and cannot be increased or decreased after
allocation. If more memory is allocated than requirement, then memory is wasted. If
less memory is allocated than requirement, then program will not run successfully.
So exact memory requirements must be known in advance.
2. Dynamic Memory Allocation:
When memory is allocated during run/execution time, it is called ‗Dynamic Memory
Allocation‘. This memory is not fixed and is allocated according to our requirements.
Thus in it there is no wastage of memory. So there is no need to know exact memory
requirements in advance.
Garbage Collection-
Whenever a node is deleted, some memory space becomes reusable. This memory
space should be available for future use. One way to do this is to immediately insert the
free space into availability list. But this method may be time consuming for the operating
system. So another method is used which is called ‗Garbage Collection‘. This method is
described below: In this method the OS collects the deleted space time to time onto the
availability list. This process happens in two steps. In first step, the OS goes through all
the lists and tags all those cells which are currently being used. In the second step, the
OS goes through all the lists again and collects untagged space and adds this collected
space to availability list. The garbage collection may occur when small amount of free
space is left in the system or no free space is left in the system or when CPU is idle and
has time to do the garbage collection.
Compaction
One preferable solution to garbage collection is compaction.
The process of moving all marked nodes to one end of memory and all available
memory to other end is called compaction. Algorithm which performs compaction is
called compacting algorithm.
 Lecture-12

Infix to Postfix Conversion

1 #include<stdio.h>
2 char stack[20];
3 int top = -1;
4 void push(char x)
5 {
6 stack[++top] = x;
7 }
8
9 char pop()
10 {
11 if(top == -1)
12 return -1;
13 else
14 return stack[top--];
15 }
16
17 int priority(char x)
18 {
19 if(x == '(')
20 return 0;
21 if(x == '+' || x == '-')
22 return 1;
23 if(x == '*' || x == '/')
24 return 2;
25 }
26
27 main()
28 {
29 char exp[20];
30 char *e, x;
31 printf("Enter the expression :: ");
32 scanf("%s",exp);
33 e = exp;
34 while(*e != '\0')
35 {
36 if(isalnum(*e))
37 printf("%c",*e);
38 else if(*e == '(')
39 push(*e);
40 else if(*e == ')')
41 {
42 while((x = pop()) != '(')
43 printf("%c", x);
44 }
45 else
46 {
47 while(priority(stack[top]) >= priority(*e))
48 printf("%c",pop());
49 push(*e);
50 }
51 e++;
52 }
53 while(top != -1)
54 {
55 printf("%c",pop());
56 }
57 }

OUTPUT:

Enter the expression :: a+b*c

abc*+

Enter the expression :: (a+b)*c+(d-a)

ab+c*da-+
Evaluate POSTFIX Expression Using Stack

1 #include<stdio.h>

2 int stack[20];

3 int top = -1;

4 void push(int x)

5 {

6 stack[++top] = x;

7 }

9 int pop()

10 {

11 return stack[top--];

12 }

13

14 int main()

15 {

16 char exp[20];

17 char *e;

18 int n1,n2,n3,num;

19 printf("Enter the expression :: ");

20 scanf("%s",exp);

21 e = exp;

22 while(*e != '\0')

23 {

24 if(isdigit(*e))
25 {

26 num = *e - 48;

27 push(num);

28 }

29 else

30 {

31 n1 = pop();

32 n2 = pop();

33 switch(*e)

34 {

35 case '+':

36 {

37 n3 = n1 + n2;

38 break;

39 }

40 case '-':

41 {

42 n3 = n2 - n1;

43 break;

44 }

45 case '*':

46 {

47 n3 = n1 * n2;

48 break;

49 }
50 case '/':

51 {

52 n3 = n2 / n1;

53 break;

54 }

55 }

56 push(n3);

57 }

58 e++;

59 }

60 printf("\nThe result of expression %s = %d\n\n",exp,pop());

61 return 0;

62

63 }

64

Output:

Enter the expression :: 245+*

The result of expression 245+* = 18

 Lecture-13

Binary Tree

A binary tree consists of a finite set of nodes that is either empty, or consists of one
specially designated node called the root of the binary tree, and the elements of two
disjoint binary trees called the left subtree and right subtree of the root.
Note that the definition above is recursive: we have defined a binary tree in terms of
binary trees. This is appropriate since recursion is an innate characteristic of tree
structures.
Diagram 1: A binary tree

Binary Tree Terminology

Tree terminology is generally derived from the terminology of family trees (specifically,
the type of family tree called a lineal chart).
 Each root is said to be the parent of the roots of its subtrees.
 Two nodes with the same parent are said to be siblings; they are the children of
their parent.
 The root node has no parent.
 A great deal of tree processing takes advantage of the relationship between a
parent and its children, and we commonly say a directed edge (or simply
an edge) extends from a parent to its children. Thus edges connect a root with
the roots of each subtree. An undirected edge extends in both directions between
a parent and a child.
  Grandparent and grandchild relations can be defined in a similar manner; we
could also extend this terminology further if we wished (designating nodes as
cousins, as an uncle or aunt, etc.).

Other Tree Terms

 The number of subtrees of a node is called the degree of the node. In a binary
tree, all nodes have degree 0, 1, or 2.
 A node of degree zero is called a terminal node or leaf node.
 A non-leaf node is often called a branch node.
 The degree of a tree is the maximum degree of a node in the tree. A binary tree
is degree 2.
 A directed path from node n1 to nk is defined as a sequence of nodes n1, n2,
..., nk such that ni is the parent of ni+1 for 1 <= i < k. An undirected path is a
similar sequence of undirected edges. The length of this path is the number of
edges on the path, namely k – 1 (i.e., the number of nodes – 1). There is a path
of length zero from every node to itself. Notice that in a binary tree there is
exactly one path from the root to each node.
 The level or depth of a node with respect to a tree is defined recursively: the level
of the root is zero; and the level of any other node is one higher than that of its
parent. Or to put it another way, the level or depth of a node ni is the length of the
unique path from the root to ni.
 The height of ni is the length of the longest path from ni to a leaf. Thus all leaves
in the tree are at height 0.
 The height of a tree is equal to the height of the root. The depth of a tree is equal
to the level or depth of the deepest leaf; this is always equal to the height of the
tree.
 If there is a directed path from n1 to n2, then n1 is an ancestor of n2 and n2 is a
descendant of n1.
 Lecture-14

Special Forms of Binary Trees

There are a few special forms of binary tree worth mentioning.

If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is
termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary
tree are of degree zero or two, never degree one. A strictly binary tree with N leaves
always contains 2N – 1 nodes.
Some texts call this a "full" binary tree.
A complete binary tree of depth d is the strictly binary tree all of whose leaves are at
level d.
The total number of nodes in a complete binary tree of depth d equals 2d+1 – 1. Since all
leaves in such a tree are at level d, the tree contains 2d leaves and, therefore, 2d - 1
internal nodes.
Diagram 2: A complete binary tree

A binary tree of depth d is an almost complete binary tree if:

 Each leaf in the tree is either at level d or at level d – 1.
 For any node nd in the tree with a right descendant at level d, all the left
descendants of nd that are leaves are also at level d.
Diagram 3: An almost complete binary tree
An almost complete strictly binary tree with N leaves has 2N – 1 nodes (as does any
other strictly binary tree). An almost complete binary tree with N leaves that is not
strictly binary has 2N nodes. There are two distinct almost complete binary trees
with N leaves, one of which is strictly binary and one of which is not.
There is only a single almost complete binary tree with N nodes. This tree is strictly
binary if and only if N is odd.

Representing Binary Trees in Memory

Array Representation
For a complete or almost complete binary tree, storing the binary tree as an array may
be a good choice.
One way to do this is to store the root of the tree in the first element of the array. Then,
for each node in the tree that is stored at subscript k, the node's left child can be stored
at subscript 2k+1 and the right child can be stored at subscript 2k+2. For example, the
almost complete binary tree shown in Diagram 2 can be stored in an array like so:

However, if this scheme is used to store a binary tree that is not complete or almost
complete, we can end up with a great deal of wasted space in the array.
For example, the following binary tree

would be stored using this techinque like so:

Linked Representation
If a binary tree is not complete or almost complete, a better choice for storing it is to use
a linked representation similar to the linked list structures covered earlier in the
semester:
Each tree node has two pointers (usually named left and right). The tree class has a
pointer to the root node of the tree (labeled root in the diagram above).
Any pointer in the tree structure that does not point to a node will normally contain the
value NULL. A linked tree with N nodes will always contain N + 1 null links.
 Lecture-15
Tree Traversal:
Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root
(head) node. That is, we cannot randomly access a node in a tree. There are three
ways which we use to traverse a tree −
 In-order Traversal
 Pre-order Traversal
 Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to
print all the values it contains.
In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right
sub-tree. We should always remember that every node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.

We start from A, and following in-order traversal, we move to its left subtree B. B is
also traversed in-order. The process goes on until all the nodes are visited. The output
of inorder traversal of this tree will be −
D→B→E→A→F→C→G
Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally
the right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then move
to its left subtree B. B is also traversed pre-order. The process goes on until all the
nodes are visited. The output of pre-order traversal of this tree will be −
A→B→D→E→C→F→G

Algorithm

Until all nodes are traversed −

Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
Post-orderTraversal
In this traversal method, the root node is visited last, hence the name. First we traverse
the left subtree, then the right subtree and finally the root node.

We start from A, and following Post-order traversal, we first visit the left subtree B. B is
also traversed post-order. The process goes on until all the nodes are visited. The
output of post-order traversal of this tree will be −
D→E→B→F→G→C→A

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
 Lecture-16
AVL Trees
An AVL tree is another balanced binary search tree. Named after their
inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to
be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-
trees differ in height by at most 1, maintaining an O(logn) search time. Addition and
deletion operations also take O(logn) time.
Definition of an AVL tree
An AVL tree is a binary search tree which has the following
properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Balance requirement
for an AVL tree: the left
and right sub-trees
differ by at most 1 in
height.

You need to be careful with this definition: it permits some apparently unbalanced trees!
For example, here are some trees:

Tree AVL tree?

Yes
Examination shows
that each left sub-tree
has a height 1 greater
than each right sub-
tree.
 No
Sub-tree with root 8 has
height 4 and sub-tree
with root 18 has height
2

Insertion
As with the red-black tree, insertion is somewhat complex and involves a number of
cases. Implementations of AVL tree insertion may be found in many textbooks: they rely
on adding an extra attribute, the balance factor to each node. This factor indicates
whether the tree is left-heavy (the height of the left sub-tree is 1 greater than the right
sub-tree), balanced (both sub-trees are the same height) or right-heavy(the height of the
right sub-tree is 1 greater than the left sub-tree). If the balance would be destroyed by
an insertion, a rotation is performed to correct the balance.
A new item has been
added to the left subtree
of node 1, causing its
height to become 2
greater than 2's right sub-
tree (shown in green). A
right-rotation is performed
to correct the imbalance.
 Lecture-17

B+-tree

In B+-tree, each node stores up to d references to children and up to d − 1 keys. Each

reference is considered ―between‖ two of the node's keys; it references the root of a
subtree for which all values are between these two keys.
Here is a fairly small tree using 4 as our value for d.

A B+-tree requires that each leaf be the same distance from the root, as in this picture,
where searching for any of the 11 values (all listed on the bottom level) will involve
loading three nodes from the disk (the root block, a second-level block, and a leaf).
In practice, d will be larger — as large, in fact, as it takes to fill a disk block. Suppose a
block is 4KB, our keys are 4-byte integers, and each reference is a 6-byte file offset.
Then we'd choose d to be the largest value so that 4 (d − 1) + 6 d ≤ 4096; solving this
inequality for d, we end up with d ≤ 410, so we'd use 410 for d. As you can see, d can
be large.
A B+-tree maintains the following invariants:
 Every node has one more references than it has keys.
 All leaves are at the same distance from the root.
 For every non-leaf node N with k being the number of keys in N: all keys in the
first child's subtree are less than N's first key; and all keys in the ith child's
subtree (2 ≤ i ≤ k) are between the (i − 1)th key of n and the ith key of n.
 The root has at least two children.
 Every non-leaf, non-root node has at least floor(d / 2) children.
  Each leaf contains at least floor(d / 2) keys.
 Every key from the table appears in a leaf, in left-to-right sorted order.
In our examples, we'll continue to use 4 for d. Looking at our invariants, this requires
that each leaf have at least two keys, and each internal node to have at least two
children (and thus at least one key).
2. Insertion algorithm
Descend to the leaf where the key fits.
1. If the node has an empty space, insert the key/reference pair into the node.
2. If the node is already full, split it into two nodes, distributing the keys evenly
between the two nodes. If the node is a leaf, take a copy of the minimum value in
the second of these two nodes and repeat this insertion algorithm to insert it into
the parent node. If the node is a non-leaf, exclude the middle value during the
split and repeat this insertion algorithm to insert this excluded value into the
parent node.
Initial:

Insert 20:

Insert 13:
Insert 15:

Insert 10:

Insert 11:

Insert 12:

3. Deletion algorithm

Descend to the leaf where the key exists.

1. Remove the required key and associated reference from the node.
2. If the node still has enough keys and references to satisfy the invariants, stop.
 3. If the node has too few keys to satisfy the invariants, but its next oldest or next
youngest sibling at the same level has more than necessary, distribute the keys
between this node and the neighbor. Repair the keys in the level above to
represent that these nodes now have a different ―split point‖ between them; this
involves simply changing a key in the levels above, without deletion or insertion.
4. If the node has too few keys to satisfy the invariant, and the next oldest or next
youngest sibling is at the minimum for the invariant, then merge the node with its
sibling; if the node is a non-leaf, we will need to incorporate the ―split key‖ from
the parent into our merging. In either case, we will need to repeat the removal
algorithm on the parent node to remove the ―split key‖ that previously separated
these merged nodes — unless the parent is the root and we are removing the
final key from the root, in which case the merged node becomes the new root
(and the tree has become one level shorter than before).
Initial:

Delete 13:
Delete 15:

Delete 1:

Expression Trees:
Trees are used in many other ways in the computer science. Compilers and database
are two major examples in this regard. In case of compilers, when the languages are
translated into machine language, tree-like structures are used. We have also seen an
example of expression tree comprising the mathematical expression. Let‘s have more
discussion on the expression trees. We will see what are the benefits of expression
trees and how can we build an expression tree. Following is the figure of an expression
tree.
In the above tree, the expression on the left side is a + b * c while on the right side, we
have d * e + f * g. If you look at the figure, it becomes evident that the inner nodes
contain operators while leaf nodes have operands. We know that there are two types of
nodes in the tree i.e. inner nodes and leaf nodes. The leaf nodes are such nodes which
have left and right subtrees as null. You will find these at the bottom level of the tree.
The leaf nodes are connected with the inner nodes. So in trees, we have some inner
nodes and some leaf nodes.
In the above diagram, all the inner nodes (the nodes which have either left or right child
or both) have operators. In this case, we have + or * as operators. Whereas leaf nodes
contain operands only i.e. a, b, c, d, e, f, g. This tree is binary as the operators are
binary. We have discussed the evaluation of postfix and infix expressions and have
seen that the binary operators need two operands. In the infix expressions, one operand
is on the left side of the operator and the other is on the right side. Suppose, if we have
+ operator, it will be written as 2 + 4. However, in case of multiplication, we will write as
5*6. We may have unary operators like negation (-) or in Boolean expression we have
NOT. In this example, there are all the binary operators. Therefore, this tree is a binary
tree. This is not the Binary Search Tree. In BST, the values on the left side of the nodes
are smaller and the values on the right side are greater than the node. Therefore, this is
not a BST. Here we have an expression tree with no sorting process involved.
This is not necessary that expression tree is always binary tree. Suppose we have a
unary operator like negation. In this case, we have a node which has (-) in it and there is
only one leaf node under it. It means just negate that operand.
Let‘s talk about the traversal of the expression tree. The inorder traversal may be
executed here.
 Lecture-18
Binary Search Tree (BST)
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties −
 The left sub-tree of a node has a key less than or equal to its parent node's key.
 The right sub-tree of a node has a key greater than to its parent node's key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right
sub-tree and can be defined as −

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Representation
BST is a collection of nodes arranged in a way where they maintain BST properties.
Each node has a key and an associated value. While searching, the desired key is
compared to the keys in BST and if found, the associated value is retrieved.
Following is a pictorial representation of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree
and the higher valued keys on the right sub-tree.
Basic Operations
Following are the basic operations of a tree −
 Search − Searches an element in a tree.
 Insert − Inserts an element in a tree.
 Pre-order Traversal − Traverses a tree in a pre-order manner.
 In-order Traversal − Traverses a tree in an in-order manner.
 Post-order Traversal − Traverses a tree in a post-order manner.
Node
Define a node having some data, references to its left and right child nodes.

struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};

Search Operation
Whenever an element is to be searched, start searching from the root node. Then if the
data is less than the key value, search for the element in the left subtree. Otherwise,
search for the element in the right subtree. Follow the same algorithm for each node.

Algorithm

struct node* search(int data){

struct node *current = root;
printf("Visiting elements: ");

while(current->data != data){

if(current != NULL) {
printf("%d ",current->data);

//go to left tree

if(current->data > data){
current = current->leftChild;
} //else go to right tree
else {
current = current->rightChild;
}

//not found
 if(current == NULL){
return NULL;
}
}
}

return current;
}

Insert Operation
Whenever an element is to be inserted, first locate its proper location. Start searching
from the root node, then if the data is less than the key value, search for the empty
location in the left subtree and insert the data. Otherwise, search for the empty location
in the right subtree and insert the data.

Algorithm

void insert(int data) {

struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;

tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;

//if tree is empty

if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
 while(1) {
parent = current;

//go to left of the tree

if(data < parent->data) {
current = current->leftChild;
//insert to the left

if(current == NULL) {
parent->leftChild = tempNode;
return;
}
} //go to right of the tree
else {
current = current->rightChild;

//insert to the right

if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
 Module-3:
Lecture-19
Graphs Terminology
A graph consists of:
 A set, V, of vertices (nodes)
 A collection, E, of pairs of vertices from V called edges (arcs)
Edges, also called arcs, are represented by (u, v) and are either:
Directed if the pairs are ordered (u, v)
u the origin
v the destination
Undirected if the pairs are unordered
A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed
as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and Eis the set
of edges, connecting the pairs of vertices. Take a look at the following graph −

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Then a graph can be:
Directed graph (di-graph) if all the edges are directed
Undirected graph (graph) if all the edges are undirected
Mixed graph if edges are both directed or undirected
Illustrate terms on graphs
End-vertices of an edge are the endpoints of the edge.
Two vertices are adjacent if they are endpoints of the same edge.
An edge is incident on a vertex if the vertex is an endpoint of the edge.
Outgoing edges of a vertex are directed edges that the vertex is the origin.
Incoming edges of a vertex are directed edges that the vertex is the destination.
Degree of a vertex, v, denoted deg(v) is the number of incident edges.
Out-degree, outdeg(v), is the number of outgoing edges.
In-degree, indeg(v), is the number of incoming edges.
Parallel edges or multiple edges are edges of the same type and end-vertices
Self-loop is an edge with the end vertices the same vertex
Simple graphs have no parallel edges or self-loops
Properties
If graph, G, has m edges then Σv∈G deg(v) = 2m
If a di-graph, G, has m edges then
Σv∈G indeg(v) = m = Σv∈G outdeg(v)
If a simple graph, G, has m edges and n vertices:
If G is also directed then m ≤ n(n-1)
If G is also undirected then m ≤ n(n-1)/2
So a simple graph with n vertices has O(n2) edges at most
More Terminology
Path is a sequence of alternating vetches and edges such that each successive vertex
is connected by the edge. Frequently only the vertices are listed especially if there are
no parallel edges.
Cycle is a path that starts and end at the same vertex.
Simple path is a path with distinct vertices.
Directed path is a path of only directed edges
Directed cycle is a cycle of only directed edges.
Sub-graph is a subset of vertices and edges.
Spanning sub-graph contains all the vertices.
Connected graph has all pairs of vertices connected by at least one path.
Connected component is the maximal connected sub-graph of a unconnected graph.
Forest is a graph without cycles.
Tree is a connected forest (previous type of trees are called rooted trees, these are free
trees)
Spanning tree is a spanning subgraph that is also a tree.
More Properties
If G is an undirected graph with n vertices and m edges:
 If G is connected then m ≥ n - 1
 If G is a tree then m = n - 1
 If G is a forest then m ≤ n – 1
Graph Traversal:
1. Depth First Search
2. Breadth First Search
 Lecture-20
Depth First Search:
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses
a stack to remember to get the next vertex to start a search, when a dead end occurs
in any iteration.

As in the example given above, DFS algorithm traverses from S to A to D to G to E to

B first, then to F and lastly to C. It employs the following rules.
 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it
in a stack.
 Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will
pop up all the vertices from the stack, which do not have adjacent vertices.)
 Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

Step Traversal Description

Initialize the stack.

2
Mark S as visited and put it
onto the stack. Explore any
unvisited adjacent node
from S. We have three nodes
and we can pick any of them.
For this example, we shall
take the node in an
alphabetical order.

Mark A as visited and put it

onto the stack. Explore any
unvisited adjacent node from
A. Both Sand D are adjacent
to A but we are concerned for
unvisited nodes only.

4
Visit D and mark it as visited
and put onto the stack. Here,
we have B and C nodes,
which are adjacent to D and
both are unvisited. However,
we shall again choose in an
alphabetical order.

We choose B, mark it as
visited and put onto the stack.
Here Bdoes not have any
unvisited adjacent node. So,
we pop Bfrom the stack.
6

We check the stack top for

return to the previous node
and check if it has any
unvisited nodes. Here, we
find D to be on the top of the
stack.

Only unvisited adjacent node

is from D is C now. So we
visit C, mark it as visited and
put it onto the stack.

As C does not have any unvisited adjacent node so we keep popping the stack until we
find a node that has an unvisited adjacent node. In this case, there's none and we keep
popping until the stack is empty.
 Lecture-21
Breadth First Search
Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and
uses a queue to remember to get the next vertex to start a search, when a dead end
occurs in any iteration.

As in the example given above, BFS algorithm traverses from A to B to E to F first then
to C and G lastly to D. It employs the following rules.
 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it
in a queue.
 Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
 Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Step Traversal Description

Initialize the queue.

2

We start from
visiting S(starting node), and
mark it as visited.

3
We then see an unvisited
adjacent node from S. In this
example, we have three nodes
but alphabetically we
choose A, mark it as visited
and enqueue it.

Next, the unvisited adjacent

node from S is B. We mark it
as visited and enqueue it.

Next, the unvisited adjacent

node from S is C. We mark it
as visited and enqueue it.
6

Now, S is left with no unvisited

adjacent nodes. So, we
dequeue and find A.

From A we have D as
unvisited adjacent node. We
mark it as visited and enqueue
it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm
we keep on dequeuing in order to get all unvisited nodes. When the queue gets
emptied, the program is over.
 Lecture-22
Graph representation
You can represent a graph in many ways. The two most common ways of representing
a graph is as follows:
Adjacency matrix
An adjacency matrix is a VxV binary matrix A. Element Ai,j is 1 if there is an edge from
vertex i to vertex j else Ai,jis 0.
Note: A binary matrix is a matrix in which the cells can have only one of two possible
values - either a 0 or 1.
The adjacency matrix can also be modified for the weighted graph in which instead of
storing 0 or 1 in Ai,j, the weight or cost of the edge will be stored.
In an undirected graph, if Ai,j = 1, then Aj,i = 1. In a directed graph, if Ai,j = 1,
then Aj,i may or may not be 1.
Adjacency matrix provides constant time access (O(1) ) to determine if there is an
edge between two nodes. Space complexity of the adjacency matrix is O(V2).
The adjacency matrix of the following graph is:
i/j : 1 2 3 4
1:0101
2:1010
3:0101
4:1010

The adjacency matrix of the following graph is:

i/j: 1 2 3 4
1:0100
2:0001
3:1001
4:0100
Adjacency list
The other way to represent a graph is by using an adjacency list. An adjacency list is an
array A of separate lists. Each element of the array Ai is a list, which contains all the
vertices that are adjacent to vertex i.
For a weighted graph, the weight or cost of the edge is stored along with the vertex in
the list using pairs. In an undirected graph, if vertex j is in list Ai then vertex i will be in
list Aj.
The space complexity of adjacency list is O(V + E) because in an adjacency list
information is stored only for those edges that actually exist in the graph. In a lot of
cases, where a matrix is sparse using an adjacency matrix may not be very useful. This
is because using an adjacency matrix will take up a lot of space where most of the
elements will be 0, anyway. In such cases, using an adjacency list is better.
Note: A sparse matrix is a matrix in which most of the elements are zero, whereas a
dense matrix is a matrix in which most of the elements are non-zero.

Consider the same undirected graph from an adjacency matrix. The adjacency list of the
graph is as follows:
A1 → 2 → 4

A2 → 1 → 3

A3 → 2 → 4
A4 → 1 → 3

Consider the same directed graph from an adjacency matrix. The adjacency list of the
graph is as follows:
A1 → 2

A2 → 4

A3 → 1 → 4

A4 → 2
 Lecture-23
Topological Sorting:
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices
such that for every directed edge uv, vertex u comes before v in the
ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
For example, a topological sorting of the following graph is ―5 4 2 3 1 0‖. There can be
more than one topological sorting for a graph. For example, another topological sorting
of the following graph is ―4 5 2 3 1 0‖. The first vertex in topological sorting is always a
vertex with in-degree as 0 (a vertex with no in-coming edges).
Algorithm to find Topological Sorting:
In DFS, we start from a vertex, we first print it and then recursively call DFS for its
adjacent vertices. In topological sorting, we use a temporary stack. We don‘t print the
vertex immediately, we first recursively call topological sorting for all its adjacent
vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is
pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so
on) are already in stack.
Topological Sorting vs Depth First Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In
topological sorting, we need to print a vertex before its adjacent vertices. For example,
in the given graph, the vertex ‗5‘ should be printed before vertex ‗0‘, but unlike DFS, the
vertex ‗4‘ should also be printed before vertex ‗0‘. So Topological sorting is different
from DFS. For example, a DFS of the shown graph is ―5 2 3 1 0 4‖, but it is not a

topological sorting
Dynamic Programming
The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The
problem is to find shortest distances between every pair of vertices in a given edge
weighted directed Graph.
Example:
Input:
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0} }
which represents the following graph
10
 (0) ------ >(3)
| /|\
5| |
| |1
\|/ |
(1) ------ >(2)
3
Note that the value of graph[i][j] is 0 if i is equal to j
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.

Output:
Shortest distance matrix
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
Floyd Warshall Algorithm

We initialize the solution matrix same as the input graph matrix as a first step. Then we
update the solution matrix by considering all vertices as an intermediate vertex. The
idea is to one by one pick all vertices and update all shortest paths which include the
picked vertex as an intermediate vertex in the shortest path. When we pick vertex
number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1}
as intermediate vertices. For every pair (i, j) of source and destination vertices
respectively, there are two possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of
dist[i][j] as it is.
2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j]
as dist[i][k] + dist[k][j].
The following figure shows the above optimal substructure property in the all-pairs
shortest path problem.
 Lecture-24
Bubble Sort
We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're
keeping it short and precise.

Bubble sort starts with very first two elements, comparing them to check which one is
greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we
compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one
iteration, the array should look like this −

To be precise, we are now showing how an array should look like after each iteration.
After the second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sorts learns that an array is completely
sorted.

Now we should look into some practical aspects of bubble sort.

Algorithm
We assume list is an array of n elements. We further assume that swapfunction
swaps the values of the given array elements.
begin BubbleSort(list)

for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for

return list

end BubbleSort
Pseudocode
We observe in algorithm that Bubble Sort compares each pair of array element unless
the whole array is completely sorted in an ascending order. This may cause a few
complexity issues like what if the array needs no more swapping as all the elements
are already ascending.
To ease-out the issue, we use one flag variable swapped which will help us see if any
swap has happened or not. If no swap has occurred, i.e. the array requires no more
processing to be sorted, it will come out of the loop.
Pseudocode of BubbleSort algorithm can be written as follows −
procedure bubbleSort( list : array of items )

loop = list.count;

for i = 0 to loop-1 do:

swapped = false
 for j = 0 to loop-1 do:

/* compare the adjacent elements */

if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if

end for

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped) then

break
end if

end for

end procedure return list

 Lecture-25
Insertion Sort
We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted
sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see
that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the
sorted sub-list remains sorted after swapping.

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.

So we swap them.

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.

This process goes on until all the unsorted values are covered in a sorted sub-list. Now
we shall see some programming aspects of insertion sort.

Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive
simple steps by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Pseudocode
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
valueToInsert = A[i]
holePosition = i

while holePosition > 0 and A[holePosition-1] > valueToInsert do:

A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
A[holePosition] = valueToInsert

end for
end procedure
 Lecture-26
Selection Sort
Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first
position where 14 is stored presently, we search the whole list and find that 10 is the
lowest value.

So we replace 14 with 10. After one iteration 10, which happens to be the minimum
value in the list, appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a
linear manner.

We find that 14 is the second lowest value in the list and it should appear at the second
place. We swap these values.

After two iterations, two least values are positioned at the beginning in a sorted
manner.

The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −
Now, let us learn some programming aspects of selection sort.

Algorithm

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted
Pseudocode

procedure selection sort

list : array of items
n : size of list

for i = 1 to n - 1
/* set current element as minimum*/
min = i

/* check the element to be minimum */

for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for

/* swap the minimum element with the current element*/

if indexMin != i then
swap list[min] and list[i]
end if
end for

end procedure
 Lecture-27
Merge Sort
To understand merge sort, we take an unsorted array as the following −

We know that merge sort first divides the whole array iteratively into equal halves
unless the atomic values are achieved. We see here that an array of 8 items is divided
into two arrays of size 4.

This does not change the sequence of appearance of items in the original. Now we
divide these two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more be
divided.

Now, we combine them in exactly the same manner as they were broken down. Please
note the color codes given to these lists.
We first compare the element for each list and then combine them into another list in a
sorted manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10
and in the target list of 2 values we put 10 first, followed by 27. We change the order of
19 and 35 whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values, and
merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this −

Now we should learn some programming aspects of merge sorting.

Algorithm
Merge sort keeps on dividing the list into equal halves until it can no more be divided.
By definition, if it is only one element in the list, it is sorted. Then, merge sort combines
the smaller sorted lists keeping the new list sorted too.
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
Merge sort works with recursion and we shall see our implementation in the same way.
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while

while ( a has elements )

add a[0] to the end of c
remove a[0] from a
end while

while ( b has elements )

add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
 Lecture-28
Quick sort
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of
data into smaller arrays. A large array is partitioned into two arrays one of which holds
values smaller than the specified value, say pivot, based on which the partition is made
and another array holds values greater than the pivot value.
Quick sort partitions an array and then calls itself recursively twice to sort the two
resulting subarrays. This algorithm is quite efficient for large-sized data sets as its
average and worst case complexity are of Ο(n2), where n is the number of items.
Partition in Quick Sort
Following animated representation explains how to find the pivot value in an array.

The pivot value divides the list into two parts. And recursively, we find the pivot for
each sub-lists until all lists contains only one element.
Quick Sort Pivot Algorithm
Based on our understanding of partitioning in quick sort, we will now try to write an
algorithm for it, which is as follows.
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
Quick Sort Pivot Pseudocode
The pseudocode for the above algorithm can be derived as −
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1

while True do
while A[++leftPointer] < pivot do
 //do-nothing
end while

while rightPointer > 0 && A[--rightPointer] > pivot do

//do-nothing
end while

if leftPointer >= rightPointer

break
else
swap leftPointer,rightPointer
end if

end while

swap leftPointer,right
return leftPointer

end function
Quick Sort Algorithm
Using pivot algorithm recursively, we end up with smaller possible partitions. Each
partition is then processed for quick sort. We define recursive algorithm for quicksort as
follows −
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively
Quick Sort Pseudocode
To get more into it, let see the pseudocode for quick sort algorithm −
procedure quickSort(left, right)

if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
 Lecture-29
Heap Sort
Heap sort is a comparison based sorting technique based on Binary Heap data
structure. It is similar to selection sort where we first find the maximum element and
place the maximum element at the end. We repeat the same process for remaining
element.
What is Binary Heap?

Let us first define a Complete Binary Tree. A complete binary tree is a binary tree in
which every level, except possibly the last, is completely filled, and all nodes are as far
left as possible
A Binary Heap is a Complete Binary Tree where items are stored in a special order
such that value in a parent node is greater(or smaller) than the values in its two children
nodes. The former is called as max heap and the latter is called min heap. The heap
can be represented by binary tree or array.
Why array based representation for Binary Heap?

Since a Binary Heap is a Complete Binary Tree, it can be easily represented as array
and array based representation is space efficient. If the parent node is stored at index I,
the left child can be calculated by 2 * I + 1 and right child by 2 * I + 2 (assuming the
indexing starts at 0).
Heap Sort Algorithm for sorting in increasing order:

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last
item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of
tree.
3. Repeat above steps while size of heap is greater than 1.
How to build the heap?

Heapify procedure can be applied to a node only if its children nodes are heapified. So
the heapification must be performed in the bottom up order.
Lets understand with the help of an example:
Input data: 4, 10, 3, 5, 1
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)

The numbers in bracket represent the indices in the array

representation of data.
Applying heapify procedure to index 1:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)

Applying heapify procedure to index 0:

10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
The heapify procedure calls itself recursively to build heap
in top down manner.
Radix Sort
The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort,
Quick-Sort .. etc) is Ω(nLogn), i.e., they cannot do better than nLogn.
Counting sort is a linear time sorting algorithm that sort in O(n+k) time when elements
are in range from 1 to k.
What if the elements are in range from 1 to n2?

We can‘t use counting sort because counting sort will take O(n 2) which is worse than
comparison based sorting algorithms. Can we sort such an array in linear time?
Radix Sort is the answer. The idea of Radix Sort is to do digit by digit sort starting from
least significant digit to most significant digit. Radix sort uses counting sort as a
subroutine to sort.
 Lecture-30
Radix Sort

1) Do following for each digit i where i varies from least significant digit to the most
significant digit.
… ..............a) Sort input array using counting sort (or any stable sort) according to the i‘th
digit.
Example:
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1s place) gives: [*Notice that we keep 802 before 2,
because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and
45 & 75.]
170, 90, 802, 2, 24, 45, 75, 66
Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802
comes before 2 in the previous list.]
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
What is the running time of Radix Sort?
Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the
base for representing numbers, for example, for decimal system, b is 10. What is the
value of d? If k is the maximum possible value, then d would be O(log b(k)). So overall
time complexity is O((n+b) * logb(k)). Which looks more than the time complexity of
comparison based sorting algorithms for a large k. Let us first limit k. Let k <= n c where
c is a constant. In that case, the complexity becomes O(nLog b(n)). But it still doesn‘t
beat comparison based sorting algorithms.

Linear Search

Linear search is to check each element one by one in sequence. The following
method linearSearch() searches a target in an array and returns the index of the target; if
not found, it returns -1, which indicates an invalid index.
1 int linearSearch(int arr[], int target)
2 {
3 for (int i = 0; i < arr.length; i++)
4 {
5 if (arr[i] == target)
6 return i;
7 }
8 return -1;
9 }
 Linear search loops through each element in the array; each loop body takes constant
time. Therefore, it runs in linear time O(n).

Lecture-31

Binary Search

For sorted arrays, binary search is more efficient than linear search. The process starts
from the middle of the input array:
 If the target equals the element in the middle, return its index.
 If the target is larger than the element in the middle, search the right half.
 If the target is smaller, search the left half.
In the following binarySearch() method, the two index variables first and last indicates the
searching boundary at each round.
1 int binarySearch(int arr[], int target)
2 {
3 int first = 0, last = arr.length - 1;
4
5 while (first <= last)
6 {
7 int mid = (first + last) / 2;
8 if (target == arr[mid])
9 return mid;
10 if (target > arr[mid])
11 first = mid + 1;
12 else
13 last = mid - 1;
14 }
15 return -1;
16 }
1 arr: {3, 9, 10, 27, 38, 43, 82}
2
3 target: 10
4 first: 0, last: 6, mid: 3, arr[mid]: 27 -- go left
5 first: 0, last: 2, mid: 1, arr[mid]: 9 -- go right
6 first: 2, last: 2, mid: 2, arr[mid]: 10 -- found
7
8 target: 40
9 first: 0, last: 6, mid: 3, arr[mid]: 27 -- go right
10 first: 4, last: 6, mid: 5, arr[mid]: 43 -- go left
11 first: 4, last: 4, mid: 4, arr[mid]: 38 -- go right
12 first: 5, last: 4 -- not found
Binary search divides the array in the middle at each round of the loop. Suppose the
array has length n and the loop runs in t rounds, then we have n * (1/2)^t = 1 since at
each round the array length is divided by 2. Thus t = log(n). At each round, the loop
body takes constant time. Therefore, binary search runs in logarithmic time O(log n).
The following code implements binary search using recursion. To call the method, we
need provide with the boundary indexes, for example,
binarySearch(arr, 0, arr.length - 1, target);
1
2 binarySearch(int arr[], int first, int last, int target)
3 {
4 if (first > last)
5 return -1;
6
7 int mid = (first + last) / 2;
8
9 if (target == arr[mid])
10 return mid;
11 if (target > arr[mid])
12 return binarySearch(arr, mid + 1, last, target);
13 // target < arr[mid]
14 return binarySearch(arr, first, mid - 1, target);
15 }
 Lecture-32
Hashing

Introduction

The problem at hands is to speed up

searching. Consider the problem of
searching an array for a given value. If
the array is not sorted, the search might
require examining each and all
elements of the array. If the array is
sorted, we can use the binary search,
and therefore reduce the worse-case
runtime complexity to O(log n). We
could search even faster if we know in
advance the index at which that value is
located in the array. Suppose we do
have that magic function that would tell
us the index for a given value. With this
magic function our search is reduced to
just one probe, giving us a constant
runtime O(1). Such a function is called
a hash function . A hash function is a
function which when given a key,
generates an address in the table.
The example of a hash function is a book call number. Each book in the library has
a unique call number. A call number is like an address: it tells us where the book is
located in the library. Many academic libraries in the United States, uses Library of
Congress Classification for call numbers. This system uses a combination of letters and
numbers to arrange materials by subjects.
A hash function that returns a unique hash number is called a universal hash function.
In practice it is extremely hard to assign unique numbers to objects. The later is always
possible only if you know (or approximate) the number of objects to be proccessed.
Thus, we say that our hash function has the following properties
 it always returns a number for an object.
 two equal objects will always have the same number
 two unequal objects not always have different numbers
The precedure of storing objets using a hash function is the following.
Create an array of size M. Choose a hash function h, that is a mapping from
objects into integers 0, 1, ..., M-1. Put these objects into an array at indexes
computed via the hash function index = h(object). Such array is called a hash
table.
Collisions

When we put objects into a hashtable, it is possible that different objects (by
the equals() method) might have the same hashcode. This is called a collision. Here is
the example of collision. Two different strings ""Aa" and "BB" have the same key: .
"Aa" = 'A' * 31 + 'a' = 2112
"BB" = 'B' * 31 + 'B' = 2112

How to resolve collisions? Where do we put

the second and subsequent values that hash
to this same location? There are several
approaches in dealing with collisions. One of
them is based on idea of putting the keys that
collide in a linked list! A hash table then is an
array of lists!! This technique is called
a separate chaining collision resolution.

The big attraction of using a hash table is a constant-time performance for the basic
operations add, remove, contains, size. Though, because of collisions, we cannot guarantee
the constant runtime in the worst-case. Why? Imagine that all our objects collide into the
same index. Then searching for one of them will be equivalent to searching in a list, that
takes a liner runtime. However, we can guarantee an expected constant runtime, if we
make sure that our lists won't become too long. This is usually implemnted by
maintaining a load factor that keeps a track of the average length of lists. If a load factor
approaches a set in advanced threshold, we create a bigger array and rehash all
elements from the old table into the new one.
Another technique of collision resolution is a linear probing. If we cannoit insert at index
k, we try the next slot k+1. If that one is occupied, we go to k+2, and so on.
 Lecture-33
Hashing Functions
Choosing a good hashing function, h(k), is essential for hash-table based
searching. h should distribute the elements of our collection as uniformly as possible to
the "slots" of the hash table. The key criterion is that there should be a minimum
number of collisions.
If the probability that a key, k, occurs in our collection is P(k), then if there are m slots in
our hash table, a uniform hashing function, h(k), would ensure:

Sometimes, this is easy to ensure. For example, if the keys are randomly distributed in
(0,r], then,
h(k) = floor((mk)/r)
will provide uniform hashing.
Mapping keys to natural numbers
Most hashing functions will first map the keys to some set of natural numbers, say (0,r].
There are many ways to do this, for example if the key is a string of ASCII characters,
we can simply add the ASCII representations of the characters mod 255 to produce a
number in (0,255) - or we could xor them, or we could add them in pairs mod 216-1, or
...
Having mapped the keys to a set of natural numbers, we then have a number of
possibilities.
1. Use a mod function:
h(k) = k mod m.
When using this method, we usually avoid certain values of m. Powers of 2 are
usually avoided, for k mod 2b simply selects the b low order bits of k. Unless we
know that all the 2b possible values of the lower order bits are equally likely, this
will not be a good choice, because some bits of the key are not used in the hash
function.
Prime numbers which are close to powers of 2 seem to be generally good
choices for m.
For example, if we have 4000 elements, and we have chosen an overflow table
organization, but wish to have the probability of collisions quite low, then we
might choose m = 4093. (4093 is the largest prime less than 4096 = 212.)
2. Use the multiplication method:
o Multiply the key by a constant A, 0 < A < 1,
o Extract the fractional part of the product,
o Multiply this value by m.
Thus the hash function is:
h(k) = floor(m * (kA - floor(kA)))
 In this case, the value of m is not critical and we typically choose a power of 2 so
that we can get the following efficient procedure on most digital computers:
p
o Choose m = 2 .
w
o Multiply the w bits of k by floor(A * 2 ) to obtain a 2w bit product.
o Extract the p most significant bits of the lower half of this product.
It seems that:
A = (sqrt(5)-1)/2 = 0.6180339887
is a good choice (see Knuth, "Sorting and Searching", v. 3 of "The Art of
Computer Programming").
3. Use universal hashing:
A malicious adversary can always chose the keys so that they all hash to the
same slot, leading to an average O(n) retrieval time. Universal hashing seeks to
avoid this by choosing the hashing function randomly from a collection of hash
functions (cf Cormen et al, p 229- ). This makes the probability that the hash
function will generate poor behaviour small and produces good average
performance.