3EC2A Data Structures & Algorithms
Unit 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
Unit 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
Unit 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
Unit 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.
Unit 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.
0 comments:
Post a Comment