BMS COLLEGE OF ENGINEERING, BENGALURU-19.

Department of Computer Science and Engineering.

Autonomous Institute, Affiliated to VTU
PROPOSED NEW SYLLABUS
Academic Aug-Dec 2019/Jan-May Sem 3
Year 2020

Course Title: Data structures

Course 19CS3PCDST
Code:
L-T-P: 3-0-1 Total 4
Credits:

A Syllabus
Unit Topics Hrs Text book No. from
No. which Unit topics are
being covered
1 Basic concepts: Structures, Pointers and dynamic
Textbook1
memory allocation, Chapter 1:1.4
Data Abstraction, Stack: Definition and examples, Chapter 2 : 2.3
Representation of stacks in c, Applications of Stack: 8
Chapter 1:1.2
Converting an expression from Infix to postfix and Textbook2
Chapter 2: 2.1, 2.2,2.3
Evaluation of Expression, Recursion: Factorial, Fibonacci
Chapter 3 : 3.2,3.3
Sequence, Tower of Hanoi

2 Queues: The queue and its sequential representation, Textbook1: 3.3

Applications of Queues- Job Scheduling. Circular Queues, 7
Textbook 2
Double Ended Queue, Priority Queues. Chapter 4: 4.1

3 Linked Lists: Linked list, Array implementation of Lists,

Limitations of the array implementation, Allocating and Textbook 2:
freeing dynamic variables, Linked list using dynamic Chapter 4: 4.2
variables, Circular lists, and Doubly linked lists. 9 Textbook 1:
Applications of Linked list: Linked Stacks and Queues, Chapter 4: 4.4
Addition of long positive integers using circular list,
Adding Polynomials
4 Trees: Introduction, Representation of trees, Binary Tree,
Properties of Binary Trees, Binary tree representation-
Binary tree traversals, Binary Search Tree(BST) : 7
Textbook1
Definition, Searching a BST, Inserting into BST, deletion Chapter 5:5.1,5.2,5.3,5.7
from BST

5 AVL, Splay tree, B-tree, threaded binary tree, suffix trees, Textbook1
Tries. Hashing: Hash tables, Hash function, Overflow 8
Chapter 10: 10.2,10.4
handling: Open Addressing, Chaining Chapter 5: 5.5
Chapter 8: 8.2
 BMS COLLEGE OF ENGINEERING, BENGALURU-19.
Department of Computer Science and Engineering.
Autonomous Institute, Affiliated to VTU
Prescribed Text Book
Sl. No. Book Title Authors Edition Publisher Year
1 Fundamentals of Horowitz, Second Universities 2008
Data Structures in C Sahni, Press
Anderson
Freed
2. Data Structures using Aaron Fifth Pearson 2007
C M.Tenenbaum, education
Yedidyah
Langsam,
Moshe J.
Augenstein

Reference Text Book

Sl. No. Book Title Authors Edition Publisher Year
2. Data Robert L. Second Prentice Hal 1997
structures Kruse, Clovis
and program L. Tondo,
design in C Bruce P.
Leung
4 Data A.M Padma Thirteenth Sri Nandi 2013
Structure Reddy edition
using C

E-Book
Sl. Book Title Authors Edition Publisher Year URL
No.
1. Data Reema Second Oxford 2014 https://www.academia.edu/28758384/
Structures Thareja Edition Univsersity Data_structures_using_c_2nd_reema_thareja
using C press
2.

MOOC Course
Sl. No. Course Course Year URL
name Offered By
1. Data Coursera https://www.coursera.org/learn/data-
Structures structures
2. Data NPTEL https://nptel.ac.in/courses/106102064/
Structures
and
algorithms

B Course Outcomes

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

CO1 Apply the concept of linear and nonlinear data structures to various applications

Analyse the usage of appropriate data structure for a given application

CO2

Design and implement operations of linear and nonlinear data structure

CO3
 BMS COLLEGE OF ENGINEERING, BENGALURU-19.
Department of Computer Science and Engineering.
Autonomous Institute, Affiliated to VTU
Ability to conduct practical experiments for demonstrating the operations of
CO4
different data structures and sorting techniques.

C CO-PO-PSO mapping

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO1
3
CO2
3
CO3
3
CO4
3 2 3

Indicate strength of mapping (1/2/3) with justification

