Department of Computer Science and Engineering

B.Tech. II (CO) Semester - 3

L

T

P

C

CO203 : DATA STRUCTURES AND ALGORITHMS (CS-2)

3

1

2

5
COURSE OBJECTIVES
  • To teach fundamental data structures like arrays, stacks, lists.
  • To teach complex data structures like trees.
  • To make students understand various searching, sorting techniques and their need and differences.
  • To teach analysis of basic algorithms.
    		•
    COURSE OUTCOMES
    After successful completion of this course, student will be able to
    • Recognize the need of various Data Structures.
    • Analyze various structures and their applicability.
    • Design and Implement various techniques for searching, sorting and recurrence.
    • Identify the appropriate data structure and algorithm design method for the given application.
    COURSE CONTENT
    INTRODUCTION TO DATA STRUCTURE

    (04 Hours)

    Basic Terminology, Internal representation of Primitive Data structure: Integers, Floating point numbers, Packed decimal, Characters and data object and Pointers etc

    BASIC DATA TYPES

    Arrays: Definition, Memory organization, Operations on Arrays: Traversing, Insertion, Deletion

    (03 Hours)

    Updating, Resizing., Stacks: Basic operations, Stack, Dstack and applications

    (02 Hours)

    Queues : Operations of queues, Circular Queue, Priority Queue, Dequeue, Application of queues

    (03 Hours)

    Simulation of time sharing operating systems, Continuous network monitoring system etc.

    (02 Hours)

    Linked list : Singly linked lists and memory representation, Operations of Link list(Traversing, Searching, Insertion, Deletion, inversion, concatenation, copying and comparison, allocation and deallocation), Doubly linked list and operations, Circular Link list, Multilevel link list

    (04 Hours)
    TREES AND GRAPH

    Trees: Introduction, Binary Trees and their representation, Operations on Binary trees: Creation, transformation of trees into binary trees, traversal, Searching, Insertion and Deletion. Type of trees: Complete Binary trees, Extended binary trees, General trees, AVL trees, Threaded trees, B trees Application: Arithmetic expression evaluation, infix-prefix-postfix notation conversion.

    (08 Hours)

    Graph: Formal Introduction, types of graph, Representation of graphs: Sequential, List structure, Adjacency list, multilinked representation, Search in directed and undirected graphs, BFS, DFS, Transversal Connected Component and Spanning trees, Shortest path and Transitive Closure, Activity Networks, Topological Sort and Critical Paths.

    (08 Hours)
    ILLUSTRATED ALGORITHMS

    (08 Hours)

    Sorting (Bubble, Selection, Quick, Radix, Bucket sort, Heap sort), Dictionaries, hashing, analysis of collision resolution techniques, Searching(Linear Search, Binary Search), Character String and different string operations
    Tutorials will be based on the coverage of the above topics separately

    (14 Hours)
    (Total Contact Time: 42 Hours + 14 Hours = 56 Hours)
    PRACTICALS
    1. Implementation of Array and Application.
    2. Implementation of Link List and Application.
    3. Implementation of Trees and Application.
    4. Implementation of Graph and Application.
    5. Mini Project (Implementation using above Data Structure)
    BOOKS RECOMMENDED
    1. Trembley & Sorenson: "An Introduction to Data Structures with Applications", 2/E, TMH, 1991
    2. Tanenbaum & Augenstein: "Data Structures using C and C++", 2/E, PHI, 2007
    3. Horowitz and Sahani: "Fundamentals of Data Structures", Galgotia Publications, reprint 2004.
    4. T. H. Cormen, C. E. Leiserson, R. L. Rivest: "Introduction to Algorithms",2/E, PHI, 2001
    5. Robert L.Kruse, C.L.Tondo and Brence Leung: "Data Structures and Program Design in C", Pearson Education, 2/E, 2001.