Starting from 22.09.2015
Data Structures and Algorithms (L + P - 50 hrs.)
Objectives: To provide theoretical and practical concepts along with the uses of data structures and algorithms.
Outcome: On completion of this course, students are expected to be capable of understanding the data structures, their advantages, and drawbacks, how to implement them in C or in their known language, how their drawbacks can be overcome and what the applications are and where they can be used. Students should be able to learn about the data structures, methods, and algorithms mentioned in the course with a comparative perspective so as to make use of the most appropriate data structure, method, or algorithm in a program to enhance efficiency (i.e., reduce the run-time) or for better memory utilization, based on the priority of the implementation. The participant should be able to convert an inefficient program into an efficient one using the knowledge gathered from this course.
Theory (L - 50 hrs.)
| S.No | Topic | Lecture (hrs) |
|---|---|---|
| 1 | Algorithm efficiency and analysis, order notations | 1 |
| 2 | Array: Different representations – row major, column major. Sparse matrix - its implementation and usage | 2 |
| 3 | Array representation of polynomials | 1 |
| 4 | Linked List: Singly linked list, circular linked list, doubly linked list | 2 |
| 5 | Representation of polynomial expression and Sparse Matrix using suitable Linked List | 2 |
| 6 | Stack and its implementations, Principles of recursion – use of stack, Tail recursion, Applications - The Tower of Hanoi, Eight Queens Puzzle | 2 |
| 7 | Queue, circular queue, Dequeqe, Priority Queue and its different Implementation, Applications | 1 |
| 8 | Trees: Basic Concepts & representation, Binary trees - Traversal (pre-, in-, post- order), Threaded binary tree (left, right, full), Expression tree | 3 |
| 9 | Binary search tree- operations (creation, insertion, deletion, searching) | 2 |
| 10 | B-Trees & B+ Tree – operations | 1 |
| 11 | Heaps: Balanced Search Trees as Heaps, Array-Based Heap, Heap-Ordered Trees and Half-Ordered Trees, Leftist Heaps, Skew Heap, Binomial Heaps, Changing Keys in Heaps | 2 |
| 12 | Height-Balanced Trees and Weight Trees | 2 |
| 13 | Red-Black Trees and Trees of Almost Optimal Height | 1 |
| 14 | Top-Down Rebalancing for Red-Black Trees, Trees with Constant Update Time at a Known Location, Finger Trees and Level Linking | 2 |
| 15 | Trees with Partial Rebuilding: Amortized Analysis, Splay Trees: Adaptive Data Structures | 1 |
| 16 | Skip Lists: Randomized Data Structures, Joining and Splitting Balanced Search Trees | 1 |
| 17 | Interval Trees, Segment Trees, Trees for Interval-Restricted Maximum Sum Queries, Orthogonal Range Trees, and Higher-Dimensional Segment Tree | 2 |
| 18 | Searching: Sequential search, binary search, interpolation search. | 2 |
| 19 | Sorting Algorithms: Bubble sort and its optimizations, insertion sort, shell sort, selection sort, merge sort, quick sort, heap sort, radix sort | 4 |
| 20 | Graph definitions and concepts. Graph representations/storage implementations – adjacency matrix, adjacency list, adjacency multi-list | 2 |
| 21 | Graph traversal algorithm: Breadth First Search (BFS) and Depth First Search (DFS) – Classification of edges - tree, forward, back and cross edges – complexity and comparison | 1 |
| 22 | Basic Hash Tables and Collision Resolution, Universal Families of Hash Functions, Perfect Hash Functions, and Hash Trees, Extendible Hashing, Membership Testers and Bloom Filters | 2 |
| 23 | Divide & Conquer Algorithms | 2 |
| 24 | Greedy Algorithms: Basic method, use, Examples | 2 |
| 25 | Dynamic Programming: Basic method, use, Examples | 4 |
| 26 | Backtracking Algorithms: | 4 |
| 27 | Notion of NP-completeness: P class, NP class, NP hard class, NP complete class – their interrelationship, Satisfiability problem, Cook’s theorem, Clique decision problem | 4 |
| Total lecture (hrs.) | 50 |
Laboratory
- Lab 1: Sequential search, binary search, interpolation search, Array insertion and deletion from any position, sparse matrix, array representation using polynomial.
- Lab 2: Implementation of linked lists: inserting, deleting, and inverting a linked list. Polynomial addition and Polynomial multiplication using linked lists.
- Lab 3: Stacks and Queues: adding, deleting elements Circular Queue, Priority queue, Infix to prefix and postfix conversion.
- Lab 4: Factorial using recursion, Tower of Hanoi, Backtracking: Implement 8 Queen problem.
- Lab 5: Merge sort, quick sort, radix sort, Sequential search, binary search, interpolation search.
- Lab 6: Binary Tree, Traversal of Binary Tree, Binary Search Tree.
- Lab 7: AVL tree, Red and Black Tree, B-Tree.
- Lab 8: Balanced search trees as heap, Fibonacci heap, heap sort.
- Lab 9: Graph Traversal Algorithm: (i) Breadth First Search (BFS), (ii) Depth First Search (DFS).
- Lab 10: Greedy method: Minimum Cost Spanning Tree by (i) Prim's Algorithm, and (ii) Kruskal's Algorithm.