ABSS INSTITUTE OF TECHNOLOGY,

MEERUT

[Link] (CSE) Department

(Session: 2024-25)

COURSE FILE

DATA STRUCTURE(BCS-301)
YEAR/SEMESTER: 2nd/3rd

Faculty Name: HOD (CSE Department)

Mrs. Pooja Goel Dr. Gopinder kumar
Assistant Professor(CSE Department)
 Index
Sr. No. Title

1. Cover Page

2. Program Educational Objectives(PEO’s)

3. Course Outcome

4. Program Outcomes

5. Evaluation Scheme

6. Syllabus

7. Class Time Table

8. Lesson Plan

9. Notes (Unit-1 to Unit-5)

10. Assignments

11. Question Bank

12. Previous year question papers of last three years

13. Pre Board Test (PUT)

14. Model Question Paper

15. Student academic performance(internal) analysis

16. List of weak and slower student.

17. Action to improve performance of weak and slower student

18. Reference Books, web content etc.

 Program Educational Objectives
The educational objectives of our program is to ensure that the
graduates are fundamentally solid, practical, dependable,
collaborative, and professional. Specifically, four years after
graduation, the successful graduates will have

 Engaged in successful professional practices in their chosen

discipline
 Demonstrated professional and personal leadership in their
workspace and the society
 Demonstrated effective collaboration and communication in the
work environment and beyond
 Utilized formal and informal learning opportunities to maintain
and enhance technical excellence and professional growth
 DATA STRUCTURE (BCS-301)

Course Outcome (CO) Bloom’s Knowledge Level (KL)

At the end of course, the student will be able to

CO 1 Describe how arrays, linked lists, stacks, queues, trees, and K1,K2
graphs are represented in memory, used by the algorithms
and their common applications

Discuss the computational efficiency of the sorting and

CO 2 searching algorithms.
K2

CO 3 Implementation of Trees and Graphs and perform various K3

operations on these data structure.

Understanding the concept of recursion, application of

recursion and its implementation and removal
K4
CO 4
of recursion.

CO 5 Identify the alternative implementations of data structures

with respect to its performance to solve a K5,K6
real world problem.
 DATA BASE MANAGEMENT SYSTEM (BCS-301)

Program Outcomes

1. Describe how arrays, linked lists, stacks, queues, trees, and graphs are
represented in memory, used by the algorithms and their common
applications.
2. Discuss the computational efficiency of the sorting and searching
algorithms.
3. mplementation of Trees and Graphs and perform various operations on
these data structure.
4. Understanding the concept of recursion, application of recursion and its
implementation
5. Identify the alternative implementations of data structures with respect to
its performance to solve a real world problem.
EVALUATION SCHEME
SYLLABUS
CLASS TIME TABLE
 LESSON PLAN
Unit Lectur Topics Covered
e No.
UnitTitle: Introduction
1 Basic Terminology, Elementary Data Organization, Built in Data Types in C.
2 Algorithm, Efficiency of an Algorithm, Time and Space Complexity
3 Asymptotic notations: Big Oh, Big Theta and Big Omega
4 Time-Space trade-off. Abstract Data Types (ADT)
5 Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row
I Major Order, and Column Major Order
6 Derivation of Index Formulae for 1-D,2-D,3-D and n-D Array
7 Application of arrays, Sparse Matrices and their representations.
8 Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists
9 Doubly Linked List
10 Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal
11 Polynomial Representation and Addition Subtraction
12 Multiplications of Single variable & Two variables Polynomial.
13 Revision
Unit Title: Stacks & Queues
14 Abstract Data Type, Primitive Stack operations: Push & Pop
15 Array and Linked Implementation of Stack in C,
16 Application of stack: Prefix and Postfix Expressions,
17 Evaluation of postfix expression
18 Iteration and Recursion- Principles of recursion, Tail recursion

II 19 Removal of recursion Problem solving using iteration and recursion with examples such as
binary search
20 Fibonacci numbers, and Hanoi towers.
21 Tradeoffs between iteration and recursion
22 Queues: Operations on Queue: Create, Add, Delete
23 Full and Empty, Circular queues
24 Array and linked implementation of queues in C
25 Dequeue and Priority Queue
Unit Title: Searching & Sorting
26 Concept of Searching, Sequential search, Index Sequential Search,Binary Search.
27 Concept of Hashing & Collision resolution Techniques used in Hashing
III 28 Sorting: Insertion Sort, Selection, Bubble Sort
29 Quick Sort, Merge Sort
30 Heap Sort and Radix Sort
Unit Title: Trees
31 Basic terminology used with Tree, Binary Trees, Binary Tree Representation: Array
Representation and Pointer(Linked List) Representation,
32 Binary Search Tree, Strictly Binary Tree ,Complete Binary Tree . A Extended Binary Trees,
IV Tree Traversal algorithms: Inorder, Preorder and Postorder,
33 Constructing Binary Tree from given Tree Traversal, Operation of Insertation, Deletion
34 Searching & Modification of data in Binary Search .Threaded Binary trees
35 Traversing Threaded Binary trees. Huffman coding using Binary Tree
36 AVL Tree
37 B Tree & Binary Heap
38 Revision

