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