Showing the latest revision in section Curriculum 2022. The earlier version is in section Curriculum 2017.
Curriculum 2022
Prerequisite (if any) : Systems Programming or Introduction to Programming
Course Content
Introduction
Computation, algorithms and data structures. Elementary data types, abstract data types and data structures. RAM model of computation. Example of computational problems and algorithms  searching an element in an array using linear search and binary search. Notion of efficiency of algorithms  running time and memory consumption. Notions of best, worst and average case complexity. [3 lectures]
Iteration and Recursion
Iterative and recursive algorithms (Towers of Hanoi, Euclidâ€™s GCD algorithm), proof of correctness using induction. Sorting arrays using selection sort, insertion sort, quicksort and merge sort (with proof of correctness and efficiency analysis). [8 lectures]
Asymptotic Analysis
Asymptotic notation. Estimates of binomials and factorials. Methods of solving recurrences using induction, recursion tree and Master method. Application of asymptotics to analysing efficiency of algorithms. [8 lectures]
Linear Data Structures
Arrays and linked lists (single and doubly linked lists). Array and linked list based implementations for Queue and Stack. Applications to infixpostfix conversion and expression evaluation. [6 lectures]
Nonlinear Data Structures
Trees  rooted trees, traversal of trees, binary trees, expression trees, binary search trees. Heaps and priority queues using min/max heaps. [8 lectures]
Graphs  adjacency matrix and adjacency list representations, depth first search, breadth first search. [6 lectures]
Hash tables  hash functions, open addressing, chaining. [3 lectures]
Learning Outcomes

To understand basic data structures, their implementation and some of their standard applications.

To develop the ability to design and analyze basic algorithms and prove their correctness using the appropriate data structure learned in the course.
Text Books
 Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. Introduction to Algorithms, Third Edition, PHI Learning, 2009. ISBN:9788120340077.
References
 Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 9780073523408.
Curriculum 2017
Learning Objectives
 Acquire some basic mathematical tools and techniques of algorithm analysis.
 To familiarise with basic data structures and to develop the ability to choose the appropriate data structure for designing efficient algorithms.
 Learn some basic algorithms with their rigorous proofs of correctness and efficiency analysis of implementation using appropriate data structures.
Learning Outcomes
 To know about some basic data structures, their implementation and some of their standard applications.
 To develop the ability to analyze the running time and prove the correctness of basic algorithms.
 To develop the ability to design and analyze simple algorithms using the appropriate data structure learned in the course.
Syllabus
Data Representation  Basic concepts of data structures; Abstract data types; Elementary data types; Mathematical preliminaries  asymptotic notations; efficiency of algorithms; notion of time and space complexity; notions of best, worst and average case performance analysis, solving simple recurrences, solving divide and conquer type recurrences.
Computations on arrays with best and worst case performance analysis  binary search, bubble sort, insertion sort, quicksort, external merge sort, heaps and heapsort, priority queues using heaps.
Linked lists  single and doubly linked lists.
Queue and Stack data structures  array based and linked list based implementations. Infix to postfix conversion and expression evaluation. Graphs  Adjacency matrix and adjacency list representations, DFS, BFS.
Hash Tables  hash functions, open addressing, chaining. Trees  rooted tree representation, traversal of trees, binary trees, expression trees. Search Tree  binary search trees. Balanced search trees  234 tree, BTree  an external memory data structure.
Textbook(s)
 Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. Introduction to Algorithms, Third Edition, PHI Learning, 2009. ISBN:9788120340077.\
 Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 9780073523408.
Metadata
Proposing Faculty: Department: Computer Science and Engineering Programme: B.Tech Proposing date: Approved date: Proposal type: Offerings: