Data Structures and Algorithms - CS25C04

 

CS25C04:

Data Structures and Algorithms

 

Course Objective:

• To provide the fundamentals of data organization and algorithms.

 

Data Types: Abstract Data Types (ADTs), ADTs and classes, introduction to OOP, Classes in Python, Inheritance, Namespaces, Shallow and Deep Copying.

Practical: Implement simple ADTs as Python classes

 

Linear Structures: List ADT, array-based implementations, linked list implementations, singly linked lists, circularly linked lists, doubly linked lists, Stack ADT, Queue ADT, double ended queues, applications

Practical: List ADT using Python arrays, Linked list, Stack and Queue ADTs and Applications.

Tree Structures: Tree ADT, Binary Tree ADT, tree traversals, binary search trees, AVL trees, heaps, multi-way search trees

Practical: Tree representation and traversal algorithms, Binary Search Trees, Heaps.

 

Graph Structures: Graph ADT, representations of graph, graph traversals, DAG, topological ordering, greedy algorithms, dynamic programming, shortest paths, minimum spanning trees, introduction to complexity classes and intractability

Practical: Graph representation and Traversal algorithms, Single source shortest path algorithm, Minimum spanning tree algorithms.

 

Algorithm: Analysis of algorithms, Asymptotic notations, Divide & Conquer, Recursion, Recursive Algorithms

Practical: Implement recursive algorithms in Python.

 

Sorting and Searching

Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort, Analysis of sorting algorithms, Linear & Binary search, Hashing, Hash functions, Collision handling, Load factors, Rehashing, and Efficiency

Practical: Sorting and searching algorithms, Hash tables.

 

Weightage: Continuous Assessment: 40%, End Semester Examinations: 60% 

Assessment Methodology: Quiz (10%), Assignments (30%) Review of GATE questions (20%) and Internal Examinations (50%)

 

References:

1. Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2021). Data structures & algorithms in Python (Indian adaptation). John Wiley & Sons Inc.

2. Lee, K. D., & Hubbard, S. (2015). Data structures and algorithms with Python. Springer.

3. Necaise, R. D. (2011). Data structures and algorithms using Python. John Wiley & Sons.

4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2002). Introduction to algorithms. McGraw-Hill.

5. Weiss, M. A. (2014). Data structures and algorithm analysis in C++. Pearson Education.

E-Resource:

 https://nptel.ac.in/courses/106106133