CS2700 - Programming and Data Structures

Course Data :

Last updated on Jan 2018

Course Objectives:

The objective of the course is to teach programming (with an emphasis on problem solving) and introduce elementary data structures. The student should, at a rudimentary level, be able to prove correctness (loop invariants, conditioning, etc) and analyze efficiency (using the `O' notation).

Learning Outcomes:

After the successful completion of the course the student will be able to :
  • Design correct programs to solve problems.
  • Choose efficient data structures and apply them to solve problems.
  • Analyze the efficiency of programs based on time complexity.
  • Prove the correctness of a program using loop invariants, pre-conditions and post-conditions in programs.

Course Contents:

  • Review of Problem Solving using computers, Abstraction, Elementary Data Types. Algorithm design- Correctness via Loop invariants as a way of arguing correctness of programs, preconditions, post conditions associated with a statement. (3 lectures)
  • Complexity and Efficiency via model of computation (notion of time and space), mathematical preliminaries, Elementary asymptotics (big-oh, big-omega, and theta notations). (3 lectures)
  • ADT Array -- searching and sorting on arrays:Linear search, binary search on a sorted array. Bubble sort, Insertion sort, Merge Sort and analysis; Emphasis on the comparison based sorting model. Counting sort, Radix sort, bucket sort. (6 lectures)
  • ADT Linked Lists, Stacks, Queues:List manipulation, insertion, deletion, searching a key, reversal of a list, use of recursion to reverse/search. Doubly linked lists and circular linked lists. (3 lectures)
  • Stacks and queues as dynamic data structures implemented using linked lists. Analyse the ADT operations when implemented using arrays. (3 lectures)
  • ADT Binary Trees:Tree representation, traversal, application of binary trees in Huffman coding. Introduction to expression trees: traversal vs post/pre/infix notation. Recursive traversal and other tree parameters (depth, height, number of nodes etc.) (4 lectures)
  • ADT Dictionary: Binary search trees, balanced binary search trees - AVL Trees. Hashing - collisions, open and closed hashing, properties of good hash functions. (3+3 lectures)
  • ADT Priority queues: Binary heaps with application to in-place sorting (5 lectures)
  • Graphs: Representations (Matrix and Adjacency List), basic traversal techniques: Depth First Search + Breadth First Search (Stacks and Queues) (5 lectures)
  • (Note : The ADTs will be taught using C++, introducing its syntax as required to explain the concepts (such as objects, classes, encapsulation, operator overloading, polymorphism and basic STL such as string and vector).


Text Books:

  • Data Structures and Algorithm Analysis in C++, by Mark Allen Weiss (Pearson 2007).


Reference Books:

  • Data structures and Algorithms in C++ -- by Adam Drozdek (1994 2001).
  • How to solve it by Computer -- by R G Dromey (PHI 1982, Paperback 2008).
  • Fundamentals of Data Structures in C -- by Horowitz, Sahni and Anderson-Freed (Silicon Press 2007).
  • Data Structure Using C and C++ -- by Y. Langsam, M. J. Augenstein and A. N. Tanenbaum (Pearson Education, 2nd Edition, 2015).

Pre-Requisites

Parameters

Credits Type Date of Introduction
3-1-0-0-6-10 Core Jul 2015

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits