15CS252J DATA STRUCTURES AND ALGORITHMS LTPC 2 0 2 3

15CS252J Co-requisite: Prerequisite: Data Book / Codes/Standards Course Category Course designed by Approval

PURPOSE

Nil P PROFESSIONAL ELECTIVE Department of Computer Science and Engineering Academic Council Meeting , 2016

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

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

Description of Topic (Theory) UNIT I LINEAR STRUCTURES

1.

List ADT: Implementation using arrays, linked list, cursorbased linked lists

2. 3. 4.

6.

7. 8.

9. 10. 11. 12. 13.

a a a a a

Contact hours

b b b b b CD- IOs Reference I-O

6 1

C

1

1

Doubly-linked lists, applications of lists Stack ADT: Concept and Applications.

2

C

1

1

C

1

1 1,4

Queue ADT: Queue, Circular queue, Applications.

2 6

C

1

1,4

3

C

2

1,2

3

C

2

1,3

6

C

4

C

3

1

2

C

3

1,3

6

C

3

C

4

1

2 1 6

C C C

4 4

1,3 1 1

3

C

5

1

2

C

5

1

UNIT II NON-LINEAR DATA STRUCTURES, SORTING 5.

C 3

Nil Nil

INSTRUCTIONAL OBJECTIVES

Session

L T P 2 0 2

DATA STRUCTURES AND ALGORITHMS

Tree ADT: Basics, Tree traversals, Binary Tree, expression trees, applications, binary search tree. Sorting: Insertion Sort – Shell Sort – Heap Sort – Merge Sort – Quick Sort – External Sorting UNIT III BALANCED SEARCH TREES, INDEXING & HASHING Balanced Search Trees, AVL trees, Binary Heaps, B-Tree. Indexing & hashing: Hash Function – Separate Chaining – Open Addressing UNIT IV GRAPHS Definitions – Topological sort – breadth-first traversal shortest-path algorithms – minimum spanning tree. Prim's and Kruskal's algorithms – Depth-first traversal. Applications of graphs UNIT V ALGORITHM DESIGN AND ANALYSIS Greedy algorithms – Divide and conquer – Dynamic programming. Backtracking – Branch and Bound.

1,2

C

1

1

14.

Algorithm analysis – Asymptotic notations.

1

C

Total contact hours Sl. No. 1. 2. 3. 4. 5. 6.

Description of experiments

List: Array and linked list implementations Stack: Array and linked list implementations Selection sort, Bubble sort implementation Binary search tree implementations Linear search, Binary search implementation Prim's and Kruskal's algorithms implementation 7. Branch and bound algorithm for traveling salesperson problem implementation Total contact hours

5

1

30 CContact D-I- IOs Reference hours O 2 C, I 1 1,2 2 2 2 2 2

C, I C, I C, I C, I C, I

1 2 3 3 4

3

C, I

5

1,2 1,2 1,2 1,2 1,2 1,2

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%) InAssessment 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 Record Total Intool s Voce examination semester Weightage 40% 5% 5% 10% 60% End semester examination Weightage : 40%