CS2700 - Programming and Data Structures

Course Data :

Learning Outcomes:

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

Topics:

  • 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)
  • The laboratory component will require the student to write computer programs using a careful choice of data structures (in C language) from scratch, based on the concepts learnt in the theory course.

Textbooks:

  • Data Structures and Algorithm Analysis in C, by Mark Allen Weiss, Addison-Wesley, (1997).

References:

  • Data structures and Algorithms in C, by Adam Drozdek (1994).
  • 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).

  • 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