!)0,('(.
)
%,(.

%

*,-,#
.2.))%

 


# 
 
REVISED EDITION
2017

Department of Pre-University Education

Malleshwaram, Bengaluru - 560 012
www.pue.kar.nic.in

I
 Director’s Message

Dear Students,

We at the Department of Pre-university Education,

Karnataka strive to empower each student to dream big
and equip them with the tools that enable them to reach
new heights and successfully deal with the challenges of
life. As Swami Vivekananda said, "Real education is that
which enables one to stand on one's own legs".

The course contents in this book are designed with

the objective of equipping you well for the next level of
study.

We wish you well on your journey and look forward to

you becoming a responsible citizen of the nation and give
back to the betterment of the society.

With best wishes,

Sd/-
C. Shikha, IAS
Director
Department of Pre University Education
Bengaluru
II
 Preface
Dr. P. Nagabhushan
BE,MTech,Phd,FIE,FIETE
Professor, Department of Studies in Computer Science
Chief Nodal Officer,
University of Mysore, Mysore-570 006

I am pleased to understand that Department of Pre-University Education,

Govt. of Karnataka, took up an important academic exercise to revise the
syllabi and accordingly came out with an appropriate text book, which is
jointly authored by a committee of qualified and experienced faculty
members drawn across Karnataka state.
The committee of authors consisted of Sri. Rajappa, Empress Govt. PU
College, Tumkur, as the Chairperson and Sri. Santus Xavio B K, Stracey
Memorial PU College, Bengaluru as the Co-ordinator and Sri Nagaraje Urs,
Maharaja Govt. PU College, Mysore, Smt. M R Nagamani, SBRR Mahajana
PU College Mysore, Sri Ravindra K V, Govt. PU College, Sagara, Smt. Sharon
Mednora, Govt PU College, Malleshwaram, Bengaluru, Sri. Naveen Kumar
B, Govt. PU College for Girls, Malleshwaram, Bangalore and Smt. Padmashree
R, NMKRV PU college, Bengaluru, as the members. When the committee
members met me for seeking my remarks on the draft syllabus proposed, I
felt comfortable to see the balanced distribution of topics to serve the needs
of Commerce as well as Science students of PU Education. The spread and
the organisation of the syllabus is quite good and care has been taken to
see that the contents in Second Year Pre-University Course is properly
placed as an extension to First PUC. The committee has ensured that the
entire syllabus is on par with NCERT.
The committee has put its best effort to provide a comprehensive coverage
of both theoretical and practical aspects and also have paid careful attention
to make the learners to acquire necessary skills, which makes the learners
feel comfortable to work with the machine.
I am happy to understand that the draft book is thoroughly reviewed by
Dr. Somashekara M T, Bengaluru University and also by prof. Mukundappa,
Tumkur University. The exercise problems set by the authors at the end of
every chapter are good enough to keep the interests of the learners alive.
I commend the excellent collective effort put by the committee of authors
and also the two reviewers, and I am confident Second year PUC students
of Karnataka would be greatly benefitted.

III
Computer Science Syllabus Review and Textbook Development
Committee
Department of Pre-University Education, Govt. of Karnataka

AUTHORS

Rajappa
Chairperson
Empress Govt. Pre-University College
Tumakuru
Co-ordinator:
Santus Xavio B K
Lecturer
Stracey Memorial Pre-University College
#52, St. Marks' Road, Bengaluru
Members:
Nagaraje Urs
Lecturer
Maharaja Govt. Pre-University College
JLB Road, Mysore
Sharon Mednora
Lecturer
Govt. Pre-University College
18th Cross, Malleshwaram
Bengaluru
Ravindra K V
Lecturer
Govt. Pre-University College
Sagara, Shimoga District
Nagamani M R
Lecturer
SBRR Mahajana Pre-University College
Jayalakshmipuram, Mysore
Padmashree R
Lecturer
NMKRV Pre-University College
Jayanagar, Bengaluru

IV
 Acknowledgements
I am very fortunate to have esteemed personality Dr. Nagabhushan P,
Professor, Dept. of Computer Science, Manasagangothri, University of
Mysore who guided us in shaping the syllabus. We are also grateful to
our reviewers Dr. Somashekar M T, Associate Professor, Dept. of Com-
puter Science, Bengaluru University and Prof. Mukundappa , HOD, Dept.
of Computer Science, University Science College, Tumkur. I whole
heartedly thank them personally and on behalf of the committee.

I acknowledge Sri. Marulaiah B, Principal, Empress Govt. PU College,

Tumkur for his outstanding encouragement. I also thank A B Jagadish,
P r i n c i p a
th
l Cross, Malleshwaram, Bengaluru who
, G o v t . P U C o l l e g e , 1 8

helped us by providing the Computer Science laboratory. I also thank the

College Management, SBMM Mahajana PU College, Jayalakshmipuram,
Mysore for their support. We thank Dr. Serkad Arunachalam Kribanandan,
Principal, Stracey Memorial PU College, Bengaluru for his overall support
rendered to us.

I proudly remember the service of Mr. Nagendrakumar K M, Lecturer,

Govt. First Grade College, Tumkur who did fine DTP work amidst his busy
engagements. I also thank Mr. Armstrong .M, former syllabus committee
member, for his valuable suggestions and corrections.

I also recall the support of my wife Shylaja. Last but not least, I acknowl-
edge the support of family and friends of our committee members who
directly or indirectly helped us in bringing out this text book.
Rajappa
Chairperson
Computer Science Syllabus Review and
Textbook Development Committee
Department of Pre-University Education
Govt. of Karnataka

V
 Government of Karnataka
Computer Science Syllabus Review Committee
Department of Pre-University Education, Bengaluru
Rajappa Santus Xavio B K
Chairperson Co-ordinator
Empress Govt. Pre-University College Stracey Memorial PU College
Tumakuru Bengaluru
e-mail: rajappatumkur @gmail.com [email protected]

Reviewers:
Dr. Nagabhushan P, Dept. of Computer Science, Manasagangothri, Mysore
Dr. Somashekar M T, Dept. Computer Science, Gnanabharathi, Bengaluru
Prof. Mukundappa, HOD, Dept of Computer Science, University Science
College, Tumkur
Members:
Nagaraje Urs
Lecturer
Maharaja Govt. Pre-University College
JLB Road, Mysore
Sharon Mednora
Lecturer
Govt. Pre-University College
18th Cross, Malleshwaram, Bengaluru
Ravindra K V
Lecturer
Govt. Pre-University College
Sagara, Shimoga District
Naveen Kumar B
Lecturer
Govt. Pre-University College
13th Cross, Malleshwaram, Bengaluru
Nagamani M R
Lecturer
SBRR Mahajana Pre-University College
Jayalakshmipuram, Mysore
Padmashree R
Lecturer
NMKRV Pre-University College
Jayanagar, Bengaluru

VI
Chapter No Topics Page No.
UNIT A BACKDROP OF COMPUTERS 35 Hrs
Chapter 1 Typical configuration of Computer system 1
1.1 Introduction 2
1.2 Motherboard 4
1.2.1 Introduction to Motherboard 4
1.2.2 Types of Motherboards 5
1.2.3 Components of Motherboard 6
1.3 Memory 15
1.4 Power supply to the computer system 18
1.5 Assembling the computer system 19
Chapter 2 Boolean Algebra 24
2.1 Introduction 25
2.2 Binary valued quantities-constants and variables 25
2.3 Logical operations 26
2.3.1 Logical functions or compound statements 26
2.3.2 Logical operators 26
2.4 Evaluation of Boolean expressions using truth table 29
2.4.1 Basic logic gates 34
2.5 Basic postulates of Boolean Algebra (with proof ) 36
2.5.1 Properties of 0 and 1 38
2.5.2 Indempotence law 41
2.5.3 Involution law 42
2.5.4 Complementarity law 43
2.5.5 Commutative law 44
2.5.6 Associative law 46
2.5.7 Distributive law-different forms 47
2.5.8 Absorption law 48
2.6 De Morgan’s theorems 50
2.6.1 De Morgan’s I theorem 50
2.6.2 De Morgan’s II theorem 51
2.6.3 Applications of De Morgan’s theorems 53
2.6.4 Basic duality of Boolean algebra 53
2.7 Derivation of Boolean expressions 54
2.7.1 Min terms 54
2.7.2 Max terms 57
2.7.3 Canonical expressions 57
2.7.4 Minimization of Boolean expressions 64
2.8 Simplification using Karnaugh map 65
2.8.1 Sum-of-product reduction using Karnaugh map 66
2.8.2 Product-of-sum reduction using Karnaugh map 76

VII
Chapter 3 Logic gates 86
3.1 Introduction 87
3.1.1 Invertor (NOT gate) 87
3.1.2 OR gate 88
3.1.3 AND Gate 89
3.2 Derived Gates 90
3.2.1 NOR Gate 90
3.2.2 NAND Gate 91
3.2.3 XOR Gate 91
3.2.4 XNOR Gate 93
3.2.5 Circuit diagram 94
3.2.6 NAND,NOR as universal Gates 95
Chapter 4 DATA STRUCTURE 103
4.1 Introduction 104
4.2 Data representation 104
4.3 Classification of Data structures 105
4.3.1 Primitive Data structure 105
4.3.2 Operations on primitive data structures 106
4.3.3 Non-primitive Data structures 106
4.3.4 Linear data structure 107
4.3.5 Non-Linear data structure 107
4.4 Operations on linear data structures 107
4.5 Arrays 107
4.5.1 Types of array Memory representation of data 108
4.5.2 One dimensional array 109
4.5.3 Memory representation one dimensional array 109
4.5.4 Basic operations on one-dimensional array 109
4.5.5 Traversing using one dimension array 110
4.5.6 Searching an element 111
4.5.7 Insertion of an element 114
4.5.8 Deletion of an element 116
4.5.9 Sorting the elements 118
4.5.10 Two dimension Array 119
4.6 Stacks 123
4.6.1 Introduction 123
4.6.2 Representation of stacks in memory 124
4.6.3 Operations on stacks 127
4.6.4 Applications of Stacks 128
4.7 Queues 133
4.7.1 Introduction 133
4.7.2 Types of Queues 134

VIII
 4.7.3 Operations on queues 136
4.7.4 Memory representation of queues 136
4.7.5 Applications of Queues 138
4.8 Linked lists 139
4.8.1 Introduction 139
4.8.2 Types of linked list 139
4.8.3 Operations on single linked lists 141
4.9 Non-Linear data structure 153
4.9.1 Introduction 153
4.9.2 Trees 153
4.9.3 Graphs 155
UNIT B COMPUTING IN C++ 45 Hrs
Chapter 5 Review of C++ 158
5.1 Review of c++ language 158
5.2 Fundementals of c++ 160
5.3 Structure of c++ program 164
5.4 Libraray functions 164
5.5 Data types 165
5.6 Input and output operations 166
5.7 Control statements 167
5.8 Arrays 169
5.9 Functions 172
5.10 User-defined Functions 175
5.11 Structures 180
Chapter 6 Basic concepts of OOP 181
6.1 Introduction 182
6.2 Basic concepts of OOP 183
6.2.1 Objects 183
6.2.2 classses 183
6.2.3 Data Abstraction 184
6.2.4 Data Encapsulation 184
6.2.5 Inheritance 184
6.2.6 Overloading 185
6.2.7 Polymorphism 185
6.2.8 Dynamic Biding 185
6.2.9 Message passing 185
6.3 Advantages of OOP over earlier programming methods 186
6.4 Limitations of OOP 186
6.5 Applications of OOP 186

IX
Chapter 7 Classes and objects 189
7.1 Introduction 190
7.2 Definition and declaration of classes and objects 191
7.3 Access specifiers (scope of class & its members) 193
7.3.1 Private 193
7.3.2 Public 193
7.3.3 Protected 194
7.4 Members of the class 194
7.5 Member functions 196
7.5.1 Member functions inside class definition 196
7.5.2 Member functions out side class definition 196
7.6 Defining objects of a class 198
7.7 Arrays as members of class 199
7.8 Array of objects 200
7.9 Objects as function arguments 202
7.10 Diffrences between structures and classes in C++ 204
Chapter 8 Function overloading 207
8.1 Introduction 208
8.2 Need for function overloading 208
8.3 Definition and declaration of overloaded function 208
8.4 Restrictions on overloaded function 209
8.4.1 Calling over loaded functions 209
8.5 Other functions in a class 210
8.5.1 Inline function 211
8.5.2 Friend function 212
Chapter 9 Constructor and Destructor 216
9.1 Introduction 217
9.2 Declaration and definition of constructor 218
9.3 Types of constructors 219
9.3.1 Default constructor 219
9.3.2 Parameterized constructor 221
9.3.3 Copy constructor 224
9.4 Constructor overloading 227
9.5 Destructor 228
Chapter 10 Inheritance(Extending classes) 232
10.1 Introduction 233
10.2 Base class 233
10.3 Derived class 233
10.3.1 Defining derived class 233
10.3.2 Public derived class 234
10.3.3 Private derived class 235

X
 10.3.4 Protected dervied class 235
10.4 Visibility modes 235
10.4.1 Public inheritance 235
10.4.2 Private inheritance 236
10.4.3 Protected inheritance 236
10.5 Levels of inheritance 236
10.5.1 Single level inheritance 237
10.5.2 Multilevel inheritance 237
10.5.3 Multiple inheritance 238
10.5.4 Hierarchical inheritance 238
10.5.5 Hybrid inheritance 238
10.6 Relationship between classes 240
10.6.1 Virtual base classes 240
10.6.2 Abstract classes 242
10.6.3 Constructors in Derived classses 242
10.6.4 Destructors in Dervied classes 243
Chapter 11 Pointers 247
11.1 Introduction 248
11.2 Memory representation of pointers 248
11.3 Declaration & initialization of pointers 249
11.4 Address operator 249
11.5 Pointer operator(indirection operator) 250
11.6 Pointer arithmetic 250
11.7 Pointer and arrays 251
11.8 Arrays of pointers 252
11.9 Pointers to strings 253
11.10 Pointer as function parameters 253
11.11 Pointer and structures 254
11.12 Memory allocation of pointers(static and dynamic) 254
11.12.1 Static allocation of memory 254
11.12.2 Dynamic allocation of memory-new and delete 254
11.13 Free store (heap memory) 256
11.14 Memory leak 256
11.15 Self Referential Structure 256
11.16 Pointers and functions 257
11.16.1 Invoking functions by passing the references 257
11.16.2 Invoking functions by passing the pointers 258
11.17 Memory comes and memory goes 260
11.18 Pointer and objects 260
11.19 this pointer 261

XI
Chapter 12 Data file handling 266
12.1 Introduction 267
12.2 Header files(fstream.h) 268
12.2.1 Classes for file stream operation 269
12.3 Types of data files 270
12.3.1 Text file 270
12.3.2 Binary file 270
12.4 Opening & closing files 270
12.4.1 Opening file using constructor 270
12.4.2 Using open() 271
12.4.3 File modes -In ,out, app modes 272
12.4.4 closing files 273
12.5 Input and output operation in text files 273
12.6 Detecting end of file 275
12.7 File pointers -tellg(), tellp(), seekg(), seekp() functions 275
UNIT C LARGE DATA, DATABASE & QUERIES 20 HRs
Chapter 13 Database Concepts 282
13.1 Introduction 283
13.2 Appllications of database 284
13.3 Origin of Data : Facts,data,information,features 284
13.4 Evolution of database 285
13.5 Data processing cycle 286
13.6 Data base terms 287
13.7 Data Types in DBMS 288
13.8 DBMS 289
13.9 Data abstraction 291
13.10 Data independence 293
13.11 Database Model 298
13.11.1 Hierarchial data model 299
13.11.2 Network data Model 300
13.11.3 Relational Data model 301
13.12 Codd's Rules 302
13.13 Logical data concepts 304
13.13.1 Normalization 304
13.13.2 Entity-relationship Model 308
13.13.3 Cardinality 313
13.14 KEYS-Primary,Secondary,Candidate,Foreign, Alternate 315
13.15 Relational Algebra 318
13.16 Data warehousing 327
13.17 Data Mining 329

XII
Chapter 14 Structured Query Language 333
14.1 Introduction 334
14.1.1 SQL Architecture 335
14.2 SQL commands 337
14.2.1 DDL 337
14.2.2 DML 338
14.3 Data types in SQL 339
14.3.1 Exact Numeric data types 339
14.3.2 Floating point Numeric data types 339
14.3.3 Date and time data types 339
14.3.4 Character and string data type 340
14.4 Operators in SQL 340
14.4.1 SQL arithemetic operators 340
14.4.2 Comparison operators 341
14.4.3 Logical operators 341
14.5 SQL expressions 342
14.5.1 SQL Boolean Expression 342
14.5.2 SQL Numeric expression 343
14.5.3 Date expression 343
14.6 SQL constraints 344
14.6.1 Primary key 344
14.6.2 Foreign Key or Referential integrity 346
14.6.3 Not NULL constraint 347
14.6.4 Unique Key 347
14.6.5 Check constraint 348
14.7 Implementation of SQL Commands 348
14.7.1 Create table statement 348
14.7.2 Alter 349
14.7.3 Insert Statement 350
14.7.4 Select statement 351
14.7.5 AND operator 353
14.7.6 OR operator 354
14.7.7 Update statement 354
14.7.8 Delete Statement 356
14.7.9 Order by 357
14.7.10 Group by 357
14.7.11 Distinct statement 359
14.7.12 Join 361
14.7.13 NULL 363
14.8.1 Create View 365
14.9.1 Commit 365

XIII
 14.10 DCL commands 365
14.10.1 Grant command 365
14.10.2 Revoke command 366
14.11 Built-In Function 368
14.11.1 Single row function 368
14.11.2 Group function 368
UNIT D ADVANCED CONCEPTS IN COMMUNICATION TECHNOLOGY 20Hrs
Chapter 15 Networking Concepts 375
15.1 Introduction 376
15.1.1 Networking Goals 376
15.1.2 Need of networking 376
15.2.1 Arpanet 376
15.2.2 OSI reference Model 377
15.2.3 TCP/IP 378
15.3.1 HTTP 380
15.3.2 FTP 381
15.3.3 SLIP 381
15.4.1 Internet 381
15.4.2 Interspace 382
15.4.3 Elementary terminologies of networking 382
15.4.4 Types of services 382
15.4.5 Types of networking 383
15.4.6 Networking Topologies 386
15.4.7 Transmission medium 393
15.4.8 Switching techniques 398
15.4.9 Communication modes 399
15.4.10 Networking devices 400
15.5.1 Gateway 403
15.6.1 SIM 404
15.7.1 GPRS 406
15.8.1 Applications of Networking 410
15.8.2 Wi-fi 411
15.9.1 Network security 411
15.10.1 Cookies 413
15.11.1 Virus 413
Chapter 16 Internet and Open source concepts 416
16.1 Introduction 416
16.1.2 Free software 417
16.1.3 Open source software 417
16.1.4 OSS and FLOSS 418

XIV
 16.1.5 GNU 419
16.1.6 FSF 419
16.2.1 OSI 419
16.2.2 W3C 419
16.2.3 Proprietary software 419
16.2.4 www 420
16.2.5 Telnet 420
16.2.6 Web browser 420
16.2.7 Webserver 420
16.2.8 Webpage 421
16.3 URL and domain 421
16.4 E-Commerce 422
16.4.1 Types of E-commerce 424
16.4.2 Advantages of e-commerce 425
16.5 IPR issues 426
Chapter 17 Web designing 428
17.1 Introduction 429
17.1.1 HTML structure 430
17.2.1 Advanced HTML tags/commands 432
17.2.2 Text formating 432
17.2.3 Resizing text 432
17.2.4 Example for resizing text 433
17.2.5 Text layout 434
17.2.6 Number listing 435
17.2.7 Links 437
17.2.8 Inserting images 438
17.2.9 Background 439
17.2.10 Background color and fixed images 440
17.2.11 Tables 440
17.2.12 Frames 442
17.2.13 Forms 443
17.2.14 Settings and text fields 444
17.3.1 Web Hosting 447
17.3.2 Domain registration 448
17.4.1 Uploading HTML file 449
17.5.1 XML 450
17.6.1 DYNAMIC HTML 451
17.7.1 Web scripting 453
Model Question Paper 455

XV
 DESIGN OF QUESTION PAPER

CLASS: SECOND PUC

SUBJECT: COMPUTER SCIENCE (41)

Time : 3Hours 15 Minutes(of which minutes for reading the questions Paper).

Max.Marks:70

The weightage of the distribution of marks over different dimensions of the

question paper shall be as follows:

Weightage to Objectives:

Objective Weightage Marks

Knowledge 30% 31
Understanding 40% 43
Application 20% 21
Skill 10% 10
Total 100% 105

Weight age to Content/Subject units: Computer Science(41)

Unit Description VSA(1 SA(2 LA(3 E(5Marks) Total
Mark) Marks) Marks) Marks
A BACKDROP OF COMPUTERS 3 2 3 3 31
35
Hrs
B COMPUTING IN C++ 2 3 2 5 39
45Hrs
C LARGE DATA, DATABASE & 1 2 1 2 18
20Hrs QUERIES
D ADVANCED CONCEPTS IN 4 1 2 1 17
20Hrs COMMUNICATION
TECHNOLOGY
Total Marks 10 16 24 55 105

120 Total No of Questions to be 1X10=10 2X5/8=10 3X5/8=15 5X7/11=35 70/37

Hrs answered

XVI
 VSA SA LA E Total
UNIT DESCRIPTION
(1 Mark) (2 Marks) (3 Marks) (5 Marks) Marks
BACKDROP OF
A
35 Hrs COMPUTERS 3 2 3 3 31

Chapter 1 Typical
5 Hrs configuration of 1 ------ 1 ------- 4
Computer system
Chapter 2 Boolean algebra
-------- 2 ----- 1 09
10 Hrs
Chapter 3 Logic Gates
1 ------ 1 ------- 04
5 Hrs
Chapter 4 Data structures
1 ------ 1 2 14
15 Hrs
B COMPUTING IN
C++ 2 3 2 5 39
45Hrs
Chapter 5 Review of C++
3 Hrs covered in First ------- ------- ------- ------ ----
PUC
Chapter 6 OOP concepts
---- 1 ---- 1 07
4 Hrs
Chapter 7 Classes and objects
1 ------ ----- 1 06
6 Hrs
Chapter 8 Function
------ ------ ------ 1 05
3 Hrs Overloading
Chapter 9 Constructors and
---- 1 ---- 1 07
8 Hrs Destructors
Chapter 10 Inheritance
------ ----- ------ 1 05
8 Hrs
Chapter 11 Pointers
1 ----- 1 ------ 04
7 Hrs
Chapter 12 Data File handling
------- 1 1 ------ 05
6 Hrs
LARGE DATA,
C
DATABASE & 1 2 1 2 18
20Hrs
QUERIES
Chapter 13 Database concepts
1 1 1 1 11
8 Hrs
Chapter 14 SQL commands
------- 1 ----- 1 07
12 Hrs
ADVANCED
D CONCEPTS IN
4 1 2 1 17
20Hrs COMMUNICATIO
N TECHNOLOGY
Chapter 15 Networking
2 1 ---- 1 9
10 Hrs Concepts
Chapter 16 Internet and Open
1 ---- 1 ----- 4
5 Hrs source concepts
Chapter 17 Web Designing
5 Hrs 1 ----- 1 ------ 4

Total Marks
10 16 24 55 105
Total No of
Questions to be 1X 10=10 2X 5/8=10 3X5/8=15 5X7/11=35 70/37
answered

XVII
 List of programs to be conducted in practical sessions
Section A C++ and Data structure
1. Write a program to find the frequency of presence an element in an array.
2. Write a program to insert an element into an array at a given position.
3. Write a program to delete an element from an array from a given position
4. Write a program to sort the elements of an array in ascending order using
insertion sort.
5. Write a program to search for a given element in an array using Binary
search method.
6. Write a program to create a class with data members principle, time and
rate. Create member functions to accept data values to compute simple
interest and to display the result.
7. Write a program to create a class with data members a, b, c and member
functions to input data, compute the discriminant based on the following
conditions and print the roots.
 If determinant=0, print the roots that are equal
 If the discriminant is>0, print the real roots
 If the discriminant<0, print that the roots are imaginary
8. Program to find the area of a square/rectangle/triangle using function
overloading.
9. Program to find the cube of a number using inline functions.
10. Write a program to find the sum of the series 1+ x + x2 + … + xn using
constructors.
11. Create a base class containing the data members roll number and name.
Also create a member function to read and display the data using the
concept of single level inheritance. Create a derived class that contains
marks of two subjects and total marks as the data members.
12. Create a class containing the following data members register No., name
and fees. Also create a member function to read and display the data
using the concept of pointers to objects.
13. Write a program to perform push items into the stack.
14. Write a program to pop elements from the stack.
15. Write a program to perform enqueue and dequeue.
16. Write a program t o create a linked list and appending nodes.
Section B SQL
17. Generate the Electricity Bill for one consumer
18. Create a student database and compute the result.
19 Generate the Employee details and compute the salary based on the
department.
20. Create database for the bank transaction.
Section C HTML
21. Write a HTML program to create a study time-table.
22. Create an HTML program with table and Form.

XVIII
Typical configuration of computer system 1

Chapter 1
Typical Configuration of Computer system

Objectives

 To understand various units of a computer system

 To recognize various components of the motherboard
 To analyze the configuration of todays' computer system
 Insight to assemble a computer system
 2 Typical configuration of computer system

1.1 Introduction:
The computer has evolved as a result of man’s search for fast, accurate
calculating devices. Computers have thus become an integral part of everyone’s
life and useful in many ways by increasing man’s efficiency and enhancing his
abilities.
Computers are used to perform various tasks in different fields like science,
engineering, business, education, training, entertainment. The computer works
at high speed, can handle large volumes of data with greater accuracy and have
the ability to carry out a specified sequence of operations without human
intervention.
The term computer basically includes a series of electrical and electronic
circuits together to form a single unit to perform the required operations for the
user. The computer has no intelligence of its own and thus cannot perform any
task by itself. Thus it requires the hardware, software, data and users which
form the computer system to perform the different operations.
The related terms and definitions in the study of computer systems are:

 Hardware consists of physical devices of the computer such as

keyboard, monitor, printer, processor and motherboard.
 Software consists of set of instructions called programs that instructs
the computer the tasks to be performed and how it should be
performed.
 Data are values or raw facts which are provided as input to the
computer, then processed to generate some meaningful information.
 Users are people who write computer programs or interact with the
computer.

Review of block diagram of Computer system

The computer system comprises of four main units which can be seen in
the block diagram given below. They are,
Central processing unit
1. Input Unit,
2. Central Processing Unit (CPU),
Arithmetic and
i. Control Unit (CU), Control unit
logic unit
ii. Arithmetic Logic Unit (ALU),
iii. Registers,
3. Storage Unit, and Registers
4. Output Unit
Central processing unit
Typical configuration of computer system 3

1. Input Unit
The user interacts with the computer via the input unit. The Input unit
accepts data from the user and converts it into a form that is understandable by
the computer. The input data can be characters, word, text, sound, images,
document, etc. The input is provided to the computer using input devices like
keyboard, mouse, joystick, trackball, microphone, scanner etc.
2. Central Processing Unit (CPU)
CPU controls, coordinates and supervises the operations of the computer. It is
also responsible for processing of the input data. CPU consists of Arithmetic
Logic Unit (ALU) and Control Unit (CU).CPU also has a set of registers for
temporary storage of data, instructions addresses and intermediate results of
calculation.
a. ALU performs all the arithmetic and logic operations on the input data.
b. CU controls the overall operations of the computer i.e. it checks the
sequence of execution of instructions, controls and co-ordinates the overall
functioning of the units of computer.
c. Registers are high speed storage units within the CPU, but have least
storage capacity. Registers are not referenced by their address, but are directly
accessed and manipulated by the CPU during instruction execution. They are
referred to as the CPU’s working memory as they are used to store data,
instructions, addresses and intermediate results of processing.
 4 Typical configuration of computer system

3. Storage Unit
There are two types of memory associated with storage unit. They are:
primary memory and secondary memory.
The primary memory also called as the main memory of the computer,
consists of RAM (Random Access Memory) and ROM (Read Only Memory)
memories. Main memory stores the data, instructions, intermediate results and
output, temporarily, during the processing of data. The input data that is to be
processed is brought into the main memory before processing. The instructions
required for processing of data, any intermediate results are also stored in the
main memory. The output is stored in main memory before being transferred to
the output device. CPU can work with the information stored in the main memory.
The secondary memory also called as the external memory of the computer
stores permanently the data, programs and the output. Magnetic disks, magnetic
tapes, optical disks and flash drives are examples of secondary memory.
4. Output Unit
The output unit provides the processed data i.e. the result generated after
processing of data. The output may be in the form of text, sound, image, document,
etc. The computer may display the output on a monitor, sends output to the
printer or plotter for printing, and also sends sound output to the speaker, etc.
1.2 Motherboard
The computer is built up around a motherboard. The motherboard is the
most important part of any computer. It is a large Printed Circuit Board (PCB)
having many chips, ports, controllers and other electronic components mounted
on it.
1.2.1 Introduction to Motherboard
The motherboard or the system board is the main circuit board inside a
computer. Every component inside the computer has to communicate through
the motherboard, either by directly plugging into it or by communicating through
one of the motherboard ports. The motherboard provides a platform for all the
components and peripherals to communicate with each other.
The electronic components mounted on the motherboard are processor,
memory chips, interfaces, various ports and all expansion cards. The motherboard
is the hub, which is used to connect all the necessary components of a computer.
The RAM, hard drive, disk drives and optical drives are all plugged into interfaces
on the motherboard.
The motherboard may be characterized by the form factor, chipset and
type of processor socket used.
Typical configuration of computer system 5

 Form factor refers to the motherboard’s geometry, dimensions,

arrangement and electrical requirements. Different standards have
been developed to build motherboards, which can be used in different
brands. Advanced Technology Extended (ATX)) is the most common
design of motherboard for desktop computers.
 Chipset controls the majority of resources of the computer. The
function of chipset is to coordinate data transfer between the various
components of the computer. As the chipset is integrated into the
motherboard, it is important to choose a motherboard, which includes
a recent chipset, in order to maximize the computer’s upgradeability.
 The processor socket may be a rectangular connector into which
the processor is mounted vertically, or a square shaped connector
with many small connectors into which the processor is directly
inserted.
1.2.2 Types of Motherboard
There are various types of motherboards available depending on the
processors that are used. Some of them are XT, AT, Baby AT and ATX
motherboards.
XT Motherboard:
XT stands for eXtended Technology. These are all old model motherboard.
In these motherboards, we find old model processor socket LIF (Low Insertion
Force) sockets, ram slots DIMM and ISA (Industry Standards Architecture) slots,
12 pin power connector and no ports.
They have slot type processors, DIMM memory modules, ISA slots for add-
on card, and no ports. There are connectors and add-on cards for ports.
Example: Pentium-I, Pentium-MMX, Pentium -II and Pentium-II Processors.
AT Motherboard:
AT stands for Advanced Technology. Advanced Technology Motherboards
have PGA (Pin Grid Array) Socket, SDRAM slots, 20 pin power connector PCI
slots and ISA slots. We find the above components on AT motherboards.
Example: Pentium III Processors
Baby AT Motherboard:
Baby AT Motherboards have the combination of XT and AT. They have slot
type processor sockets and PGA processor sockets, SDRAM slots and DDRRAM
slots, PCI slots and ISA slots, 12 pin power connector and 20 pin power connector
and ports.
Example: Pentium-III and Pentium-IV
 6 Typical configuration of computer system

ATX Motherboard:
ATX stands for Advanced Technology eXtended. Latest motherboards all are
called as ATX motherboards, designed by ATX form factor. In this motherboard,
we find MPGA processor sockets, DDRRAM slots, PCI slots, AGP slots, Primary
and secondary IDE interfaces, SATA connectors, 20 pin and 24 pin ATX power
connector and ports.
Example: Pentium-IV, Dual Core, Core 2 Duo, Quad Core, i3, i5 and i7 processors.
1.2.3 Components of Motherboard
The motherboard components are:
 Processor (CPU)
 BIOS
 CMOS
 Slots
 Disk Controllers
 I/O Ports and Interfaces
 BUS

Figure 1.2 Motherboard components

Processor (CPU)
The processor or CPU is the main component on the motherboard and is
called the brain of the computer. The CPU consists of Arithmetic Logic Unit
(ALU) and Control Unit (CU). CPU also has a set of registers which are temporary
storage areas for holding data, and instructions. ALU performs the arithmetic
and logic operations on the data. CU is responsible for organizing the processing
Typical configuration of computer system 7

of data and instructions. CU controls and coordinates the activity of the other
units of computer.
During processing the CPU gets data and instructions from the memory
and interprets the program instructions and performs the arithmetic and logic
operations required for the processing of data. It then sends the processed data
to the memory.
The clock speed of a CPU is defined as the frequency with which a
processor executes instructions or the data that is processed. Higher clock
frequencies mean more clock ticks per second. The computer’s operating speed
is linked to the speed of the system clock. The clock frequency is measured in
millions of cycles per second or megahertz (MHz) or gigahertz (GHz) which is
billions of cycles per second. A CPU’s performance is measured by the number
of instructions executed per second, i.e. MIPS or BIPS. PCs presently come with
a clock speed of more than1GHz.
In Windows OS, the System Properties dialog box is selected to see
the processor name and clock frequency.
The diagram of the CPU is given in Figure 1.3 CPU with Buses and Controllers

The CPU is fabricated as a single Integrated Circuit (IC) chip and is also known
as the microprocessor. This tiny chip contains the entire computation engine.
The microprocessor is plugged into the motherboard of the computer. Intel is
one of the leading processor manufacturers in the world today.
General Structure of motherboard
The primary function of the processor is to execute the instructions given
to it and to produce the results. It fetches instructions and data from the primary
memory and performs the required operations. This movement of data between
 8 Typical configuration of computer system

the processor and memory is established by a communication path called bus.

The processor contains number of special purpose registers in addition to ALU
which is responsible for doing calculations. The different components inside the
processor can be seen in the figure 1.4.

CPU

Graphics Clock
card slot Generator

High speed Memory

graphics bus Slots
(AGP or PCI Northbridge Memory
Express) Bus
(Memory
controller hub)

Internal
Bus PCI
Onboard
Bus
Southbridge graphics
(I/O controller controller
PCI Bus
hub) IDE
SATA
USB Cables and
Ethernet ports leading
Audio Codec off-board
CMOS Memory
PCI Slots

LPC Bus Super I/O

Serial Port
Parallel Port
Flash ROM Floppy Disk
(BIOS) Keyboard
Mouse
Figure 1.4 Schematic diagram of Motherboard
Typical configuration of computer system 9

Figure 1.5 is the replica of the motherboard structure, except that it

displays the actual devices connected to the CPU.

Figure 1.5 Overview of the motherboard structure

The north bridge or host bridge is one of the two chips in the core
logic chipset on a PC motherboard, used to manage data communications
between the CPU and motherboard. It is supposed to be paired with a second
support chip known as a south bridge.
North Bridge or north Chipset is responsible for control of high speed
components like CPU, RAM, and Video Card. Chipset BUS speed control and
switch control data, ensuring data back and forth between the components is a
smooth and continuous, fully exploit the speed of the CPU and RAM. It can be a
chipset like the traffic in an intersection, as drivers switch traffic lights to allow
each data stream passes through a period of time, while speed control is a BUS
different directions of the intersection, the vehicle must run on a specified speed.
South Bridge or south Chipset is similar as north chipset, but the south
bridge driver chipset components slower as: Sound Card, Net Card, hard disk,
CD ROM drive, USB port, SIO and BIOS IC etc.
BIOS (Basic Input Output System)
BIOS is a small chip on the motherboard that holds a set of instructions to
load the hardware settings required to activate various devices like keyboards,
monitors or disk drives. The BIOS runs when the computer is switched ON. It
performs a Power On Self Test (POST) that checks if the hardware devices are
present and functioning properly. BIOS invoke the bootstrap loader to load the
 10 Typical configuration of computer system

operating system into memory. Most new PCs come with Flash BIOS-these BIOS
can be software upgraded to support new devices.
CMOS (Complementary Metal Oxide Semiconductor)
CMOS is a type of memory chip
to store the date, time and system
setup parameters. These
parameters are loaded every time
the computer is started. That is
why we observe, when the
computer is turned ON, the system
still displays the correct clock time.
BIOS as well as CMOS are kept
powered by a small lithium Ion
battery located on the motherboard
It can be seen in the figure 1.6
below.
Figure 1.6 CMOS battery
Slots
A slot is an opening in a computer where you can insert a printed circuit
board. Slots are often called expansion slots because they allow you to
expand the capabilities of a computer.
 Expansion Slots These slots are located on the motherboard. The
expansion cards are inserted in the expansion slots. These cards
give the computer new features or increased performance. There
are several types of slots:
 ISA (Industry Standard Architecture) slot – ISA slot is used to
connect modem and input devices.
 PCI (Peripheral Component Inter Connect) slot – PCI slots are
used to connect graphics accelerator cards, sound cards, internal
modems or SCSI cards. They are much faster than ISA cards.
 AGP (Accelerated Graphic Port) slot – AGP slot is meant to provide
faster access to a graphics accelerator card, thus enhancing the
visual experience for the user. All Celeron and Pentium-III
motherboards come with an AGP slot.
 RAM slot – RAM slot is used to install memory and is of two types.
They are SIMM (Single Inline Memory Module) slot and DIMM (Dual
Inline Memory Module) slot. The original Pentium systems typically
have either four 72-pin SIMM slots, or two 168-pin DIMM slot to
install memory.
Typical configuration of computer system 11

 Processor slot – Processor slot is used to insert the processor chip

which is the largest chip on the motherboard. It can be identified,
as a heat sink or fan is located on top of it.
 PCI Express slot – It has faster bus architecture than AGP and PCI
buses.
 PC Card – It is used in laptop computers. It includes Wi-Fi card,
network card and external modem.
Disk Controllers
Disk controller is the circuit that enables the CPU to communicate with
a hard disk, floppy disk or other kind of disk drive. Modern disk controllers are
integrated into the disk drive.
Hard disk controller (HDC)
The hard disk controller is the interface that enables the computer to read
and write information to the hard drive. Today, hard drives have the controller
built on to them.
The first standard hard disk controller developed is the IDE standard drive
also known as Advanced Technology Attachment (ATA). This drive is attached to
the motherboard by means of 40-wire ribbon cable. The IDE standard also allows
two drives to connect in a daisy-chain fashion. The enhanced IDE (EIDE) standard
followed shortly. The EIDE standard is a specification that allows four drives to
be connected to a dual channel controller.
Floppy disk controller (FDC)
A floppy-disk controller is the interface that directs and controls reading
from and writing to a computer’s floppy disk drive (FDD). The floppy disk
controller usually performs data transmission in direct memory access (DMA)
mode.
A single floppy-disk controller board supports a 33-wire ribbon cable and
can connect up to four floppy disk drives to the motherboard. The controller is
linked to the system bus of the computer and appears as a set of I/O ports to
the CPU.
I/O Ports and Interfaces
The ports and interfaces are used to connect external devices like printers,
keyboards or scanners to the computer, which gets connected to the computer’s
motherboard. These ports and interfaces are found on the rear side of a computer.
There are several types of ports like serial port, parallel port, USB port, and AGP
port etc. which is given in figure 1.7.
 12 Typical configuration of computer system

Serial port
Serial port is also known as
communication (COM) ports or RS-
232-c ports. They are used for
connecting communication devices
like mouse and modem. This port
transfers data serially one bit at a
time. It needs a single wire to transmit
1 bit of data. Hence it takes 8 times
longer to transfer a byte. There are
two varieties of Com ports, the 9-pin
ports and 25-pin ports.
Parallel port:
Parallel ports are used to
connect external input/output Figure 1.7 Types of ports in the motherboard
devices like printers or scanners. This
port facilitates the parallel transfer of data, usually one byte (8-bits) at a time.
Parallel ports come in the form of 25-pin connector.
IDE (Integrated Digital Electronics) port
IDE devices like CD-ROM drives or hard disk drives are connected to the
motherboard through the IDE port.
USB (Universal Serial Bus) port
USB port gives a single, standardized, easy-to-use
way to connect a variety of newer peripherals to a
computer. These devices include printers, scanners,
digital cameras, web cameras, speakers etc. USB
supports a data speed of 12 megabits per second,
supporting up to 127 devices. USB is a plug- and-play
interface between a computer and add-on devices. i.e. a
new device can be added to the computer without adding
an adapter card or even turning the computer off. The
figure 1.8 shows the symbol used to represent a USB Figure 1.8 USB port
port.
PS-2 port (Personal System-2 port)
The PS-2 port was developed by IBM to interface keyboards and pointing
devices like mouse, trackballs and touch pads. This port is also called as mouse
port as most computers now have a PS-2 port to connect a mouse. This port uses
synchronous serial signals to communicate between the keyboard and a mouse
to the computer.
Typical configuration of computer system 13

AGP (Accelerated Graphics Port) port

The AGP port is used to connect to graphic card that provides high-speed
video performance typically required in games and other multimedia applications.
SCSI (Small Computer System Interface) port
This port is used for adding external devices such as high-speed hard-
disks, high-end scanners and CD-ROM drives. It does fast data transfers and
I-O operations. These ports are expensive, as they provide faster access at very
high speeds and need separate dedicated adapters to function.
VGA (Visual Graphics Adaptor) port connects monitor to a computer’s video
card. It has 15 holes and is similar to serial port connector, but serial port
connector has pins, this has holes.
Power Connector has three-pronged plug. It connects to the computer’s power
cable that plugs into a power bar or wall socket.
Firewire Port transfer large amounts of data at very fast speed. It connects
camcorders and video equipment’s to the computer. The data travels at 400 to
800 megabits per second. It is invented by Apple. The three variants of firewire
port are 4-Pin firewire 400 connector, 6-Pin firewire 400 connector and 9-Pin
firewire 800 connector
Modem (Modulator demodulator) connects a PC’s modem to the telephone
network.

Ethernet Port connects to a network and high speed Internet. It connects

network cable to a computer. This port resides on an Ethernet Card. Data travels
at 10 megabits to 1000 megabits per second depending upon the network
bandwidth.

Game Port connects a PC to a joystick. It is now replaced by USB.

DVI (Digital Video Interface) port connects a Flat panel LCD monitor to the
computer’s high-end video graphic cards. It is very popular among video card
manufacturers.

Sockets are used to connect microphone, speakers

to sound card of the computer.
MIDI (Musical Instrument Digital Interface) port is
a system designed to transmit information between
Figure 1.9 MIDI port electronic musical instruments. A MIDI musical
keyboard can be attached to a computer and allow a performer to play music
that is captured by the computer system as a sequence of musical notes with
 14 Typical configuration of computer system

the associated timing ( instead of recording digitized sound waves). The port
and interface are required for connectivity.

Figure 1.10 MIDI interface

BUS
The different components of computer, i.e. CPU, I/O unit, and memory
unit are connected to each other by a bus. The data, instructions and the signals
are carried between the different components via a bus.
A bus is a collection of parallel wires that form a pathway to carry
address, data and control siagnals

CPU Memory Input and

Output

Control bus
System bus

Address bus

Data bus

Figure 1.11 Bus structure

The functional features of a bus are:
 A bus is a set of wires and each wire can carry one bit of data.
 A bus width is defined by the number of wires in the bus.
A computer bus can be divided into two types: Internal bus and External
bus.
Typical configuration of computer system 15

 The Internal bus connects major computer components like,

processor, memory and I/O. It is also called as System bus.
 The External bus connects the different external devices,
peripherals, expansion slots, I/O ports and drive connections to the
rest of computer. The external bus allows various devices to be
attached to the computer, thus expanding the computer’s
capabilities. It is also called as Expansion bus and is slower than
the system bus.
A system bus or expansion bus comprise of three kinds of buses: data
bus, address bus and control bus shown ins figure 1.11.
 Data bus provides a path to transfer
data between CPU and memory. The data
bus may consist of 32, 64, 128 lines of wire.
The number of lines is referred to as the
width of the data bus. The data bus width
affects the speed of computer. In a 16-bit
line bus can transfer 16 bits of data. The
bus speed is measured in MHz and higher
the bus speed, faster the processer speed.
 Address bus connects CPU and RAM
with a set of lines of wire similar to data
bus. The address bus width determines the
maximum number of memory locations the
computer
Figure 1.12 I-Ocan address. Pentium Pro, II, III, IV have 36-bit address
Buses
bus that can address 236 bytes or 64 GB of memory. PCs presently
have a bus speed varying from 100 MHz to 400 MHz.
 Control bus is used to control the access to and the use of the data
and address lines.
1.3 Memory
A computer memory refers to the electronic storing space for instructions
and data where the computer’s processor can reach quickly. The computer storage
refers to permanent computer memory that stores all the data files and
instructions even after the computer system is turned off.
A computer processor has very limited memory. Thus it has to rely on
other kinds of memories to store data, instructions and results.
The memory in a computer can be of two basic types: Internal memory
and Secondary memory shown in figure 1.13
 Internal memory
Internal memory includes registers, cache memory and primary memory
which can be directly accessed by the processor. It is used for temporary storage
 16 Typical configuration of computer system

of data and instructions on which

the processor is currently working.
This memory is the fastest among
all other memories and is expensive.
Therefore a very small part of
internal memory is used in the
computer system. The features of
internal memory are:
 Temporary storage
 Limited storage capacity
 Fast access
 High cost

Figure 1.13 Memory accessing levels of the processor

Registers
The registers are high speed temporary storage areas located inside the
CPU. After the CPU gets the data and instructions from the cache or RAM, the
data and instructions are moved to registers for processing. These registers work
under the direction of the control unit (CU) to accept, store and transfer
instructions or data, and perform arithmetic or logical comparisons at high speed.
Since CPU uses registers for the processing of data, the number of registers in a
CPU and the size of each register affect the power and speed of a CPU.
Cache memory
The cache memory is a very high speed memory placed in between RAM
and CPU. Cache memory stores data that is used more often, temporarily and
makes it available to CPU at a fast rate. Hence it is used to increase the speed of
processing. During processing, the CPU first checks cache for the required data.
If data is not found in cache, then it looks in the RAM for data.
The Cache memory is a high speed memory available inside CPU
to speed up access of data and instructions stored in RAM memory.

Processor

Regs L1 cache L2 cache Memory Disk

Figure 1.14 Illustration of cache memory

Typical configuration of computer system 17

Cache memory is very expensive, so it is smaller in size. Generally,

computers have cache memory of sizes 256 KB to 2MB.
Cache memory is built into the processor, and may also be located next to
it on a separate chip between CPU and RAM. Cache built into the CPU is faster
than separate cache, almost at the speed of the microprocessor itself. However,
separate cache is roughly twice as fast as RAM.
The CPU has a built-in Level1 (L1) cache and Level2 (L2) cache, as shown
in figure 1.14 below. In addition to the built-in L1 and L2 cache, some CPUs
have a separate cache chip on the motherboard called Level3 (L3) cache. These
days, high-end processor comes with built-in L3 cache, like in Intel core i7. The
L1, L2 and L3 cache store the most recently executable instructions, the next
ones and the possible ones, respectively. Typically, CPUs have cache size varying
from 256KB (L1), 6MB (L2), to 12MB (L3) cache.
Primary memory
Primary memory is also known as main memory. This memory is of two
types: Random Access Memory (RAM) and Read Only Memory (ROM)
 RAM temporarily stores the computer’s operating system, application
programs and current data so that the processor can reach them quickly. RAM
is a faster memory and volatile in nature. i.e. when the power is switched off, the
data in this memory is lost.
 ROM is a small memory, which stores the boot firmware (called BIOS).
BIOS hold enough information to enable the computer to check its hardware
and load its operating system into its RAM at the time of system booting. ROM is
non-volatile in nature. i.e. even when the computer is switched off, the contents
of ROM remains available.
Types of RAM
There are different types of RAM, depending on the technology used to
construct a RAM. Some of the common types are:
DRAM or Dynamic RAM is the most common type of memory chip. DRAM
is mostly used as main memory, since it is small and cheap. It uses transistors
and capacitors. The transistors are arranged in a matrix of rows and columns.
The capacitor holds the bits of information 0 and 1. The transistor and capacitor
are paired to make a memory cell. The transistor acts as a switch that lets the
control circuitry on the memory chip read the capacitor or change its state.
DRAM must be refreshed continually to store information; otherwise it
will lose what it is holding. The refresh operation occurs automatically thousands
of times per second. DRAM is slow because the refreshing takes time. Access
speed of DRAM ranges from 50 to 150 ns.
 18 Typical configuration of computer system

SRAM or Static Random Access memory chip is usually used in cache

memory due to its high speed. SRAM uses multiple transistors (4 to 6), for each
memory cell. It does not have a capacitor in each cell. A SRAM memory cell has
more parts, so it takes more space on a chip than DRAM cell. It does not need
constant refreshing and therefore is faster than DRAM. SRAM is more expensive
than DRAM, and it takes up more space. It stores information as long as it is
supplied with power. SRAM is very fast and easier to use. The access speed of
SRAM ranges from 2 to 10ns.
SDRAM or Synchronous Dynamic Random Access Memory is a special
type of DRAM that is synchronized to the system clock. Since it is synchronized
to the CPU, it knows when the next cycle is coming, and has the data ready
when the CPU requests it. This increases efficiency by reducing CPU waiting
time.
DDR-SDRAM or Double-Data Rate SDRAM works the same way as does
ordinary SDRAM. Data transfer rate is double when compared to SDRAM.
1.4 Power Supply to a Computer System
Electric power is the main source of supply for the operation of electronic
components of a computer. Therefore continuous power supply is essential for
the computer to prevent them from failures, breakdown or shutdown. All
computers come with a power supply.
There are two types of power supply connected to a computer system.
They are, Switch Mode Power Supply (SMPS) and Uninterruptable Power Supply
(UPS).
 SMPS
An SMPS converts AC power from an electrical outlet to the DC power
needed by system components. An SMPS is a metal box in the rear of the system
that is attached to the computer chassis and to the system board. The power
supply contains the power card plug and a fan for cooling, because it generates
a lot of heat. An SMPS with a rating of more than 300 watts is needed; any less
will not reliably power modern components. In a PC the SMPS converts 230 volts
of AC to 5 to 12 DC volts and the wattage is around 180 to 300 watts, 450 watts
and 500 watts.
 UPS
An UPS is a power supply that includes a battery to maintain power in the
event of a power failure. Typically, an UPS keeps a computer running for several
minutes to few hours after a power failure, enabling us to save data that is in
RAM and then shut down the computer gracefully.
Many UPS now offer a software component that enables us to automatically
backup and shut down procedures in case there is a power failure while we are
away from the computer.
 Types of UPS
There are two types of UPS: Online UPS and Standby UPS
Typical configuration of computer system 19

Online UPS – An online UPS avoids those momentary power lapses by

continuously providing power from its own inverter, even when the power line is
functioning properly. Online UPS is more costly than Standby UPS. For a PC
with color monitor 15", requires an UPS of 500VA and for a PC with color monitor
17", requires an UPS of 600VA.
Standby UPS – A Standby UPS (or off-line UPS) monitors the power line and
switches to battery power as soon as it detects a problem. The switch over to
battery, however, can require several milliseconds, during which time the
computer is not receiving any power.

Offline UPS

Online UPS

Figure 1.15 Types of UPS

1.5 Assembling the Computer System

Computer configuration is the process of setting up your hardware

devices and assigning resources to them so that they work together without
problems. A properly-configured system will allow you to avoid nasty
resource conflict problems, and make it easier for you to upgrade your
system with new equipment in the future. An improperly-configured system
will lead to strange errors and problems, and make upgrading a nightmare.
20 Typical configuration of computer system

Basic components for assembling a new computer system

Figure 1.16 Components of Computer System

Activity
Typical configuration of computer system 21

Points to remember
 The motherboard is the main circuit board inside a computer which
provides a platform for all the components and peripherals to communicate
with each other.
 The motherboard may be characterized by the form factor, chipset and
type of processor socket used.
 The motherboard types are XT, AT, Baby AT and ATX motherboards.
 The motherboard components are Processor (CPU), BIOS, CMOS, Slots,
Disk Controllers, I-O Ports/Interfaces and BUS

 The processor is the main component on the motherboard and is called

the brain of the computer.
 The clock speed of a CPU is defined as the frequency with which a
processor executes instructions or the data is processed.
 The north-bridge and south bridge are the two chips in the core
logic chipset on a PC motherboard, used to manage data communications
between a CPU and a motherboard.
 BIOS is a small chip on the motherboard that holds a set of instructions
to load the hardware settings required to activate various devices like
keyboards, monitors or disk drives.
 CMOS is a type of memory chip to store the date, time and system setup
parameters.
 A slot also called as expansion slots, allows expanding the capabilities of a
computer to give the computer new features or increased performance.
 The disk controller is the circuit which enables the CPU to
communicate with a hard disk, floppy disk or other kind of disk drive.
 The ports and interfaces are used to connect external devices like
printers, keyboards or scanners to the computer, which gets connected
to the computer’s motherboard.
 A bus is a collection of parallel wires that form a pathway to carry
address, data, and control signals.
 A system bus or expansion bus comprises of data bus, address bus and
control bus
 A computer memory refers to the electronic storing space for
instructions and data where the computer’s processor can reach quickly.
 The parts of internal memory are registers, cache and primary memory-
RAM and ROM.
 Cache memory is a high speed memory available inside CPU in order to
speed up access to data and instructions stored in RAM memory.
 The types of RAM are DRAM, SRAM, SDRAM and DDR-SDRAM.
 Power supply is essential for the computer to prevent computers from
failures, breakdown or shutdown.
 Types of power supply connected to a computer system are SMPS or
UPS
 22 Typical configuration of computer system

Review questions
One marks questions:
1. What is a motherboard?
2. What is microprocessor?
3. What is the purpose of registers in the CPU?
4. How does the computer communicate with other devices?
5. What is system bus?
6. What is the function of control bus?
7. What is a data bus?
8. What is a port?
9. What is an interface?
10. Expand PCI.
11. How many bits of data are sent in a serial port?
12. Expand USB.
13. Give one feature of USB port.
14. What is meant by plug and play device?
15. Name any one USB device.
16. Is device controller a hardware or software?
17. What is cache memory?
18. Where is L1 cache located?
19. Where is L2 cache located?
20. Expand SDRAM.
21. Give the expansion of DDRRAM.
22. Expand SMPS.
23. What is the use of SMPS?
24. What is the approximate power consumed by a PC?
25. Expand UPS.
26. What is the use of UPS?
27. List the types of UPS.
Two marks questions:
28. Name any two types of motherboard.
29. Mention any two characteristics of motherboard.
30. Mention the components of motherboard.
31. Explain system bus.
32. What is data bus and address bus?
33. What is the purpose of expansion slot?
34. What is the purpose of AGP slot?
35. Name the different types of I/O ports.
36. Explain serial port.
Typical configuration of computer system 23

37. Explain parallel port.

38. Explain USB port.
39. What is meant by plug and play card?
40. What is the purpose of ports and buses?
Three marks question questions:
41. Explain the different components of motherboard.
42. Explain the characteristics of motherboard.
43. Explain the Schematic diagram of Motherboard.
44. Explain different types of I/O ports.
45. Give the features of USB port.
46. Explain cache memory.
47. Explain the types of power supply.
48. What is the purpose of ports, buses and controllers in the I/O system?
49. What is a Slot? mention any two types.
50. Name the different components of North bridge.

******
 24 Boolean Algebra

Chatpter 2
Boolean Algebra
Objectives:

 To understand the concept of boolean algebra

 To understand the concept of simplifications of boolean expressions

Boolean Algebra 25

2.1 Introducton to Boolean Algebra

In the previous course, we have seen that computers normally use binary
numbers. In this chapter, you will learn about an algebra that deals with the
binary number system. This algebra, known as Boolean algebra, is very useful
in designing logic circuits used by the processors of computer systems. In addition
to this, you will also learn about the elementary logic gates that are used to
build up circuits of different types to perform the necessary arithmetic operations.
These logic gates are the building blocks of all the circuits in a computer. Finally,
in this chapter, we will also learn how to use Boolean Algebra to design simple
logic circuits frequently used by the arithmetic logic unit of almost all computers.
Long ago Aristotle constructed a complete system of formal logic and wrote
six famous works on the subject, contributing greatly to the organization of
man’s reasoning. For centuries afterward, mathematicians kept on trying to
solve these logic problems using conventional algebra but only George Boole
could manipulate these symbols successfully to arrive at a solution with his own
mathematical system of logic. Boole’s revolutionary paper ‘An Investigation of
the laws of the thought’ was published in 1854 which led to the development of
new system, the algebra of logic, ‘BOOLEAN ALGEBRA’.
Boole’s work remained confined to papers only until 1938 when Claude
E. Shannon wrote a paper titled A Symbolic Analysis of Relay Switching Circuits.
In this paper he applied Boolean Algebra to solve relay problems. As logic problems
are binary decisions and Boolean Algebra effectively deals with these binary
values. Thus it is also called ‘Switching Algebra’.
2.2 Binary Valued Quantities - Variable and Constants
Everyday we have to make logic decisions. For example, consider the
following questions:
“Should I carry the book or not?”
“Should I use calculator or not?”
“should I miss TV programme or not?”
Each of these questions requires the answer YES or NO. These are the
only two possible answers.
Therefore, each of the above mentioned is a binary decision. Binary decision
making also applies to formal logic.
A variable used in an algebraic formula is generally assumed that the
variable may take any numerical value through the entire field of real numbers.
However a variable used in Boolean Algebra or Boolean equation can have only
one of two possible values. The two values are FALSE (or 0) and TRUE (or 1).
Thus, sentences which can be determined to be TRUE or FALSE are called logical
statements or truth functions and the results TRUE or FALSE are called truth
 26 Boolean Algebra