Unit Title: Graphs:

39 Terminology used with Graph, Data Structure for Graph Representations: Adjacency Matrices,
V Adjacency List, Adjacency.
40 Graph Traversal: Depth First Search and Breadth First Search, Connected Component
41 Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm.
42 Transitive Closure and Shortest Path algorithm: Warshal Algorithm
43 Dijikstra Algorithm.
44 Revision
45 Revision
 Question Bank
UNIT-1

Q1. Define following terms:-Time-Space trade-off, Abstract Data Type(ADT), Time complexity
and Space Complexity . Explain best, worst and average case analysis in this respect with an
example. Rank the following typical bounds in increasing order of growth rate: O(log n), O(n4
), O(1), O(n2 log n).

Q2. Define the term Data Structure. List some linear and non-linear data structures stating the
application area where they will be used. Also explain various asymptotic notations.

Q3. Define a sparse matrix. Suggest a space efficient representation for space matrices.

Q4. Write advantages and disadvantages of linked list over arrays. List the various operations
on linked list. Write a 'C' function creating new linear linked list by selecting alternate
elements of a linear linked list.

Q5. What are the merits and demerits of array? Given two arrays of integers in ascending order,
develop an algorithm to merge these arrays to form a third array sorted in ascending order.

Q6. What is doubly linked list? List the advantages of doubly linked list over single linked list.
What are its applicatios? Explain how an element can be deleted from doubly linked list using
C program.

Q7. Discuss the representation of polynomial of single variable using linked list. Write 'C'
functions to (i)Add (ii) Multiply two such polynomials represented by linked list.

Q8. Differentiate between overflow and underflow condition in linked list. Write a C program to
insert a node at kth position in single linked list. Also Write an algorithm to insert a node at the
end in a Circular linked list.

Q9. Consider a two-dimensional Array A[90] [30] with base address starts at 1000. Calculate the
address of A[10] [20] in row major order and column major order. Assume the first element is
stored at A[2][2] and each element take 2 byte.

UNIT-2

Q1. Convert the following arithmetic infix expression into its equivalent postfix expression.
Expression: A-B/C+D*E+F.

Q2. Explain circular queue. Write the full and empty condition for a circular queue data structure.

Q3. What is a Stack . Write algorithm for push and pop operations in stack. Write a C program
to reverse a string using stack.

Q4. Define recursion and tail recursion. Explain with a suitable example. Write a recursive and
non recursive program to calculate the factorial of the given number. Give advantages and
disadvanges of recursion.

Q5. Evaluate the following postfix expression using stack: 2 3 9 * + 2 3 ^ - 6 2 / + , show the
contents of each and every steps. Also find the equivalent prefix form of above expression. Where ^
is an exponent operator.

Q6. Convert the following infix expression to reverse polish

notation expression using stack. x=(-b+(b2-4ac)^(1/2))/2a

Q7. Explain Tower of Hanoi problem and write a recursive algorithm to solve it. Calculate
total number of moves for Tower of Hanoi for n=10 disks.

Q8. Write array and linked representation of queue data structure in C. Also explain priority
queue and dequeue.

Q9. Write a C program to implement stack using array and single linked list.

UNIT-3

Q1. Give example of one each stable and unstable sorting techniques. Why is quick sort named
as quick? Use quick sort algorithm to sort 15,22,30,10,15,64,1,3,9,2. Is it a stable sorting
algorithm? – Justify.

Q2. Write short notes on: i. Collision Resolution Hashing Technique ii. Garbage collection . iii.
Bubble Sort iv. Radix Sort.

Q3. How does selection sort work? Explain it. Also Write algorithms of insertion sort and
Implement the same on the following numbers 13, 16, 10, 11, 4, 12,6, 7 also calculate its time
complexity.

Q4. Differentiate between liner and binary search algorithm. Write a C function to implement binary
search. Also Write a C program for Index Sequential Search.

Q5. Use the merge sort algorithm to sort the following elements in ascending order. 13, 16, 10,
11, 4, 12, 6, 7. What is the time and space complexity of merge sort?

