BCA DS C++

Discipline Specific Course (Core) 1
DATA STRUCTURES THROUGH C++

Course Code: CSE 202 Credit Units: 03
Total Hours: 45
Course Objective:
To understand the basic concepts such as Abstract Data Types, Linear and Non Linear Data structures. To
understand the notations used to analyze the Performance of algorithms. To understand the behavior of data
structures such as stacks, queues, trees, hash tables, search trees, Graphs and their representations. To choose an
appropriate data structure for a specified application. To understand and analyze various searching and sorting
algorithms. To learn to implement ADTs such as lists, stacks, queues, trees, graphs, search trees in C++ to solve
problems.
Course Contents:
Module I: Introduction to C++: (9 Hours)

C++ Programming Concepts: Review of C, input and output in C++, functions in C++- value parameters, reference
parameters, Parameter passing, function overloading, function templates, Exceptions-throwing an exception and
handling an exception, arrays, pointers, new and delete operators, class and object, access specifiers , friend
functions, constructors and destructor, Operator overloading, class templates, Inheritance and Polymorphism.
Basic Concepts - Data objects and Structures, Algorithm Specification-Introduction, Recursive algorithms, Data
Abstraction, Performance analysis- time complexity and space complexity, Asymptotic Notation-Big O, Omega
and Theta notations, Complexity Analysis Examples, Introduction to Linear and Non Linear data structures.
Module II: Introduction to DS: (9 Hours)

Representation of single, two dimensional arrays, sparse matrices-array and linked representations.
Linear list ADT-array representation and linked representation, Singly Linked Lists- Operations-Insertion,
Deletion, Circularly linked lists-Operations for Circularly linked lists, Doubly Linked Lists- Operations- Insertion,
Deletion.
Stack ADT, definition, array and linked implementations, applications-infix to postfix conversion, Postfix
expression evaluation, recursion implementation, Queue ADT, definition, array and linked Implementations,
Circular queues-Insertion and deletion operations.
Module III: Trees: (9 Hours)

Trees – definition, terminology, Binary trees-definition, Properties of Binary Trees, Binary Tree ADT,
representation of Binary Trees-array and linked representations, Binary Tree traversals, Threaded binary trees,
Priority Queues –Definition and applications, Max Priority Queue ADT-implementation-Max Heap-Definition,
Insertion into a Max Heap, Deletion from a Max Heap.
Minimum Spanning Tree: Prim’s and Kruskal’s Algorithm, Shortest Path Algorithms.
Module IV: Searching & Sorting: (9 Hours)

Searching - Linear Search, Binary Search, Hashing-Introduction, hash tables, hash functions, Overflow Handling,
Comparison of Searching methods.
Sorting-Insertion Sort, Selection Sort, Radix Sort, Quick sort, Heap Sort, Merge sort, Comparison of Sorting
methods.
Module V: Graphs: (9 Hours)

Graphs–Definitions, Terminology, Applications and more definitions, Properties, Graph ADT, Graph
Representations- Adjacency matrix, Adjacency lists, Graph Search methods - DFS and BFS, Complexity analysis,
Search Trees-Binary Search Tree ADT, Definition, Operations- Searching, Insertion and Deletion, Balanced
search trees-AVL Trees-Definition and Examples only, B-Trees- Definition and Examples only, Red-Black Trees-
Definitions and Examples only, Comparison of Search Trees.
Course Outcomes:
• Ability to choose appropriate data structures to represent data items in real world problems.
• Ability to analyze the time and space complexities of algorithms.
• Ability to design programs using a variety of data structures such as stacks, queues, hash tables, binary
trees, search trees, heaps, graphs, and B-trees.
• Able to analyze and implement various kinds of searching and sorting techniques.
Examination Scheme:
Components A CT S/V/Q/HA ESE

Weightage (%) 5 15 10 70
A: Attendance, CT: Class Test, S/V/Q/HA: Seminar/Viva/Quiz/ Home Assignment, ESE: End Semester
Examination;
Text & References:

