SEMESTER S3

DATA STRUCTURES AND ALGORITHMS

(Common to CS/CA/CM/CD/CR/AI/AM/AD/CB/CN/CC/CU/CI/CG)

Course Code PCCST303 CIE Marks 40

Teaching Hours/Week
3:1:0:0 ESE Marks 60
(L: T:P: R)

Credits 4 Exam Hours 2 Hrs. 30 Min.

Prerequisites (if any) UCEST105 Course Type Theory

Course Objectives:

1. To provide the learner a comprehensive understanding of data structures and algorithms.

2. To prepare them for advanced studies or professional work in computer science and related
fields.

SYLLABUS

Module Contact
Syllabus Description
No. Hours
Basic Concepts of Data Structures
Definitions; Data Abstraction; Performance Analysis - Time & Space
Complexity, Asymptotic Notations; Polynomial representation using
1 11
Arrays, Sparse matrix (Tuple representation); Stacks and Queues - Stacks,
Multi-Stacks, Queues, Circular Queues, Double Ended Queues; Evaluation
of Expressions- Infix to Postfix, Evaluating Postfix Expressions.
Linked List and Memory Management
Singly Linked List - Operations on Linked List, Stacks and Queues using

2 Linked List, Polynomial representation using Linked List; Doubly Linked 11

List; Circular Linked List; Memory allocation - First-fit, Best-fit, and
Worst-fit allocation schemes; Garbage collection and compaction.
Trees and Graphs
Trees :- Representation Of Trees; Binary Trees - Types and Properties,
Binary Tree Representation, Tree Operations, Tree Traversals; Expression
3 11
Trees; Binary Search Trees - Binary Search Tree Operations; Binary Heaps
- Binary Heap Operations, Priority Queue.
Graphs :- Definitions; Representation of Graphs; Depth First Search and
 Breadth First Search; Applications of Graphs - Single Source All
Destination.
Sorting and Searching
Sorting Techniques :- Selection Sort, Insertion Sort, Quick Sort, Merge
Sort, Heap Sort, Radix Sort.

4 Searching Techniques :- Linear Search, Binary Search, Hashing - Hashing 11

functions : Mid square, Division, Folding, Digit Analysis; Collision
Resolution : Linear probing, Quadratic Probing, Double hashing, Open
hashing.

Course Assessment Method

(CIE: 40 marks, ESE: 60 marks)

Continuous Internal Evaluation Marks (CIE):

Internal Internal
Assignment/
Attendance Examination-1 Examination- 2 Total
Microproject
(Written) (Written)

5 15 10 10 40

End Semester Examination Marks (ESE)

In Part A, all questions need to be answered and in Part B, each student can choose any one
full question out of two questions

Part A Part B Total

 2 Questions from each  Each question carries 9 marks.
module.  Two questions will be given from each module, out
 Total of 8 Questions, each of which 1 question should be answered.
60
carrying 3 marks  Each question can have a maximum of 3 sub
divisions.
(8x3 =24 marks) (4x9 = 36 marks)
 Course Outcomes (COs)

At the end of the course students should be able to:

Bloom’s
Course Outcome Knowledge
Level (KL)
CO1 Identify appropriate data structures for solving real world problems. K3
Describe and implement linear data structures such as arrays, linked K3
CO2
lists, stacks, and queues.
Describe and Implement non linear data structures such as trees and K3
CO3
graphs.
Select appropriate searching and sorting algorithms to be used in K3
CO4
specific circumstances.
Note: K1- Remember, K2- Understand, K3- Apply, K4- Analyse, K5- Evaluate, K6- Create

CO-PO Mapping Table (Mapping of Course Outcomes to Program Outcomes)

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 3 3 3 3

CO2 3 3 3 3

CO3 3 3 3 3

CO4 3 3 3 3
Note: 1: Slight (Low), 2: Moderate (Medium), 3: Substantial (High), -: No Correlation

Text Books
Name of the Edition
Sl. No Title of the Book Name of the Author/s
Publisher and Year
Universities
Ellis Horowitz, Sartaj Sahni
1 Fundamentals of Data Structures in C press, 2/e, 2007
and Susan Anderson-Freed,
Thomas H Cormen, Charles
2 Introduction to Algorithms Leisesrson, Ronald L PHI 3/e, 2009
Rivest, Clifford Stein
 Reference Books
Name of the Edition
Sl. No Title of the Book Name of the Author/s
Publisher and Year
Prentice Hall
1 Classic Data Structures Samanta D. 2/e, 2018
India.
Aho A. V., J. E.
Pearson
2 Data Structures and Algorithms Hopcroft and J. D. 1/e, 2003
Publication.
Ullman
Introduction to Data Structures with Tremblay J. P. and P. G. Tata McGraw
3 2/e, 2017
Applications Sorenson Hill.
Theory and Problems of Data
4 Lipschuts S. Schaum’s Series 2/e, 2014
Structures

Video Links (NPTEL, SWAYAM…)

Module
Link ID
No.
1 https://nptel.ac.in/courses/106102064
2 https://ocw.mit.edu/courses/6-851-advanced-data-structures-spring-2012/