Q6. Explain any three commonly used hash function with the suitable example? A hash function H
defined as H(key) =key%7, with linear probing, is used to insert the key 37,38,72,48,98,11,66 into a
table indexed from 0 to 6. what will be the location of key 11? Justify your answer, also count
the total number of collisions in this probing.

[Link] Heap sort. Examine the minimum number of interchanges needed to convert the
array 90, 20, 41,18, 13, 11, 3, 6, 8,12, 7, 71, 99 into a maximum heap. Write short notes on min
heap.
 UNIT-4

Q.1. The order of nodes of a binary tree in inorder and postorder traversal are as
follows: In order : B, I, D, A, C, G, E, H, F.
Post order: I, D, B, G, C, H, F, E, A.

1. (i) Draw the corresponding binary tree.

2. (ii) Write the pre order traversal of the same tree.

Q.2 Discuss left skewed and right skewed binary tree. Construct an AVL tree by
inserting the following elements in the order of their occurrence:

60, 2, 14, 22, 13, 111, 92, 86.

Q.3 What is B-Tree? Write the various properties of B- Tree. Show the results of
inserting the keys F, S, Q, K ,C, L, H, T, V, W, M, R, N, P, A, B in order into a
empty B-Tree of order 5.

Q.4 Examine the minimum number of interchanges needed to convert the array
90, 20, 41,18, 13, 11, 3, 6, 8,12, 7, 71, 99 into a maximum heap

Q.5 Write Short notes of following

(a) Extended Binary Trees (b) Complete Binary Tree (c) Threaded Binary Tree.
(d). ACBT

Q.6. What is the difference between a Binary Search Tree(BST) and heap? For a
given sequence of numbers, construct a heap and a BST.

34,23,67,45,12,54,87,43,98,75,84,93,31

UNIT-5

Q.1. Write and explain the Floyd Warshall algorithm to find the all pair shortest path. Use
the Floyd Warshall algorithm to find shortest path among all the
vertices in the given graph:

Downloaded by pooja Goel

Q.2 What is spanning tree? Write down the Kruskal’s algorithm to obtain minimum cost
spanning tree. Use Kruskal’s algorithm to find the minimum cost spanning tree in the
following graph:

Q.3 Use Dijkstra’s algorithm to find the shortest paths from source to all other
vertices in 3 the following graph.

Q.4. Apply Prim’s algorithm to find a minimum spanning tree in the following
weighted 3 graph as shown below.

Q.5. Differentiate between DFS and BFS. Draw the breadth First Tree for the above graph.

Q.6. List the different types of representation of graphs. Differentiate between DFS and BFS. Also
write short notes on transitive closure.

Downloaded by pooja Goel

Old Question Papers

Downloaded by pooja Goel

(poojagoel2441994@[Link])
 Pre University Test(PUT)
Downloaded by pooja Goel
(poojagoel2441994@[Link])
 Model Question Paper
Unit I

1. Define Instances and schemas of database?

2. List the Database Applications?
3. List the disadvantages of file processing system?
4. Define a) Entity b) Attribute.
5. Discuss about Data Manipulation Language?
6. List the advantages of DBMS?
7. Discuss Data Independence?
8. Discuss about Data Definition Language?
9. Discuss about Data Manipulation Language?
10. Define a) Entity b) Relationship.
11. What are the application programs? Explain database access from application
programs?
12. State and explain various features of E-R Models.
13. Discuss in detail Views and also Creating, Altering, Destroying of Views.
14. Name the main steps in the Database design. What is the goal of each step? In which
steps is the ER model mainly used?
15. Explain about Integrity Constraints over relations in detail?
16. Explain about Database users and Administrators?
17. Explain about Logical database design?
18. Explain about Database Architecture?

UNIT-II

19. What is domain integrity? Give example.

20. Define SELECT operation in Relational algebra?
21. Discuss about trigger?
22. Define UNION operation in Relational algebra?
23. What is the use of group by clause?
24. List the aggregate functions supported by SQL?
25. Discuss the basic form of SQL query?
Downloaded by pooja Goel
(poojagoel2441994@[Link])
 26. Define CROSS PRODUCT operation in Relational algebra?
27. Define JOIN operation in Relational algebra?
28. Explain about Aggregate operators in sql with examples?
29. Discuss correlated nested queries?
30. Write and explain a query to find the names of sailors who have reserved a red boat?
Explain Set operations of Relational Algebra with examples?
31. Define trigger and explain its three parts? Compare row level and statement level
triggers?
32. Explain about Selection, Projection, Rename, division and Cartesian product operations
in relational algebra?
33. Discuss about Domain Relational Calculus? Write and explain a query in DRC to Find
the names of sailors who have reserved boat 103.
34. Write and Explain a Query for finding the names of sailors who have reserved a Red or
a Green Boat. (in sql)
35. Write and explain a query for finding the colors of Boats reserved by ‘Lubber’. (in sql)
36. Discuss about Tuple Relational Calculus? Write and explain a query in TRC to Find the
names of sailors who have reserved boat 103.

