Syllabus (COMPUTER SCIENCE)

Course Type: MAJ-2

Semester: 2

Course Code: BCOSMAJ02C

Course Title: Data Structure

(L-P-Tu): 4-2-0

Credit: 6

Practical/Theory: Combined

Course Objective: • Understand various Data Structures and Algorithms. • To analyze the performance of Algorithms • Application of Data Structures and Algorithms to solve complex problems. • Solve problems involving graph, trees, heaps, sorting, searching etc.

Learning Outcome: • Understand basic Data Structures, Dynamic Memory Management. • Ability to implement abstract data types. • Ability to understand algorithm analysis procedure. • Ability to understand time complexity and space complexity of various Algorithms.

Theory

Arrays

Single and Multi-Dimensional Arrays, Sparse Matrices (Array and Linked Representation).(6 Lectures)

Linked Lists

Singly, Doubly and Circular Linked Lists, Basic Operations on these Lists, Polynomial Representation using Linked List. (8 Lectures)

Stacks

Implementing Stack (Array and Linked Representation), Prefix, Infix, and Postfix Expressions; Utility, and Conversion of these Expressions from one to another, Applications of Stack, Limitations of Array Representation of Stack. (8 Lectures)

Queues

Array and Linked Representation of Queues, Circular Queues, Priority Queues.(6 Lectures)

Recursion

Developing Recursive Definitions of Simple Problems and their Implementations, Tracing Recursion, Analyzing Recursion, Towers of Hanoi. (6 Lectures)

Trees and Graphs

Introduction to Trees, Binary Trees, Tree Traversals, Binary Search Trees, Various operations on Binary Search Trees, Height-Balanced Trees, Various Operations on Adelson-Velski and Landis (AVL) Trees, BFS, DFS, Spanning Tree. (10 Lectures)

Searching and Sorting

Linear Search, Binary Search, Comparison of Linear Search and Binary Search, Selection Sort, Bubble Sort, Insertion Sort, Shell Sort, Quick Sort, Merge Sort, Comparison of Sorting Techniques. (10 Lectures)

Hashing

Direct Address Table, Introduction to Hashing, Chaining, Open Addressing (Linear Probing, Quadratic Probing, Double Hashing). (6 Lectures)

Data Structures Lab using Python

• Implement single and multi-dimensional arrays, and perform operations.
• Implement linked lists (singly, doubly, and circular) and their basic operations.
• Implement stacks (array and linked representation), and perform conversions between prefix, infix, and postfix expressions.
• Implement queues (array and linked representation), circular queues, and priority queues.
• Develop recursive solutions for simple problems and analyze recursion.
• Implement tree structures (binary trees, binary search trees, AVL trees) and perform tree traversals.
• Implement searching algorithms (linear search, binary search) and sorting algorithms (selection sort, bubble sort, insertion sort, shell sort, quicksort, merge sort).
• Implement hashing techniques (direct address table, chaining, open addressing).

References:

1. Michael T. Goodrich, Data Structures and Algorithms in Python.
2. Narasimha Karumanchi, Data Structures and Algorithmic Thinking with Python.
3. Kent D. Lee and Steve Hubbard, Data Structures and Algorithms with Python.
4. Bradley N Miller and David L. Ranum, Problem Solving with Algorithms and Data Structures Using Python.
5. Aaron M. Tenenbaum, Moshe J. Augenstein, Yedidyah Langsam, “Data Structures Using C and C++”, PHI.