Tentative weekly teaching plan is as follows:

Week Content

Sets
Finite and infinite sets, uncountable infinite sets; functions, relations,
1-3 properties of binary relations, closure, partial ordering relations,
pigeonhole principle, permutation and combination, induction, inclusion
exclusion

Growth of Functions
4-5 Asymptotic notations, summation formulas and properties, summation
formulas and properties (contd.), bounding summations, approx. by
integrals

Recurrences
Recurrence relations, generating functions, linear recurrence relations
6-8 with constant coefficients and their solution, recursion trees, Master’s
Theorem

Graph Theory
Basic terminology, models and types, multigraphs and weighted graphs,
9-13 graph representation, graph isomorphism, connectivity, Euler and
Hamiltonian Paths and Circuits, planar graphs, graph coloring, Trees,
basic terminology and properties of Trees, introduction to spanning trees.

Prepositional Logic
14-15 Logical connectives, well-formed formulas, tautologies, equivalences,
inference theory

Assessment Methods
Written tests, assignments, quizzes, presentations as announced by the instructor in the class.

Keywords
recurrence, trees and graphs, combinatorics, inductive and deductive reasoning, asymptotic
complexity.

Data Structures (BHCS05) Discipline Specific Core Course - (DSC)

28
Credit: 06

Course Objective
This course aims at developing the ability to use basic data structures like array, stacks, queues,
lists, trees and hash tables to solve problems. C++ is chosen as the language to understand
implementation of these data structures.

Course Learning Outcomes

At the end of the course, students will be able to:
1. Implement and empirically analyse linear and non-linear data structures like Arrays, Stacks,
Queues, Lists, Trees, Heaps and Hash tables as abstract data structures. (RBT L2/3)
2. Write a program, choosing a data structure, best suited for the application at hand. (RBT L3/4)
3. Re-write a given program that uses one data structure, using a more appropriate/efficient data
structure (RBT L4)
4. Write programs using recursion for simple problems. Explain the advantages and
disadvantages of recursion.(RBT L2/L3)
5. Identify Ethical Dilemmas.

Detailed Syllabus
Unit 1
Arrays: single and multi-dimensional arrays, analysis of insert, delete and search operations in
arrays (both linear search and binary search), implementing sparse matrices, applications of
arrays to sorting: selection sort, insertion sort, bubble sort, comparison of sorting techniques via
empirical studies. Introduction to Vectors.
Unit 2
Linked Lists: Singly- linked, doubly-linked and circular lists, analysis of insert, delete and
search operations in all the three types, implementing sparse matrices. Introduction to Sequences.
Unit 3
Queues: Array and linked representation of queue, de-queue, comparison of the operations on
queues in the two representations. Applications of queues.
Unit 4

29
Stacks: Array and linked representation of stacks, comparison of the operations on stacks in the
two representations, implementing multiple stacks in an array; applications of stacks: prefix,
infix and postfix expressions, utility and conversion of these expressions from one to another;
applications of stacks to recursion: developing recursive solutions to simple problems,
advantages and limitations of recursion
Unit 5
Trees and Heaps: Introduction to tree as a data structure; binary trees, binary search trees,
analysis of insert, delete, search operations, recursive and iterative traversals on binary search
trees. Height-balanced trees (AVL), B trees, analysis of insert, delete, search operations on AVL
and B trees.
Introduction to heap as a data structure. analysis of insert, extract-min/max and delete-min/max
operations, applications to priority queues.
Unit 6
Hash Tables: Introduction to hashing, hash tables and hashing functions -insertion, resolving
collision by open addressing, deletion, searching and their analysis, properties of a good hash
function.

