Department of Computer Science & Engineering

Syllabus

Problem Solving using Computers: Abstraction - Abstract data types; Data Representation; Elementary data types; Basic concepts of data Structures; Mathematical preliminaries - big-Oh notation; efficiency of algorithms; notion of time and space complexity; performance measures for data structures.
ADT array - Computations on arrays - sorting and searching algorithms.
ADT Stack, Queue, list - array, linked list, cursor based implementations of linear structures. ADT Tree - tree representation, traversal of trees; ADT Binary tree - binary trees, threaded binary trees, application of binary trees - Huffmann coding; application of threaded binary trees - differentiation;
Search Tree - Binary search tree; balanced binary search trees - AVL tree; Applications of Search Trees - TRIE; 2-3 tree, 2-3-4 tree; concept of B-Tree. ADT Dictionary - array based and tree based implementations; hashing - definition and application - LZW encoding. ADT Priority Queue - Heaps; heap-based implementations; applications of heaps - sorting; Graphs - shortest path, minimum spanning tree, DFS, BFS - an application of DFS and BFS. Algorithm Design Paradigms - greedy, divide and conquer, dynamic programming, backtracking.