UNIT-III
37. Demonstrate transitive dependency? Give an example?
38. Define BCNF?
39. Discuss Normalization?
40. Define Third Normal Form?
41. Explain about Loss less-join dependency?
42. Define Second Normal Form?
43. Define Armstrong axioms for FD’s?
44. Define First Normal Form?
45. List different Normal Forms?
46. Determine the closer of the following set of functional dependencies for a relation
scheme R(A,B,C,D,E,F,G,H), F={ AB→C, BD→EF, AD→G, A→H} List the
candidate keys of R.
47. What is normalization? What are the conditions are required for a relation to be in 2NF,
3NF and BCNF explain with examples.
48. Determine the closer of the following set of functional dependencies for a relational
scheme R (A,B,C,D,E) ,F= {A→BC, CD→E, B→D, E→A}. List out the candidate
keys of R. ͢͢͢͢͢͢͢͢͢͢͢͢͢͢͢͢
49. What is meant by functional dependencies? Discuss about Third Normal From?
50. Determine the closer of the following set of functional dependencies for a relational
scheme R(A,B,C,D) and FDs {AB → C, C → D, D → A}. List out the candidate keys
of R.
51. Explain BCNF. What are the steps to be followed to convert a relation in 3NF to
BCNF?
52. What is normalization? What are the conditions are required for a relation to be in 1NF,
2NF and 3NF explain with examples.
53. What is meant by closure of F? Where F is the set of functional dependencies. Explain
computing F+ with suitable examples.

UNIT-IV

Downloaded by pooja Goel

(poojagoel2441994@[Link])
 54. List the properties of transaction?
55. Define a Transaction?
56. Discuss about View Serializability?
57. Explain about remote backup systems?
58. Explain about ACID properties?
59. Define a checkpoint?
60. Discuss about Conflict Serializability?
61. What are serial, non-serial schedules?
62. When is a transaction Rolled back?
63. What are various reason for transaction failure?
64. What is transaction? Explain the ACID Properties of transactions?
65. Discuss serializable schedule. Discuss conflict serializability with suitable example.
66. What is Conflict Serializable Schedule? Check the given Schedule S1 is Conflict Serializable
or not? S1: R1(X), R2(X),R2(Y),W2(Y),R1(Y),W1(X)
67. Discuss the procedure of deadlock detection and recovery in transaction?
68. What do you understand by interleaving of transaction? How is it differ from the serial
execution.

UNIT-V
69. Define Two Phase Commit Protocol?
70. Explain about multiple granularity?
71. Explain about remote backup systems?
72. List the various level of locking?
73. What are Concurrent Transaction?
74. What is lock in transaction management?
75. Explain recovery from concurrent transaction
76. Explain in detail about Lock-Based Protocols?
77. Explain in detail about Validation-Based Protocols?
78. Explain in detail about Timestamp-Based Protocols?
79. Discuss 2 phase commit (2PC) protocol and time stamp protocol with suitable example
80. Explain time stamp based concurrency control technique.

Downloaded by pooja Goel

(poojagoel2441994@[Link])
 Student Accedmic Performance

LIST OF WEAK STUDENT

[Link] STUDENT NAME FATHER NAME CONTACT NO

Downloaded by pooja Goel

(poojagoel2441994@[Link])
1 ADARSH SHARMA Mr. HEMANT SHARMA 9690832165

2 KHUSHI SHARMA Mr. NITIN SHARMA 9068936944

3 TANU CHAUDHARY Mr. SANJAY KUMAR 7302462822

4 NAVNEET KUMAR Mr. SATYAPAL SINGH 7011973012

5 AKUL BHARDWAJ Mr. HARIOM BHARDWAJ 9368711947

Action to improve performance of weak and slower

students
1. Individual Teaching
2. Encourage Active Participations
3. Stay positive
4. Participating in co-curricular activities
Downloaded by pooja Goel
(poojagoel2441994@[Link])
5. Group Discussion

RERERENCES BOOKS

1. Korth, Silbertz, Sudarshan,” Database Concepts”, McGraw Hill

2. Elmasri, Navathe, “ Fundamentals of Database Systems”, Addision Wesley

Downloaded by pooja Goel

(poojagoel2441994@[Link])
Downloaded by pooja Goel
(poojagoel2441994@[Link])