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

#### Parameters

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