Indian Institute of Information Technology, Allahabad

Data Structures and Algorithms

Jan-May 2024 Semester

Course Information

Course Description: In this course, students learn the concepts of Data Structures and Algorithms and practice them using C language.

Course Outline:

  • Unit 1: Introduction, Complexity Analysis, Recursion, Searching, Sorting.
  • Unit 2: Linked List, Abstract Data Types, Stacks and Queues.
  • Unit 3: Trees, Traversal, Binary Search Tree, Height Balanced Tree (AVL Tree), Heap, Priority Queue, Heap Sort, Hashing, Dictionaries.
  • Unit 4: Graphs, Graph Representation, Graph Traversal - DFS, BFS, Minimum Spanning Tree - Prim's and Kruskal's, Single Source Shortest Path - Dijkstra, Geometric data structures.

Course Instructor

Dr. Shiv Ram Dubey

TAs

  • Akash Verma - RSI2023001
  • HRITU RAJ - MHC2022007
  • VIKAS RAJPUT - MHC2022012
  • HARSHIT GUPTA - MML2022017
  • MANISH DAS - PMR2023002
  • RAHULKUMAR RANJEET JHA - MNS2023002
Class Schedule (Section B)
Class: Monday 11.00 AM - 01.00 PM and Thursday 12.00 Noon - 01.00 PM, Lab: Thursday 03.00 PM - 05.00 PM
Course Ethics
  • Students are strictly advised to avoid the unethical practices in the course including tests and practice components.
  • It is best to try to solve problems on your own, since problem solving is an important component of the course.
  • You are allowed to discuss class material, problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions you must work/implement by yourself.
  • You are not allowed to take the codes from any source, including online, books, your classmate, etc. in the assignments and exams.
  • You may use free and publicly available sources (at idea level only), such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose marks for using external sources.)
  • You may not use any paid service and you must clearly and explicitly cite all outside sources and materials that you made use of.
  • Students are not allowed to post the code/report/any other material of course assignment/project in public domain or share with any one else without written permission from course instructors.
  • We consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the Institute's policies on academic dishonesty.
  • Instances will be dealt with harshly and typically result in a failing course grade.
  • Cheating cases will attract severe penalties.

Schedule

Lecture Topic Class Material
L01-04 Introduction, Selection Sort and Merge Sort Slide
L05-06 Asymptotic Analysis Slide
L07 Searching Slide
L08 Quick Sort Slide
L09-10 Linked List Slide
L11-12 Stacks Slide
L13-14 Queues and Lists Slide
L15-16 Binary Search Tree Slide
L17-19 Height Balanced Tree (AVL Tree) Slide
L20-22 Heap Sort and Priority Queues Slide
L23-24 Hashing Slide
L25 Graphs Slide
L26-27 Depth First Search (DFS) Slide
L28-29 Breadth First Search (BFS) Slide
L30-31 Minimum Spanning Tree (MST) Slide
L32-34 Single Source Shortest Path (Dijkstra) Slide

Grading

  • Internal (35%)
  • Mid Exam (25%)
  • End Exam (40%)

Prerequisites

  • Ability to deal with abstract mathematical concepts
  • Problem Solving
  • Computer Programming

Books/References

  • Fundamentals of Data Structures in C by E. Horowitz, S. Sahni, S. Anderson-Freed, Second Edition, 2008.
  • Data Structures Using C and C++ by Y. Langsam, M. J. Augenstein, A. M. Tenenbaum, PHI, New Delhi, 2001.
  • Data Structures and Algorithm Analysis in C (DSAC) by Mark Allen Weiss, Second Edition, 2002
  • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Third Edition, The MIT Press
  • Algorithms Design by Jon Kleinberg and Eva Tardos, Pearson
  • The Design and Analysis of Algorithms by A V Aho, J E Hopcroft, and J D Ullman, Pearson
  • Data Structures, S. Lipschutz, Schaum’s Outline Series
  • Data structures and Network Algorithms by Robert Endre Tarjan, Society for Industrial and Applied Mathematics Philadelphia, PA, USA, 1983, ISBN:0-89871-187-8
  • The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie, Prentice Hall
  • Programming with C, Byron Gottfried
  • Programming in ANSI C, E. Balaguruswamy
  • Expert C Programming: Deep C Secrets by Peter van der Linden, Prentice Hall
  • C Programming FAQs by Steve Summit, Deborah Lafferty, Addison-Wesley Professional
  • C Traps and Pitfalls by Andrew Koenig, Addison-Wesley Professional
  • The C Puzzle Book by Alan R. Feuer, Addison-Wesley Professional

Disclaimer

The content (text, image, and graphics) used in this slide are adopted from many sources for Academic purposes. Broadly, the sources have been given due credit appropriately. However, there is a chance of missing out some original primary sources. The authors of this material do not claim any copyright of such material.