NIELIT A Level DATA STRUCTURE THROUGH C++ Syllabus

Objective of the Course

The objective of the course is to introduce the fundamentals of Data Structures, Abstract concepts and how these concepts are useful in problem solving.

After completion of this course student will be able to -

• To Understand and the concepts of object oriented language such as c++
• Analyze step by step and develop algorithms to solve real world problems.
• Implementing various data structures viz. Stacks, Queues, Linked Lists, Trees and Graphs.
• Understanding various searching & sorting techniques.

Outline of Course

Topic                                                     Minimum number of hours

Analysis of Algorithm                                      10

Basics of C++, Elementary Data                      18

Structures  Arrays, linked lists

Abstract Data types Stacks and                        05

 Queues 

Trees                                                                12

Searching, sorting and                                     10

Complexity 

Graphs                                                             05 

                                                     Lectures = 60

                                      Practical/tutorials = 60

                                                         Total = 120

Detailed Syllabus

1. Analysis of Algorithm 10 Hrs.

Introduction to Algorithm Design and Data Structures: Design and analysis of algorithm:Algorithm definition, comparison of algorithms. Top down and bottom up approaches to Algorithm design. Analysis of Algorithm; Frequency count, Complexity measures in terms of time and space. structured approach to programming.

2. Basics of C++, Elementary Data Structures : Arrays, linked lists 18 Hrs.

Basics of C++: Structure of a program Variables. Data Types. Constants Operators, Basic Input/Output, Control Structure , Functions, Compound Data Types: Arrays, Pointers, Dynamic Memory , Object Oriented Programming :Classes, Encapsulation, Abstraction, inheritance, Polymorphism, Representation of arrays: single and multidimensional arrays. Address calculation using column and row major ordering. Various operations on Arrays, Vectors. Application of arrays: Matrix multiplication, Sparse polynomial representation and addition, Stacks and Queues : Representation of stacks and queues using arrays and linked-list. Circular queues, Priority Queue and D-Queue. Applications of stacks: Conversion from infix to postfix and prefix expressions, Evaluation of postfix expression using stacks. Pointers: Definition, Pointer Arithmetic, Array of pointers, Arrays in terms of pointers. Linked list: Singly linked list; operations on list, Linked stacks and queues. Polynomial representation and manipulation using linked lists. Circular linked lists, Doubly linked lists. Generalized list structure. Sparse Matrix representation using generalized list structure, stacks, queues.

3. Abstract Data types Stacks and Queues 05 Hrs.

Definition of ADT, Stack ADT (array implementation), FIFO queue ADT (array,implementation)

4. Trees 12 Hrs.

Binary tree traversal methods : Preorder, In-order, Post-ordered traversal. Recursive Algorithms for above mentioned Traversal methods. Representation of trees and its applications : Binary tree representation of a general tree. Conversion of forest into tree.Threaded binary trees. Binary search tree. : Height balanced (AVL) tree, B-trees.

5. Searching, Sorting and Complexity 10 Hrs.

Selection sort, Insertion sort, Bubble sort, Quick sort, merge sort , Heap sort, Radix sort and their complexity, Searching: Sequential search, Binary Search, Binary Search Tree, ASVL trees, B trees, Searching , sorting and complexity, Searching : Sequential and binary searches, Indexed search, Hashing Schemes. Sorting : Insertion, selection, bubble, Quick,merge, radix, Shell, Heap sort, comparison of time complexity.

6. Graphs 05 Hrs.

Graph representation : Adjacency matrix, Adjacency lists, Traversal schemes : Depth first search, Breadth first search.Spanning tree : Definition, Minimal spanning tree algorithms. Shortest Path algorithms (Prime’s and Kruskal ‘s).

-

RECOMMENDED BOOKS

MAIN READING

1. Hubbard John. R, “Schaum’s outline of Data Structures with C++”, Tata McGraw-Hill,

2007.

2. Langsam Y,.Augenstein M.J and Tanenbaum A. M, “Data Structures Using C and C++”,

Second Edition, Pearson Education, 2007.

3. Kruse R, Tonodo C.L. and Leung B, “Data Structures and Program Design in C”,

Pearson Education, 2007.

SUPPLEMENTARY READING

1. Horowitz E, Sahni S and Mehta D, “Fundamentals of Data Structures in C++,”

Galgotia Publiction, 2009.

2. Weiss M A, “Data Structures and Algorithm Analysis in C++”, Pearson Education,

2007.

3. Litvin G, “Programmking with C++ and Data Structures”, Vikas Publishing House.

Back