D Proposed Assessment Plan (for 50 marks of CIE)

Tool Remarks Marks

Internals 20
QUIZ 5

Lab Component 25
Alternate Assessment Tool
Total 50

E Proposed Tutorial Plan (if applicable)

NIL

F Proposed Laboratory Plan (if applicable)

Lab Unit # Program Details
Program
1 Write a program to simulate the working of stack using an
array with the following :
a) Push
b) Pop
1
c) Display
The program should print appropriate messages for stack
overflow, stack underflow

1 WAP to convert a given valid parenthesized infix arithmetic

expression to postfix expression. The expression consists of
2 single character operands and the binary operators + (plus), -
(minus), * (multiply) and / (divide)

1 Write recursive C programs for

a) Solving the Towers of Hanoi problem.
3 b) Finding the GCD of three numbers.
c) Finding the nth Fibonacci number
d) Reverse the list
BMS COLLEGE OF ENGINEERING, BENGALURU-19.
Department of Computer Science and Engineering.
Autonomous Institute, Affiliated to VTU
2 WAP to simulate the working of a queue of integers using an
array. Provide the following operations
a) Insert
b) Delete
4
c) Display
The program should print appropriate messages for queue
empty and queue overflow conditions

2 WAP to simulate the working of a circular queue of integers

using an array. Provide the following operations.

a) Insert
5 b) Delete
c) Display
The program should print appropriate messages for queue
empty and queue overflow conditions

6 2 WAP to implement a double ended queue ADT

2 WAP to simulate the round robin scheduling algorithm using
7
queue
3 WAP to Implement Single Link List with following
operations

a) Create a linked list.

b) Insertion of a node at first position, at any position
8
and at end of list.
c) Deletion of first element, specified element and
last element in the list.
d) Display the contents of the linked list.

3 WAP to Implement Single Link List with following

operations

9 a) Create a List
b) Count the number of nodes in the link list.
c) Search a node in the link list.

3 WAP Implement Single Link List with following operations

a) Sort the linked list.

10
b) Reverse the linked list.
c) Concatenation of two linked lists

3 WAP to implement Stack & Queues using Linked

11 Representation
 BMS COLLEGE OF ENGINEERING, BENGALURU-19.
Department of Computer Science and Engineering.
Autonomous Institute, Affiliated to VTU
3 WAP Implement doubly link list with primitive operations

a) Create a doubly linked list.

12 b) Insert a new node to the left of the node.
c) Delete the node of a given data.
d) Display the contents of the list

13 3 WAP to implement Polynomial Arithmetic using Linked List

4 Write a program
a) To construct a binary Search tree.

b) To traverse the tree using all the methods i.e., in-

14 order, preorder and post order

c) To display the elements in the tree.

5 WAP to implement the following

Given a File of N employee records with a set K of Keys(4-
digit) which uniquely determine the records in file F.

Assume that file F is maintained in memory by a Hash Table

(HT) of m memory locations with L as the set of memory
addresses (2-digit) of locations in HT.
15
Let the keys in K and addresses in L are integers.

Design and develop a Program in C that uses Hash function

H: K -> L as H(K)=K mod m (remainder method), and
implement hashing technique to map a given key K to the
address space L.
Resolve the collision (if any) using linear probing.
16 5 Write the following C functions to implement threaded binary
tree (use inorder threading) and general tree : a) create a
threaded BT/General tree b) traverse the threaded binary tree
in inorder c) traverse the general tree in preorder, inorder and
postorder.
G Proposed Alternate Assessment ToolPlan (if applicable)

NIL
H SEE Exam Question paper format

Unit-1 Internal Choice One Question to be asked for 20 Marks

Unit-2 Mandatory One Question to be asked for 20 Marks

Unit-3 Mandatory Two Questions to be asked for 20 Marks each

Unit-4 Mandatory One Question to be asked for 20 Marks

Unit-5 Internal Choice Two Questions to be asked for 20 Marks each

 BMS COLLEGE OF ENGINEERING, BENGALURU-19.
Department of Computer Science and Engineering.
Autonomous Institute, Affiliated to VTU

Bloom’s Level Percentage of

Questions to be
Covered
Remember / 35%
Understand
Apply / Analyze 40%
Create / Evaluate 25%