DSA -Theory

Rajasthan Technical University, Kota
Detailed Syllabus for B.Tech. (Computer Engineering)
Session 2009-10 (Main Examination)
3CS3 DATA STRUCTURES & ALGORITHMS (Common to Comp. Engg. & Info. Tech)
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 listsinsertion,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 of stack, queue, dequeue implemented using linked structures.Polynomial representation using linked lists for addition, Concepts of HeadNode 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.