Learning Objectives

Acquire some basic mathematical tools and techniques of algorithm analysis. To be familiar with some important data structures and to develop the ability to choose the appropriate data structure for designing efficient algorithms. Learn some basic algorithms with their rigours proofs of correctness and efficiency analysis of implementation using appropriate data structures.

Syllabus

Problem Solving using Computers: Abstraction - Abstract data types; Data Representation; Elementary data types; Basic concepts of data Structures; Mathematical preliminaries - big-Oh notation; efficiency of algorithms; notion of time and space complexity; performance measures for data structures. ADT array - Computations on arrays - sorting and searching algorithms. ADT Stack, Queue, list - array, linked list, cursor based implementations of linear structures. ADT Tree - tree representation, traversal of trees; ADT Binary tree - binary trees, threaded binary trees, application of binary trees - Huffmann coding; application of threaded binary trees - differentiation; Search Tree - Binary search tree; balanced binary search trees - AVL tree; Applications of Search Trees - TRIE; 2-3 tree, 2-3-4 tree; concept of B-Tree. ADT Dictionary - array based and tree based implementations; hashing - definition and application - LZW encoding. ADT Priority Queue - Heaps; heap-based implementations; applications of heaps - sorting; Graphs - shortest path, minimum spanning tree, DFS, BFS - an application of DFS and BFS. Algorithm Design Paradigms - greedy, divide and conquer, dynamic programming, backtracking.

Textbook(s)

  1. 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.

  2. Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 978-0073523408.

Past Offerings

  • Offered in Jan-May, 2018 by Jasine
  • Offered in Jan-May, 2017 by Jasine

Course Metadata

Item Details
Course Title Data Structures and Algorithms
Course Code CS2800
Course Credits 3-1-0-4
Course Category PMT
Approved on Senate of IIT Palakkad