Concept based notes Data Structure and Algorithms

[Pages:199]Algorithms and Data Structure

1

Biyani's Think Tank

Concept based notes

Data Structure and Algorithms

(BCA Part-I)

Bhavana Sangamnerkar

M.Sc. (Comp. Prog.), PGDCA H.O.D.

Revised by: Neha jain Revised by: Ms Rashmi Sharma Information Technology Biyani Girls College, Jaipur

2

Published by :

Think Tanks Biyani Group of Colleges

Concept & Copyright :

Biyani Shikshan Samiti

Sector-3, Vidhyadhar Nagar, Jaipur-302 023 (Rajasthan) Ph : 0141-2338371, 2338591-95 Fax : 0141-2338007 E-mail : acad@ Website :;

ISBN : 978-93-81254-40-0

Edition : 2011 Price :

While every effort is taken to avoid errors or omissions in this Publication, any mistake or omission that may have crept in is not intentional. It may be taken note of that neither the publisher nor the author will be responsible for any damage or loss of any kind arising to anyone in any manner on account of such errors and omissions.

Leaser Type Setted by : Biyani College Printing Department

Algorithms and Data Structure

3

Preface

I am glad to present this book, especially designed to serve the needs of the

students. The book has been written keeping in mind the general weakness in understanding the fundamental concepts of the topics. The book is self-explanatory and adopts the "Teach Yourself" style. It is based on question-answer pattern. The language of book is quite easy and understandable based on scientific approach.

Any further improvement in the contents of the book by making corrections, omission and inclusion is keen to be achieved based on suggestions from the readers for which the author shall be obliged.

I acknowledge special thanks to Mr. Rajeev Biyani, Chairman & Dr. Sanjay Biyani, Director (Acad.) Biyani Group of Colleges, who are the backbones and main concept provider and also have been constant source of motivation throughout this Endeavour. They played an active role in coordinating the various stages of this Endeavour and spearheaded the publishing work.

I look forward to receiving valuable suggestions from professors of various educational institutions, other faculty members and students for improvement of the quality of the book. The reader may feel free to send in their comments and suggestions to the under mentioned address.

Author

4

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

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. Unsolved Papers 2011 to 2006 13. MCQ

5

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

solving the problem. Through the use of algorithms, we can make computers "intelligent" by programming them with various algorithms to solve problems. Because of their speed and accuracy, computers are well-suited for solving tedious problems such as searching for a name in a large telephone directory or adding a long column of numbers. However, the usefulness of computers as problem solving machines is limited because the solutions to some problems cannot be stated in an algorithm.

Much of the study of computer science is dedicated to discovering efficient algorithms and representing them so that they can be understood by computers.

An informal definition of an algorithm is "a set of instructions for solving a problem" and we illustrated this definition with a recipe, and instructions for changing the oil in a car engine. You also created your own algorithm for putting letters and numbers in order. While these simple algorithms are fine for us, they are much too ambiguous for a computer. In order for an algorithm to be applicable to a computer, it must have certain characteristics. We will specify these characteristics in our formal definition of an algorithm.

An algorithm is a well-ordered collection of unambiguous and effectively computable operations that when executed produces a result and halts in a finite amount of time [Schneider and Gersting 1995].

With this definition, we can identify five important characteristics of algorithms :

Algorithms are well-ordered.

Algorithms have unambiguous operations.

Algorithms have effectively computable operations.

Algorithms produce a result.

Algorithms halt in a finite amount of time.

When writing algorithms, we have several choices of how we will specify the operations in our algorithm. One option is to write the algorithm using plain English. Although plain English may seem like a good way to write an algorithm, it has some problems that make it a poor choice. First, plain English is too wordy. When we write in plain English, we must include many words

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download