The objective of the course is to teach programming (with an emphasis on problem solving) and introduce elementary data structures.

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

Important Links

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

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.

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