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).
- 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.
- Data Structures and Algorithm Analysis in C, by Mark Allen Weiss, Addison-Wesley, (1997).
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).