values. The truth values are depicted by logical constants TRUE and FALSE or 1
and 0 respectively. 1 means TRUE and 0 means FALSE. The variables which can
store these truth values are called logical variables or binary valued variables as
these can store one of the two values 1 or 0 (TRUE or FALSE).
The decision which results into either YES (TRUE or 1) or NO (FALSE or 0)
is called a Binary Decision.
Also, if an equation describing logical circuitry has several variables, it is
still understood that each of the variables can assume only the values 0 and 1. For
instance, in the equation A + B = C , each of the variables A , B and C may have
only the values 0 or 1.

2.3.0 LOGICAL OPERATIONS

There are some specific operations that can be applied on truth functions.
Before learning about these operations, you must know about compound logical
functions and logical operations.

2.3.1 Logical Function or Compound Statement

Algebraic variables like a, b, c or x, y, z etc. are combined with the help of
mathematical operators like +, -, x, / to form algebraic expressions.
For example, 2 x A + 3 x B – 6 = (10 x Z) /2 x Y i.e., 2A + 3B – 6C = 10Z/2Y
Similarly, logic statements or truth functions are combined with the help of
Logical Operators like AND, OR and NOT to form a compound statement or logical
function.
These logical operators are also used to combine logical variables and logical
constants to form logical expressions.
For example, assuming that x, y and z are logical variables, the logical
expressions are
X NOT Y OR Z
Y AND X OR Z
2.3.2 Logical Operators
Truth Table is a table which represents all the possible values of logical
variables/statements along with all the possible results for the given combinations
of values.
Boolean Algebra 27

Before we start discussion about logical operators, let us first understand

what a Truth Table is ?. Logical statements can have only one of the two values
TRUE (YES or 1) or FALSE (NO or 1).
For example, if X and Y are the logical statements and R is the result,
then the truth table can be written as follows:
If result of any logical statement or expression
X Y R
is always TRUE or 1, it is called Tautology and if the
0 0 0 result is always FALSE or 0 it is called Fallacy.
0 1 0
1 0 0 1 represents TRUE value and 0 represents
1 1 1 FALSE value.
This is a truth table i.e., table of truth values of
Table 1.1 truth functions.
Now let us proceed with our discussion about logical operators. There are
three logical operators: NOT, OR and AND Operators.

NOT Operator
This operator operates on single variable and operation performed by NOT
operator is called complementation and the symbol we use for it is (bar). Thus
X means complement of X and YZ means complement of YZ. As we know, the
variables used in Boolean equations have a unique characteristic that they may
assume only one of two possible values 0 and 1, where 0 denotes FALSE and 1
denotes TRUE value. Thus the complement operation can be defined quite simply.
0=1 or NOT (FALSE) = TRUE and
1=0 or NOT (TRUE) = FALSE and
The truth table for the NOT operator is
X X Several other symbols like ‘~’ are also used for the
complementation symbol. If ~ is used then ~X is read as ‘negation
0 1
of X’ and if symbol ’ is used then X’ is read as complement of X.
1 0

Table 1.2 Truth Table for NOT operator

NOT operation is singular or unary operation as it operates

x x on single variable.
Venn diagram for x is given above where shaded area
depicts x.

Figure 1.3. Venn diagram for x

 28 Boolean Algebra

OR operator
A second important operator in Boolean algebra is OR operator which
denotes operation called logical addition and the symbol we use for it is +. The
+ symbol, therefore, does not mean arithmetic addition, but is a logical addition
or logical OR symbol. Thus, X + Y can be read as X OR Y. For OR operation,
the possible input and output combinations are as follows :
0+0=1
0+1=1
1+0=1
1+1=1
The truth table of OR operator is given below:
X Y X+Y Note that when any one or both X and Y is 1, X + Y is 1.
0 0 0
0 1 1 and both X and Y is 0, X+Y is 0
1 0 1
1 1 1
Table 1.4 : Truth Table for OR operator

To avoid ambiguity, there are other symbols e.g.,  and  have been
recommended as replacements for the + sign. Computer people still use the + sign,
however, which was the symbol originally proposed by Boole.
Venn diagram for X + Y is given below where the shaded area depicts X + Y.

Shaded portion shows X + Y

Figure 1.2 : Venn diagram for X+Y

AND Operator
AND operator performs another important operation of Boolean Algebra
called logical multiplication and the symbol for AND operation is ‘.’ (dot). Thus
X.Y will be read as X AND Y. The rules for AND operation are :
0.0 = 0
0.1 = 0
1.0 = 0
1.1 = 1
Boolean Algebra 29

And the truth table for AND is as follows :

X Y X.Y
0 0 0 X Y
0 1 0
1 0 0
1 1 1

Table 1.10 : Truth Table for AND operator FIGURE 1.3 : Venn Diagram for (X.Y)

Note that only when both X and Y are 1’s, X.Y has the result 1. If any one
of X and Y is 0, XY result 0. Venn diagram for X.Y is given in the figure above where
the shaded area depicts X.Y
2.4.0 Evaluation of Boolean Expressions Using Truth Table
Logical variables are combined by means of logical operators AND, OR
and NOT to form a Boolean expression. For example, X+Y.Z+Z is a Boolean
expression.
It is often convenient to shorten X.Y.Z to XYZ and using this convention,
above expression can be written as X+YZ+Z
To study a Boolean expression, it is very useful to construct a table of values
for the variables and then to evaluate the expression for each of the possible
combinations of variables in turn. Consider the expression X+YZ. Here three
variables X, Y, Z are forming the expression. Each variable can assume the value
0 or 1. The possible combinations of values may be arranged in ascending order
as in Table 1.11

X Y Z Since X, Y, and Z are the three (3) variables in total. A truth

table involving 3 input variables will have 23 = 8 rows or
0 0 0 combinations in total. The left most column will have half of
0 0 1 total entries (4 entries) as zeroes and half as 1’s (in total 8).
0 1 0 The next column will have number of 0’s and 1’s halved than
0 1 1 first column completing 8 rows and so on. That is why, first
1 0 0 column has four 0’s and four 1’s, next column has two 0’s
1 0 1 followed by two 1’s completing 8 rows in total and the last
1 1 0 column has one 0 followed by one 1 completing 8 rows in
1 1 1 total.

Table 1.11 Possible Combinations of X, Y and Z

 30 Boolean Algebra

So a column is added to list Y.Z (Table 1.12)

X Y Z Y.Z
0 0 0 0
0 0 1 0
0 1 0 0 AND operation is applied only on columns Y and Z.
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Table 1.12 Truth Table for (Y.Z)

One more column is now added to list the values of YZ (Table 1.13)
X Y Z Y.Z YZ
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1 Note that YZ contains complemented values of YZ.
0 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 0

Table 1.13 truth table for Y Z and YZ

Now values of X are ORed (logical addition) to the values of YZ and the
resultant values are contained in the last column (Table 1.14).

X Y Z Y.Z YZ X+YZ
0 0 0 0 1 1 Now observe the expression X+YZ, after
0 0 1 0 1 1 ANDing Y and Z, the result has been
0 1 0 0 1 1 complemented and then ORed with X. Here
0 1 1 1 0 0 the result is 0 only when both the columns
1 0 0 0 1 1 X and YZ have 0, otherwise if there is 1 in
1 0 1 0 1 1 any of the two columns X and YZ , the result
1 1 0 0 1 1 is 1.
1 1 1 1 0 1

Table 1.14 Truth Table for X + YZ.

Boolean Algebra 31

A Boolean expression will be evaluated using precedence rules. The order of

evaluation of an expression is called as precedence. The precedence is, firstly
NOT, then AND and then OR. If there is parenthesis, then the expression in
parenthesis is evaluated first.

Example 1.13: In the Boolean algebra, verify using truth table that X+XY = X for
each X, Y in 0 and 1.
As the expression X+XY=X is a two variable expression, so we require
four possible combinations of values of X, Y. Truth Table will be as follows:
X Y XY X+XY
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Comparing the columns X+XY and X, we find, contents of both the columns
are identical, hence verified.
Example 1.14: In the Boolean Algebra, verify using truth table that
X+Y = X . Y in 0 and 1.
Solution: As it is a 2-variable expression, truth table will be as follows:
X Y X+Y X+Y X Y X.Y
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Comparing the columns X+Y and X . Y both the columns are identical, hence
verified.
Example 1.15: Prepare a table of combinations for the following Boolean algebra
expressions:
(a) X Y + X Y (b) XY Z + X Y Z (c) X Y Z + X Y
 32 Boolean Algebra

Solution: (a) As X Y + XY is a 2-variable expression, its truth table is as

follows:

X Y X Y XY XY XY+XY
0 0 1 1 1 0 1
0 1 1 0 0 1 1
1 0 0 1 0 0 0
1 1 0 0 0 0 0

(b) Truth table for this 3 variable expression is as follows :

X Y Z X Y Z XYZ X YZ XYZ+XYZ
0 0 0 1 1 1 0 0 0
0 0 1 1 1 0 0 1 1
0 1 0 1 0 1 0 0 0
0 1 1 1 0 0 0 0 0
1 0 0 0 1 1 0 0 0
1 0 1 0 1 0 0 0 0
1 1 0 0 0 1 1 0 1
1 1 1 0 0 0 0 0 0

(a) Truth table for XYZ + XY is as follows:

X Y Z X Y Z XYZ XY XYZ+XY
0 0 0 1 1 1 0 0 0
0 0 1 1 1 0 0 0 0
0 1 0 1 0 1 1 0 1
0 1 1 1 0 0 0 0 0
1 0 0 0 1 1 0 1 1
1 0 1 0 1 0 0 1 1
1 1 0 0 0 1 0 0 0
1 1 1 0 0 0 0 0 0

Example 1.16 Prepare truth table for the following Boolean algebra
expressions:
(a) X(Y+Z) +X Y (b) XY (Z+YZ)+Z (c) A[(B+C)+C]
Boolean Algebra 33

Solution (a) Truth table for X(+) +X is as follows :

X Y Z Y Z (Y+Z) X(Y+Z) XY X(Y+Z)+XY

0 0 0 1 1 1 0 0 0
0 0 1 1 0 1 0 0 0
0 1 0 0 1 1 0 0 0
0 1 1 0 0 0 0 0 0
1 0 0 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1
1 1 0 0 1 1 1 0 1
1 1 1 0 0 0 0 0 0

(b) Truth table for XY (Z+Y)+ is as follows:

X Y Z Y Z YZ Z+YZ XY XY(Z+YZ) XY(Z+YZ)+Z

0 0 0 1 1 0 0 0 0 1
0 0 1 1 0 0 1 0 0 0
0 1 0 0 1 1 1 0 0 1
0 1 1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 1 0 1
1 0 1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 0 0 1
1 1 1 0 0 0 1 0 0 0

(c) Truth table for A[(B+C)+C] is as follows :

A B C B C (B+C) (B+C)+C A[(B+C)+C]

0 0 0 1 1 1 1 0
0 0 1 1 0 1 1 0
0 1 0 0 1 0 1 0
0 1 1 0 0 1 1 0
1 0 0 1 1 1 1 1
1 0 1 1 0 1 1 1
1 1 0 0 1 0 1 1
1 1 1 0 0 1 1 1
 34 Boolean Algebra

2.4.1 BASIC LOGIC GATES

After Shannon applied Boolean algebra in telephone switching circuits,
engineers realized that Boolean algebra could be applied to computer electronics
as well.
In the computers, these Boolean operations are performed by logic gates.

What is a Logic Gate?

Gates are digital (two-state) circuits because the input and output signals
are either low voltage (denotes 0) or high voltage (denotes 1). Gates are often
called logic circuits because they can be analyzed with Boolean algebra.

A Gate is simply an electronic circuit which operates on one or more input

signals to produce an output signal.

There are three types of logic gates:

 NOT gate or Inverter
 OR gate
 AND gate

Inverter (NOT Gate)

An inverter (NOT Gate) is a gate with only one input signal and one output
signal. The output state is always the opposite of the input state.
An inverter is also called a NOT gate because the output is not the same
as the input. The output is complement (opposite) of the input. Following tables
summarizes the operation:
X X X X
Low High 0 1
High Low 1 0

Table 1.15 Truth Table for NOT gate Table 1.16 Alternative truth table for NOT gate

A low input or 0 produces high output or 1 and vice versa. The symbol for inverter
is given in adjacent Fig. 1.4.
X X
Fig. 1.4. Not gate symbol
Boolean Algebra 35

NOT Gate is a gate or an electronic circuit that accepts only one input and
produces one output signal. The output state is always the complement of
the input state.

OR Gate
The OR Gate has two or more input signals, but only one output signal. This
gate gives the logical addition of the inputs. If any of the input signals or both is 1
(high), the output signal is 1 (high). The output will be low if all the inputs are low.
An OR gate can have as many inputs as desired. No matter how many
inputs are there, the action of OR gate is the same.
The OR gate has two or more input signals, but only one output signal. The
out will be the logical addition of the inputs.
Following tables show OR action
X Y F X Y Z F
0 0 0 0 0 0 0
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 0 1 1 1
1 0 0 1
Table : F=X+Y
1 0 1 1
1 1 0 1
1 1 1 1
Table : F=X+Y+Z
The symbol for OR gate is given below:
A A F A F
F B B
B C C
D
a) 2 input OR gate b) 3 input OR gate c) 4 input OR
gate Figure 1.5

AND gate
The AND Gate can have two or more than two input signals and produce
an output signal. When all the inputs are 1 or high only then the output is 1,
otherwise output is 0 only.
If any one or all the inputs is 0, the output is 0. To obtain output as 1, all
inputs must be 1.
An AND gate can have as many inputs as desired.

The AND Gate has two or more input signals, but only one output signal.
The out will be the logical multiplication of the inputs.
 36 Boolean Algebra

Following tables illustrate AND action.

X Y Z X.Y.Z
X Y A.B 0 0 0 0
0 0 0 0 0 1 0
0 1 0 0 1 0 0
1 0 0 0 1 1 0
1 1 1 1 0 0 0
1 0 1 0
Table 1.19 Two input AND gate
1 1 0 0
1 1 1 1

Table 1.20 Three input AND gate

The symbol for AND is
A A A
F F B F
B
B C
C D
Figure 1.6 (a) 2-input AND gate (b) 3-input AND gate (c) 4 input AND gate

2.5 BASIC POSTULATES OF BOOLEAN ALGEBRA

Boolean algebra is a system of mathematics and consists of fundamental
laws. These fundamental laws are used to build a workable, cohesive framework
upon which are based the theorems of Boolean algebra. These fundamental laws
are known as Basic Postulates of Boolean algebra. These postulates state the
basic relations in Boolean algebra:
The fundamental laws of the Boolean algebra are called as the postulates
of Boolean algebra

The Boolean postulates are:

I. If X  0 then X = 1; and If X  1 then X = 0
II. OR Relations (Logical Addition)
0+0=0 0 0
OR
0

0+1=1 0 1
OR
1
1 1
1+0=1 OR
0

1 1
1+1=1 OR
1
Boolean Algebra 37

III AND Relations (Logical Multiplication)

0.0 = 0

0.1 = 0

1.0 = 0

1.1 = 1

IV Complement Rules
0=1 0 1

1=0 1 0

PRINCIPLE OF DUALITY
This is a very important principle used in Boolean algebra. This states
that starting with a Boolean relation another Boolean relation can be derived by
i. Changing each OR sign (+) to an AND sign (.)
ii. Changing each AND sign (.) to an OR sign (+)
iii. Changing each 0 by 1 and each 1 by 0.
The derived relation using duality principle is called dual of original
expression.
For instance, we take postulates of OR relation, which states that
(a) 0+0=0 (b) 0 + 1 = 1 (c) 1 + 0 = 1 (d) 1 + 1 = 1
Now working according to above guidelines, '+' is changed to '.' 0's are replaced by
1’s and 1’s are replaced by 0’s, these equations become
(i) 1.1=1 (ii) 1.0=0 (iii) 0.1=0 (iv) 0.0=0
These are nothing but postulate III related to AND relations. We’ll be applying
this duality principle in the theorems of Boolean algebra.
 38 Boolean Algebra

Basic theorems of Boolean algebra

Basic postulates of Boolean algebra are used to define basic theorems of
Boolean algebra that provide all the tools necessary for manipulating Boolean
expressions. Although simple in appearance, these theorems may be used to
construct the Boolean algebra expressions.
Boolean theorems can be proved by substituting all possible values of the
variables that are 0 and 1. This technique of proving theorems is called as proof
by perfect induction. Boolean theorems can also be proved using truth table
also.

Proof by perfect induction is a method of proving Boolean theorems by

substituting all possible values of the variables.

2.5.1 Properties of 0 and 1

a) 0+X=X 0 X (gate representation of (a))
OR
X
1
b) 1+X=1 OR 1 (gate representation of (b))
X
0
c) 0.X=0 AND 0 (gate representation of (c))
X
1
d) 1.X=X AND X (gate representation of (d))
X

Proof a) 0+x = x
If x = 0, then LHS = 0 + x
=0+0
=0 { By OR relation }
=x
= RHS
If x = 1, then LHS = 0 + x
=0+1
=1 { By OR relation }
=x
= RHS
Boolean Algebra 39

Thus, for every value of x, 0 + x = x always.

O x R=0+x Truth table for above expression is given in table 1.21,
0 0 0 where R signifies the output.
0 1 1

Table 1.21 Truth Table for 0 + x = x

As X can have values either 0 or 1 (postulate 1) both the values ORed with
0 produce the same output as that of X. hence proved.

(a) 1+x=1
Proof: If x = 0, LHS = 1 + x
=1+0
=1 { By OR relation }
If x = 1, LHS =1+x (
=1+1
=1 { By OR relation }
Thus, for every value of x, 1 + x = 1 always.
Truth table for above expression is given below in Table 1.21, where R signifies
the output or result.
1 x 1+x
1 0 1
1 1 1

Table 1.22 Truth Table for 1 + x = 1

Again x can have values 0 or 1. Both the values (0 and 1) ORed with 1
produce the output as 1. Therefore 1+X=1 is a tautology.
(a) 0.X = 0
Proof: If x = 0, LHS = 0.x
= 0.0
=0 { By AND relation }
= RHS
 40 Boolean Algebra

If x = 1, LHS = 0.x
= 0.1
=0 { By AND relation }
= RHS
Thus, for every value of x, 0.x = 0 always.

As both the possible values of X (0 and 1) are to be ANDed with 0,

produce the output as 0. The truth table for this expression is as follows:
0 X R=0.X
0 0 0
0 1 0
Table 1.23 Truth Table for 0.X = 0
Both the values of X(0 and 1), when ANDed with, produce the output as
0. Hence proved. Therefore, 0.X=0 is a fallacy.

(d) 1.X = X
Proof: If x = 0, LHS = 1.x
= 1.0
=0 { By AND relation }
=x
=RHS
If x = 1, LHS = 1.x
= 1.1
=1 { By AND relation }
=y
=RHS
Thus, for every value of x, 1.x = x always.

Now both the possible values of X (0 and 1) are to be ANDed with 1 to

produce the output R. Thus the truth table for it will be as follows :
Boolean Algebra 41

1 X 1.X
1 0 0
1 1 1

Table 1.24 : Truth Table for 1.X=X

Now observe both the values (0 and 1) when ANDed with 1 produce the
same output as that of X. Hence proved.
2.5.2 Indempotence Law
This law states that when a variable is combines with itself using OR or
AND operator, the output is the same variable.

X
a) X + X = X OR X (gate representation for (a))
X

X
AND X
b) X . X = X X (gate representation for (b))

Proof :
(a) X+X=X
If x = 0, consider LHS = x + x
=0+0
=0 { By OR relation }
=x
=RHS
If x = 1, consider LHS = x + x
=1+1
=1 { By OR relation }
=x
=RHS
Thus, for every value of x, x + x = x always.
To prove this law, we will make truth table for above expression. As X is to
be ORed with itself only, we will prepare truth table with the two possible values
of X (0 and 1).
 42 Boolean Algebra

X X X+X
0 0 0
1 1 1
Table 1.25 Truth Table for x + x = x
(b) X.X = X
Here X if ANDed with itself.
Proof: If x = 0, consider LHS = x.x
= 0.0
=0 { By AND relation }
=x
=RHS
If x = 1, LHS = x.x
= 1.1
=1 { By AND relation }
=x
=RHS
Thus, for every value of x, x + x = x always.
x x x.x
0 0 0
1 1 1
Table 1.26 Truth Table for X.X = X

2.5.3 Involution
This law states that the complement of a variable is complemented again,
we get the same variable.
X
(X) = X ie., X X=X

Proof: If x = 0, then x =1 and (x) = 1 = 0 = x

If x = 1, then x = 0 and (x) = 0 = 1 = x
Thus, if a variable is complemented twice, we get the same variable.
We’ll prepare truth table which is given below:
Boolean Algebra 43

X X X
0 1 0
1 0 1

Table 1.27 Truth Table for X=X

First column represents possible values of X, second column represents

complement of X (i.e., X) and the third column represents complement of X (i.e.,X)
which is same as that of X. Hence proved.
This law is also called double-inversion rule.

2.5.4 Complementarity Laws

Here, we will combine a variable with its complement.
i. These laws states that
a) X + X = 1 X (gate representation of (a))
X OR
X+X=1
b) X.X = 0
X
X AND X.X=0

Proof: If x = 0, LHS = x + x
=0+1 (x = 1)
=1 { By OR relation }
= RHS
If x = 1, LHS = x + x
=1+0
=1 { By OR relation }
= RHS
Thus, for every value of x, x + x = 1 always.

We will prove x + x=1 with the help of truth table which is given below :
 44 Boolean Algebra

X X X+X
0 1 1
1 0 1

Table 1.28 Truth Table for X + X =1

Here, in the first column possible values of X have been taken, second column
consists of X values (complement values of X), X and X values are ORed and the
output is shown in third column. As the equation holds true for both possible
values of X, it is a tautology.
(b) X.X = 0
Proof: If x = 0, LHS = x . x
= 0 . 1 ( x = 1)
=0 { By AND relation }
If x = 1, LHS = x . x
= 1 . 0 ( x = 0)
=0 { By AND relation }
Thus, for every value of x, x . x = 0 always.
Truth table for the expression is as follows:
X X X.X
0 1 0
1 0 0
Table 1.29 Truth table for X . X = 0

The equations X.X = 0 as it holds true for both the values of X. Hence
proved. Observe that X.X=0. It is a fallacy. It is the dual of X+X=1.

2.5.5 Commutative Law

These laws state that a) x + y = y + x and b) x . y = y .x
X
X
OR
R
=
Y
OR R
AND R = Y AND
R
Y X Y X

(R signifies the output)

Boolean Algebra 45

If x = 0 then LHS = x + y
=0+y
=y
RHS = y + x
=y+0
=y
Therefore, for x = 0, x+y=y+x
If x = 1 then LHS = x + y
=1+y
=1
RHS = y + x
=y+1
=1
Therefore, for x = 1, x + y = y + x. Hence the proof.
X Y X+Y Y+X
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 1

Table 1.30 Truth Table for X + Y = Y +X

Compare the columns X + Y and Y +X, both of these are identical. Hence also
proved by truth table.
(b) Truth Table for X . Y = Y . X is given below:
Proof: If x = 0 then LHS = x . y
=0.y
=0
RHS = y . x
=y.0
=0
Therefore, for x = 0, x+y=y+x
If x = 1 then LHS = x . y
 46 Boolean Algebra

=1.y
=y
Therefore, for x = 1, x + y = y + x. Hence the proof.
X Y X.Y Y.X
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1

Table 1.31 Truth Table for X . Y = Y . X

Both of the columns X . Y and Y . X are identical, hence proved.

2.5.6 Associative Law
These laws state that
(a) X + (Y + Z) = (X + Y) + Z (associative Law of addition)
X X+Y
X R R
Y = Y
Z
Z Y+Z

(b) X (Y Z) = (X Y) . Z (associative Law of multiplication)

X XY
X R = Y R
Y
Z
Z YZ

a) X+(Y+Z) = (X+Y)+Z
Proof: If X = 0 the LHS = X + (Y + Z)
= 0 + (Y+ Z)
= Y+Z
RHS = (X+Y)+Z
= (0+Y)+Z
= Y+Z
Therefore for X=0, X+(Y+Z) = (X+Y)+Z
If X=1, then LHS =X+(Y+Z) RHS = (X+Y)+Z
=1+(Y+Z) =1+(Y+Z)
=1 =1+Z
Therefore X=1, X+(Y+Z) = (X+Y)+Z =1
Boolean Algebra 47

Proof. (a) Truth table for X + (Y + Z) = (X + Y) + Z is given below :

X Y Z Y+Z X+Y X+(Y+Z) (X+Y)+Z

0 0 0 0 0 0 0
0 0 1 1 0 1 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
(a) Table 1.32 Truth Table for X + (Y + Z) = (X + Y) + Z

Compare the columns X+(Y+Z) and (X+Y)+Z, both of these are identical.
Hence proved. Note : Give proof with table for rule (b). Since rule (b) is a dual of
rule (a), hence it is also proved.

2.5.7 Distributive Law

This law states that
(a) X (Y + Z) = XY+XZ X X+Y
Y
X R OR R
Y AND =
OR X
Z Y+Z X+Z
Z

(a) X + YZ = (X+Y) (X+Z)

X X+Y
Y
X R Z R
Y OR = AND
AND
Z YZ X
Z
Proof: a) X(Y+Z) = XY + XZ
If X=0, LHS = X(Y+Z) RHS = XY + XZ
= 0(Y+Z) = 0.Y + 0.Z
=0 =0+0
=0
If X=1, LHS = X(Y+Z) RHS = XY + XZ
= 1(Y+Z) = 1.Y + 1.Z
= Y+Z =Y+Z
 48 Boolean Algebra

Therefore, for every value of x, LHS = RHS. i.e., x(y+z) = xz + yz

Truth Table for X (Y + Z) = XY+XZ is given below:
Table 1.33 Truth table for X (Y + Z) = XY+XZ
X Y Z Y+Z XY XZ X(Y+Z) XY+XZ
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 0 1 1 1
1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1

Both the columns X(Y+Z) and XY+XZ are identical, hence proved.
Note : Since rule (b) is dual of rule (a), hence it is also proved
(b) X + YZ = (X+Y) (X+Z)
Proof: RHS = (X+Y) (X+Z)
= XX + XZ +XY + YZ
= X+XZ+XY+YZ (XX=X)
= X(1 + Z + Y) + YZ
= X + YZ (1 + z + y = 1)
= LHS Hence the proof
Truth table for X+YZ = (X+Y)(X+Z) is given below
2.5.8 Absorption Law
According to this law
a) X+XY=X b) X(X+Y)=X
X X
X
XY OR X+Y AND
AND OR
Y Y
Logic diagram (a) Logic diagram (b)
Proof: a) X+XY = X
LHS = x + xy
= x(1 + y)
= x.1 (1+Y=1)
= x (X.1=X)
= RHS
Boolean Algebra 49

Truth Table for X+XY = X is given below:

X Y XY X+XY
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Table 1.34 : Truth Table for X+XY = X

Column X and X+XY are identical. Hence proved
(b) Since rule (b) is dual of rule (a), it is also proved. However, we are giving the
algebraic proof of this law.
L.H.S.= X(X+Y) = X.X + XY
= X.X + XY
= X + XY (X.X = X Indempotence Law)
= X(1+Y)
= X.1 (using 1 + Y = 1 properties of 0, 1)
=X (X . 1 = X using property of 0, 1)
= RHS
Truth table for X(X+Y)=X

X Y X+Y X(X+Y)
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1

Some Other Rules of Boolean Algebra

There are some more rules of Boolean algebra which are given below:
X+XY=X+Y (This is the third distributive law)
This rule can easily be proved by truth tables. As you are quite familiar with
truth tables now, truth table proof is left for you as exercise, the other proofs of
these rules are being given here:
X+XY=X+Y

X
X
R = X R=X+Y
XY Y
Y
 50 Boolean Algebra

Proof : LHS = X + XY
= (x+x)(x+y) { x+x= 1}
= 1.(x+y)
= x+y
= RHS
All the theorems of Boolean algebra, which we have been covered so far, are
summarized in the following table:
Table 1.35 Boolean algebra rules
1 0+X=X Properties of 0
2 0.X = 0
3 1+X=1 Properties of 1
4 1.X = X
5 X+X=X Indempotence law
6 X.X=X
7 X =X Involution
8 X+X=1 Complementarity law
9 X. X = 0
10 X+Y=Y+X Commutative law
11 X . Y = Y. X
12 X + (Y + Z) = (X+Y)+Z Associative law
13 X(YZ) = (XY) Z
14 X (Y+Z) = XY+XZ Distributive law
15 X+YZ=(X+Y) (X+Z)
16 X+XY=X Absorption law
17 X . (X+Y) = X
18 X+XY=X+Y

2.6 De Morgan’s theorems

One of the most powerful identities used in Boolean algebra is De Morgan’s
theorem. Augustus De Morgan had paved the way to Boolean algebra by
discovering these two important theorems. This section introduces these two
theorems of De Morgan.
De Morgan’s First Theorem
It states that X+Y = XY
X X
X R
= R
Y
Y Y
Boolean Algebra 51

Proof: To prove this theorem, we need to recall complementarity laws, which

state that X+X=1 and X . X = 0 i.e., a logical variable/expression when added with
its complement produces the output 1 and when multiplied with its complement
produces the output 0.
Now to prove De Morgan’s first theorem, we will use complementarity laws.
Let us assume that P=X+Y where, P, X, Y are logical variables. Then, according
to complementation law P + P = 1 and P.P = 0.
That means, if P, X, Y are Boolean variables then this complementarity law must
hold for variable P. i.e., P = X+Y = XY
Therefore P+P=(X+Y)+XY
(X+Y) + X Y must be equal to 1. (As X+X = 1)
And, (X+Y). X Y must be equal to 0 (As X. X = 0)
Let us first prove the first part, i.e., (X + Y) + (XY) = 1
(X + Y) + (XY) = ((X + Y) + X) . ((X + Y)+Y) (ref. X+YZ=(X+Y)(X+Z))
= (X + X + Y) . (X + Y + Y)
= (1 + Y) . (X + 1)
= 1.1 (ref. X + X = 1)
=1 (ref. 1 + X = 1)
Now, let us prove the second part. i.e., (X + Y) . (XY) = 0
(X + Y) . (XY) = XY. (X + Y) (ref. X(YZ)=((XY)Z)
= XXY + XYY
= 0.Y + X.0
= 0+0=0 (ref. X . X = 0)
2.6.2 De Morgan’s Second Theorem
This theorem states that: (X.Y) = X + Y

X X
X X.Y R
= R
Y Y Y

Proof: Again to prove this theorem, we will make use of complementarity law i.e.,
X + X = 1 and X.X = 0
If XY’s complement is X + Y then it must be true that
(a) X Y + (X + Y) =1 and (b) X Y (X + Y) = 0
 52 Boolean Algebra

To prove the first part

L.H.S. = XY + (X + Y)
= (X + Y) + XY
= (X + Y + X) . (X + Y + Y)
= (X + X + Y) . (X + Y + Y)
= (1 + Y) . (X + 1) (ref. X + X = 1)
= 1.1 (ref. 1 + X = 1)
= 1 = R.H.S.
Now, the second part. i.e., XY . (X + Y) = 0
L.H.S. = XY. (X + Y) (ref. X(Y+Z)=XY+XZ)
= XYX + XYY
= XXY + XYY
= 0.Y + X.0 (ref. X . X = 0)
= 0+0
=0
= RHS
XY.(X + Y) = 0 and XY(X + Y) = 1
Thus, X.Y = X+Y Hence the theorem.

Although the identities above represent De Morgan’s theorem, the transformation

is more easily performed by following these steps:
(i) Complement the entire function
(ii) Change all the ANDs (.) to ORs (+) and all the ORs (+) to ANDs (.)
(iii) Complement each of the individual variables.
This process is called De Morganization.
‘Break the line, change the sign’ to De Morganize a Boolean expression.
Boolean Algebra 53

a) Solve using De Morgan's Theorem

