L T P C

15CS252J DATA STRUCTURES AND ALGORITHMS

2 0 2 3
Co-requisite: Nil
Prerequisite: Nil
Data Book /
Codes/Standards Nil
Course Category P PROFESSIONAL ELECTIVE
Course designed by Department of Computer Science and Engineering
Approval Academic Council Meeting , 2016

PURPOSE To introduce the concept of Data Structures, Algorithm design and analysis.

INSTRUCTIONAL OBJECTIVES STUDENT

OUTCOMES
At the end of the course, student will be able to
1. To introduce the concepts of linear data structures a b
2. To learn about non-linear data structures, sorting a b
3. To introduce the concepts of balanced search tress, indexing and hashing a b
4. To understand the graph structures a b
5. To get exposure to the various algorithm design and analysis techniques. a b

C-
Session Description of Topic (Theory) Contact
D- IOs Reference
hours
I-O
6
UNIT I LINEAR STRUCTURES
List ADT: Implementation using arrays, linked list, cursor-
1. 1 C 1 1
based linked lists
2. Doubly-linked lists, applications of lists 2 C 1 1
3. Stack ADT: Concept and Applications. 1 C 1 1,4
4. Queue ADT: Queue, Circular queue, Applications. 2 C 1 1,4
6 1,2
UNIT II NON-LINEAR DATA STRUCTURES, SORTING C
Tree ADT: Basics, Tree traversals, Binary Tree, expression
5. 3 C 2 1,2
trees, applications, binary search tree.
6. Sorting: Insertion Sort – Shell Sort – Heap Sort – Merge Sort – 1,3
3 C 2
Quick Sort – External Sorting
UNIT III BALANCED SEARCH TREES, INDEXING & 6 C 1
HASHING
7. Balanced Search Trees, AVL trees, Binary Heaps, B-Tree. 4 C 3 1
Indexing & hashing: Hash Function – Separate Chaining –
8. 2 C 3 1,3
Open Addressing
UNIT IV GRAPHS 6 C 1
9. Definitions – Topological sort – breadth-first traversal - 1
3 C 4
shortest-path algorithms – minimum spanning tree.
10. Prim's and Kruskal's algorithms – Depth-first traversal. 2 C 4 1,3
11. Applications of graphs 1 C 4 1
UNIT V ALGORITHM DESIGN AND ANALYSIS 6 C 1
12. Greedy algorithms – Divide and conquer – Dynamic 1
3 C 5
programming.
13. Backtracking – Branch and Bound. 2 C 5 1
 14. Algorithm analysis – Asymptotic notations. 1 C 5 1

Total contact hours 30

Sl. C-
Description of experiments Contact
D-I- IOs Reference
No. hours
O
1. List: Array and linked list implementations 2 C, I 1 1,2
2. Stack: Array and linked list implementations 2 C, I 1 1,2
3. Selection sort, Bubble sort implementation 2 C, I 2 1,2
4. Binary search tree implementations 2 C, I 3 1,2
5. Linear search, Binary search implementation 2 C, I 3 1,2
6. Prim's and Kruskal's algorithms implementation 2 C, I 4 1,2
7. Branch and bound algorithm for traveling salesperson problem 1,2
3 C, I 5
implementation
Total contact hours 15

LEARNING RESOURCES
Sl.
TEXT BOOKS
No.
1. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, Pearson India, 2007.
2. Aaron M. Tenenbaum , Yedidyah Langsam, Moshe J. Augenstein, “Data Structures Using C”,
Pearson India, 2009.
REFERENCE BOOKS/OTHER READING MATERIAL
3. R. F. Gilberg, B.A. Forouzan, “Data Structures: A Pseudocode approach with C”, Second Edition,
Cengage India, 2007.
4. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms”, Pearson India, 2009.

Course nature Theory + Practical

Assessment Method – Theory Component (Weightage 50%)
In- Assessment tool Cycle test I Cycle test II Cycle Test III Surprise Test Quiz Total
semester Weightage 15% 25% 5% 5% 50%
End semester examination Weightage : 50%

Assessment Method – Practical Component (Weightage 50%)

Assessment Experiment MCQ/Quiz/Viva Model
In- Record Total
tool s Voce examination
semester
Weightage 40% 5% 5% 10% 60%
End semester examination Weightage : 40%