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 infix-postfix conversion and expression evaluation. [6 lectures]
Non-linear 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:978-81-203-4007-7.
References
- Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 978-0073523408.
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 - 2-3-4 tree, B-Tree - 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:978-81-203-4007-7.\
- Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 978-0073523408.
Past Offerings
- Offered in Aug-Dec, 2022 by Unnikrishan C
- Offered in Jul-Dec, 2021 by Jasine
- Offered in Jul-Dec, 2020 by Unnikrishnan
- Offered in July-Dec, 2019 by Sahely
- Offered in July-Dec, 2018 by Krithika
Course Metadata
| Item | Details |
|---|---|
| Course Title | Data Structures and Algorithms |
| Course Code | CS2030 |
| Course Credits | 3-0-0-3 |
| Course Category | PMC |
| Proposing Faculty | Jasine Babu & Krithika Ramaswamy |
| Approved on | Senate 20 of IIT Palakkad |
| Course prerequisites | Systems Programming or Introduction to Programminmg |
| Course status | revised |
| Course revision information | Minor revision of CS2030 Data Structures & Algorithms Course |