AB+A+AB = AB + A + AB (AB=A+B; Demorgan's 2nd theorem)

=
= AB . A . AB ((X+Y=X.Y) Demorgan's law)
= ABA(A+B)
= ABAA + ABAB
= AB(AA+AB)
= AB(0+AB)
=AB.0+ABAB
=0+0
=0

2.6.3 Applications of De Morgan's Theorem

1. De Morgan's theorem useful in the implementation of the basic gate
operations with alternative gates, particularly with NAND and NOR gates which
are readily available in IC form.
2. De Morgan's theorem is used in the simplification of Boolean expressions.
3. De Morgan's laws commonly apply to text searching using Boolean
operators AND, OR and NOT. Consider a set of documents containing the words
"cars" or "trucks". De Morgan's laws hold that these two searches will return the
same set of documents.
4. De Morgan's laws are an example of a more general concept of mathematical
duality.

2.6.4 Basic Duality of Boolean algebra

We already have talked about duality principle. If you observe all the theorems
and rules covered so far, you’ll find a basic duality which underlines all
Boolean algebra. The postulates and theorems which have been presented can
all be divided into pairs.
For example, X+X.Y = X
Its dual will be X.(X+Y) = X
(Remember, change . to + and vice versa; complement 0 and 1.)
Similarly, (X+Y)+Z = X+(Y+Z) is the dual of (X.Y).Z=X.(Y.Z)
and X+0 = X is dual of X.1 = X
 54 Boolean Algebra

In proving the theorems or rules of Boolean algebra, it is then necessary to prove

only one theorem, and the dual of the theorem follows necessarily.
In effect, all Boolean algebra is predicated on this two-for-one basis.
Example 1.17: Give the dual of following result in Boolean algebra:
XX = 0 for each X.
Solution: Using duality principle, dual of X.X=0 is X+X=1 (By changing (.) to
(+) and vice versa and by replacing 1’s by 0’s and vice versa).
Example 1.18: Give the dual of X+0=X for each X.
Solution: Using duality principle, dual of X+0=X is X.1=X
Example 1.19: State the principle of duality in Boolean algebra and give the
dual of the Boolean expression: (X+Y).(X+Z).(Y+Z)
Solution: Principle of duality states that from every Boolean relation, another
Boolean relation can be derived by
(i) Changing each OR sign (+) to an AND (.) sign
(ii) Changing each AND (.) sign to an OR ( +) sign
(iii) Replacing each 1 by 0 each 0 by 1
The new derived relation is known as the dual of the original relation.
Dual of (X+Y).(X+Z).(Y+Z) will be
(X.Y) + (X.Z) + (Y.Z) = XY +XZ + YZ
2.7 DERIVATION OF BOOLEAN EXPRESSION
Boolean expressions which consist of a single variable or its complement
e.g., X or Y or Z are known as literals.
Now before starting derivation of Boolean expression, first we will talk about
two very important terms. These are (i) Minterms (ii)Maxterms
2.7.1 Minterms
Minterm is a product of all the literals (with or without the bar) within the
logic system.
One of the most powerful theorems within Boolean algebra states that any Boolean
function can be expressed as the sum of products of all the variables within the
system. For example, X+Y can be expressed as the sum of several products, each
of the product containing letters X and Y. These products are called Minterms and
each product contains all the literals with or without the bar.
Also when values are given for different variables, minterm can easily be
formed. E.g., if X=0, Y=1, Z=0 then minterm will be XYZ i.e., for variable with a
value 0, take its complement and the one with value 1, multiply it as it is. Similarly
for X=1, Y=0, Z=0, minterm will be XYZ.
Boolean Algebra 55

Steps involved in minterm expansion of expression

1. First convert the given expression in sum of products form.
2. In each term, if any variable is missing (e.g., in the following example Y is
missing in first term and X is missing in second term), multiply that term with
(missing term+missing term) factor, (e.g., if Y is missing multiply with Y+Y).
3. Expand the expression.
4. Remove all duplicate terms and we will have minterm form of an expression.
Example 1.20: Convert X+Y to minterms.
Solution: X+Y=X.1+Y.1
=X.(Y+Y)+Y(X+X) (X+X=1 complementary law)
=XY+XY+XY+XY
=XY+XY+XY+XY
=XY + XY + XY (XY + XY = XY Indempotent law)
Note that each term in the above example contains all the letters used: X
and Y. The terms XY, X and Y are therefore minterms. This process is called
expansion of expression.
Other procedure for expansion could be
1. Write down all the terms
2. Put X’s where letters much be inserted to convert the term to a product
term.
3. Use all combinations of X’s in each term to generate minterms.
4. Drop out duplicate terms.
Example 1.21: Find the minterms for AB+C.
Solution: It is a 3 variable expression, so a product term must have all three
letters, A, B and C.
1. Write down all terms AB+C
2. Insert X’s where letters are missing ABX+XXC
3. Write all the combinations of X’s in first term ABC, ABC
Write all the combinations of X’s in second term ABC, ABC, ABC, ABC
4. Add all of them. Therefore, AB+C= ABC+ABC+ABC+ABC+ABC+ABC
5. Now remove all duplicate terms. ABC+ABC+ABC+ABC+ABC
Now to verify, we will prove vice versa
ABC+ABC+ABC+ABC = AB + C
LHS = ABC+ABC+ABC+ABC+ABC
= ABC+ABC+ABC+ABC+ABC
= AC(B + B) +ABC+AB(C + C)
= AC.1 + ABC+ AB.1
 56 Boolean Algebra

= AC.1 + ABC+ AB.1

= AC + AB + ABC
= AC + A(B + BC)
= AC + A(B + C) (B+BC=B+C Absorption law)
= AC + AB + AC
= AC + AC + AB
= C(A+A) + AB
= C.1 + AB
= C + AB
= AB + C
= RHS
Shorthand minterm Notation
Since all the letters (2 in case of 2 variable expression, 3 in case of 3
variable expressions) must appear in every product, a shorthand notation has
been developed that saves actually writing down the letters themselves. To form
this notation, following steps are to be followed:
1. First of all, copy original terms.
2. Substitute 0’s for barred letters and 1’s for non-barred letters
3. Express the decimal equivalent of binary word as a subscript of m.
Example 1.22: To find the minterm designation of XYZ
Solution: 1. Copy original form = XYZ
2. Substitute 1’s for non-barred and 0’s for barred letters.
Binary equivalent = 100
3. Decimal equivalent of 100 = 1x22 + 0x21 + 0x20 = 4 + 0 + 0 = 4
4. Express as decimal subscript of
Thus XYZ = m4
Similarly, minterm designation of ABCD would be
Copy Original Term ABCD
Binary equivalent = 1010
Decimal equivalent = 1x23 + 0x22 + 1x21 + 0x20 = 8 + 0 + 2 + 0 = 10
Express as subscript of m = m10
Boolean Algebra 57

2.7.2 Maxterms
A maxterm is a sum of all the literals (with or without the bar) within the
logic system.
Trying to be logical about logic, if there is something called minterm, there
surely must be one called maxterm and there is.
If the value of a variable is 1, then its complement is added otherwise the
variable is added as it is.
Example: If the values of variables are X=0, Y=1 and Z=1 then its Maxterm will
be X + Y + Z(Y and Z are 1’s, so their complements are taken; X= 0, so it is taken
as it is).
Similarly if the given values are X=1, Y=0, Z =0 and W=1 then its Maxterm is
X + Y + Z + W.
Maxterms can also be written as M (Capital M) with a subscript which is
decimal equivalent of given input combination e.g., above mentioned Maxterm
X+Y+Z+W whose input combination is 1001 can be written as M9 as decimal
equivalent of 1001 is 9.
2.7.3 Canonical Expression
Canonical expression can be represented in following two forms:
(i) Sum-of-Products (SOP)
(ii) Product-of-sums (POS)

Boolean Expression composed entirely either of minterms or maxterms is

referred to as Canonical Expression.

Sum-of-Products (SOP)
A logical expression is derived from two sets of known values:
 Various possible input values
 The desired output values for each of the input combinations.
Let us consider a specific problem.
A logical network has two inputs X and Y and an output Z. The relationship
between inputs and outputs is to be as follows:
(i) When X=0 and Y=0 then Z=1
(ii) When X =0 and Y=1 then Z=0
(iii) When X =1 and Y=0, then Z=1
 58 Boolean Algebra

(iv) When X=1 and Y=1, then Z=1

We can prepare a truth table from the above relations as follows:

X Y Z Product Terms
0 0 1 XY
0 1 0 XY
1 0 1 XY
1 1 1 XY

Table 1.36 truth table for product terms (2-input)

Here, we have added one more column to the table consisting list of product
terms or minterms. Adding all the terms for which the output is 1. i.e., Z=1 we get
following expression:
XY + XY + XY = Z
Now see, it is an expression containing only minterms. This type of expression
is called minterm canonical form of Boolean expression or canonical sum-of-
products form of expression.

When a Boolean expression is represented purely as sum of minterms, it

said to be in canonical SOP form.

Example 1.23: A Boolean function F defined on three input variables X, Y and Z

is 1 if and only if number of 1(one) inputs is odd (e.g., F is 1 if X=1, Y=0,Z=0), Draw
the truth table for the above function and express it in canonical sum of products
from.
Solution: The output is 1, only if one of the inputs is odd. All the possible
combinations when one of inputs is odd are
X=1. Y=0, Z=0
X=0, Y=1, Z=0
X=0, Y=0, Z=1
X=1, Y=1, Z=1
For these combinations output is 1, otherwise output is 0. Preparing the truth
table for it we get the following truth table.
Boolean Algebra 59

X Y Z F Product Terms/
Minterms
0 0 0 0 XYZ
0 0 1 1 XYZ
0 1 0 1 XYZ
0 1 1 0 XYZ
1 0 0 1 XYZ
1 0 1 0 XYZ
1 1 0 0 XYZ
1 1 1 1 XYZ

Table 1.37 truth table for product terms (3-input)

Adding all the minterms (product terms) for which output is 1, get
XYZ + XYZ + XYZ + XYZ
This is the desired Canonical SOP from
So, deriving SOP expression from truth table can be summarized as follows:
1. For a given expression, prepare a truth table for all possible combinations
of inputs.
2. Add a new column for minterms and list the minterms for all the combinations.
3. Add all the minterms for which there is output as 1. This gives you the
desired canonical S-O-P expression.
Another method of deriving canonical SOP expression is algebraic method.
This is just the same as above. We will take another example here.
Example 1.24: Convert XY + XZ into canonical SOP from.
Solution: Rule 1: Simplify the given expression using appropriate theorems/
rules.
(XY) + (XZ) = (X + Y) (X + Z) using demorgan's law
= X + YZ (Using Distributive law)
Since it is a 3 variable expression, a product term must have all 3 variables.
Rule 2: Wherever a literal is missing, multiply that term with
missing variable + missing variable
X + YZ = X(Y + Y) (Z + Z) + (X + X) YZ
 60 Boolean Algebra

(Y, Z are missing in first term, x is missing in second term)

= (XY + XY)(Z + Z) + XYZ + XYZ
= Z(XY + XY) + Z(XY + XY) + XYZ + XYZ
= XYZ + XYZ + XYZ + XYZ + XYZ + XYZ
Rule 3: By removing the duplicate terms, we get XYZ + XYZ + XYZ + XYZ + XYZ
This is the desired Canonical SOP from.
Above Canonical SOP expression can also be represented by following
shorthand notation. Here F is a variable function and m is a notation for minterm.
This specifies that output F is sum of 1st, 4th, 5th, 6th and 7th minterms.
i.e., F = m1 + m4 + m5 + m6 + m7 or F=(1,4,5,6,7)
Converting Shorthand notation to minterms
We already have learnt how to represent minterm into shorthand notation.
Now we will learn how to convert vice versa.
Rule1: Find binary equivalent of decimal subscript e.g., for m6 subscript is
6, binary equivalent of 6 is 110.
Rule2: For every 1’s write the variable as it is and for 0’s write variable’s
complemented form i.e., for 110 it is XYZ . XYZ is the required minterm for m6.
Example 1.25: Convert the following three input function F denoted by the
expression into its canonical SOP form.
Solution: If three inputs are X, Y and Z then
F = m0 + m1 + m2 + m5
m0=000  XYZ
m1=001  XYZ
m2=010  XYZ
m5=101  XYZ
Canonical SOP form of the expression is
X Y Z + X Y Z +X Y Z +X Y Z
Product-of-sum form (POS)
When a Boolean expression is represented purely as product of Maxterms,
it is said to be in canonical Product-of-Sum form.
This form of expression is also referred to as Maxterm canonical form of
Boolean expression.
Boolean Algebra 61

Just as any Boolean expression can be transformed into a sum of minterms, it

can also be represented as a product of Maxterms.
(a) Truth table method
The truth Table method for arriving at the desired expression is as follows:
1. Prepare a table of inputs and outputs
2. Add one additional column of sum terms. For each row of the table,
a sum term is formed by adding all the variables in complemented
or uncomplemented form. i.e., if input value for a given variable is 1,
variable is complemented and if 0, not complemented.
Example: If X=0, Y=1, Z=1 then Sum term will be X + Y + Z
Now the desired expression is product of the sums from the rows in which the
output is 0.
Example 1.26: Express in the product of sums from the Boolean function F(X,
Y, Z) and the truth table for which is given below:
X Y Z F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

Solution: Add a new column containing Maxterms. Now the table is as follow:

X Y Z F Maxterms
0 0 0 1 X + Y + Z
0 0 1 0 X + Y + Z
0 1 0 1 X + Y + Z
0 1 1 0 X + Y + Z
1 0 0 1 X + Y + Z
1 0 1 0 X + Y + Z
1 1 0 1 X + Y + Z
1 1 1 1 X + Y + Z
 62 Boolean Algebra

Now by multiplying maxterms for the output 0’s, we get the desired product
of sums expression which is (X + Y + Z) (X + Y + Z) (X + Y + Z)

(b) Algebraic Method

We will explain this method with the help of an example.
Example 1.27 Express X Y + Y( Z (Z + Y)) into canonical product-of-sums form.
Solution: Rule 1: Simplify the given expression using appropriate theorems/rules:
X Y + Y (Z (Z + Y)) = XY + Y(Z Z + Y Z) { X(Y+Z) = XY+XZ }
= XY + Y (Z + YZ ) (Z . Z = Z as X . X = X)
= XY + Y.Z(1 + Y)
=XY+YZ.1 {1 + Y = 1}
=XY+YZ
Rule 2: To convert into product of sums form, apply the Boolean algebra rule
which states that X + YZ = (X + Y) (X + Z)
XY + YZ = (X Y + Y) (X Y + Z) (X + Y = Y + X)
= (Y + X Y) (Z + X Y)
= (Y + X) (Y + Y) (Z + X) (Z + Y)
= (X + Y) Y (X + Z) (Y + Z) (X + Y = Y)
Now, this is in product of sums form but not in canonical product of sums
form (In Canonical expression all the sum terms are Maxterms.)
Rule 3: After converting into product of sum terms, in a sum term for a missing
variable add (Missing variable . missing variable.) e.g., if variable Y is missing add
YY.
(X + Y) (Y)(X + Z)(Y + Z) = (X + Y + ZZ) (X X + Y + ZZ) (X + Y Y + Z) (X X + Y + Z)
Rule 4: Keep on simplifying the expression (using the rule, X+YZ=(X+Y)(X+Z))
until you get product of sum terms which are maxterms.
(X + Y + ZZ) = (X + Y + Z) (X + Y + Z) = M 4. M5
( X X + Y + ZZ) = (XX + Y + Z) (XX + Y + Z)
= (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) =M 0.M4.M1.M5
(X + YY + Z) = (X + Y + Z) (X + Y + Z)= M5.M7
( X X + Y + Z ) = (X + Y + Z) (X + Y + Z) =M1.M5
(X + Y) (Y) (X+Z) (Y+Z) = (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
(X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
Boolean Algebra 63

Short hand = M4, M5, M0, M4, M1, M5, M5, M7, M1, M5 = M(0, 4, 5, 7)
Rule 5: Removing all the duplicate terms, we get
(X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
This is the desired canonical product of sums form of expression.
Shorthand maxterm notation
Shorthand notation of the above given canonical product of sums expression is
F= (0,1,4,5,7) or F =  M(0,1,4,5,7)
This specifies that output F is product 0th, 1st, 4th and 7th Maxterms
i.e., F = M0.M1.M5.M5.M7
Here, M0 means Maxterm for Binary equivalent of 0 i.e., 000 ie., X=0, Y=0, Z=0
And, Maxterm will be (X+Y+Z) (Complemented variable is 1 and uncomplemented
variable is 0)
Similarly, M1 Means 0 0 1 X+Y+ Z
AS F = M0 .M1 .M4. M5 .M7
and M0 = 000 X+Y+Z
M1 = 001 X+Y+Z
M4 =100 X+Y+Z
M5 = 101 X+Y+Z
M7 = 111 X+Y+Z
F = (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
Example 1.28: Convert the following function into canonical product of sums
form: F(X, Y, Z) = M(0, 2, 4, 5)
Note: To convert an expression from shorthand SOP form to shorthand POS
form, just create truth table from given expression. From the created truth table,
derive other form of expression. For example, from truth table, you can convert
an expression F(X, Y,Z)= (0,1,3,5) to M(2,4,6,7)
Solution: F (X, Y, Z) = M(0, 2,4,5) = M0 . M2 .M4 .M5
M0 = 000 X+Y+Z
M2 = 010 X+Y+Z
M4 = 100 X+Y+Z
M5 = 101 X+Y+Z
F = (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
 64 Boolean Algebra

Sum term V/s Maxterm and product term V/s minterm

Sum term means sum of the variables. It does not necessarily mean that
all the variables must be included whereas Maxterm means a sum-term having
the entire variables.
For Example, for 3 Variables F(X, Y, Z) functions X + Y, X + Z, Y + Z etc. are
sum terms whereas X + Y + Z, X + Y + Z, X + Y + Z etc. are Maxterms.
Similarly, product term means product of the variables, not necessarily all
the variables, whereas minterm means product of all the variables.
For A 3 variable (a, b, c) function abc, abc, abc etc. are minterms whereas
ab, bc, bc, ac etc. are product terms only.
Same is the difference between Canonical SOP or POS expression. A
Canonical SOP or POS expression must have all the Minterms or Maxterms
respectively, whereas a simple SOP or POS expression can just have product
terms or sum terms respectively.
2.7.4 Minimization of Boolean expression
After obtaining an SOP or POS expression, the next thing to do is to
simplify the Boolean expression, because Boolean operations are practically
implemented in the form of gates. A minimized Boolean expression means less
number of gates which means simplified circuitry. This section deals with two
methods simplification of Boolean expression.
Algebraic Method
This method makes use of Boolean postulates, rules and theorems to
simplify the expressions.
Example 1.29 simplify ABCD + ABCD + ABCD + ABCD
Solution: ABCD + ABCD + ABCD + ABCD
ABC(D + D) + ABC(D + D) = ABC.1 + ABC.1 (D + D = 1)
= AC(B+B) = AC
Example 1.30: Reduce the expression XY + X + XY
Solution: XY + X + XY

= (X + Y) + X + XY (using Demorgan’s 2nd theorem i.e., )

= X + X + XY + Y
= X + XY + Y {X + X = X as X + X = X}
= (X + X) (X + Y) + Y (Putting X + X = 1
=X+Y+Y {Y + Y = 1}
=X+1 {Putting Y + Y = 1)
=1 {putting X + 1 = 1 as 1 + X =1}
Boolean Algebra 65

Example 1.31: Minimize AB + AC + ABC (AB + C)

Solution AB + AC + ABC (AB + C) = AB + AC + ABCAB + ABCC
= AB + AC + AABBC + ABCC
= AB + AC + ABC {BB = 0 and CC = C}
= AB + A + C + ABC {AC = A + C}
= A + AB + C + ABC {rearranging the terms}
= A + B + C + ABC {A + AB = A + B because X + XY = X + Y}
= A + C + B + ACB (B + BAC = B + AC because X + XY = X + Y)
= A + C + B + AC (C + CA = C + A)
= A + B + C + AC
=A+ B+ C +A
=A+A+ B + C
=1+B+C {A + A = 1}
=1 (1 + X = 1)

Example 1.32: Reduce X Y Z + X Y Z + X Y Z + X Y Z

Solution. X Y Z + X Y Z + X Y Z + X Y Z = X (Y Z + Y Z) + X ( Y Z + Y Z)
= (X + X) (YZ + YZ)

= Z(Y+Y)

=Z

2.8 Simplification using Karnaugh Maps

Truth tables provide a nice, natural way to list all values of a function.
There are several other ways to represent function values. One of the way is
Karnaugh Map (in short K-Map) named after its originator Maurice Karnaugh.
These maps are sometimes also called Veitch diagrams.
 66 Boolean Algebra

Karnaugh Map or K-Map is a graphical display of the fundamental

product in a truth table.
Karnaugh map is nothing but a rectangle made up of certain number of
squares, each square representing a Maxterm or Minterm.
2.8.1 Sum of products Reduction using Karnaugh Map
In S-O-P reduction each square of K-Map represents a minterm of the
given function. Thus, for a function of n variables, there would be a map of 2 n
squares, each representing a minterm (refer to Fig. 1.7). Given a K-map, for SOP
reduction the map is filled in by placing in squares whose minterms lead to a 1
output.
Following are 2,3,4 variable K-maps for SOP reduction. (see fig. 1.7)
Note in every square a number is written. These subscripted numbers
denote that this square corresponds to that number’s minterm. For example, in
3 variable map X Y Z box has been given number 2 which means this square
corresponds to M2. Similarly, box number 7 means it corresponds to m7 and so
on.
Please notice the numbering scheme here, it is 0, 1, 3, 2 then 4, 5, 7, 6
and so on, always squares are marked using this scheme while making a K-map.

Y Y
(0)Y (1)Y (0)Y (1)Y
X X

(0)X XY XY (0)X

0 1 0 1

(1)X XY XY (1)X
2 3 2 3

(a) (a)

Y Y
X (00)YZ (01)YZ (11)YZ (10)YZ X (00)YZ (01)YZ (11)YZ (10)YZ

(0)X XYZ XYZ XYZ XYZ (0)X

0 1 3 2 0 1 3 2

(1)X XYZ XYZ XYZ XYZ (1)X

4 5 7 6 4 5 7 6
(c) (d)
Boolean Algebra 67

Y Y
X (00)YZ (01)YZ (11)YZ (10)YZ X (00)YZ (01)YZ (11)YZ (10)YZ

(00)WX WXYZ WXYZ WXYZ WXYZ (00)WX

0 1 3 2 0 1 3 2

(01)WX WXYZ WXYZ WXYZ WXYZ (01)WX

4 5 7 6 4 5 7 6

(11)WX WXYZ WXYZ WXYZ WXYZ (11)WX

12 13 15 14 12 13 15 14

(10)WX WXYZ WXYZ WXYZ WXYZ (10)WX

8 9 11 10 8 9 11 10

4-variable K Map representing minterms.

Observe carefully above given K-map. See the binary numbers at the top
of K-map. These do not follow binary progression, instead they differ by only one
place when moving from left to right : 00, 01, 11, 10. It is done so that only one
variable changes from complemented to un complemented form or vice versa.
The terms are A B . A B, AB, A B
This binary code 00, 01, 11, 10 is called Gray code. Gray Code is the
binary code in which each successive number differs only in one place. That is
why box numbering scheme follows above order only.
How to Map in K-Map?
We’ll take an example of 2 variable map to be illustrated, with the following
truth table for mapping (Table 1.38)
Table 1.38
A B F
0 0 0
0 1 0
1 0 1
1 1 1
Canonical S-O-P expression for this table is F=AB + AB or F = (2,3).
To map this function first we’ll draw an empty 2-variable K-map as shown in Fig.
1.8(a)
 68 Boolean Algebra

B B B
(0) (1) (0) (1) (0) (1)
A A A

(0) (0) (0) 0 0

(1) (1) 1 1 (1) 1 1

(a) (b) (c)

Now look for output 1 in the given truth table (1.38) for a given truth
table,.
For minterms M2 and M3 the output is 1. Thus mark 1 in the squares for
m2 and m3 i.e., square numbered as 2 and the one numbered as 3. Now our K-
map will look like fig 1.8 (b)
After entering 1’s for all 1 outputs, enter 0’s in all blank squares. K-map
will now look like Fig 1.8 same is the method for mapping 3-variable and 4-
varible maps i.e., enter 1’s for all 1 outputs in the corresponding squares and
then enter 0’s in the rest of the squares.

How to reduce Boolean expression in S-O-P form using K-map?

For reducing the expression, first we have to mark pairs, quads and octets.
To reduce an expression, adjacent 1’s are encircled. If 2 adjacent 1’s are
encircled, it makes a pair; if 4 adjacent 1’s are encircled, it makes a quad; and if 8
adjacent 1’s are encircled, it makes an octet.
While encircling groups of 1’s, firstly search for octets and mark them, then
for quads and lastly go for pairs. This is because a bigger group removes more
variables thereby making the resultant expression simpler.
Reduction of a pair : In the K-map in fig. 1.9, after mapping a given
function F(W, X, Y, Z) two pairs have been marked. Pair-1 is m0+m4 (group of 0th
minterm and 4th minterm as these numbers tell us minterm’s subscript). Pair-2
is m14+m15.
Observe that Pair-1 is a vertical pair. Moving vertically in pair-1, see one
variable X is changing its state from X to X as m0 is W X YZ and m4 is W X YZ.
Compare the two and we see W X YZ changes to W X YZ . So, the variable X can
be removed.
Boolean Algebra 69

YZ YZ
WX (00)YZ (01)YZ (11)YZ (10)YZ WX (00)YZ (01)YZ (11)YZ (10)YZ

(00)WX 1 0 0 0 (00)WX 1 0 0 0
0 1 3 2 0 1 3 2

(01)WX 1 0 0 0 (01)WX 1 0 1 1
4 5 7 6 4 5 7 6

(11)WX 0 0 1 1 (11)WX 1 0 1 1
12 13 15 14 12 13 15 14

(10)WX 0 0 0 0 (10)WX 1 0 0 0
8 9 11 10 8 9 11 10

Pair Reduction Rule

Remove the variable which changes its state from complemented to
uncomplemented or vice versa. Pair removes one variable only.
Thus reduced expression for Pair-1 is W Y Z as W X Y Z (m0) changes to W X Y Z
(m4)
We can prove the same algebraically also as follows :
Pair-1= m0 + m4 = W X Y Z + W X Y Z
= W Y Z ( X + X)
=WYZ.1 (X + X = 1)
=WYZ
Similarly, reduced expression for Pair-2 (m14+m15) will be WXY as WXYZ
(m14) changes to WXYZ (m15). Z will be removed as it is changing its state from
to Z.
Reduction of a quad
If we are given with the K-map shown in fig. 1.10 in which two quads have
been marked.
Quad-1 is m0 + m4 + m12 + m8 and Quad-2 is m7+m6+m15+m14. When we
move across quad-1, two variables change their states i.e., W and X are changing
their states, so these two variables will be removed.
Quad, Reduction Rule
Remove the two variables which change their states. A Quad removes two
variables. Thus reduced expression for quad-1 is Y Z as W and X (both) are
removed.
 70 Boolean Algebra

Similarly, in Quad -2 (m7+m6+m15+m14), horizontally moving, variable Z is

removed as W X Y Z (m7) changes to W X Y Z (m6) and vertically moving, variable
W is removed as (m7) changes to WXYZ. Thus reduced expression for quad-2 is (by
removing W and Z) XY. XY+YZ
Reduction of an octet
Suppose, we have K-map with an octet marked as shown in Fig. 1.11.
YZ
WX (00)YZ (01)YZ (11)YZ (10)YZ

(00)WX 0 0 0 0
0 1 3 2

(01)WX 0 0 0 0
4 5 7 6

(11)WX 1 1 1 1
12 13 15 14

(10)WX 1 1 1 1
8 9 11 10

While moving horizontally in the octet two variables Y and Z are removed
and moving vertically one variable x is removed. Thus eliminating X, Y and Z, the
reduced expression for the octet is W only.
Octet Reduction Rule
Remove the three variables which change their states. An octet removes 3-
variables. But after marking pairs, quads and octets, there are certain other things
to be taken care of before arriving at the final expression. These are map rolling,
overlapping groups and redundant groups.

Map Rolling
Map Rolling means roll the map i.e., consider the map as if its left edges are
touching the right edges and top edges are touching the bottom edges. This is a
special property of Karnaugh maps that its opposite edges squares and corner
squares are considered contiguous (Just as the world map is treated contiguous
at its opposite ends). As in opposite edges squares and in corner squares only one
variable changes its state from complemented to uncomplemented state or vice
versa. Therefore, while making the pairs, quads and octets, map must be rolled.
Following pairs, quads and octets are marking after rolling the map.
Boolean Algebra 71

CD CD
AB (00)CD (01)CD (11)CD (10)CD AB (00)CD (01)CD (11)CD (10)CD

1 1 1
(00)AB (00)AB
0 1 3 2 0 1 3 2

(01)AB 1 1 (01)AB 1 1
4 5 7 6 4 5 7 6

(11)AB (11)AB 1 1
12 13 15 14 12 13 15 14

(10)AB (10)AB
1 1
8 9 1 11 10 8 9 11 10

ABD+BCD BD+BD
Overlapping Groups
Overlapping means same 1 can be encircled more than once. For example,
if the following K-map is given:
CD
(00)CD (01)CD (11)CD (10)CD
AB

(00)AB
0 1 3 2

(01)AB 1 1 1
4 5 7 6

(11)AB
1 1
12 13 15 14

(10)AB 1
8 9 11 10

Observe that 1 for m7 has been encircled twice. Once for Pair-1(m5+m7)
and again for Quad (m7+m6+m15+m14). Also 1 for m14 has been encircled twice.
For the Quad and for Pair-2 (m14+m10).
Here, reduced expression for Pair-1 is ABD
Reduced expression for Quad is BC
Reduced expression for Pair-2 is ACD
Thus final reduced expression for this map is ABD + BC + ACD
 72 Boolean Algebra

Thus reduced expression for entire K-map is sum of all reduced expressions
in the very K-map.
But before writing the final expression we must take care of redundant
Groups.

Redundant Groups
Reduntant group is a group whose all 1’s are overlapped by other groups
(i.e., pairs, quads, octets). Here is an example, given below.

CD CD
AB (00)CD (01)CD (11)CD (10)CD AB (00)CD (01)CD (11)CD (10)CD

(00)AB (00)AB
0 1 3 2 0 1 3 2

(01)AB 1 1 (01)AB 1 1
4 5 7 6 4 5 7 6

(11)AB 1 1 (11)AB 1 1
12 13 15 14 12 13 15 14

(10)AB (10)AB
8 9 11 10 8 9 11 10

Fig. 1.14(a) has a redundant group. There are three pairs : Pair-1 (m4+m5),
Pair-2 (m5+m13), Pair-3 (m13+m15). But Pair-2 is a redundant group as its all 1’s
are marked by other groups.
With this reduntant group, the reduced expression will be ABC+BD+ABD.
For a simpler expression, Redundant Groups must be removed. After removing
the redundant group, we get the K-map shown in fig. 1.14 (b).
The reduced expression, for K-map in fig. 1.14 (b), will be
ABC + ABD
Which is much simpler expression .
Thus removal of redundant group leads to much simpler expression.

Summary of all the rules for S-O-P reduction using K-map

1. Prepare the truth table for given function.
2. Draw an empty K-map for the given function (i.e., 2 variable K-map for 2
variable function; 3 variable K-map for 3 variable function, and so on).
Boolean Algebra 73

3. Map the given function by entering 1’s for the outputs as 1 in the
corresponding squares.
4. Enter 0’s in all left out empty squares.
5. Encircle adjacent 1’s in form of octets, quads and pairs. Do not forget to
roll the map and overlap.
6. Remove redundant groups, if any.
7. Write the reduced expressions for all the groups and OR (+) them.
Example 1.33 Reduce F (a, b, c, d) = m (0,2,7,8,10,15) using Karnaugh map.
Solution: Given F (a, b, c, d) = m (0,2,7,8,10,15)
= m0 + m2 + m7 + m8 + m10 + m15
m0 = 0000 = A B C D m2 = 0010 = A B C D
m7 = 0111 = A B C D m8 = 1000 = A B C D
m10 = 1010 = A B C D m15 = 1111 = A B C D

Truth table for the given Mapping the given function in a K-map
function is as follows : we get
A B C D F
0 0 0 0 1 CD
(00)CD (01)CD (11)CD (10)CD
0 0 0 1 AB
0 0 1 0 1
(00)AB 1 0 0 1
0 0 1 1
0 1 3 2
0 1 0 0
0 1 0 1 (01)AB 0 0 1 0
0 1 1 0 4 5 7 6
0 1 1 1 1
1 0 0 0 1 (11)AB 0 0 1 0
1 0 0 1 12 13 15 14
1 0 1 0 1
(10)AB
1 0 1 1 1 0 1 1
8 9 11 10
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1 1

In the above K-map two groups have been marked, one Pair and One Quad.
Pair is m7 + m15
 74 Boolean Algebra

And Quad is m0 + m2 + m8 + m10

Reduced expression for pair (m7 + m15) is BCD as A is removed. Reduced
expression for quad (m0 + m2 + m8 + m10) is BD as for horizontal corners C is
removed and for vertical corners A is removed.
Thus final reduced expression is BCD + BD
Example 1.34: What is the simplified Boolean equation for the function?
F(A,B,C,D) =(7,9,10,11,12,13,14,15)
Solution: Completing the given Karnaugh map by entering 0’s in the empty
squares, by numbering the squares with their minterm’s subscripts and then by
encircling all possible groups, we get the following K-map.
There is one pair, three quads CD
AB (00)CD (01)CD (11)CD (10)CD
Pair-1= m7 + m15
(00)AB 0 0 0 0
Quad-1 = m12 + m13 + m14 + m15
0 1 3 2
Quad-2 = m13 + m15+m9 +m11
(01)AB 0 0 1 0
Quad-3 = m15 + m11 +m14 + m10 4 5 7 6

(11)AB 1 1 1 1
12 13 15 14

(10)AB
0 1 1 1
8 9 11 10

Reduced expression for pair-1 (m7 + m15) is BCD, as ABCD (m7) changes to
ABCD (m15) eliminating A.
Reduced expression for Quad-1 (m12 + m13 + m14) is AB, as while moving
across the Quad, C and D both are removed because both are changing their
states from complemented to uncomplemented or vice-versa.
Reduced expression for Quad 2 (m13 + m15+m9 +m11) is AD, as moving
horizontally, C is removed and moving vertically, B is removed.
Reduced expression of Quad-3 (m15 + m11 +m14 + m10) is AC as horizontal
movement removes D and vertical movement removes B.
Thus, Pair-1 = BCD, Quad-1 = AB, Quad-2 = AD, Quad-3 = AC
Hence final reduced expression will be BCD+AB+AD+AC.
Example 1.35: Obtain a simplified expression for a Boolean function F (X, Y,
A) the Karnaugh map for which is given below:
Boolean Algebra 75

YZ
[00] [01] [11] [10]
X

[0] [1] [1]

0 1 3 2

[1] [1] [1]

4 5 7 6

Solution: Completing the given K-map.

We have 1 group which is a Quad i.e.,
m1 + m3 +m5 + m7
YZ
Reduced expression for this Quad is Z, as (00)YZ (01)YZ (11)YZ (10)YZ
X
moving horizontally from X Y Z (m1) to
X Y Z (m3), Y is removed (Y changing from (0)X 0 1 1 0
Y to Y) and moving vertically from m1 to 0 1 3 2

m5 or m3 to m7, X changes to X, thus X (1)X 0 1 1 0

is removed. 4 5 7 6
(c)

Example 1.36: Minimize the following

function using a Karnaugh map:
F (W, X, Y, Z) = (0,4,8,12)
Solution: Given function F (W, X, Y, Z) = (0,4,8,12)
F = m0 + m4 + m8 + m12 YZ
WX (00)YZ (01)YZ (11)YZ (10)YZ
m0 = 0000 = W X Y Z
m4 = 0100 = W X Y Z (00)WX 1 0 0 0
0 1 3 2
m8 = 1000 = W X Y Z
(01)WX 1 0 0 0
m12 = 1100 = W X Y Z
4 5 7
6
(11)WX 1 0 0 0

12 13 15
(10)WX 14
1 0 0 0
 76 Boolean Algebra

Maping the given function on a K-Map, we get (m0 + m4 + m8)

Reduced expression for this quad is YZ as while moving across the Quad
W and X are removed. Because these are changing their states from
complemented to uncomplemented or vice versa.
Thus, final reduced expression is YZ.
Example 1.37: Using the Karnaugh technique obtain the simplified expression
as sum products for the following map:

YZ
X (00) (01) (11) (10)

(0) 1 1

(1) 1 1

(d)

Solution: Completing the given K- map, we get one group which is a Quad has
been marked.
Quad reduces two variables. Y
Moving horizontally, Z is removed as it X (00)YZ (01)YZ (11)YZ (10)YZ
changes from Z to Z and moving
(0)X 0 0 1 1
vertically, X is removed as it changes 0 1 3 2
from X to X. Thus only one variable Y
(1)X 0 0 1 1
is left. Hence Reduced S-O-P 4 5 7 6
expression is Y. Thus F=Y assuming F
is the given function.

2.8.2 Product-of-Sum Reduction using Karnaugh Map

In POS reduction each square of K-map represents a Maxterm. Karnaugh
map is just the same as that of the used in S-O-P reduction. For a function of n
variables, map would represent 2n squares, each representing a maxterm.
For POS reduction map is filled by placing 0’s in squares whose Maxterms
lead to output 0.Following are 2, 3 4 variable K-Maps for POS reduction.
Boolean Algebra 77

Y Y
(0) Y (1) Y (0) Y (1) Y
X X

(0) X (0) X (X + Y) (X + Y)
0 1 0 1

(1) X (1) X (X + Y) (X + Y)
2 3 2 3

(a) (b)

2- variable K-Map representing Maxterms.

YZ YZ
(00)Y+Z (01)Y+Z (11)Y+Z (10)Y+Z (00)Y+Z (01)Y+Z (11)Y+Z (10) Y+Z
X X

(0) X (0) X X+Y+Z X+Y+Z X+Y+Z X+Y+Z

0 1 3 2 0 1 3 2

(1) X (1) X X+Y+Z X+Y+Z X+Y+Z X+Y+Z

4 5 7 6 4 5 7 6

(c) (d)

3-variable K-Map representing Maxterms

YZ
(00)Y+Z (01)Y+Z (11)Y+Z (10)Y+Z
X

YZ
(00) (01) (11) (10) [00] W+X W + X + Y + Z W + X + Y + Z W + X + Y + Z W + X + Y + Z
X
[00] 0 1 3 2 0 1 3 2
[00] 4 5 7 6
W+X+Y+Z W+X+Y+Z W+X+Y+Z W+X+Y+Z
[01] W+X
[00] 12 13 15 14
4 5 7 6
[00]
8 9 11 10
[11] W+X W + X + Y + Z W + X + Y + Z W + X + Y + Z W + X + Y + Z
(e)
12 13 15 14

[10] W+X W + X + Y + Z W + X + Y + Z W + X + Y + Z W + X + Y + Z

8 9 11 10

(f)
4 varible K–Map representing Minterms
Figure 1.115: 2,3,4 variable K-Maps of POS expression.
 78 Boolean Algebra

Again the numbers in the squares represent Maxterm subscripts. Box

with number 1 represent M1, Number 6 represent, M6, and so on. Also notice
box numbering scheme is the same i.e., 0, 1, 3, 2 ; 4, 5, 7, 6 ; 12, 13, 15, 14 ; 8,
9, 11, 10.
One more similarity in SOP K-map and POS K-map is that they are binary
progression in gray code only. So, here also some Gray Code appears at the top.
But one major difference is that in POS K-Map, complemented letters
represent 1’s uncomplemented letters represent 0’s, whereas it is just the opposite
in SOP K-Map. Thus in the fig 1.15 (b), (d), (f) for 0’s uncomplemented letters
appear and for 1’s complemented letters appear.
How to derive POS Boolean expression using K-Map?
Rules for deriving expression are the same except for the thing i.e., POS
expression adjacent 0’s are encircled in the form of pairs, quads and octets.
Therefore, rules for deriving POS Boolean expression can be summarized as follows:
1. Prepare the truth table for a given function.
2. Draw an empty K-map for given function (i.e., 2-variable K-map for 2 variable
function; 3 variable K-map for 3 variable function and so on).
3. Map the given function by entering 0’s then squares numbered 5 and 13
will be having 0’s)
4. Enter 1’s in all left out empty squares.
5. Encircle adjacent 0’s in the form of octets, quads, and pair. Do not forget to
role the map and overlap.
6. Remove redundant groups, if any.
7. Write the reduced expressions for all the groups and AND (.) them.
Example 1.38: Reduce the following Karnaugh map in Product of sums form:

BC
A (00) (01) (11) (10)

(0) 0 0 0 1

(1) 0 1 1 1

Solution: To reach at POS expression, we’ll have to encircle all possible groups
of adjacent 0’s encircling we get the following K-map.
Boolean Algebra 79

There are 3 pairs which are;

BC
A [00]B+C [01]B+C [11] B+C B+C

[0]A 0 0 0
0 1 3 2
[1]A
0 0 0
4 5 7 6

Pair1: M0 . M1;
Pair 2: M0 .M4;
Pair 3: M1 . M3;

But there is one redundant group also i.e., Pair-1 (it’s all 0’s are encircled
by other groups). Thus removing this redundant pair-1, we have only two groups
now.
Reduced POS expression for Pair-2 is (B+C), as while moving across pair-2,
A changes its state from A to A, thus A is removed.
Reduced POS expression for Pair 3 is (A+C), as while moving across Pair 3
B changes to B, hence eliminated.
Final POS expression will be (B+C).(A+C)
Example1.39: Find the minimum POS expression of
Y(A, B, C, D) = (0, 1, 3, 5, 6, 7 10, 14, 15).
Solution: As the given function is 4 variable function, we’ll draw 4 variable K-
Map and then put 0’s for the given Maxterms. i.e., in the squares whose numbers
are 0, 1, 3, 5, 6, 7, 10, 14, 15 as each square number represents its Maxterm.
So, K-map will be
CD
AB (00)C+D (01)C+D (11)C+D (10)C+D

(00)A+B 0 0 0 1
0 1 3 2

(01)A+B 1 0 0 0
4 5 7 6

(11)A+B 1 1 0 0
12 13 15 14

(10)A+B 1 1 1 0
8 9 11 10
 80 Boolean Algebra

Encircling adjacent 0’s we have following groups:

Pair-1 = M0. M1; Pair -2= M14. M10;

Quad = M1 .M3. M5. M7; Quad-2 = M7. M6. M15. M14;
Reduced expressions are the following:
For Pair -1, (A+B+C) (as D is eliminated: D changes to D)
For pair-2, (A+C+D) (B Changes to B; hence eliminated)
For Quad-1, (A+D) (Horizontally C and vertically B is eliminated
as C, B are changing their states)
For Quad-2, (B+C) (horizontally D and vertically A is
eliminated)
Hence final POS expression will be
Y(A, B, C, D) = (A+B+C) (A+C+D+) (A+D) (B+C)
Boolean Algebra 81

Review questions:
One mark questions:
1. What is another name of Boolean algebra?
2. What do you understand by logic function?
3. Give examples for logic function.
4. What is meant by tautology and fallacy?
5. Prove the 1+Y is a tautology and 0.Y is a fallacy.
6. State indempotence law.
7. Prove indempotence law using truth table.
8. Draw logic diagram to represent indempotence law.
9. State Involution law.
10. Prove Involution law using truth table.
11. Draw logic diagram to represent Involution law.
12. State Complementarity law.
13. Prove Complementarity law using truth table.
14. Draw logic diagram to represent Complementarity law.
15. State Commutative law.
16. Prove Commutative law using truth table.
17. Draw logic diagram to represent Commutative law.
18. State Associative law.
19. Prove Associative law using truth table.
20. Draw logic diagram to represent Associative law.
21. State Distributive law.
22. Prove Distributive law using truth table.
23. Draw logic diagram to represent Distributive law.
24. Prove that X+XY = X (Absorption law )
25. Prove that X(X+Y) = X (Absorption law )
26. Draw logic diagram to represent Absorption law.
27. Prove that XY + XY = X
28. Prove that (X+Y)(X+Y) = X
29. Prove that X + X Y = X + Y
 82 Boolean Algebra

30. What is a minterm?

31. Find the minterm for XY + Z.
32. What is a maxterm?
33. Find the maxterm for X + Y + Z.
34. What is the canonical form of Boolean expression?

Two marks questions:

1. Prove algebraically that ( X + Y ) ( X + Z ) = X + YZ
2. Prove algebraically that X +XY = X + Y
3. Use duality theorem to derive another Boolean relation from : A + AB=A+B
4. What would be complement of the following :
(a) A(BC + BC)
(b) AB + CD
(c) XY + YZ + ZZ
(d) X + XY + XZ
5. What are the fundamental products for each of the input words;
ABCD = 0010, ABCD = 110, ABCD = 1110. Write SOP expression.
6. A truth table has output 1 for each of these inputs.
ABCD = 0011, ABCD = 0101, ABCD = 1000, what are the fundamental products
and write minterm expression.
7. Construct a Boolean function of three variables X, Y and Z that has an output
1 when exactly two of X, Y and Z are having values 0, and an output 0 in all
other cases.
8. Construct a truth table for three variables A, B and C that will have an
output 1 when XYZ = 100, XYZ = 101, XYZ = 110 and XYZ = 111. Write the
Boolean expression for logic network in SOP form.
9. Convert the following expressions to canonical Product-of-Sum form:
(a) (A+C)(C+D)
(b) A(B+C)(C + D)
(c) (X+Y)(Y+Z)(X+Z)
10. Convert the following expressions to canonical Sum-of-Product form:
(a) (X+XY+XZ)
(b) YZ + XY
(c) AB (B + C)
11. Draw Karnaugh maps for the following expressions:
(a) XY + XY
(b) XYZ + XYZ
(c) XYZ + XYZ + XYZ
12. Draw a general K-map for four variables A, B, C and D.
13. Given the expression in four variables , draw the K – map for the function:
(a) m2 + m3 + m5 + m 7 + m9 + m11 + m13
(b) m0 + m2 + m4 + m8 + m9 + m10 + m11 + m12 + m13
Boolean Algebra 83

14. Draw the K – map for the function in three variables given below.
(a) m0 + m2 + m4 + m6 + m7
(b) m1 + m2 + m3 + m5 + m7
15. Write S-O-P expression corresponding to the function F in the following truth
table and draw the logic gate diagram ( use OR and AND gates)
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Three marks questions:

1. State and prove any three theorems of Boolean algebra.
2. State and prove associative law of addition and multiplication.
3. State and prove De Morgam’s theorems by the method of perfect induction.
4. Obtain the minterm expression for the Boolean function F = A+BC.
5. Explain with an example how to express a Boolean function in its sum-of-
products form.
6. Explain with an example how to express a Boolean function in its product- of-
sum form.
7. Construct a truth table for minterms and maxterms for three variables and
designate the terms.
8. Using basic gates, construct a logic circuit for the Boolean expression
(X+Y).(X+Z).(Y+Z)
9. Simplify the following Boolean expressions and draw logic circuit diagrams of
the simplified expressions using only NAND gates.
(a) ABC + ABC + ABC + ABC
(b) AC + AB + ABC + BC
(c) (ABC).(ABC)+ABC + ABC
(d) ABC + ABC + ABC + ABC
(e) (A+B+C)(A+B+C)(A+B+C)(A+B+C)
10. For a four variable map in w,x,y and z draw the subcubes for
(a) WXY (b) WX (c) XYZ (d) Y
11. Convert the following product-of-sums form into its corresponding sum-of-
products form using write the truth table.
F(x,y,z) = (2,46,7)
12. (a) Reduce the following Boolean expression to the simplest form:
A.[ B+C.(AB + AC)
(b) Given : F(x,y,z) =(1,3,7) then prove that F’(x,y,z) = (0,2,4,5,6)
 84 Boolean Algebra

Five marks questions:

1. Using maps, simplify the following expressions in four variables W, X, Y and
Z.
(a) m1+m3+m5+m6+m7+m9+m11+m13
(b) m0+m2+m4+m8+m9+m10+m11+ m12+m13
2. For the Boolean function F and F’ in the truth table , find the following:
(a) List the minterms of the functions F and F’
(b) Express F and F’ in sum of minterms in algebraic form.
(c) Simplify the functions to an expression with a minimum number of literals.

A B C F F’
0 0 0 0 1
0 0 1 0 1
0 1 0 1 0
0 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 0

3. State and prove De Morgan’s theorems algebraically.

4. Find the complement of F = X + YZ, then show that F.F’ =0 and F + F’ = 1.
5. (a) State the two Absorption laws of Boolean algebra. Verify using truth
table.
(b) Simplify using laws of Boolean algebra. At each step state clearly the law
used for simplification. F = x.y + x.z + x.y.z
6. Given the Boolean function F (x, y, z) = (0, 2, 4, 5, 6). Reduce it using
Karnuagh map method.
7. (a) State the two complement properties of Boolean algebra. Verify using
the truth tables. (b) x.(yz + yz)
8. Given the Boolean function F(A,B,C,D) = (5,6,7,8,9,10.14). Use Karnaugh’s
map to reduce the function F using SOP form. Write a logic gate diagram for
the reduced SOP expression.
9. Given ; F(A,B,C,D) = (0,2,4,6,8,10,14). Use Karnaugh map to reduce the
function F using POS form. Write a logic gate diagram for the reduced POS
expression.
10. Use Karnaugh map to reduce the given functions using SOP form. Draw the
logic gate diagrams for the reduced SOP expression. You may use gates with
more than two inputs. Assume that the variables and their complements
are available as inputs.
Boolean Algebra 85

11. Given the Boolean function F(A,B,C,D)=(0,4,8,9,10,11,12,13,15).

Reduce it by using Karnaugh map.

Working Sheet:
 86 Logic gates

Chapter 3
Logic Gates

Objectives:

 Learning differnt types of gates

 Designing the logical circuits
Logic gates 87

LOGIC GATES
3.1 Introduction
After Shannon applied Boolean algebra in telephone switching circuits,
engineers realized that Boolean algebra could be applied to computer electronics
as well.
In the computers, these Boolean operations are performed by logic gates.

Elementary logic gates

Gates are digital (two-state) circuits because the input and output signals are
either low voltage (denotes 0) or high voltage (denotes 1). Gates are often called
logic circuits, because they can be analyzed with Boolean algebra.

A gate is simply an electronic circuit which operates on one or more

signals and always produces an output signal.

Gates are classified into two types.

(a) Basic gates
(b) Derived gates
(a) Basic gates
There are three basic logic gates:
1. NOT gate (inverter)
2. OR gate
3. AND gate
(b) Derived gates
There are four derived gates:
1. NOR gate
2. NAND gate
3. XOR gate (Exclusive OR gate)
4. XNOR gate (Exclusive NOR gate)
3.1.1 Inverter (NOT gate)
An inverter is also called a NOT gate, because the output is not the same
as the input. The output is sometimes called the complement (opposite) of the
input.
 88 Logic gates

An Inverter is a gate with only one input signal and one output
signal; the output state is always the opposite of the input state.

X
X

X X
X X
0 1
Low High
1 0
High Low

A low input i.e., 0 produces high output i.e., 1 and vice versa. NOT operation
is symbolized as or i.e., NOT X is written as X 1 or X.
3.1.2 OR Gate
The OR gate has two or more input signals but only one output signal. If
one or more input signals are 1 (high), the output signal is 1 (high).
An OR gate can have as many inputs as desired. No matter how many
inputs are there, the action of OR gate is the same.

The OR gate has two or more input signals but only one output
signal. If any of the input signals is 1 (high), the output signal is 1
(high).

Following tables show OR action:

X Y Z F=X+Y+Z
0 0 0 0
X Y F=X+Y
0 0 1 1
0 0 0
0 1 0 1
0 1 1
0 1 1 1
1 0 1
1 0 0 1
1 1 1
1 0 1 1
Table 3.3 Truth table for 1 1 0 1
1 1 1 1
2-input OR gatea
Table 3.4 Truth Table for three input OR gate
Logic gates 89
The symbol for OR gate is given below:

A A A
F B F B F
B C C
D

OR operation is symbolized as + i.e., X or Y is written as X+Y.

3.1.3 AND gate
This gate also can have two or more inputs and always gives single output.
If any input is 0, the output is 0. To obtain output as 1, all inputs must be 1.
Thus, the AND represents the logical multiplication.

The AND Gate can have two or more input signals and produce one
output signal. When all the inputs are high then the output is
high. Otherwise, the output is low.

X Y F=X.Y
0 0 0
0 1 0
1 0 0
1 1 1
Table 3.5: 2- input AND gate

X Y Z F=X.Y.Z
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Table 3.6: 3-input AND gate

 90 Logic gates

The symbol for AND is

A A
A B
F B F F
B C
C D

AND operation is symbolized as X AND Y is written as X.Y

3.2 Derived gates
3.2.1 NOR Gate
NOR gate is nothing but NOT OR gate or inverted OR gate. This means, an
OR gate is always followed by a NOT gate to give NOR gate.
This gate also accepts two or more than two inputs and always produces
single output. If either of the two inputs is 1 (high), the output will be 0 (low).
Also, if all the inputs are low, then the output is high.

The NOR gate has two or more input signals but only one output
signal. If all the inputs are 0 (low), then the output signal is 1
(high).

X Y F = X+Y
0 0 1
0 1 0
1 0 0
1 1 0
Table 3.7: 2-input NOR gate

X Y Z F=X+Y+Z
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0

Table 3.8: 3-input NOR gate

Logic gates 91
NOR operation is symbolized as i.e., X NOR Y is written as X + Y.

(a)

(b) (c) (d)

3.2.2 NAND Gate
NAND gate is NOT AND gate or inverted AND gate. This means, an AND
gate is always followed by a NOT gate to give NAND gate.
NAND gate can also have two or more inputs. This gate produces 0 (low)
for all 1 (high) inputs and produces 1 (high) for other input combinations.

The NAND Gate has two or more input signals but only one output
signal. If all of the inputs are 1 (high), then the output produced is
0 (low).
NAND action is illustrated in following Truth Tables (2.9 and 2.10)
X Y F = XY X Y Z F = XYZ
0 0 1 0 0 0 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 0 0 1 1 1
1 0 0 1
Table 3.9: Truth table of 2-input NAND gate 1 0 1 1
1 1 0 1
1 1 1 0
Table 3.10 Truth table of 3-input NAND gate

The logical meaning of NAND gate can be shown as follows:

NAND operation is symbolized as i.e., X NAND Y is written as X.Y.
3.2.3 XOR Gate or Exclusive-OR Gate
The XOR Gate can also have two or more inputs, but produces one output
signal. Exclusive–OR gate is different from OR gate. OR gate produces output 1
for any input combination having one or more 1’s, but XOR gate produces output
1 for only those input combinations that have odd number of 1’s.
 92 Logic gates

 Accepts two or more inputs and produces single output.

 The output is 0 if there are even number of 1’s in the inputs.
 The output is 1 if there are odd number of 1’s in the inputs.

In Boolean algebra,  sign stands for XOR operation. Thus, A XOR B can
be written as AB.
Following Truth Tables (2.11 and 2.12) illustrates XOR operation.

No. of 1’s X Y Z = AB

Even/odd
Even 0 0 0
Odd 0 1 1
Odd 1 0 1
Even 1 1 0

Table 3.11 Truth table of 2-input XOR gate

No. of 1’s X Y Z F
Even 0 0 0 0
Odd 0 0 1 1
Odd 0 1 0 1
Even 0 1 1 0
Odd 1 0 0 1
Even 1 0 1 0
Even 1 1 0 0
Odd 1 1 1 1

Table 3.12 3 input XOR gate

The symbols of XOR gates are given below:

XOR addition can be summarized as following:

0 0 = 0; 0  1 = 1; 1 0 = 1; 1 1 = 0
The operation representing XOR may be written as F = xy = x y + xy
Logic gates 93
3.2.4 XNOR Gate or Exclusive NOR Gate
An XOR gate is followed by a NOT gate (inventor) becomes XNOR gate.
Thus, The XNOR Gate is logically equivalent to an inverted XOR gate. Thus
XNOR produces 1 (high) as output when the input combination has even number
of 1’s or when all the inputs are 0’s.
Following truth tables 2.13 and 2.14 illustrate XNOR action.
No. of 1’s X Y F
Even/odd
Even 0 0 1
Odd 0 1 0
Odd 1 0 0
Even 1 1 1
Table 3.13 2 input XNOR gate

No. of 1’s X Y Z F
Even 0 0 0 1
Odd 0 0 1 0
Odd 0 1 0 0
Even 0 1 1 1
Odd 1 0 0 0
Even 1 0 1 1
Even 1 1 0 1
Odd 1 1 1 0

Table 3.14 3 input XNOR gate

Following are the XNOR gate symbols:

The bubble (small circle), on the output of NAND, NOR, XNOR gates
represents complementation.
The expression representing XNOR may be written as
F = (X+Y) . (X+Y)
The XNOR operation is symbolized as  i.e. X NOR Y is written as XY.
Now that you are familiar with logic gates, you can use them in designing
logic circuits.
 94 Logic gates

3.2.5 Circuit diagrams

Boolean algebra is useless unless it can be translated into hardware, in
the form of gates. This translation of Boolean algebra in the gates’ form is known
as logic circuits. A logic circuit can be represented diagrammatically using the
traditional symbols of gates. Let us see how this is done, in the following
examples.
Example 2.1: Design a circuit to realize the following:
F(A, B, C) = AB + AC + BAC
Solution: The given Boolean expression can also be written as follows
F(A, B, C) = A . B + A . C + B . A . C
or F(A, B, C) = (A AND B) OR (A AND (NOT C)) OR ((NOT B) AND (NOT A) AND C)
Now these logical operators can easily be implemented in form of logic
gates. Thus circuit diagram for above expression will be as follows:
A AB
B

A AC F
C
AB+AC+BAC

B
BAC
A
C
Example 2.2 Draw the diagram of digital circuit for the function:
F(X, Y, Z) = (X + Y) . (X + Z) . (Y + Z)
Solution: Above expression can also be written as
F(X, Y, Z) = (X OR Y) AND ((NOT X) OR (NOT Z)) AND (Y OR Z)
Thus circuit diagram will be
Logic gates 95

X X+Y
Y

X X+Z F
Z
(X+Y).(X+Z).(Y+Z)

Y Y+Z
Z

3.2.6 NAND, NOR as Universal Gates

We can design circuits using AND, OR and NOT gates as we have done so
far. But NAND and NOR gates are more popular as these are less expensive and
easier to design. Also, The basic gates AND, OR and NOT can easily be
implemented using NAND/NOR gates. Thus NAND, NOR gates are also referred
to as Universal Gates.

Universal gate is a gate using which all the basic gates can be
designed. NAND and NOR gates are called as the universal gates.

NAND–to-NOT logic
Not Operation

X X

NOT X = X NAND X
= X.X {De Morgan's Second Theorem}
=X+X {De Morgan's Second Theorem}
=X

NAND–to-AND logic
AND and OR operations from NAND gates are shown below:
 96 Logic gates

AND operation

X X.Y X.Y
Y

AND operation using NAND is

X . Y = (X NAND Y) NAND (X NAND Y)
Proof: X NAND Y = X.Y
=X+Y (De Morgan’s Second Theorem)
(X NAND Y) NAND (X NAND Y)
= (X + Y) NAND (X + Y)
= (X + Y) . (X + Y) (De Morgan’s Second Theorem)
= X.Y + X.Y (De Morgan’s First Theorem)
=X.Y+X.Y (X = X)
= XY (X + X = X)
OR Operation
X.X
X

X+Y

Y
Y.Y

X + Y = (X NAND X) NAND (Y NAND Y)

Proof : X NAND X = X.X {De Morgan’s Second Theorem}
=X+X {De Morgan’s Second Theorem}
=X { X+X=X }
Similarly, Y NAND Y = Y
Therefore, (X NAND X) NAND (Y NAND Y) = X NAND Y
= (X . Y)
=X+Y {X = X, Y = Y}
=X+Y
Logic gates 97
NAND-to-NAND logic is best suited for Boolean expression in Sum-of-
Products form.

Design rule for NAND-TO-NAND logic Network (only for two-level-circuits)

1 Derive simplified sum-of products expression.
2 Draw a circuit diagram using AND, OR and NOT gates.
3 Just replace AND, OR and NOT gates with NAND gates
For example, XYZ + XZ can be drawn as follows, assuming that inputs and
their complements are available:

X X
Y Y
Z Z
=
Z XYZ+ZX XYZ+ZX
Z
X X

Example 2.3: Draw the diagram of a digital circuit for the function
F(X, Y, Z) = YZ + XZ using NAND gates only.
Solution : F(X, Y, Z) = YZ + XZ can be written as
= (Y NAND Z) NAND (X NAND Z)
Thus logic circuit diagram is

Y
Z Y.Z
X.Z YZ+ZX
X
Z
Example 2.4: Draw the diagram of digital circuit:
F (A, B, C) = AB + BC + CD using NAND-to-NAND logic.
Solution: F(A, B, C) = AB + BC + CD
= (A NAND B) NAND (B NAND C) NAND (C NAND D)
 98 Logic gates

Thus logic circuit is

A A.B
B

B B.C
C AB+BC+CD

C C.D
D

Example 2.5: Draw the circuit diagram for

F = ABC + CB using NAND-to-NAND LOGIC ONLY.
Solution: F = ABC + CB
= ((A NAND (NOT B) NAND C) NAND ((NOT C) NAND B))
Circuit Diagram is

A
B
C

ABC+CB
C
B

NOR-to-NOT logic
NOT, AND and OR operations can be implemented in NOR-to-NOR form
as shown on below.

A A

NOT X = X NOR X
= X+X
= X.X
=X
Logic gates 99
NOR to OR Operation
A + B = (A NOR B) NOR (A NOR B)

A A+B
A+B
B

NOR to AND Operation

A . B = (A NOR A) NOR (B NOR B)

A
A

A.B
B
B

NOR-to-NOR logic is best suited for Boolean expression in Product-of-sum form.

Design rule for NOR-to-NOR logic network (only for two-level-circuits):
1 Derive a simplified product-of-sums form of the expression.
2 Draw a circuit diagram using NOT, OR and AND gates.
3 Finally substitute NOR gates tor NOT, OR and AND gates.
Example 2.6: Represent (X + Y) (Y + Z) (Z + X) in NOR-to-NOR form.
Solution: (X + Y) (Y + Z) (Z + X) = (X NOR Y) NOR (Y NOR Z) NOR (Z NOR X)

A A.B
B

B B.C
C AB+BC+CD

C C.D
D
 100 Logic gates

One mark questions:

1. What is a logic gate?
2. Mention the three basic logic gates?
3. Which basic gate is named as Inverter?
4. Which are the three logic operations?
5. Write the standard symbol for AND gate.
6. Write the truth table for AND gate.
7. Write the logic circuit for AND gate.
8. Write the standard symbol for OR gate.
9. Write the truth table for OR gate.
10.Write the logic circuit for OR gate.
11.Write the standard symbol for NOT gate.
12.Write the truth table for NOT gate.
13.Write the logic circuit for NOT gate.
14.What is a truth table?
15.What is meant by universal gates?
16.Mention different universal gates.
17.What is the output of the two input NAND gate for the inputs:
A=0, B=1?
18.What are the values of the inputs to a three input NAND gate, if its
output is 1?
19.What are the values of the inputs to a three input NAND gate, if its
output is 0?
20.What is the output of the two input OR gate for the inputs: A=0, B=0?
21.What are the values of the inputs to a three input OR gate, if its output
is 0?
22.What are the values of the inputs to a three input OR gate, if its output
is 1?
23.For the truth table given below, what type of logic gate does the output
X represent?

A B C X
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

24.For the truth table given below, what type of logic gate does the output
X represent?
Logic gates 101
A B X
0 0 0
0 1 1
1 0 1
1 1 0

25.State any one of the principle from duality of theorems.

Three Marks Questions

1. What is meant by proof by perfect induction? Give an example.

2. Write the truth table and standard symbol of NAND gate.

3. Explain the working of NAND gate .( write the output conditions)

4.Write the truth table and standard symbol of NOR gate.

5.Explain the working of NOR gate .( write the output conditions)

6.Draw the logic gate diagram to implement AND and OR gates using NAND
gates only. ( any two gates )

7.Draw the logic gate diagram to implement AND and OR gates using NOR
gates only. ( any two gates )

8.Draw the logic gate diagram to implement NOT using

(a) only NOR gates (b) only NAND gates.

9.State De Morgan’s theorems.

10.What is principle of duality? Give an example.

11.Give the dual form of (any two) :

(a) 0.X + X.Y + 1.X
(b) X.(Y+Z) = X.Y + X.Z
(c) X + . Y = X + Y
(d) 1 + X = 1

12.Simplify the following logical expression using De Morgan’s theorems.

(a) (A+B).C
(b) (A+BC).(D+EF)
102 Logic gates

13.Prove the following rules using the proof by perfect induction.

(a) X + XY = X
(b) X+Y =X+Y
14.Draw logic circuit diagram for the following expressions.
(a) Y = AB + C +
(b) Y= +Z + Z
15.Simplify the following Boolean expressions.
(a) A
(b) AB + A

********
Data structure 103

Chatpter 4
Data Structures

Objectives:

 To understand the concept of data structures

 To understand the types of data structures
 To understand the operations on different data structures
 The implementation of different data structures
 Data structure
104

4.1 Introduction
Data is a collection of raw facts that are processed by computers. Data
may contain single value or set of values. For example students name may contain
three sub items like first name, middle name, and last name, whereas students
regno can be treated as a single item. These data have to be processed to form
information.
In order to process the data the data should be organized in a particular
way. This leads to structuring of data. Utilization of space by data in memory
and optimization of time taken for processing, plays an important role in data
structures. Data structures are efficient way to organize the data.
Data structures provide a means to manage large amount of data efficiently.
Data structures are also key factor in designing efficient algorithms. In this
chapter we will discuss about various types of data structures and operations
performed on them.
Data structure means organization or structuring a collection of data items
in appropriate form so as to improve the efficiency of storage and processing.

A data structure is a specialized format for organizing and storing

data.

4.2 Data representation

Computers memory is used to store the data which is required for
processing. This process is known as data representation. Data may be of same
type or different types. A need may arise to group these items as single unit.
Data structures provide efficient way of combining these data types and process
data.
Data structure is a method of storing data in memory so that it can be
used efficiently. The study of data structure mainly deals with:
 Logical or mathematical description of structure.
 Implementation of structure on a computer.
 Analysis of structure which includes determining amount of space
in memory and optimization of time taken for processing.

We consider only the first and second cases are considered in this chapter.
 Data structure 105

4.3 classification of data structures

Integer

Floating
Primitive Data point
structure
Character

Pointers

Single
Dimension
Data
Structure Arrays Two
Dimension

Multi
Dimension
Stack
Non-Primitive
Data Structure Queues
Linear Data
Structures
Linked
Lists List

Files Trees
Non-Linear
Data structure
Graph

4.3.1 Primitive data structures:

Data structures that are directly operated upon by machine-level
instructions are known as primitive data structures.
The integer, real (float), logical data, character data, pointer and reference
are primitive data structures.
 Data structure
106

4.3.2 Operations on primitive data structures

The various operations that can be performed on primitive data structures
are:
 Create: Create operation is used to create a new data structure. . This
operation reserves memory space for the program elements. It
can be carried out at compile time and run-time.
For example, int x;
 Destroy: Destroy operation is used to destroy or remove the data
structures from the memory space.
When the program execution ends, the data structure is
automatically destroyed and the memory allocated is eventually
de-allocated. C++ allows the destructor member function
destroy the object.
 Select: Select operation is used by programmers to access the data within
data structure. This operation updates or alters data.
 Update: Update operation is used to change data of data structures. An
assignment operation is a good example of update operation.
For example, int x = 2; Here, 2 is assigned to x.
Again, x = 4; 4 is reassigned to x. The value of x now is 4
because 2 is automatically replaced by 4, i.e. updated.
4.3.3 Non primitive data structures:
Non-primitive data structures are more complex data structures. These
data structures are derived from the primitive data structures. They stress on
formation of groups of homogeneous and heterogeneous data elements.
Non-primitive data structures are classified as arrays, lists and files.
Array is the collection of homogenous elements under the same name.
The different types of arrays are one-dimensional, two-dimensional and multi-
dimensional.
Data structures under lists are classified as linear and non-linear data
structures.
 Data structure 107

4.3.4 Linear data structure:

Linear data structures are a kind of data structure that has homogenous
elements. Each element is referred to by an index. The linear data structures
are Stack, Queues and Linked Lists.
Data elements of linear data structures will have linear relationship
between data elements. One of the methods is to have linear relationship between
elements by means of sequential memory locations. The other method is to have
linear relationship between data elements by means of pointers or links.
4.3.5 Non-linear data structure:
A non-linear data structure is a data structure in which a data item is
connected to several other data items. The data item has the possibility to reach
one or more data items. Every data item is attached to several other data items
in a way that is specific for reflecting relationships. The data items are not arranged
in a sequential structure.
Trees and Graphs are the examples of non-linear data structures.
4.4 Operations on linear data structure
The basic operations on non-linear data structures are as follows:

 Traversal: The process of accessing each data item exactly once to perform
some operation is called traversing.

 Insertion: The process of adding a new data item into the given collection
of data items is called insertion.

 Deletion: The process of removing an existing data item from the given
collection of data items is called deletion.

 Searching: The process of finding the location of a data item in the given
collection of data items is called as searching.

 Sorting: The process of arrangement of data items in ascending or

descending order is called sorting.

 Merging: The process of combining the data items of two structures to

form a single structure is called merging.
4.5 Arrays
An array is a collection of homogeneous elements with unique name and
the elements are arranged one after another in adjacent memory location.
 Data structure
108

The data items in an array are called as elements. These elements are
accessed by numbers called as subscripts or indices. Since the elements are
accessed using subscripts, arrays are also called as subscripted variables.
4.5.1 Types of Arrays:
There are three types of array:
 One-dimensional Array
 Two-dimensional Array
 Multi-dimensional array
4.5.2 One-dimension Array
An array with only one row or column is called one-dimensional array. It
is finite collection of n number of elements of same type such that
 Elements are stored in contiguous locations
 Elements can be referred by indexing
Array can be denoted as: data type Arrayname[size];
Here, size specifies the number of elements in the array and the index
(subscript) values ranges from 0 to n-1.
 Data structure 109

Features:
 Array size should be positive number only.
 String array always terminates with null character (‘\0’).
 Array elements are counted from 0 to n-1.
 Useful for multiple reading of elements.
Calculating the length of Array
Arrays can store a list of finite number (n) of data items of same data type
in consecutive locations. The number n is called size or length of the array.
The length of an array can be calculated by L = UB – LB + 1
Here, UB is the largest index and LB is the smallest index of an array.
Example: If an array A has values 10, 20, 30, 40, 50, 60 stored in locations 0, 1,
2, 3, 4, 5 then UB = 5 and LB= 0
Size of the array L = 5 – 0 + 1 = 6
4.5.3 Representation of one-dimensional arrays in memory
Elements of linear array are stored in consecutive memory locations. Let P
be the location of the element. Address of first element of linear array A is given
by Base(A) called the Base address of A. Using this we can calculate the address
of any element of A by the formula
LOC(A[P]) = Base(A) + W(P – LB)
Here W is the number of words per memory cell.
Example: Suppose if a string S is used to store a string ABCDE in it with starting
address at 1000, one can find the address of fourth
element as follows:

Now the address of element S[3] can be

calculated as follows:
Address(S[3]) = Base(S) + W(P - LB) Here W =
1 for characters
= 1000 + 1(3 - 0)
= 1003

4.5.4 Basic operations on one-dimensional arrays

The following operations are performed on arrays:
 Data structure
110

1. Traversing: Accessing each element of the array exactly once to do

some operation.
2. Searching: Finding the location of an element in the array.
3. Sorting: Arranging the elements of the array in some order.
4. Insertion: Inserting an element into the array.
5. Deletion: Removing an element from the array.
6. Merging: Combining one or more arrays to form a single array.
4.5.5 Traversing a Linear Array
Traversing is the process of visiting each subscript at least once from the
beginning to last element.
For example, to find the maximum element of the array we need to access
each element of the array.
Algorithm: Let A be a linear array with LB and UB as lower bound and upper
bound. This algorithm traverses the array A by applying the operation PROCESS
to each element of A.
1. for LOC = LB to UB
PROCESS A[LOC]
End of for
2. Exit
Program: To input and output the elements of the array.
#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
void main()
{
int a[10], i, n;
clrscr();
cout<<“How many elements? “;
cin>>n;
cout<<“Enter the elements: “;
for(i=0; i<n; i++)
cin>>a[i];
cout<<“The elements are “;
for(i=0; i<n; i++)
cout<<setw(4)<<a[i];
getch();
}
 Data structure 111

How many elements? 5

Enter the elements 5 10 20 15 10
The elements are 5 10 20 15 10
4.5.6 Searching an element
It refers to finding the location of the element in a linear array. There are
many different algorithms. But the most common methods are linear search
and binary search.
Linear Search
This is the simplest method in which the element to be searched is
compared with each element of the array one by one from the beginning till end
of the array. Since searching is one after the other it is also called as sequential
search or linear search.
Algorithm: A is the name of the array with N elements. ELE is the element to be
searched. This algorithm finds the location loc where the search ELE element is
stored.
Step 1: LOC = -1
Step 2: for P = 0 to N-1
if( A[P] = ELE)
LOC = P
GOTO 3
End of if
End of for
Step 3: if(LOC >= 0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: Exit

Program: To find the location of an element

#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main( )
{
int a[50], i, pos, ele, n;
clrscr( );
cout<<“Enter the number of elements: “;
 Data structure
112

cin>>n;
cout<<“Enter the elements: “;
for(i=0; i<n; i++)
cin>>a[i];
cout<<“Enter the search element: “;
cin>>ele;
pos=-1;
for(i=0; i<n ;i++)
if(ele == a[i])
{
pos = i;
break;
}
if(pos>= 0)
cout<<ele<<“ is present at position “<<pos<<endl;
else
cout<<ele<<“ is not present”<<endl;
getch( );
}

Enter the number of elements: 5

Enter the elements: 10 20 50 40 30
Enter the search element: 40
40 is present at position 3
Binary Search:
When the elements of the array are in sorted order, the best method of
searching is binary search. This method compares the element to be searched
with the middle element of the array. If the comparison does not match the
element is searched either at the right-half of the array or at the left-half of the
array.
Let B and E denote the beginning and end locations of the array. The
middle element A[M] can be obtained by first finding the middle location M by
M = int(B+E)/2, where int is the integer value of the expression.
If A[M] = ELE, then search is successful. Otherwise a new segment is
found as follows:
1. If ELE<A[M] , searching is continued at the left-half of the segment. Reset
E = M – 1.
2. If ELE>A[M], searching is continued at the right-half of the segment. Reset
B = M + 1.
Data structure 113

3. If ELE not found then we get a condition B>E. This results in unsuccessful
search.
Algorithm: A is the sorted array with LB as lower bound and UB as the upper
bound respectively. Let B, E, M denote beginning, end and middle locations of
the segments of A.
Step 1: set B = 0, E = n-1 LOC=-1
Step 2: while (B <= E)
M= int(B+E)/2
if(ELE = A[M]
loc = M
GOTO 4
else
if(ELE <A[M])
E = M-1
else
B = M+1
End of while
Step 3: if(LOC >= 0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: Exit

Program: To find the location of an element.

#include<iostream.h>
void main()
{
int a[10], i, n, m, loc, b, e, pos, ele;
cout<<“How many elements? “;
cin>>n;
cout<<“Enter the elements: “;
for(i=0; i<n; i++)
cin>>a[i];
cout<<“Enter the search element “;
cin>>ele;
pos=-1;
b=0;
e=n-1;
while(b<=e)
{
 Data structure
114

m=(b+e)/2;
if(ele==a[m])
{
pos=m;
break;
}
else
if(ele<a[m])
e=m-1;
else
b=m+1;
}
if(pos>=0)
cout<<“Position= “<<pos;
else
cout<<“Search is unsuccessful”;
}

How many elements? 7

Enter the elements: 10 20 30 40 50 60 70
Enter the search element 60
Position= 5

4.5.7 Insertion an element

Insertion refers to inserting an element into the array. A new element can
be done provided the array should be large enough to accommodate the new
element.
When an element is to be inserted into a particular position, all the
elements from the asked position to the last element should be shifted into the
higher order positions.
Example: Let A be an array with items 10, 20, 40, 50 and 60 stored at consecutive
locations. Suppose item=30 has to be inserted at position 2. The following
procedure is applied.
 Move number 60 to position 5.
 Move number 50 to position 4.
 Move number 40 to position 3
 Position 2 is blank. Insert 30 into the position 2. i.e., A[2] = 30.
Data structure 115

Algorithm: A is the array with N elements. ITEM is the element to be inserted in

the position P.
Step 1: for I = N-1 downto P
A[I+1] = A[I]
End of for
Step 2: A[P] = ITEM
Step 3: N = N+1
Step 4: Exit
Program: To insert an element into the array.
#include<iostream.h>
#include<iomanip.h>
void main()
{
int a[10], i, n, ele, p;
cout<<"How many elements? ";
cin>>n;
cout<<"Enter the elements: ";
for(i=0; i<n; i++)
cin>>a[i];
cout<<"Enter the element to be inserted: ";
cin>>ele;
cout<<"Enter the position ( 0 to "<<n<<"): ";
cin>>p;
if(p > n)
 Data structure
116

cout<<"Invalid position";
else
{
for(i=n-1; i>=p; i--)
a[i+1] = a[i];
a[p] = ele;
n = n+1;
cout<<"The elements after the insertion are ";
for(i=0; i<n; i++)
cout<<setw(4)<<a[i];
}
}

How many elements? 5

Enter the elements: 1 2 4 5 6
Enter the element to be inserted: 3
Enter the position ( 0 to 5): 2
The elements after the insertion are 1 2 3 4 5 6
4.5.8 Deleting an element from the array
Deletion refers to removing an element into the array. When an element
is to be deleted from a particular position, all the subsequent shifted into the
lower order positions.
Example: Let A be an array with items 10, 20, 30, 40 and 50 stored at consecutive
locations. Suppose item=30 has to be deleted at position 2. The following
procedure is applied.
 Copy 30 to Item. i.e., Item = 30
 Move number 40 to position 2.
 Move number 50 to position 3.
Data structure 117

Algorithm: A is the array with N elements. ITEM is the element to be deleted in

the position P and it is stored into the variable Item.
Step 1: Item = A[P]
Step 2: for I = P to N-1
A[I] = A[I+1]
End of for
Step 2: N = N-1
Step 4: Exit
Program: To delete an element from the array.
#include<iostream.h>
#include<iomanip.h>
void main()
{
int a[10], i, n, ele, p;
cout<<“How many elements? “;
cin>>n;
cout<<“Enter the elements: “;
for(i=0; i<n; i++)
cin>>a[i];
cout<<“Enter the position (0 to “<<n-1<<“): “;
cin>>p;
if(p > n-1)
cout<<“Invalid position”;
else
{
ele = a[p];
for(i=p; i<n; i++)
a[i] = a[i+1];
n = n-1;
cout<<“The elements after the deletion is “;
for(i=0; i<n; i++)
cout<<setw(4)<<a[i];
}
}

How many elements? 5

Enter the elements: 10 20 30 40 50
Enter the position (0 to 4): 2
The elements after the deletion is 10 20 40 50
 Data structure
118

4.5.9 Sorting the elements

Sorting is the arrangement of elements of the array in some order. There
are various methods like bubble sort, shell sort, selection sort, quick sort, heap
sort, insertion sort etc. But only insertion sort is discussed in this chapter.
Insertion Sort:
The first element of the array is assumed to be in the correct position. The
next element is considered as the key element and compared with the elements
before the key element and is inserted in its correct position.
Example: Consider the following list of numbers 70 30 40 10 80 stored in the
consecutive locations.
Step 1: Assuming 30 in correct position 70 is compared with 30 . Since 30 is less
the list now is 30 70 40 10 8 0
Step 2: Now 40 is the key element. First it is compared with 70. Since 40 is less
than 70 it is inserted before 70. The list now is 30 40 70 10 80
Step 3: Now 10 is the key element. First it is compared with 70. Since it is less it
is exchanged. Next it is compared with 40 and it is exchanged. Finally it
is compared with 30 and placed in the first position. The list now is
10 30 40 70 80
Step 4: Now 80 is the key element and compared with the sorted elements and
placed in the position. Since 80 is greater than 70 it retains its position.
Algorithm: Let A be an array with N unsorted elements. The following algorithm
sorts the elements in order.

Step 1: for I = 1 to N-1

Step 2: J= I
While ( J >= 1 )
If( A[J] < A[J-1])
temp = A[J]
A[J] = A[J-1]
A[J-1] = temp
If end
J = J-1
While end
for end
Step 3: Exit
Data structure 119

4.5.10 Two-dimensional arrays

A two dimensional array is a collection of elements and each element is
identified by a pair of indices called as subscripts. The elements are stored in
contiguous memory locations.
We logically represent the elements of two-dimensional array as rows and
columns. If a two-dimensional array has m rows and n columns then the elements
are accessed using two indices I and J, where 0<=I<=m-1 and 0<=J<=n-1. Thus
the expression A[I][J] represent an element present at I th-row and Jth-column of
the array A. The number of rows and columns in a matrix is called as the order
of the matrix and denoted as m x n.
The number of elements can be obtained by multiplying number of rows
and number of columns.

In the above figure, the total number

of elements in the array would be,
rows x columns = 3 x 3 =9-elements.

Representation of 2-dimensional array in memory

Suppose A is the array of order m x n. To store m*n number of elements,
we need m*n memory locations. The elements should be in contiguous memory
locations.
There are two methods:
 Row-major order
 Column-major order
Row-major order
Let A be the array of order m x n. In row-major order, all the first-row
elements are stored in sequential memory locations and then all the second-row
elements are stored and so on.
Base(A) is the address of the first element. The memory address of any
element A[I][J] can be obtained by the formula
LOC(A[I][J]) = Base(A) + W[n(I-LB) + (J-LB)]
where W is the number of words per memory location.
Example: Consider the array of order 3 x 3.
 Data structure
120

Column-major order
Let A be the array of order m x n. In column-major order, all the first-
column elements are stored in sequential memory locations and then all the
second-column elements are stored and so on.
Base(A) is the address of the first element. The memory address of any
element A[I][J] can be obtained by the formula
LOC(A[I][J]) = Base(A) + W[(I-LB) + m(J-LB)]
where W is the number of words per memory location.
Example: Consider the array of order 3 x 3.
Data structure 121

Program: To read and print the elements in column-major order.

#include<iostream.h>
#include<iomanip.h>
void main()
{
int a[5][5], i, j, r, c;
cout<<“Enter the order: “;
cin>>r>>c;
cout<<“Enter the elements: “<<endl;
for(i=0; i<c; i++)
for(j=0; j<r; j++)
cin>>a[j][i];
cout<<“The matrix in column-major order is: “<<endl;
for(i=0; i<r; i++)
{
for(j=0; j<c; j++)
cout<<setw(4)<<a[i][j];
cout<<endl;
}
}
 Data structure
122

Enter the order: 2 3

Enter the elements:
1 2 3
4 5 6
The matrix in column-major order is:
1 2 3
4 5 6

Example: Consider the array A of order 25 x 4 with base value 2000 and one
word per memory location. Find the address of A[12][3] in row-major order and
column-major order.
Solution:
Given Base(A) = 2000, m = 25, n=4 LB = 0
W = 1, I = 12, J=3
Row-major order: LOC(A[I][J]) = Base(A) + W[n(I-LB) + (J-LB)]
LOC(A[12][3]) = 2000 + 1[4(12-0)+(3-0)]
= 2000 + 4(12) + 3
= 2000 + 48 + 3
= 2051
Column-major order: LOC(A[I][J]) = Base(A) + W[ (I-LB) + m(J-LB)]
LOC(A[12][3]) = 2000 + 1[(12-0)+25(3-0)]
= 2000 + 1(12 + 75)
= 2000 + 87
= 2087
Applications of arrays
1. Arrays are used to implement other data structures such as heaps, hash
tables, queues, stacks and strings etc.
2. Arrays are used to implement mathematical vectors and matrices.
3. Many databases include one-dimensional arrays whose elements are
records.
Advantages of arrays
1. It is used to represent multiple data items of same type by using only
single name.
 Data structure 123

2. It can be used to implement other data structures like linked lists, stacks,
queues, trees, graphs etc.
3. Two-dimensional arrays are used to represent matrices.
Disadvantages of arrays
1. We must know in advance that how many elements are to be stored in
array.
2. Array is static structure. It means that array is of fixed size. The memory
which is allocated to array cannot be increased or reduced.
3. Since array is of fixed size, if we allocate more memory than requirement
then the memory space will be wasted. If we allocate less memory than
requirement, then it will create problem.
4. The elements of array are stored in consecutive memory locations. So
insertions and deletions are very difficult and time consuming.

STACKS

4.6.1 Introduction
A stack is an ordered collection of items where the addition of new items
and the removal of existing items always take place at the same end. This end is
commonly referred to as the “top”. The end opposite to top is known as the base.

The base of the stack is significant since items stored in the stack that are
closer to the base represent those that have been in the stack the longest. The
most recently added item is the one that is in position to be removed first. This
ordering principle is sometimes called LIFO, last-in first-out. Newer items are
near the top, while older items are near the base.

Many examples of stacks occur in everyday situations. Almost any cafeteria

has a stack of trays or plates where you take the one at the top, uncovering a
new tray or plate for the next customer in line. Imagine a stack of books on a
desk. The only book whose cover is visible is the one on top. To access others in
the stack, we need to remove the ones that are placed on top of them. Another
Figure shows another stack. This one contains a number of primitive data
objects.
 Data structure
124

Figure A Stack of Books

One of the most useful ideas related to stacks comes from the simple
observation of items as they are added and then removed. Assume you start out
with a clean desktop. Now, place books one at a time on top of each other. You
are constructing a stack. Consider what happens when you begin removing
books. The order that they are removed is exactly the reverse of the order that
they were placed. Stacks are fundamentally important, as they can be used to
reverse the order of items. The order of insertion is the reverse of the order of
removal.

Considering this reversal property, you can perhaps think of examples of

stacks that occur as you use your computer. For example, every web browser
has a Back button. As you navigate from web page to web page, those pages are
placed on a stack (actually it is the URLs that are going on the stack). The
current page that you are viewing is on the top and the first page you looked at
is at the base. If you click on the Back button, you begin to move in reverse order
through the pages.

4.6.2 Representation of stacks in memory

The representation of a stack in the memory can be done in two ways.
 Static representation using arrays
 Dynamic representation using linked lists
 Data structure 125

Array Representation of a Stack

Stack can be represented using a one-dimensional array. A block of memory
is allocated which is required to accommodate the items to the full capacity of
the stack. The items into the stack are stored in a sequential order from the first
location of the memory block.
A pointer TOP contains the location of the top element of the stack. A
variable MAXSTK contains the maximum number of elements that can be stored
in the stack.
The condition TOP = MAXSTK indicates that the stack is full and TOP =
NULL indicates that the stack empty.
Representing a stack using arrays is easy and convenient. However, it is
useful for fixed sized stacks. Sometimes in a program, the size of a stack may be
required to increase during execution, i.e. dynamic creation of a stack. Dynamic
creation of a stack is not possible using arrays. This requires linked lists.

Linked list representation of a Stack

The size of the array needs to be fixed to store the items into the stack. If
the stack is full we cannot insert an additional item into the array. It gives an
overflow exception. But in linked list we can increase the size at runtime by
creating a new node. So it is better to implement stack data structure using
 Data structure
126

Linked list data structure. The linked list structure will be studied in detail
later.
START

50 25 20 NULL
Insertion

Insertion operation refers to Inserting an element into stack. We create a

new node and insert an element into the stack. To follow the stack principle
“Last-in-first-out”, a node need to be created from the end of the Linked list
and element need to be inserted into the node from the end of the linked list.

Deletion

Deletion operation is to delete an element or node from the Linked list.

Deletion can be done by deleting the top-most item from the stack as the last
item inserted is the first item that needs to be deleted as per stack principle. So
the recently inserted item i.e, top item must be deletes from the linked list to
perform as stack deletion.
 Data structure 127

4.6.3 Operation Stack

The stack abstract data type is defined by the following structure and
operations. A stack is structured, as described above, as an ordered collection of
items where items are added to and removed from the end called the “top.”
Stacks are ordered LIFO. The stack operations are given below.

 stack() creates a new stack that is empty. It needs no parameters and

returns an empty stack.

 push(item) adds a new item to the top of the stack. It needs the item
and returns nothing.

 pop() removes the top item from the stack. It needs no parameters and
returns the item. The stack is modified.

 peek() returns the top item from the stack but does not remove it. It
needs no parameters. The stack is not modified.

 isEmpty() tests whether the stack is empty. It needs no parameters

and returns a Boolean value.

 size() returns the number of items on the stack. It needs no parameters

and returns an integer.
Algorithm for PUSH Operation: PUSH(STACK , TOP, SIZE, ITEM )
STACK is the array that contains N elements and TOP is the pointer to the
top element of the array. ITEM the element to be inserted. This procedure inserts
ITEM into the STACK.

Step 1: If TOP = N -1then [check overflow]

PRINT “Stack is full”
Exit
End of If
Step 2: TOP = TOP + 1 [Increment the TOP]
Step 3: STACK[TOP] = ITEM [Insert the ITEM]
Step 4: Return

Algorithm for POP Operation: POP(STACK , TOP, ITEM)

STACK is the array that store N items. TOP is the pointer to the top element
of the array. This procedure deleted top element from STACK.
 Data structure
128

Step 1: If TOP = NULL then [check underflow]

PRINT “Stack is empty”
Exit
End of If
Step 2: ITEM = STACK[TOP] [Copy the top element]
Step 3: TOP = TOP – 1 [Decrement the top]
Step 4: Return

4.6.4 Application of Stacks

 The simplest application of a stack is to reverse a word. You push a given
word to stack - letter by letter - and then pop letters from the stack.
 Another application is an “undo” mechanism in text editors; this operation
is accomplished by keeping all text changes in a stack.
 Backtrackin

Backtracking: This is a process when you need

to access the most recent data element in a
series of elements. Think of a labyrinth or maze
- how do you find a way from an entrance to an
exit?
Once you reach a dead end, you must
backtrack. But backtrack to where? to the
previous choice point. Therefore, at each choice
point you store on a stack all possible choices.
Then backtracking simply means popping a
next choice from the stack.

 Language processing:
 Space for parameters and local variables is created internally
using a stack.
 Compiler’s syntax check for matching braces is implemented by
using stack.
 support for recursion
 Conversion of decimal number into binary
 To solve tower of Hanoi
 Expression evaluation and syntax parsing
 Conversion of infix expression into prefix and postfix.
 Rearranging railroad cars
 Data structure 129

 Quick sort
 Stock span problem
 Runtime memory management
Arithmetic expression: An expression is a combination of operands and operators
that after evaluation results in a single value. Operands consist of constants and
variables. Operators consists of {, +, - , * , / …….. etc., ) [ Expressions can be
 Infix expression
 Post fix expression
 Prefix expression
Infix expression: If an operator is in between two operands it is called infix
expression.
Example: a + b, where a and b are the operands and + is an operator.
Postfix expression: If an operator follows the two operands it is called post fix
expression.
Example: ab +
Prefix expression: If an operator precedes two operands, it is called prefix
expression.
Example: +ab
Algorithm for Infix to Postfix

1. Examine the next element in the input.

2. If it is operand, output it.
3. If it is opening parenthesis, push it on stack.
4. If it is an operator, then
 If stack is empty, push operator on stack.
 If the top of stack is opening parenthesis, push operator on stack
 If it has higher priority than the top of stack, push operator on
stack.
 Else pop the operator from the stack and output it, repeat step 4.
5. If it is a closing parenthesis, pop operators from stack and output them
until an opening parenthesis is encountered. Pop and discard the opening
parenthesis.
6. If there is more input go to step 1.
 Data structure
130

7. If there is no more input, pop the remaining operators to output.

Example: Suppose we want to convert 2*3/(2-1)+5*3 into Postfix form.

Evaluating a postfix expression using stack

 The postfix expression to be evaluated is scanned from left to right.

 Each operator in a postfix string refers to the previous two operands
in the string.
 Each time we read an operand we push it into a stack. When we
reach an operator, its operands will then be top two elements on
the stack.
 We can then pop these two elements, perform the indicated operation
on them, and push the result on the stack.
 So that it will be available for use as an operand of the next operator.
 Initialize an empty stack.
 While character remain in the input stream
 Read next character.
 If character is an operand, push it into the stack.
Data structure 131

 Else, if character is an operator, pop top two characters off the

stack, apply the operator, and push the answer back into the
stack.
 Pop the answer off the stack.

Picture below depicts postfix expression using stack

Algorithm for evaluating a postfix expression

WHILE more input items exist
{
If symb is an operand then
push (operand_stk, symb)
else //symbol is an operator
{
Opnd1 = pop(operand_stk);
Opnd2 = pop(operand_stk);
Value = opnd2 symb opnd1
Push(operand_stk, value);
}
} Result = pop (operand_stk);
 Data structure
132

Consider an expression S having operators, operands, left parenthesis

and right parenthesis. Operators includes +, - , /, *. Evaluations are performed
from left to right otherwise indicated by parenthesis. Stack is used to hold
operators and left parenthesis. The postfix expression can be obtained from left
to right using operands from } the operators which are removed from STACK.
Left parentheses are pushed onto stack and right parenthesis at the end of S.
Algorithm is completed when STACK is empty.
Example 1: Convert A + (B * C – (D/E^ F) into postfix notation.
Symbol scanned stack expression
1. A ( A
2. + (+ A
3. ( (+( A
4. B (+( AB
5. * (+(* AB
6. C (+(* ABC
7. - (+(- ABC*
8. ( (+(-( ABC*
9. D (+(-( ABC*D
10. / (+(-(/ ABC*D
11. E (+(-(/ ABC*DE
12. ^ (+(-(/^ ABC*DE
13. F (+(-(/^ ABC*DEF
14. ) (+(- ABC*DEF^/

Examples 2: Convert the following infix expressions postfix notation.

 Data structure 133

Queues
4.7.1 Introduction
We now turn our attention to another linear data structure. This one is
called queue. Like stacks, queues are relatively simple and yet can be used to
solve a wide range of important problems.
A queue is an ordered collection of items where the addition of new items
and the removal of existing items always take place at different ends.

A queue is an ordered collection of items where an item is inserted at

one end called the “rear,” and an existing item is removed at the other
end, called the “front.” Queues maintain a FIFO ordering property.
Insertion and deletion is performed according to the first-in first-out (FIFO)
principle. An excellent example of a queue is a line of students in the food
court of a canteen. New additions to the line are made to the back of the
queue, while removal (or serving) happens in the front. In the queue only two
operations are allowed enqueue and dequeue. Enqueue means to insert an
item into the back of the queue, dequeue means removing the front item. The
picture demonstrates the FIFO access.

The difference between stacks and queues is in removing. In a stack we

remove the item the most recently added; in a queue, we remove the item the
least recently added.

Queue is also called as FIFO list, i.e. First-In-First-Out. Here insertions

are limited to one end of the list called the rear, whereas deletions are limited to
other end called as front.
 Data structure
134

Item1 Item2 Item3 Item4 Item5

FRONT REAR

4.7.2 Types of queues

Queue can be of four types:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double Ended queue)
Data structure 135

1. Simple Queue: In Simple queue insertion occurs at the rear end of the list,
and deletion occurs at the front end of the list.

FRONT REAR

FRONT = 1
A B C D E
REAR = 5
0 1 2 3 4 5 6 7 8

2. Circular Queue: A circular queue is a queue in which all nodes are treated as
circular such that the last node follows the first node.

REAR

FRONT = 1
F D E A B C
REAR = 5
0 1 2 3 4 5 6 7 8

3. Priority Queue: A priority queue is a queue that contains items that have
some preset priority. An element can be inserted or removed
from any position depending on some priority.

4. Dequeue (Double Ended queue):

It is a queue in which insertion and deletion takes place at both the
ends.

Insertion Insertion
Deletion Deletion
 Data structure
136

4.7.3 Operations on queue

The queue abstract data type is defined by the following structure and
operations. The queue operations are given below.

 Queue() creates a new queue that is empty. It needs no parameters

and returns an empty queue.

 enqueue(item) adds a new item to the rear of the queue. It needs the
item and returns nothing. This operation is generally called as push.

 dequeue() removes the front item from the queue. It needs no parameters
and returns the item. The queue is modified. This operation is generally
called as pop.

 isEmpty() tests to see whether the queue is empty. It needs no

parameters and returns a Boolean value.

 size() returns the number of items in the queue. It needs no parameters

and returns an integer.

4.7.4 Memory representation of a queue using arrays

Queue is represented in memory linear array. Let QUEUE be a linear
queue. Two pointer variables called FRONT and REAR are maintained. The pointer
variable FRONT contains the location of the element to be removed and the
pointer variable REAR contains location of the last element inserted. The condition
FRONT = NULL indicates that the queue is empty and the condition REAR = N
indicates that the queue is full.

FRONT REAR

FRONT = 1
A B C D
REAR = 4
0 1 2 3 4 5 6 7 8

REAR = REAR +1, QUEUE[REAR] =’ E’

FRONT REAR

FRONT = 1
A B C D E
REAR = 5
0 1 2 3 4 5 6 7 8
 Data structure 137

ITEM = QUEUE[FRONT], FRONT = FRONT + 1

FRONT REAR

FRONT = 2
B C D E
REAR = 5
0 1 2 3 4 5 6 7 8

Memory representation of a queue using linked list

Queues are also represented using linked lists. In queues an item should
be inserted from rear end and an item should be removed from the front end.
The pointer front contains location of the first node of the linked list and another
pointer rear contains location of the last node.

HEAD FRONT REAR

50 25 20 NULL

HEAD FRONT REAR

50 25 20 75 NULL

HEAD FRONT REAR

25 20 75 NULL

Algorithm for insertion

Algorithm: Let QUEUE be the linear array consisting of N elements. FRONT is
the pointer that contains the location of the element to be deleted and REAR
contains the location of the inserted element. ITEM is the element to be inserted.
 Data structure
138

Step 1: If REAR = N-1 Then [Check for overflow]

PRINT “Overflow”
Exit
Step 2: If FRONT = NULL Then [Check whether QUEUE is empty]
FRONT = 0
REAR = 0
Else
REAR = REAR + 1 [Increment REAR Pointer]
Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position]
Step 4: Return

Algorithm for deletion

Algorithm: Let QUEUE is the linear array consisting of N elements. FRONT is
the pointer that contains the location of the element to be deleted and REAR
contains the location of the inserted element. This algorithm deletes the element
at FRONT position.
Step 1: If FRONT = NULL Then [Check whether QUEUE is empty]
PRINT “Underflow”
Exit
Step 2 : ITEM = QUEUE[FRONT]
Step 3: If FRONT = REAR Then [If QUEUE has only one element]
FRONT = NULL
REAR = NULL
Else
FRONT = FRONT + 1 [Increment FRONT pointer]
Step 3: Return

4.7.5 Applications of queues

 Simulation
 Various features of operating system.
[Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to
occur.]
 Multi-programming platform systems
 Different type of scheduling algorithm
 Round robin technique or Algorithm
 Printer server routines
 Various applications software is also based on queue data structure
 Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to occur.
Data structure 139

LINKED LISTS
4.8.1 Introduction
One disadvantage of using arrays is that arrays are static structures and
therefore cannot be easily extended or reduced to fit the data set. During
insertion, the array elements are shifted into higher order memory locations
and during deletion, elements ate shifted into lower order memory locations. In
this chapter we study another data structure called Linked Lists that addresses
these limitations of arrays. The linked list uses dynamic memory allocations.
Linked list
A linked list is a linear collection of data elements called nodes and the
linear order is given by means of pointers.
Each node contains two parts fields: the data and a reference to the next
node. The first part contains the information and the second part contains the
address of the next node in the list. This is also called the link field.
Data Link

START

30 20 50 10 X

The above picture is linked list with 4 with nodes, each node is contains
two parts. The left part of the node represents the information part of the node
and the right part represents the next pointer field that contains the address of
the next node. A pointer START gives the location of the first node. This pointer
is also represented as HEAD. Note that the link field of the last node contains
NULL.
4.8.2 Types of linked lists
There are three types of linked lists.
1. Singly linked list (SLL)
2. Doubly linked list (DLL)
3. Circular linked list (CLL)
Single linked list
A singly linked list contains two fields in each node – the data field and
link field. The data field contains the data of that node while the link field
contains address of the next node. Since there is only one link field in each
node, the linked list is called as singly linked list.
 Data structure
140

START

50 40 70 20 NULL

In any linked list the nodes need not necessarily represent a set of
consecutive memory locations (or contiguous memory locations).
Circular linked lists:
In a singly linked list, a pointer is available to access all the succeeding
nodes, but not preceding nodes. In the singly linked lists, the link field of the
last node contains NULL.
In circular lists, if the link field of the last node contains the address of the
first node first node, such a linked list is called as circular linked list.
In a circular linked list, it is possible to reach any node from any other
STAR
node.
T
Header node

Doubly linked lists:

It is a linked list in which each node is points both to the next node and
also to the previous node.
In doubly linked list each node contains three parts – FORW, BACK and
INFO.

INFO

BACK: It is a pointer field containing the address of the previous node.

FORW: It is a pointer field that contains the address of the next node.
INFO: It contains the actual data.
 Data structure 141

In the first node, if BACK contains NULL, it indicates that it is the first
node in the list. The node in which FORW contains NULL indicates that the
node is the last node in the linked list.

STAR T
T

x x

In our discussion, we will only study the singly linked list.

4.8.3 Operations on linked lists:
The operations that are performed on linked lists are
1. Creating a linked list
2. Traversing a linked list
3. Inserting an item into a linked list
4. Deleting an item from the linked list
5. Searching an item in the linked list
6. Merging two or more linked lists
Creating a linked list
Linked list is linear data structure which contains a group of nodes and
the nodes are sequentially arranged. Nodes are composed of data and address of
the next node or reference of the next node. These nodes are sequentially or
linearly arrayed that is why the Linked list is a linear data structure. In linked
list we start with a node and create nodes and link to the starting node in order
and sequentially. The pointer START contains the location of the first node. Also
the next pointer field of the last node must be assigned to NULL. In this topic we
will be discussing about Single Linked List. Elements can be inserted anywhere
in the linked list and any node can be deleted.
The nodes of a linked list can be created by the following structure
declaration.
struct Node
{ struct Node
int data; OR {
Node* link; int data;
} Node* link;
Node *node1, *node2;
} *node1, node2;
 Data structure
142

Here data is the information field and link

data link is the link field. The link field contains a pointer
variable that refers the same node structure.
2-bytes 2-bytes Such a reference is called as self-addressing
4-bytes pointer.
The above declaration creates two variable
structures. Each structure will be taken as node.
Thus it is linked list that contains two nodes. Another node cannot be inserted if
it not already declared. Also, there may be cases where the memory needs of a
program can only be determined during runtime. On these cases, programs
need to dynamically allocate memory, for which the C++ language use the
operators new and delete.

 Operator new allocates space.

 Operator new[] allocates memory space for array.
 Operator delete deallocate storage space.
 Operator delete[] deallocate memory space for array.
Operator new and new[]
Dynamic memory is allocated using operator new. new is followed by a
data type specifier and, if a sequence of more than one element is required, the
number of these within brackets []. It returns a pointer to the beginning of the
new block of memory allocated.

Syntax: pointer = new type

pointer = new type [number_of_elements]

The first expression is used to allocate memory to contain one single

element of the required data type. The second one is used to allocate a block (an
array) of elements of data type type, where number_of_elements is an integer
value representing the amount of these. For example:

For example, int *tmp;

tmp = new int [5]

Operator delete and delete[]

In most cases, memory allocated dynamically is only needed during

specific periods of time within a program; once it is no longer needed, it can be
freed so that the memory becomes available again for other requests of
dynamic memory. For this purpose the operator delete is used.

Syntax: delete pointer;

delete [] pointer;
Data structure 143

The first statement releases the memory of a single element allocated

using new, and the second one releases the memory allocated for arrays of
elements using new and a size in brackets [].
The value passed as argument to delete shall be either a pointer to a
memory block previously allocated with new, or a null pointer (in the case of a
null pointer, delete produces no effect).

Dynamically the memory space is allocated for the linked list using new
operator as follows:
Node *newNode;
p = new Node;
data(p) = num;
link(p) = NULL;

Program: Creating a linked list and appending nodes into the linked list.

#include <iostream.h>
class LinkList
{
private:
struct Node
{
int data;
Node* link;
}*START;
public:
LinkList();
void Print(); //Prints the contents of linked list
void Append(int num); //Adds a new node at the end
of the linked list
void Count(); //Counts number of nodes in the linked
list
};
LinkList::LinkList() //Constructor
{
START = NULL;
}

// Prints the contents of linked list

void LinkList::Print()
{
if (START == NULL)
{
cout<< “Linked list is empty”<<endl;
 Data structure
144

return;
}
//Traverse
cout<<“Linked list contains”;
Node* p = START;
while(p != NULL)
{
cout<<“ “<<p->data;;
p = p->link ;
}
}
// Adds a new node at the end of the linked list
void LinkList::Append(int num)
{
Node *newNode;
newNode = new Node;
newNode->data = num;
newNode->link = NULL;

if(START == NULL)
{
//create first node
START = newNode;
cout<<endl<<num<<“ is inserted as the first node”<<endl;
}
else
{
//Traverse
Node *p = START;
while(p->link != NULL)
p = p->link;
//add newnode to the end of the linked list
p->link = newNode;
cout<<endl<<num<<“ is inserted”<<endl;
}
}
// Counts number of nodes present in the linked list
void LinkList::Count()
{
Node *p;
int c = 0;
//Traverse the entire Linked List
for (p = START; p != NULL; p = p->link)
c++;
Data structure 145

cout<<endl<<“No. of elements in the linked list= “<<c<<endl;

}
void main()
{
LinkList* obj = new LinkList();
obj->Print();
obj->Append(100);
obj->Print();
obj->Count();
obj->Append(200);
obj->Print();
obj->Count();
obj->Append(300);
obj->Print();
obj->Count();
}

Linked list is empty

100 is inserted as the first node
Linked list contains 100
No. of elements in the linked list= 1
200 is inserted
Linked list contains 100 200
No. of elements in the linked list= 2
300 is inserted
Linked list contains 100 200 300
No. of elements in the linked list= 3

Traversing a linked list

Traversing is the process of accessing each node of the linked list exactly
once to perform some operation.
To traverse a linked list, steps to be followed are given here.
1. To begin with, move to the first node.
2. Fetch the data from the node and perform the required
operation depending on the data type.
3. Advance the pointer to the next node.
4. Step 2 and step 3 is repeated until all the nodes are visited.
 Data structure
146

Algorithm: This algorithm traverses the linked list. Here START contains the
address of the first node. Another pointer p is temporarily used to visit all the
nodes from the beginning to the end of the linked list.

Step 1: p = START [Initialize p to first node]

Step 2: while p != NULL
Step 3: PROCESS data(p) [Fetch the data]
Step 4: p = link(p) [Advance p to next node]
Step 5: End of while
Step 6: Return

Memory allocation to a linked list

Computer memory is a limited resource. Therefore some mechanism is
required where the memory space of the deleted node becomes available for
future use. Also, to insert a node to the linked list, the deleted node should be
inserted into the linked list. The operating system of the computer maintains a
special list called AVAIL list that contains only the unused deleted nodes.
AVAIL list is linked list that contains only the unused nodes. Whenever a
node is deleted from the linked list, its memory is added to the AVAIL list and
whenever a node is to be inserted into the linked list, a node is deleted from the
AVAIL list and is inserted into the linked list. AVAIL list is also called as the free-
storage list or free-pool.
Inserting a node into the linked list
Sometimes we need insert a node into the linked list. A node can be
inserted into the linked list only if there are free nodes available in the AVAIL
list. Otherwise, a node cannot be inserted. Accordingly there sre three types of
insertions.
1. Inserting a node at the beginning of the linked list
2. Inserting a node at the given position.
3. Inserting a node at the end of the linked list
Inserting a node at beginning of the linked list
START is pointer that contains the memory address of the first node. To
insert an ITEM into the linked list, the following procedure is used.
1. Create a new node.
2. Fill data into the data field of the new node.
3. Mark its next pointer field as NULL.
4. Attach this newly created node to START.
5. Make the new node as the STARTing node.
Data structure 147

Algorithm (inst-beg): This algorithm inserts a node at the beginning of the

linked list.
1. p  new Node;
2. data(p)  num;
3. link(p)  START
4. START  p
5. Return

S T A R T

4 0 7 0 2 0 x

5 0
N e w n o d e

Program: Inserting node at the beginning of the linked list.

#include <iostream.h>
#include<ctype.h>
class LinkList
{
private:
struct Node
{
int data;
Node* link;
}*START;
public:
LinkList();
void Print();
void Count();
void insert(int num);
};
LinkList::LinkList()
{
START = NULL;
}
void LinkList::Print()
{
if (START == NULL)
{
cout<< “Linked list is empty”<<endl;
return;
}
cout<<endl<<“Linked list contains”;
 Data structure
148

Node* p = START;
while(p != NULL)
{
cout<<“ “<<p->data;;
p = p->link ;
}
}
void LinkList::insert(int num)
{
Node *newNode;
newNode = new Node;
newNode->data = num;
newNode->link = START;
START = newNode;
cout<<num<<“ is inserted at the beginning”<<endl;
}
void LinkList::Count()
{
Node *p;
int c = 0;
//Traverse the entire Linked List
for (p = START; p != NULL; p = p->link)
c++;
cout<<endl<<“No. of elements in the linked list= “<<c<<endl;
}
void main()
{
LinkList* obj = new LinkList;
int item;
char ch;

cout<<“Do you want to insert a node at the beginning (Y/N): “;

cin>>ch;
while(toupper(ch) == ‘Y’)
{
cout<<“Enter the item to be inserted at the beginning: “;
cin>>item;
obj->insert(item);
cout<<“Do you want to insert a node at the beginning (Y/N): “;
cin>>ch;
}
obj->Print();
obj->Count();
cout<<“T H A N K Y O U”;
}
 Data structure 149

Do you want to insert a node at the beginning (Y/N): y

Enter the item to be inserted at the beginning: 111
111 is inserted at the beginning
Do you want to insert a node at the beginning (Y/N): y
Enter the item to be inserted at the beginning: 222
222 is inserted at the beginning
Do you want to insert a node at the beginning (Y/N): y
Enter the item to be inserted at the beginning: 333
333 is inserted at the beginning
Do you want to insert a node at the beginning (Y/N): n
Linked list contains 333 222 111
No. of elements in the linked list= 3
THANK YOU

Inserting a node at the end of the linked list

We can insert a node at the end of the linked list. To insert at the end, we
have to traverse the liked list to know the address of the last node.

START

50 40 70

20 NULL
New node

Algorithm (inst-end): Inserting a node at the end of the linked list.

1. START
2. [Identify the last node in the list]
a. p  START
b. while p != NULL
p  next(p)
while end
3. N  new Node [Create new node copy the address to the pointer N]
4. data(N)  item
5. link(N)  NULL
6. link(p)  N
7. RETURN
Inserting a node at a given position
We can insert a node at a given position. The following procedure inserts
a node at the given position.
 Data structure
150

START

50 40 20 NUL

70
New node

Algorithm (INST-POS): This algorithm inserts item into the linked list at the
given position pos.
1. START
2. [[Initialize] count  0
p1  START
3. while (p1 != NULL)
count  count +1
p1  link(p1)
while end
4. a. if (pos = 1)
call function INST-BEG()
else
b. if (pos = count +1)
call function INST-END()
else
c. if( pos <= count)
p1  START
for (i = 1; i <= pos; i++ )
p1  next(p1)
for end
d. [create] p2  new node
data(p2)  item
link(p2)  link(p1)
link(p1)  p2
else
e. PRINT “ Invalid position “
5. RETURN

Garbage collection:
If a node is deleted from the linked list or if a linked list is deleted, we
require the space to be available for future use. The memory space of the deleted
nodes is immediately reinserted into the free-storage list. The operating system
of the computer periodically collects all the deleted space into the free-storage
 Data structure 151

list. This technique of collecting deleted space into free-storage list is called as
garbage collection.

Deleting an item from the linked list:

The deletion operation is classified into three types:
1. Deletion of the first node
2. Deletion of the last node
3. Deletion of the node at the given position
Underflow
If we try to delete a node from the linked list which is empty, the condition
is called as underflow.
Deletion of the first node:
We can easily delete the first node of the linked list by changing the
START to point to the second node of the linked list. If there is only one node in
the liked list, the START can be stored with NULL.
START

20 30 50 40 X

Algorithm (DELE-BEG): This algorithm first copy data in the first node to a variable
and deletes the first node of the linked list.
Step1. START
Step2. p  START
Step3. PRINT data(p)
Step4. START link(p)
Step5. free(p)
Step6. RETURN
Deleting a node at the end (DELE-END)
To delete the last node, we should find location of the second last node.
By assigning NULL to link field of the second last node, last node of the linked
list can be deleted.
START

p1 P2

20 30 50 x 40 X
 Data structure
152

Algorithm (DELE-END): This used two pointers p1 and p2. Pointer p1 is used to
traverse the linked list and pointer p2 keeps the location of the previous node of
p1.
1. START
2. p2  START
3. while ( link(p2) != NULL)
p1  p2
p2  link(p2)
while end
4. PRINT data(p2)
5. link(p1)  NULL
free(p1)
6. STOP

Deleting a node at the given position

To delete a node at the given position, the following procedure is used.
1. Find location of the node to be deleted and the previous node.
2. Delete the node to be deleted by changing the location of the previous
node of the node to be deleted.
Algorithm (DELE-POS): Here p1 and p2 are the pointers. Pointer p2 is used to
traverse the linked list. If pointer p2 has the location of the node to be deleted,
p1 keeps the location of previous node of p2.

1. START
2. Count  0
p1  START
3. while(p1 != NULL)
count = count +1
p1 link(p1)
while end
4. if( pos = 1)
CALL DELE-BEG()
else
if(pos = count)
CALL DELE-END()
else
if(pos < count)
p2  START
for i = 1 to pos
p1  p2
p2  link(p2)
for end
 Data structure 153

PRINT data(p2)
link(p1) link(p2)
free(p2)
else PRINT "Invalid position"
5. RETURN

Non-linear data structure

4.9.1 Introduction
A non-linear data structure is a data structure in which a data item is
connected to several other data items, so that a given data item has the possibility
to reach one-or-more data items.
The data items in a non-linear data structure represent hierarchical
relationship. Each data item is called a node. Examples of non-linear data-
structures are Graphs and Trees.
Pros
 Uses memory efficiently as contiguous memory is not required for allocating
data items.

 The length of the data items is not necessary to be known prior to allocation.
Cons
 Overhead of the link to the next data item.

4.9.2 TREES

A tree is a data structure consisting of nodes organized as a hierarchy -

see figure.
 Data structure
154

Terminology
A node is a structure which may contain a value, a condition, or represent
a separate data structure (which could be a tree of its own). Each node in a tree
has zero or more child nodes, which are below it in the tree (by convention,
trees are drawn growing downwards). A node that has a child is called the parent
node (or ancestor node, or superior). A node has at most one parent.
Nodes that do not have any children are called leaf nodes. They are also
referred to as terminal nodes.
The height of a node is the length of the longest downward path to a leaf
from that node. The height of the root is the height of the tree. The depth of a
node is the length of the path to its root (i.e., its root path).
The topmost node in a tree is called the root node. Being the topmost
node, the root node will not have parents. It is the node at which operations on
the tree commonly begin. All other nodes can be reached from it by following
edges or links.
An internal node or inner node is any node of a tree that has child nodes
and is thus not a leaf node.
A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T.
Binary trees
The simplest form of tree is a binary tree. A binary tree is a tree in which
each node has at most two descendants - a node can have just one but it can’t
have more than two.
A binary tree consists of
a. a node (called the root node) and
b. left and right sub-trees.
Both the sub-trees are themselves binary trees.
The importance of a binary tree is that it can create a data structure that
mimics a “yes/no” decision making process.
 Data structure 155

Root Node: Node at the “top” of a tree - the one from which all operations on the
tree commence. The root node may not exist (a NULL tree with no nodes in it) or
have 0, 1 or 2 children in a binary tree.
Leaf Node: Node at the “bottom” of a tree - farthest from the root. Leaf nodes
have no children.
Complete Tree: Tree in which each leaf is at the same distance from the root.
i.e. all the nodes have maximum two subtrees.
Height: Number of nodes which must be traversed from the root to reach a leaf
of a tree.
4.9.3 GRAPHS
A graph is a set of vertices and edges which connect them. A graph is a
collection of nodes called vertices, and the connections between them, called
edges.
Undirected and directed graphs
When the edges in a graph have a direction, the graph is called a directed
graph or digraph, and the edges are called directed edges or arcs.
Neighbors and adjacency
A vertex that is the end point of an edge is called a neighbor of the vertex,
that is its starting-point. The first vertex is said to be adjacent to the second.
The following diagram shows a graph with 5 vertices and 7 edges. The
edges between A and D and B and C are pairs that make a bidirectional
connection, represented here by a double-headed arrow.
 Data structure
156

One mark questions

1. What are data structures?
2. Differentiate between one-dimensional and two-dimensional array.
3. Give any two examples for primitive data structures.
4. Mention any two examples for non-primitive data structures.
5. What are primitive data structures ?
6. What are non-primitive data structures ?
7. Name the data structure which is called LIFO list.
8. What is the other name of queue.
9. Define an array.
10. What are lists ?
11. What is meant by linear data structures ?
12. What are non-linear data structures ?
13. What is a stack ?
14. What is a queue ?
15. Name the data structure whose relationship between data elements is by
means of links.
16. What is a linked list ?
17 .Mention any one application of stack .
18. What do you mean by traversal in data structure.
19. Define searching in one-dimensional array.
20. What is meant by sorting in an array.
21. Mention the types of searching in the array.
22. What is a binary tree.
23. What do you mean by depth of a tree.
24. What are the operations that can be performed on stacks
25.What are the operations that can be performed on queues ?
26. Define the term PUSH and POP operation in stack.
27. What is FIFO list ?
28. What is LIFO list ?
29. Mention the different types of queues.

Two marks questions:

1. How are data structure classified ?
2. Justify the need for using arrays.
3. How are arrays classified ?
4. Mention the various operations performed on arrays .
5. How do you find the length of the array ?
6. Mention the types of linked lists.
7. What is a stack ? Mention the types of operations performed on the stacks.
8. What is a queue ? Mention the various operations performed on the queue.

Three marks questions:

 Data structure 157

1. Mention the various operations performed on data structures.

2. Explain the memory representation of a one-dimensional array.
3. Explain the memory representation of a stack using one-dimensional array.
4. Explain the memory representation of queue using one-dimensional array.
5. Explain the memory representation of single linked list .
6. Define the following with respect to binary tree
a. root b. subtree c. depth
7. Write an algorithm for traversal in a linear array.
8. Give the memory representation of two-dimensional array.
Five marks questions:
1. Write an algorithm to insert an element in an array.
2. Write an algorithm to delete an element in an array.
3. Write an algorithm to search an element in an array using binary search.
4. Write an algorithm to sort an array using insertion sort.
5. Write an algorithm for push and pop operation in stack using array.
6. Write an algorithm to insert a data element at the rear end of the queue.
7. Write an algorithm to delete a data element from the front end of the queue.
8. Write an algorithm to insert a data element at the beginning of a linked list.
9. Write an algorithm to delete a data element at the end of a linked list.
10. Apply binary search for the following sequence of numbers.
10, 20, 30, 35, 40, 45, 50, 55, 60 search for item = 35
******
158 Review of C++

Chatpter 5

Review of C++

Objectives:

 To understand the basics of C++

 To understand different control structures.

 To understand structured data types arrays,string, functions and structures.

 Review of C++159 159
5.1 Review of C++ language
OPP OOP emphasizes on data. The ideology here is to unite both the data and
the functions that operate on that data into a single unit called as “object”.
Therefore, an object is an identifiable entity with some characteristics and behavior.
OOP view any problem as object rather than as a procedure. For example,
we can say ‘mobile’ is an object and its characteristics are color, weight, display,
size etc. Its features include price, voice call, video call, memory size etc. Here OOP
considers the characteristics as data and features as functions.
Another important concept with respect to OOP is the ‘Class’. A class
serves as a plan or blueprint that specifies what data and what functions should be
included in the objects of that class.
OOP characteristics
The characteristics of OOP are:
·Abstraction Data encapsulation Inheritance·
Polymorphism Polymorphism Dynamic binding ·
Message Passing
Modularity
Modularity is a concept where given problem is divided into sub-problems
and the sub-problems are further divided. Each sub-problem is solved by writing a
subprogram. Each subprogram is called a module.
Abstraction
Abstraction is an act which represents the essential features of an entity
without including explanations or any background details about it.
OOP implements abstraction using classes as a list of abstract attributes.
Data Encapsulation
The binding of data and functions into a single unit called as the class is
known as encapsulation.
The concept of insulating the data from direct access by the program is
called data hiding.
Inheritance
Inheritance is the process by which objects of one class acquires the
properties of the objects of another class.
Polymorphism
Polymorphism means taking more than one form. Polymorphism is the
ability for a message to be processed in more than one form.
The process of making an operator to exhibit different behaviors in different
instances is known as operator overloading.
160 Review of C++

Using a single function name to perform different types of tasks is known

as function overloading.
Polymorphism allows objects to have different internal structures to share
the same external interface. It supports to implement inheritance to a great extent.
Dynamic Binding
Binding means linking of a function call to the code to be executed when
the function is called.
Dynamic Binding means that the code associated with a function call is
not known until the time of the call at run-time. It is associated with polymorphism
and inheritance.
Message Passing
The objects of a class can communicate can communicate with each other.
The objects communicate with each other by sending and receiving messages. A
message means a request for the execution of a function for an object. Therefore, a
message invokes a function in the form of an object to generate the desired output.
For example, consider the message: stack1.push();
Here, we are invoking a function push of an object stack1. stack1 is an
object of the class stack.
5.2 Fundamentals of C++
Bjarne Stroustrup developed C++ at AT & T Bell Laboratories in Murray
Hill, New Jersey. He developed this language in early 1980’s and was very much
concerned in making C++ more efficient.
C++ character set
The following are the character set in C++.
Alphabets A, B, …. , Za, b, …., z
Numerals 0, 1, 2, …., 9
Special characters: + - * % / \ . < > , = _ @ ! ^ & ~ { } [ ] ( ) etc
Tokens
A token is a smallest individual unit in a program or a lexical unit.
The most fundamental elements of a C++ program are “tokens”. These elements
help us to construct statements, definitions, declarations, and so on, which in turn
helps us to construct complete programs. C++ has following tokens:
Identifiers Keywords Variables Constants
Punctuators Operators
Identifiers
An identifier is a name given to the programming elements such as variables,
arrays, functions etc. It can contain letter, digits and underscore. C++ is case sensitive
and henceforth it treats uppercase and lowercase characters differently.
 Review of C++161 161
Exampe: Student _amount marks1 total_ score
STUDENT _AMOUNT RANK5 _Ad12
Keywords
Keyword is a predefined word that gives special meaning to the compiler.
They are reserved words which can be used for their intended purpose and should
not be used as normal identifier. Some of the keywords are given below:
and asm auto bool break case
catch char
Constants or Literals
Constant is an identifier whose value is fixed and does not change during
the execution of the program.
Integer constants
Integer constants are numbers that has no fractional pars or exponent. It
refers to the whole numbers. Integers always begin with a digit or + or -.
We can specify integer constants in decimal, octal, or hexadecimal form.
Unsigned constants:
To specify an unsigned type, use either the u or U suffix. To specify a long
type, use either the l or L suffix.
Example 7.4: 328u 0x7FFFFFL 0776745ul;
Floating point constants
Floating-point constants are also called as real constants. These values contain
decimal points (.) and can contain exponents. They are used to represent values
that will have a fractional part and can be represented in two forms - fractional form
and exponent form.
In the fractional form, the fractional number contains integer part and fractional
part. A dot (.) is used to separate the integer part and fractional part.
Example: 65.05 125.5 -125.75
In the exponential form, the fractional number contains constants a mantissa
and exponent. Mantissa contains the value of the number and the exponent contains
the magnitude of the number. The exponent, if present, specifies the magnitude of
the number as a power of 10.
Example: 7.6: 23.46e0 // 23.46 x 100 = 23.46 x 1 = 23.46
23.46e1 // 23.46 x 101= 23.46 x10 = 234.6
Character constants
Character constants are specified as single character enclosed in pair of
single quotation marks. Single character constants are internally represented as
ASCII codes.
162 Review of C++

For example: ‘A’ ‘p’ ‘5’

There is another class of characters which cannot be displayed on the screen
(non-graphic characters) but they have special meaning and are used for special
purpose. Such character constants are called as escape sequences.
For example: \’ \” \\ \0 \a
String constants
A string zero or more characters enclosed by double quotation marks (“) is
called a string or string constant.
String constants are treated as an array of char. By default, the compiler
adds a special character called the ‘null character’ (‘\0’) at the end of the string to
mark the end of the string.
For example: “Empress College” “Tumkur” “C++ Programming\0”
Punctuators
Punctuators are symbols in C++ and have syntactic and semantic meaning to
the compiler. But do not by themselves specify an operation that yields a value.
Some punctuators can be either alone or in combination. The following characters
are considered as punctuators:
For example: ! % ^ & * ( ) –
C++ Operators
An operator is a symbol that tells the compiler to perform specific mathematical
or logical manipulations.
The operators can be either ‘unary’ or ‘binary’ or even ‘ternary’ operators.
Unary operators
Unary operations have only one operand.
For example: ! & ~ * ++ — + -
Binary operators
The binary operators are those operators that operate on two operands. These
operators can be arithmetic operators, relational, logical operators, bitwise,
assignment operators.
Arithmetic Operators
The arithmetic operators are: + - * / %
These operators are used in arithmetic expressions
Relational Operators:
The relational operators are: == != > < >= <=
These operators are used in relational operations. The relational operations
always give 0 (or False) or 1 (or True).
 Review of C++163 163
Logical Operators
The logical operators supported by C++ are: && || and !
Logical operators are used in logical expressions. Such expressions
always give 0 (or False) or 1 (or True).
Bitwise Operators
Bitwise operator works on bits. The bitwise operators are: & | ^
~ << >>
The Bitwise operators supported by C++ are listed in the following table 7.9.
Shorthand operators
We combine the assignment operators with arithmetic operators and bitwise
operators. Such operators are called as shorthand operators
The shorthand operators are: += -= *= /= %=
&= |= ^=
Assignment Operator
It is an operator used to assign a value to a variable.
The syntax is variable = value or expression;
Example: n = 10; sum = n + 35;
Special Operators
Some special operators are there in C++. They are
sizeof() comma(,) dot(.) pointer(*)
Ternary operators
The ternary operators are those operators that operate on three or more
operands. Ternary operator is also called as conditional operator.
? is the ternary operator. This operator can be used as an alternative to if-else
statement.
Precedence of operators or Hierarchy of operators
If an expression contains multiple operators, the order in which operations
are to be carried out is called hierarchy.
Example : x = 7 + 3 * 2;
Here x is assigned 13, not 20 because operator * has higher precedence than
+. First multiply 3 and 2 and then adds into 7 and assign it to the variable x.
Type Conversion
Converting an expression of a given type into another type is known as type
conversion.
164 Review of C++

Type conversions are of two types, they are

Ø Implicit conversion
Ø Explicit conversion
Implicit conversion
Implicit conversions do not require any type conversion operator. They are
automatically performed when a value is copied to a compatible type. The C++
compiler will implicitly does conversion.
Explicit conversion will be performed by the user. The user can convert an
expression from one type to another type. Such conversions are called as explicit
conversion or type casting.
5.3 Structure of C++ Program
Include files
Class declarations
Member function declaration
main() function
Include files: This section is used to include all the preprocessor directives that are
necessary for the program being written.
Class declaration: A class is a blueprint for the objects. It describes the data and
functions that the object is going to use.
Member function declarations: This section defines or declares the user-defined
functions that other functions or the main() function may use.
main() function: This is also a function that integrates all the other functions of the
program. It contains the body of the function. The body should be enclosed within
curled braces {and}.
The body contains two parts: Local declarations and executable statements.
The local declaration refer to the declaration of all those variables that are used
within the main() function. The executable statements are the statements that
perform the required operations to solve the problem.
5.4 Libaray functions
C++ provides many built-in functions that save the programming time.
They include mathematical functions, character functions, string functions, console
input–output functions and some general standard library functions. Some of them
are given below and also discussed in detail in Functions chapter.
Character Functions
All the character functions require ctype.h header file. The following
table lists the function.
Some functions of character manipulation are given below:
 Review of C++165 165
isalpha() isdigit() isupper() islower() isspace() ispunct()
tolower()toupper() toascii()
String Functions
The string functions are present in the string.h header file. Some string
functions are given below:
Some of the functions are: strlen() strcat() strcpy() strrev()
strupr() strlwr() strcmp() strcmpi()
Console I/O functions
The following are the list of functions is in stdio.h are:
getchar() putchar() gets() puts()
5.5 Data types
Variables
A variable is an identifier whose value is allowed to change during the
execution of the program. A variable actually represent the name of the memory
location.
Declaration of a variable
The syntax for declaring a variable is datatype variable_name;
Example: int n = 50;
Initializing a variable
The syntax to initialize a variable is: datatype variable_name = value;
Example : Let b be a variable declared of the type int. Then, int b = 100;
C++ compiler allows us to declare a variable at run time. This is dynamic
initialization. They can be initialized anywhere in the program before they are
used.
Example int a, b;
….
int temp = a;
a = b;
b = a;
5.5 Data types: C++ support the following data types.
Data types classification
There are two types of data types.
Ø Simple or fundamental data types
Ø Complex or Derived data types
166 Review of C++

The simple or fundamental data types are the primary data types which
are not composed of any other data types.
The simple data types/fundamental data types include int, char, float
double and void.
Modifiers
The data type modifiers are listed here: signed, unsigned, long and short.
Example: unsigned int b;
Derived data types
These data types are constructed using simple or fundamental data types.
They include arrays, functions, pointers and references.
User defined data types
These data types are also constructed using simple or fundamental data
types. Some user defined data types include structure, union, class and enumerated.
5.6 Input and output Operators
Input and output operators are used to perform input and output operations.
Input Operator “>>”

The standard input device is usually the keyboard. Input in C++ is done by
using stream extraction operator (>>) on the cin stream. The operator must be
followed by the variable that will store the data that is going to be extracted from
the stream.
Example : int age;
cin>>age;
Output Operator “<<“
The standard output device is the screen (monitor) and outputting in C++
is done by using the object followed by the stream insertion operator which is
written as << . cout stands for Console output.
 Review of C++167 167
Example: cout<< “ Let us learn C++”; // prints Let us learn C++
//on the screen.
Cascading of I/O operators:
C++ supports the use of stream extraction (<<) and stream insertion (>>)
operators many times in a single input (cin) and output (cout) statements. If a
program requires more than one input variable then it is possible to input these
variables in a single cin statement using multiple stream extraction operators.
Similarly, when we want to output more than one result then this can be done
using a single cout statement with multiple stream insertion operators. This is
called as cascading of input output operators.
Example : cout<<“ enter the value for x”;
cin>> x;
cout<<“ enter the value for y”;
cin>>y;
Instead of using cin statement twice, we can use a single cin statement
and input the values for the two variables x and y using multiple stream extraction
operator as shown below.
cout<<“ enter the value for x and y”;
cin>>x>>y;
Similarly, we can even output multiple results in a single cout statement
using cascading of stream insertion operator as shown below.
cout<<“ the sum of” <<x<<“ and “<<y<<“=”<<x+y;
5.7 Control Statements
C++ provides us control structures, statements that can alter the flow of a
sequence of instructions. .
Compound statements
Compound statements or block is a group of statements which are
separated by semicolons (;) and grouped together in a block enclosed in braces {
and } is called a compound statement.
Example: {
temp = a;
a = b;
b = temp;
}
Types of control statements
C++ supports two basic control statements.
· Selection statements
· Iteration statements
168 Review of C++

Selection statements This statement allows us to select a statement or set of

statements for execution based on some condition.
The different selection statements are:
i. if statement
ii. if-else statement
iii. nested statement
iv. switch statement
if statement
This is the simplest form of if statement. This statement is also called as
one-way branching. This statement is used to decide whether a statement or a set
of statements should be executed or not. The decision is based on a condition
which can be evaluated to TRUE or FALSE.
Example if (n = = 100) cout<< “ n is 100 “;
The if–else statement
This statement is also called as two-way branching. It is used when there
are alternative statements need to be executed based on the condition. It executes
some set of statements when the given condition is TRUE and if the condition is
FALSE then other set of statements to be executed.
Nested-if statement
An if statement may contain another if statement within it. Such an if
statement is called as nested if statement.
There are two forms of nested if statements:
Format I: if-else-if statement
This structure is also called as else-if ladder. This structure will be used to
verify a range of values. This statement allows a choice to be made between different
possible alternatives. A choice must be made between more than two possibilities.
Format II:
This structure contains an if-else statement within another if-else statement.
Switch statement
C++ has a built-in multiple-branch selection statement, switch. This
successively tests the value of an expression against a list of integer or character
constants. When a match is found, the statements associated with that code is
executed.
Iteration statements or loops
Iteration statements are also called as loops. Loop is a statement that allows
repeated execution of a set of instructions until certain condition is satisfied. This
condition may be predefined or post-defined. Loops have a purpose to repeat a
 Review of C++169 169
statement or set of statements a certain number of times or some condition is
fulfilled. We use three types of looping structures in C++.
Ø while loop
Ø do- while loop
Ø for loop
while loop
This looping structure is also called as pre-tested looping structure. This
statement repeats the execution of a set of statements while the condition is TRUE.
Example: c = 1;
while(c <= 10)
cout<<setw(4)<<c;
do-while loop
This looping structure is also called as post-tested looping structure. Unlike
while loop that test the loop condition at the beginning, the do-while loop checks
the condition after the execution of the statements in it. This means that a do-while
loop always executes at least once. Its functionality is exactly the same as the while
loop, except that the condition in the do while loop is evaluated after the execution
of statement, instead of before.
Example: c = 1;
do
{
cout<<setw(4)<<c;
} while(c <= 10);
The for loop
This statement is called as the fixed execution looping statement. It is
normally used when we know in advance exactly how many times a set of statements
should be repeatedly executed again and again. It provides initialization, loop-end-
condition and increment/decrement process statements in a single line. When one
is aware of fixed number of iterations, then this looping structure is best suited.
Jump statements or Transfer of control from within loop
Transfer of control within looping are used to
Ø Terminate the execution of loop
Ø Exiting a loop
Ø Half way through to skip the loop.
All these can be done by using break, exit, and continue statements.
5.8 ARRAYS
Array fundamentals
An array is collection of objects and all the objects have the same name.
Each object is called an element. The elements are numbered as 0, 1, 2,…, n-1.
170 Review of C++

These numbers are called as indices or subscripts. These numbers are used to
locate the positions of elements within the array.
The method of numbering the ith element with index i-1 is called as zero-
based indexing. That is, the element is always same as the number of “steps”
from the initial element a[0] to that element. For example, the element a[3] is 3
steps from the element a[0].
Types of arrays
There are three types of arrays.
i. One-dimensional array
ii. Two-dimensional array
iii. Multi-dimensional array
One-dimensional array
It is an array in which each element is accessed by using only one subscript.
The only one subscript represents the position of the element in the array.
Two-dimensional array
It is an array in which each element is accessed using 2-subsripts. The
subscripts represent the position of element in the array.
Multi-dimensional array
A multidimensional array is an array of n-dimensions. In other words, an
array of arrays is called a multidimensional array. A one-dimensional array of one-
dimensional arrays is called a two-dimensional array; a one-dimensional array to
two-dimensional arrays is called a three-dimensional array and so on.
One-dimensional array:
It is an array in which each element is accessed by using only one subscript.
The only one subscript represents the position of the element in the array.
Declaration of one-dimensional array
Syntax datatype array-name[size];
Example : int marks[50];
Initialization of one-dimensional arrays
You can give values to each array element when the array is first defined.
Example : int a[5] = {9, -5, 6, 2, 8};
In the above example, value 9 is stored in a[0], value -5 is stored in a[1],
value 6 is store in a[2], value 2 is stored in a[3] and value 8 is store in a[4].
Memory representation of one-dimensional arrays:
The elements of one-dimensional arrays are stored in contiguous memory
locations.