Text:
• Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India) Pvt.Ltd, 2nd
edition, Universities Press, Pvt. Ltd.
• Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd., Second
Edition.
• Data structures and Algorithms in C++, Michael T.Goodrich, R.Tamassia and .Mount, Wiley student
edition, John Wiley and Sons.
References:
• Data structures and algorithms in C++, 3rd Edition, Adam Drozdek, Thomson
• Data structures using C and C++, Langsam, Augenstein and Tanenbaum, PHI.
• Problem solving with C++, The OOP, Fourth edition, W.Savitch, Pearson education.
DATA STRUCTURES THROUGH C++ LAB
Course Code: CSE 222 Credit Unit: 01

Total Hours: 30
Course Objective:
To write and execute programs in C++ to solve problems using data structures such as arrays, linked lists, stacks,
queues, trees, graphs, hash tables and search trees. To write and execute write programs in C++ to implement
various sorting and searching methods.
SOFTWARE REQUIREMENTS: Turbo C++ compiler or GCC compilers
Course Contents :
Lab Experiments are based on the course Data Structures through C++ (CSE 202)
List of experiments / demonstrations: (Each experiment is of 2 Hours duration and total 30 Hours)
1. List of Write a C++ programs to implement recursive and non recursive i) Linear search ii) Binary search
(2 hours)
2. Write a C++ programs to implement i) Bubble sort ii) Selection sort iii) quick sort iv) insertion sort (4
hours)
3. Write a C++ programs to implement the following using an array. A) Stack ADT b) Queue ADT (2
hours)
4. Write a C++ programs to implement list ADT to perform following operations (4 hours)
Insert an element into a list.
Delete an element from list
Search for a key element in list
count number of nodes in list
5. Write C++ programs to implement the following using a singly linked list. Stack ADT b) Queue ADT (3
hours)
6. Write C++ programs to implement the deque (double ended queue) ADT using a doubly linked list and
an array. (2 hours)
7. Write a C++ program to perform the following operations: (4 hours)
Insert an element into a binary search tree.
Delete an element from a binary search tree.
Search for a key element in a binary search tree.
8. Write C++ programs for implementing the following sorting methods: Merge sort b) Heap sort (3 hours)
9. Write C++ programs that use recursive functions to traverse the given binary tree in a) Preorder b) in
order and c) post order (2 hours)
10. Write a C++ program to perform the following operations a) Insertion into a B-tree b) Deletion from a
B-tree (4 hours)
Course Outcomes:
• Ability to identify the appropriate data structure for given problem.
• Graduate able to design and analyze the time and space complexity of algorithm or program.
• Ability to effectively use compilers includes library functions, debuggers and trouble shooting.
Examination Scheme:
IA EE
Practical Major Minor

A PR LR Viva
Based Test Experiment Experiment
5 10 15 35 15 10 10
Note: IA –Internal Assessment, EE- External Exam, A- Attendance, PR- Performance, LR – Lab Record, V –
Viva.
Text & References:

• Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India) Pvt.Ltd, 2nd
edition, Universities Press Orient Longman Pvt. Ltd.
• Data structures and Algorithms in C++, Michael T.Goodrich, R.Tamassia and .Mount, Wiley student
edition, John Wiley and Sons.
• Data structures using C and C++, Langsam, Augenstein and Tanenbaum, PHI

BCA DS C++

Uploaded by

Copyright:

Available Formats

BCA DS C++

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

BCA DS C++

Uploaded by

Copyright:

Available Formats

Discipline Specific Course (Core) 1

DATA STRUCTURES THROUGH C++

Module I: Introduction to C++: (9 Hours)

Module II: Introduction to DS: (9 Hours)

Module III: Trees: (9 Hours)

Module IV: Searching & Sorting: (9 Hours)

Module V: Graphs: (9 Hours)

Components A CT S/V/Q/HA ESE

Text & References:

Course Code: CSE 222 Credit Unit: 01

SOFTWARE REQUIREMENTS: Turbo C++ compiler or GCC compilers

Practical Major Minor

Text & References:

You might also like