3EC2A DATA STRUCTURES & ALGORITHMS (Common to EC & EIC)
  Units    Contents of the subjects
I
DEFINITION & CHARACTERISTICS OF ALGORITHMS – Structures, Difficulties in estimating exact execution time of algorithms, Concept of complexity of program, Asymptotic notations: Big-Oh, theta, Omega- Definitions and examples, Determination of time and space complexity of simple algorithms without recursion, Representing a function in asymptotic notations viz 5n2-6n=(n2) ARRAYS: Array as storage element, Row major & column major form of arrays,
computation of address of elements of n dimensional array
II
ARRAYS AS STORAGE ELEMENTS for representing polynomial of one or more degrees for addition & multiplication, Sparse matrices for transposing & multiplication, stack, queue, Dequeue, Circular queue for insertion and deletion with condition for over and underflow, Transposition of sparse matrices with algorithms of varying complexity (Includes algorithms for operations as mentioned) EVALUATION OF EXPRESSION - Concept of precedence and associativity in expressions, Difficulties in dealing with infix expressions, Resolving precedence of operators and association of operands, Postfix & prefix expressions, conversion of expression from one form to other form using stack (with & without parenthesis), Evaluation of expression in infix, postfix & prefix forms using stack. Recursion
III
LINEAR LINKED LISTS - Singly, doubly and circularly connected linear linked lists- insertion, Deletion at/ from beginning and any point in ordered or unordered lists, Comparison of arrays and linked lists as data structures Linked implementation of stack, queue and dequeue, Algorithms for of insertion, deletion and traversal of stack, Queue, Dequeue implemented using linked structures. Polynomial representation using linked lists for addition, Concepts of Head Node in linked lists SEARCHING - Sequential and binary search
IV
NON-LINEAR STRUCTURES - Trees definition, Characteristics concept of child, Sibling, Parent child relationship etc, Binary tree: different types of binary trees based on distribution of nodes, Binary tree (threaded and unthreaded) as data structure, insertion, Deletion and traversal of binary trees, constructing binary tree from traversal results. Threaded binary Tree. Time complexity of insertion, deletion and traversal in threaded and ordinary binary trees. AVL tree: Concept of balanced trees, balance factor in AVL trees, insertion into and deletion from AVL tree, balancing AVL tree after insertion and deletion. Application of trees for representation of sets.
V

GRAPHS - Definition, Relation between tree & graph, directed and undirected graph, representation of graphs using adjacency matrix and list. Depth first and breadth first traversal of graphs, Finding connected components and spanning tree. Single source single destination shortest path algorithms.

SORTING - Insertion, quick, Heap, Topological and bubble sorting algorithms for different characteristics of input data. Comparison of sorting algorithms in term of time complexity,
NOTE:
1. Algorithm for any operation mentioned with a data structure or required to
implement the particular data structure is included in the curriculum.

 

Text/References:
1. Malik – Data structures using C++, Cengage Learning
2. Drozdek – Data structures and algorithms in C++ , Cengage learning
3. An introduction to data structures with applications By Jean-Paul Tremblay, P. G. Sorenson, TMH
4. Data Structures in C/C++, Horowitz, Sawhney, Galgotia
5. Gilberg & Forouzan – Data structures: A pseudocode approach with c, Cengage learning
6. Data Structures in C/C++, Tanenbaum, Pearson
7. Data Structures in C++, Weiss, Parson