Practical
1. Write a program to search an element from a list. Give user the option to perform Linear or
Binary search. Use Template functions.
2. WAP using templates to sort a list of elements. Give user the option to perform sorting using
Insertion sort, Bubble sort or Selection sort.
3. Implement Linked List using templates. Include functions for insertion, deletion and search of
a number, reverse the list and concatenate two linked lists (include a function and also overload
operator +).
4. Implement Doubly Linked List using templates. Include functions for insertion, deletion and
search of a number, reverse the list.
5. Implement Circular Linked List using templates. Include functions for insertion, deletion and
search of a number, reverse the list.
6. Perform Stack operations using Linked List implementation.
7. Perform Stack operations using Array implementation. Use Templates.
8. Perform Queues operations using Circular Array implementation. Use Templates.
9. Create and perform different operations on Double-ended Queues using Linked List
implementation.

30
10. WAP to scan a polynomial using linked list and add two polynomial.
11. WAP to calculate factorial and to compute the factors of a given no. (i)using recursion, (ii)
using iteration
12. (ii) WAP to display fibonacci series (i)using recursion, (ii) using iteration
13. WAP to calculate GCD of 2 number (i) with recursion (ii) without recursion
14. WAP to create a Binary Search Tree and include following operations in tree: (a) Insertion
(Recursive and Iterative Implementation) (b) Deletion by copying (c) Deletion by Merging (d)
Search a no. in BST (e) Display its preorder, postorder and inorder traversals Recursively (f)
Display its preorder, postorder and inorder traversals Iteratively (g) Display its level-by-level
traversals (h) Count the non-leaf nodes and leaf nodes (i) Display height of tree (j) Create a
mirror image of tree (k) Check whether two BSTs are equal or not
15. WAP to convert the Sparse Matrix into non-zero form and vice-versa.
16. WAP to reverse the order of the elements in the stack using additional stack.
17. WAP to reverse the order of the elements in the stack using additional Queue.
18. WAP to implement Diagonal Matrix using one-dimensional array.
19. WAP to implement Lower Triangular Matrix using one-dimensional array.
20. WAP to implement Upper Triangular Matrix using one-dimensional array.
21. WAP to implement Symmetric Matrix using one-dimensional array.
22. WAP to create a Threaded Binary Tree as per inorder traversal, and implement operations
like finding the successor / predecessor of an element, insert an element, inorder traversal.
23. WAP to implement various operations on AVL Tree.
24. WAP to implement heap operations.

References
1. Drozdek, A., (2012), Data Structures and algorithm in C++. 3rd edition. Cengage Learning.
2. Goodrich, M., Tamassia, R., & Mount, D., (2011). Data Structures and Algorithms Analysis in
C++. 2nd edition. Wiley.

Additional Resources
1. Foruzan, B.A. (2012) Computer Science: A Structured Approach Using C++, Cengage
Learning
2. Lafore, R. (2008). Object Oriented Programming in C++. 4th edition. SAMS Publishing.

31
3. Sahni, S. (2011). Data Structures, Algorithms and applications in C++. 2ndEdition,
Universities Press
4. Tenenbaum, A. M., Augenstein, M. J., & Langsam Y., (2009), Data Structures Using C and
C++. 2nd edition. PHI.

Course Teaching Learning Process

● Use of ICT tools in conjunction with traditional class room teaching methods
● Interactive sessions
● Class discussions

Tentative weekly teaching plan is as follows:

Week Content
1 -2 Single and Multi-dimensional arrays, row and column major –order, static
vs. dynamic data structures
3-4 Linked Lists, doubly linked list, circular lists, implementation of link list in
array, using pointers, analysis of linked Lists operations, sparse matrices,
sequences
5-6 Queues, storage and retrieval operations, implementation of queues,
7-8 Stacks, storage and retrieval operations, implementation of stacks,
applications of stacks
9-10 Binary Trees, Recursive and iterative methods of tree traversal
11-13 AVL and B Trees
14 Heaps
15 Hash Tables

Assessment Methods
Written tests, assignments, quizzes, presentations as announced by the instructor in the class.

Keywords
Arrays and linked lists, stacks, queues, tree, heap, hashing, recursion

32