Course Outline: Data Structures and Algorithms -II
Chapter 1: Tree
1.1 Concept and Terminologies
- Definition of trees
- Nodes, edges, root, leaves, subtrees, depth, height
- Binary tree properties and terminology
1.2 Types of Binary Trees
- Binary tree, Skewed tree, Strictly binary tree, Full binary tree, Complete binary tree
- Expression tree, Binary Search Tree (BST)
- Heap (Min-Heap, Max-Heap)
1.3 Representation of Trees
- Static representation (arrays, pointers)
- Dynamic representation (linked list-based)
1.4 Implementation and Operations on Binary Search Tree (BST)
- Create, Insert, Delete, Search operations
- Tree Traversals:
- Preorder, Inorder, Postorder (Recursive implementation)
- Level-order traversal using a queue
- Counting leaf, non-leaf, and total nodes
- Tree operations:
- Copy tree, Mirror tree
1.5 Applications of Trees
- Heap Sort: Implementation using a heap
- Greedy Strategy: Introduction to Greedy algorithms
- Huffman Encoding: Implementation using a priority queue
Chapter 2: Efficient Search Trees
2.1 Terminology: Balanced Trees
- AVL Trees, Red-Black Trees, Splay Trees, Lexical search trees (Trie)
2.2 AVL Tree
- Concepts, balance factor, and rotations (Left and Right rotations)
2.3 Red-Black Trees
- Concept of Red-Black trees
- Insertion and deletion operations in Red-Black trees
2.4 Multi-way Search Trees
- B-Trees and B+ Trees:
- Insertion, Deletion operations
Chapter 3: Graph
3.1 Concept and Terminologies
- Graph definitions: Vertices, edges, directed and undirected graphs
- Weighted vs unweighted graphs, cyclic vs acyclic graphs
3.2 Graph Representation
- Adjacency Matrix
- Adjacency List
- Inverse Adjacency List
- Adjacency Multilist
3.3 Graph Traversals
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Implementation of BFS and DFS
3.4 Applications of Graphs
- Topological Sorting: Directed acyclic graphs (DAGs)
- Greedy Strategy:
- Minimal Spanning Trees (Prim’s and Kruskal’s algorithms)
- Single Source Shortest Path: Dijkstra’s algorithm
- Dynamic Programming Strategy:
- All pairs shortest path – Floyd-Warshall algorithm
- Graphs in Social Networks: Graph representation of social networks
Chapter 4: Hash Table
4.1 Concept of Hashing
- Definition and importance of hashing in efficient searching and storage
4.2 Terminologies
- Hash Table, Hash Function, Bucket, Hash Address, Collision, Synonym, Overflow, etc.
4.3 Properties of a Good Hash Function
- Uniform distribution, minimal collisions, deterministic, etc.
4.4 Hash Functions
- Division Method
- MID-square Method
- Folding Methods
4.5 Collision Resolution Techniques
- Open Addressing:
- Linear probing, Quadratic probing, Rehashing
- Chaining:
- Coalesced chaining, Separate chaining
