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.

## 12 September 2009

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment