Data Structures

CS3301 - Data Structures

Course Objectives

Understand the concepts of Abstract Data Types (ADTs).
Learn linear data structures: lists, stacks, and queues.
Understand non-linear data structures: trees and graphs.
Master sorting, searching, and hashing algorithms.
Apply tree and graph structures for various problems.

Syllabus Overview

UNIT I: Lists

Abstract Data Types (ADTs): Definition and design of ADTs as a foundation for data structures.
List ADT: Properties, operations (insert, delete, find, etc.).
Implementations:
- Array-based lists
- Linked lists:
  - Singly linked lists
  - Circularly linked lists
  - Doubly linked lists
Applications of Lists:
- Polynomial ADT
- Radix Sort
- Multilists

UNIT II: Stacks and Queues

Stack ADT:
- Stack operations (push, pop, top)
- Applications:
  - Balancing symbols
  - Evaluating arithmetic expressions
  - Infix to postfix conversion
  - Function call tracking
Queue ADT:
- Queue operations (enqueue, dequeue)
- Circular queues
- DeQueue (Double-ended Queue)
- Applications of queues

UNIT III: Trees

Tree ADT: Hierarchical structure, terminology (node, leaf, root, etc.)
Tree Traversals: In-order, pre-order, post-order
Binary Tree ADT: Definition and operations
Specialized Trees:
- Expression trees
- Binary Search Tree (BST) ADT
- AVL Trees (self-balancing trees)
- Priority Queues (Heaps)
- Binary Heaps

UNIT IV: Multiway Search Trees and Graphs

Multiway Trees:
- B-Tree
- B+ Tree
Graphs:
- Graph definition and basic terminology
- Representation: adjacency matrix, adjacency list
- Types of graphs
- Traversals:
  - Breadth-first traversal (BFS)
  - Depth-first traversal (DFS)
- Additional concepts:
  - Bi-connectivity
  - Euler circuits
  - Topological sort
  - Dijkstra’s algorithm (shortest path)
  - Minimum Spanning Tree:
    - Prim’s algorithm
    - Kruskal’s algorithm

UNIT V: Searching, Sorting, and Hashing Techniques

Searching:
- Linear Search
- Binary Search
Sorting Algorithms:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Shell Sort
- Merge Sort
Hashing:
- Hash functions
- Collision resolution:
  - Separate chaining
  - Open addressing
  - Rehashing
  - Extendible hashing

Core Textbooks

Mark Allen Weiss, Data Structures and Algorithm Analysis in C, 2nd Edition, Pearson Education, 2005.
Kamthane, Introduction to Data Structures in C, 1st Edition, Pearson Education, 2007.

Additional References

Langsam, Augenstein, and Tanenbaum, Data Structures Using C and C++, 2nd Edition, Pearson Education, 2015.
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th Edition, McGraw Hill/MIT Press, 2022.
Aho, Ullman, Hopcroft, Data Structures and Algorithms, Pearson, 2002.
Kruse, Data Structures and Program Design in C, 2nd Edition, Pearson Education, 2006.

This course forms a strong foundation in data structures theory and practice, equipping students for advanced algorithmic studies and practical software development.