Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    ADS Syallabus

    Uploaded by

    viksonio

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    ADS Syallabus

    Uploaded by

    viksonio
    4 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    4 views2 pages

    ADS Syallabus

    Uploaded by

    viksonio

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 2

    L T P C

    II Year I Semester 3 0 0 3

    ADVANCED DATA STRUCTURES & ALGORITHM ANALYSIS


    Course Objectives:
    The main objectives of the course is to
    ● provide knowledge on advance data structures frequently used in Computer Science
    domain
    ● Develop skills in algorithm design techniques popularly used
    ● Understand the use of various data structures in the algorithm design

    COURSE OUTCOMES:
    Upon successful completion of the course, the student will be able to:
     Master the Fundamentals of Algorithm Analysis
     Become Adept at Designing and Implementing Data Structures
     Develop Skills in Applying Algorithmic Techniques
     Enhance Problem-Solving Abilities
     Grasp the Notion of NP-Completeness

    UNIT – I:
    Introduction to Algorithm Analysis, Space and Time Complexity analysis, Asymptotic
    Notations.
    AVL Trees – Creation, Insertion, Deletion operations and Applications
    B-Trees – Creation, Insertion, Deletion operations and Applications

    UNIT – II:
    Heap Trees (Priority Queues) – Min and Max Heaps, Operations and Applications
    Graphs – Terminology, Representations, Basic Search and Traversals, Connected
    Components and Biconnected Components, applications
    Divide and Conquer: The General Method, Quick Sort, Merge Sort, Strassen’s matrix
    multiplication, Convex Hull

    UNIT – III:
    Greedy Method: General Method, Job Sequencing with deadlines, Knapsack Problem,
    Minimum cost spanning trees, Single Source Shortest Paths
    Dynamic Programming: General Method, All pairs shortest paths, Single Source Shortest
    Paths – General Weights (Bellman Ford Algorithm), Optimal Binary Search Trees, 0/1
    Knapsack, String Editing, Travelling Salesperson problem

    UNIT – IV:
    Backtracking: General Method, 8-Queens Problem, Sum of Subsets problem, Graph
    Coloring, 0/1 Knapsack Problem
    Branch and Bound: The General Method, 0/1 Knapsack Problem, Travelling Salesperson
    problem

    UNIT – V:
    NP Hard and NP Complete Problems: Basic Concepts, Cook’s theorem
    NP Hard Graph Problems: Clique Decision Problem (CDP), Chromatic Number Decision
    Problem (CNDP), Traveling Salesperson Decision Problem (TSP)
    NP Hard Scheduling Problems: Scheduling Identical Processors, Job Shop Scheduling

    Textbooks:
    1. Fundamentals of Data Structures in C++, Horowitz, Ellis; Sahni, Sartaj; Mehta,
    Dinesh 2nd Edition Universities Press
    2. Computer Algorithms/C++ Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran
    2nd Edition University Press

    Reference Books:
    1. Data Structures and program design in C, Robert Kruse, Pearson Education Asia
    2. An introduction to Data Structures with applications, Trembley & Sorenson, McGraw
    Hill
    3. The Art of Computer Programming, Vol.1: Fundamental Algorithms, Donald E Knuth,
    Addison-Wesley, 1997.
    4. Data Structures using C & C++: Langsam, Augenstein & Tanenbaum, Pearson, 1995
    5. Algorithms + Data Structures & Programs:, N.Wirth, PHI
    6. Fundamentals of Data Structures in C++: Horowitz Sahni & Mehta, Galgottia Pub.
    7. Data structures in Java:, Thomas Standish, Pearson Education Asia

    Online Learning Resources:


    1. https://www.tutorialspoint.com/advanced_data_structures/index.asp
    2. http://peterindia.net/Algorithms.html
    3. Abdul Bari, 1. Introduction to Algorithms (youtube.com)

    You might also like