Data Structures
Data is like your wardrobe, you want the selected clothes as fast as possible, should occupy the least magnitude of space, should take the least of efforts to add stuff and organize, and should look beautiful at the same time. Naturally the requirements are too hard to keep, especially when you're a heartthrob and people love gifting you now and then. The course preaches the way to understand your problems and get your stuff organized, the digital version. The course discusses fancy looking structures to organize your stuff; while the stuff may be ugly, the organization is beautiful and efficient.
This is largely a programming course and takes aboard the students in a challenging journey of increasing complexity as the course proceeds. Starting from the primitive uses of arrays and linked lists, and using the same primitives to implement basic data structures, the course carries forward to programming and using trees and graphs. The course presents a blend of programming primitive operations of data structures, and using the data structures for unbelievable problems creatively crafted by the instructors.
Theory Syllabus
| S. No. | Topic | Details |
| 1. | Introduction | Introduction to Data Structure, Types of Data Structure, Abstract Data Types, Introduction to Array, Array Implementation and Applications |
| 2. | Stack | Introduction:LIFO structure, create, POP, PUSH, delete stack, ADTs, Stack, Implementation using Array, Stack Implementation using Linked List, Applications, Pre-, In-, Post-fix expressions |
| 3. | Queue | Introduction: FIFO Structure, ADTs, Queue Implementation using Array, Queue, Implementation using Linked List, ApplicationsTypes of Queues: Circular Queue, Dequeue and Priority Queue: Implementation, ADTs and Applications |
| 4. | Recursion | Introduction, Types of Recursion, Application of Recursion, Backtracking |
| 5. | Linked List | What is Linked List, Advantage of Linked List, Types of Linked List, Singly Linked List- Implementation, ADTs and Applications, Circular Linked List-Implementation, ADTs and Applications, Doubly Linked List-Implementation, ADTs and Applications, Sorted Linked List- Implementation, ADTs and Applications |
| 6. | Sorting | What is Sorting, Types of Sorting, Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, Quick Sort, Quick-select, Advantages and Disadvantages of All Sorting Algorithm, Complexity Analysis of Sorting Algorithm |
| 7. | Analysis of Algorithms | Algorithm, Pseudo code for expressing algorithms, time complexity and space complexity,O-notation, Omega notation and theta notation |
| 8. | Dictionary Basics | Array Based Ordered and Unordered, Linked List Based Ordered and Unordered |
| 9. | Searching | Sequential Search, Binary Search, Algorithm and Analysis |
| 10. | Hash Table Basics | Collision Resolutions using Separate Chaining, Collision Resolutions using Open Addressing, Quadratic Probing, Double Hashing |
| 11. | String Algorithms | Naive string matching, Rabin Karp, Boyer Moore |
| 12. | Trees | Binary trees, n-ary trees, Binary Search Trees, Heaps, Heapsort, AVL Trees |
| 13. | Graph Theory | Graphs, Disjoint sets, Kruskal's MST using disjoint sets, Dijkstra's Algorithm, Floyd-Warshall's algorithm, BFS and DFS searches |
Lab Syllabus
| S. No. | Topic | Details |
| 1. | Introduction | Basics of Arrays and Pointers |
| 2. | Stack | Create, POP, PUSH, delete stack, Stack, Implementation using Array, Stack Implementation using Linked List, Applications, Pre-, In-, Post-fix expressions |
| 3. | Queue | Queue Implementation using Array, Queue, Implementation using Linked List, Applications, Types of Queues: Circular Queue, Dequeue and Priority Queue: Implementation and Applications |
| 4. | Recursion | Application of Recursion, Backtracking |
| 5. | Linked List | Singly Linked List, Circular Linked List, Doubly Linked List, Sorted Linked List, Applications |
| 6. | Sorting | Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, Quick Sort, Quick-select |
| 7. | Analysis of Algorithms | Algorithm, Pseudo code for expressing algorithms, time complexity and space complexity,O-notation, Omega notation and theta notation |
| 8. | Dictionary Basics | Array Based Ordered and Unordered, Linked List Based Ordered and Unordered |
| 9. | Searching | Sequential Search, Binary Search |
| 10. | Hash Table Basics | Collision Resolutions using Separate Chaining, Collision Resolutions using Open Addressing (no deletions), Quadratic Probing, Double Hashing |
| 11. | Trees | Binary Search Trees (no deletions), Heaps, Heapsort |
| 12. | Graph Theory | Dijkstra's Algorithm, BFS and DFS searches |
Pre-Requisites
Understanding and a good hands-on programming is very essential. The students are required to spend prolonged hours programming, more than the hours assigned in the laboratory contact hours.
Text/Reference Material
- Main textbook covering most of the topics: Y. Langasm, M. J. Augenstein, A. M. Tenenbaum (2001) Data Structures Using C And C++ , Prentice Hall India, New Delhi, India .
- Reference book: T. H. Cormen, C. E. Leiserson and R. L. Rivest (1990) Introduction to Algorithms, Third Edition, MIT Press, MA.
Whats New
- Inauguration of the Centre of Intelligent Robotics from 2nd to 3rd January, 2020
- Paper presented at CICT 2019 at IIIT Allahabad. The paper is a part of the ASEAN funded project.
- 2 Papers presented at IEEE CEC Wellington are available online.
- Paper at Computational Intelligence published in an issue.
- Hosted Teun Mentzel at IIIT Allahabad for framing the incubation program NewGen IEDC
- Hosted the first advisory board meeting of the NewGen IEDC incubation project
- Delivered a talk at IEEE CIS Summer School at IIIT Allahabad
- Visited UBL Jakarta under the ASEAN project scheme. Delivered talks at multiple venues.
- Delivered talks on Artificial Intelligence at GAT Bangalore
- Participated and presented 2 papers at the IEEE CEC 2019
