Data Structures

CS25C08:

Data Structures

Course Objectives: This course presents various data structures and their importance to provide a comprehensive view about problem solving skills.

Linear Data Structures: Abstract Data Types- Internal Representation of Primitive Data Structures- One Dimensional and Multi-Dimensional Arrays- linear lists- Singly, doubly, Circular linked lists- Applications.

Practicals

• Single and Multidimensional arrays

• Singly, Doubly and Circular Linked Lists

Stacks and Queues: Stack: Representations – Operations – Implementations – Applications.

Queue: Representations – Operations – Implementations – Types - Applications.

Practicals

• String reverse operations and Expression evaluation

• Circular Queue and Priority Queue

Trees: Representations – Types – Binary Search Trees (BSTs) - AVL Tree – Operations: Search, Traversals, Rotations - Balanced BSTs- Splay trees- B-trees- Binary Heaps.

Practicals

• Traversal operation

• AVL Tree rotations

• Query and Update operations on Balanced BSTs

Sorting, Searching & Hashing Techniques: Linear and Binary Search - Bubble Sort - Insertion Sort- Merge Sort- Bucket Sort- Quick Sort- Heap sort- Hashing techniques- Dictionaries- Hash function- Collision - Separate chaining- open addressing.

Practicals

• Quick and Heap Sort

• Binary Search and Hashing

Graphs: Representation - Types – Operations - Prim’s, Kruskal algorithms - Dijikstra’s algorithm – Connected and Biconnected Components.

Practicals

• BFS and DFS algorithms

• Minimum Spanning Tree and shortest path algorithms

Assessment Weightage:

Weightage:

Continuous Assessment: 50%

(i) . Activities: 10%

(ii) . Internal Theory Examinations: 30%

(iii) .Internal Laboratory Examination: 10%

End Semester Theory Examination: 50%

Mandated Activities with marks:

Assignments (30), Quiz (10), Project based learning (25), Flipped Classroom (10), Review of GATE questions (25).

Internal Examinations: TWO tests

References

1. Gilberg, R. F., & Forouzan, B. A, “Data Structures: A Pseudocode Approach”, Cengage Learning India Private Limited, 2023

2. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, 4th Edition, Pearson, 2014.

3. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson, 2001.

4. D.S. Malik, Data Structures Using C++, 2nd Edition, Cengage, 2012.