Syllabus
B.C.A. Part-I
Algorithms and Data Structure
Algorithms, Pseudo Code, Efficiency of Algorithms, Analyzing Algorithms and
Problems, Complexity Measures, Basic Time Analysis of an Algorithm, Space
Complexity.
Data Abstraction and Basic Data Structures, Data Types, Abstract Data Types and
C++ Classes.
String Processing (Storing Strings, String Operations, Word Processing, Pattern
Matching Algorithms).
Arrays and their Representation, Representation of Linear Arrays in Memory, Sorting
and Searching, Bubble Sort and Binary Search, Multidimensional Arrays, Pointer
Arrays, Records and Record Structures.
Linked Lists, Representation of Linked List in Memory, Insertion, Deletion and
Searching of Linked List, Two Way Lists, Stacks, Array Representation of Stacks,
Arithmetic Expressions, Polish Notations, Quick Sort, Recursion, Queues, De-queues,
Priority Queues.
Tables and Searching, Linear Search, Binary Search, Hash Tables, Trees, Binary and
N-ary Trees, Representation of Binary Trees in Memory, Traversing Binary Trees,
Traversal Algorithms using Stacks, Header Nodes, Threads, Binary Search Trees,
Heap, Heapsort, Huffman‘s Algorithm.
Graph and their Representation, Sequential Representation, Warshall‘s Algorithm,
Linked Representation of Graphs, Operations on Graphs Traversing a Graph.
Sorting and Searching : Sequential, Binary and Hashed Searching, Internal and
External Sorting Techniques, Bubble Sort, Insertion Sort, Selection Sort, Merge Sort,
Radix Sort and Quick Sort Comparison.
□□□
,Algorithms and Data Structure 5
Content
S.No. Name of Topic
1. Basics of Algorithms
2. Data Structure Organisation
3. Arrays
4. Strings
5. C++ : Classes and Objects
6. Linked List
7. Stacks
8. Queue
9. Sorting and Searching Techniques
10. Graph
11. Tree
12.
13.
Unsolved Papers 2011 to 2006
MCQ
□□□
6
Chapter-1
Basics of Algorithms
Q.1. What are the various steps to plan algorithm?
Ans.: Following steps must be followed to plan any algorithm :
,(1) Device Algorithm : Creating an algorithm is an art in which may never
be fully automated. When we get the problem, we should first analyse
the given problem clearly and then write down some steps on the
paper.
(2) Validate Algorithm : Once an algorithm is devised , it is necessary to
show that it computes the correct answer for all possible legal inputs .
This process is known as algorithm validation. The algorithm need not
as yet be expressed as a program. It is sufficient to state it in any precise
way. The purpose of validation is to assure us that this algorithm will
work correctly independently of the issues concerning the
programming language it will eventually be written in. Once the
validity of the method has been shown, a program can be written and a
second phase begins. This phase is referred to as program proving or
program verification.
(3) Analyse Algorithm : As an algorithm is executed , it uses the
computers central processing unit to perform operations and its
memory ( both immediate and auxiliary) to hold the program and data.
Analysis of algorithm or performance analysis refers to the task of
determining how much computing time and storage an algorithm
requires. An important result of this study is that it allows you to make
quantitative judgments about the value of one algorithm over another.
Another result is that it allows you to predict whether the software will
meet any efficiency constraints that exist. Analysis can be made by
taking into consideration.
Algorithms and Data Structure 7
(4) Test A Program : Testing a program consists of 2 phases : debugging
and performance management. Debugging is the process of executing
programs on sample data sets to determine whether results are
, incorrect if so corrects them. Performance management is the process of
executing a correct program on data sets and measuring the time and
space it takes to compute the results. These timing figures are useful in
that they may confirm a previously done analysis and point out logical
places to perform useful optimization.
Q.2. Define Algorithms with suitable example.
Ans.: Consider the following three examples. What do they all have in common?
How to change your motor oil
(1) Place the oil pan underneath the oil plug of your car.
(2) Unscrew the oil plug.
(3) Drain oil.
(4) Replace the oil plug.
(5) Remove the oil cap from the engine.
(6) Pour in 4 quarts of oil.
(7) Replace the oil cap.
Therefore an algorithm is a set of instructions for solving a problem. Once we
have created an algorithm, we no longer need to think about the principles on
which the algorithm is based. This means that algorithms are a way of
capturing intelligence and sharing it with others. Once you have encoded the
necessary intelligence to solve a problem in an algorithm, many people can
use your algorithm without needing to become experts in a particular field.
Q.3 Why the algorithm are important to computers. How can we create it in
understandable form?
Ans. Algorithms are especially important to computers because computers are
really general purpose machines for solving problems. But in order for a
computer to be useful, we must give it a problem to solve and a technique for
8
B.C.A. Part-I
Algorithms and Data Structure
Algorithms, Pseudo Code, Efficiency of Algorithms, Analyzing Algorithms and
Problems, Complexity Measures, Basic Time Analysis of an Algorithm, Space
Complexity.
Data Abstraction and Basic Data Structures, Data Types, Abstract Data Types and
C++ Classes.
String Processing (Storing Strings, String Operations, Word Processing, Pattern
Matching Algorithms).
Arrays and their Representation, Representation of Linear Arrays in Memory, Sorting
and Searching, Bubble Sort and Binary Search, Multidimensional Arrays, Pointer
Arrays, Records and Record Structures.
Linked Lists, Representation of Linked List in Memory, Insertion, Deletion and
Searching of Linked List, Two Way Lists, Stacks, Array Representation of Stacks,
Arithmetic Expressions, Polish Notations, Quick Sort, Recursion, Queues, De-queues,
Priority Queues.
Tables and Searching, Linear Search, Binary Search, Hash Tables, Trees, Binary and
N-ary Trees, Representation of Binary Trees in Memory, Traversing Binary Trees,
Traversal Algorithms using Stacks, Header Nodes, Threads, Binary Search Trees,
Heap, Heapsort, Huffman‘s Algorithm.
Graph and their Representation, Sequential Representation, Warshall‘s Algorithm,
Linked Representation of Graphs, Operations on Graphs Traversing a Graph.
Sorting and Searching : Sequential, Binary and Hashed Searching, Internal and
External Sorting Techniques, Bubble Sort, Insertion Sort, Selection Sort, Merge Sort,
Radix Sort and Quick Sort Comparison.
□□□
,Algorithms and Data Structure 5
Content
S.No. Name of Topic
1. Basics of Algorithms
2. Data Structure Organisation
3. Arrays
4. Strings
5. C++ : Classes and Objects
6. Linked List
7. Stacks
8. Queue
9. Sorting and Searching Techniques
10. Graph
11. Tree
12.
13.
Unsolved Papers 2011 to 2006
MCQ
□□□
6
Chapter-1
Basics of Algorithms
Q.1. What are the various steps to plan algorithm?
Ans.: Following steps must be followed to plan any algorithm :
,(1) Device Algorithm : Creating an algorithm is an art in which may never
be fully automated. When we get the problem, we should first analyse
the given problem clearly and then write down some steps on the
paper.
(2) Validate Algorithm : Once an algorithm is devised , it is necessary to
show that it computes the correct answer for all possible legal inputs .
This process is known as algorithm validation. The algorithm need not
as yet be expressed as a program. It is sufficient to state it in any precise
way. The purpose of validation is to assure us that this algorithm will
work correctly independently of the issues concerning the
programming language it will eventually be written in. Once the
validity of the method has been shown, a program can be written and a
second phase begins. This phase is referred to as program proving or
program verification.
(3) Analyse Algorithm : As an algorithm is executed , it uses the
computers central processing unit to perform operations and its
memory ( both immediate and auxiliary) to hold the program and data.
Analysis of algorithm or performance analysis refers to the task of
determining how much computing time and storage an algorithm
requires. An important result of this study is that it allows you to make
quantitative judgments about the value of one algorithm over another.
Another result is that it allows you to predict whether the software will
meet any efficiency constraints that exist. Analysis can be made by
taking into consideration.
Algorithms and Data Structure 7
(4) Test A Program : Testing a program consists of 2 phases : debugging
and performance management. Debugging is the process of executing
programs on sample data sets to determine whether results are
, incorrect if so corrects them. Performance management is the process of
executing a correct program on data sets and measuring the time and
space it takes to compute the results. These timing figures are useful in
that they may confirm a previously done analysis and point out logical
places to perform useful optimization.
Q.2. Define Algorithms with suitable example.
Ans.: Consider the following three examples. What do they all have in common?
How to change your motor oil
(1) Place the oil pan underneath the oil plug of your car.
(2) Unscrew the oil plug.
(3) Drain oil.
(4) Replace the oil plug.
(5) Remove the oil cap from the engine.
(6) Pour in 4 quarts of oil.
(7) Replace the oil cap.
Therefore an algorithm is a set of instructions for solving a problem. Once we
have created an algorithm, we no longer need to think about the principles on
which the algorithm is based. This means that algorithms are a way of
capturing intelligence and sharing it with others. Once you have encoded the
necessary intelligence to solve a problem in an algorithm, many people can
use your algorithm without needing to become experts in a particular field.
Q.3 Why the algorithm are important to computers. How can we create it in
understandable form?
Ans. Algorithms are especially important to computers because computers are
really general purpose machines for solving problems. But in order for a
computer to be useful, we must give it a problem to solve and a technique for
8
