Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Data Structures Syllabus

    Uploaded by

    shift2cs22
    The document outlines the syllabus for the M.Sc. degree program in computer science at the University of Madras. It covers 5 units on advanced algorithms topics like data structures, graph algorithms, greedy algorithms, dynamic programming, and NP-complete problems.

    Copyright:

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

    Data Structures Syllabus

    Uploaded by

    shift2cs22
    42 views2 pages
    The document outlines the syllabus for the M.Sc. degree program in computer science at the University of Madras. It covers 5 units on advanced algorithms topics like data structures, graph algorithms, greedy algorithms, dynamic programming, and NP-complete problems.

    Original Title

    data structures syllabus

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document outlines the syllabus for the M.Sc. degree program in computer science at the University of Madras. It covers 5 units on advanced algorithms topics like data structures, graph algorithms, greedy algorithms, dynamic programming, and NP-complete problems.

    Copyright:

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

    Data Structures Syllabus

    Uploaded by

    shift2cs22
    The document outlines the syllabus for the M.Sc. degree program in computer science at the University of Madras. It covers 5 units on advanced algorithms topics like data structures, graph algorithms, greedy algorithms, dynamic programming, and NP-complete problems.

    Copyright:

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

    UNIVERSITY OF MADRAS

    M.Sc. DEGREE PROGRAMME IN COMPUTER SCIENCE


    SYLLABUS WITH EFFECT FROM 2023-2024

    Title of the Paper Advanced Data Structures and Algorithms


    Core–I – Theory I Year & I Semester Credit:4 436C1A

    Objectives:
    Define the basic concepts of algorithms and analyze the performance of algorithms.
    Discuss various algorithm design techniques for developing algorithms.
    Discuss various searching, sorting and graph traversal algorithms.
    Understand NP completeness and identify different NP complete problems.
    Discuss various advanced topics on algorithms.
    Outcomes:
    1. Analyze programming problem statements.
    K1, K2
    2. Comprehend and select algorithm design approaches in a problem K2, K3
    specific manner.
    3. Choose appropriate data structures for a specific problem K3, K4
    4. Utilize necessary mathematical abstractions to solve problems K5, K6
    5. Come up with analysis of efficiency and proofs of correctness K6
    K1-Remember;K2-Understand;K3-Apply;K4-Analyze;K5-Evaluate; K6-Create

    UNIT I: Introduction: Algorithm, Pseudo code for expressing algorithms, Performance


    Analysis-Space complexity, Time complexity, Asymptotic Notation- Big oh notation, Omega
    notation, Theta notation and Little oh notation, Probabilistic analysis, Amortized analysis.

    UNIT II: Insertion and deletion and merging with 1) binary search tree, 2) AVL tree, 3) Red
    Black tree, 4) B tree, 5) B+ tree and Comparison of previous tree structures. Fibonacci Heap,
    Fibonacci Heap Operations: Find minimum, merge, insert, extract minimum, decrease key and
    delete, Complexity analysis of the above data structure operations.

    UNIT III: Representations of Graphs, Minimum Spanning Trees: Growing a Minimum


    Spanning Tree – Kruskal and Prim- Single-Source Shortest Paths: The Bellman-Ford algorithm –
    Single-Source Shortest paths in Directed Acyclic Graphs – Dijkstra ‘s Algorithm, Divide and
    conquer: General method, applications - Quick sort, Merge sort, Strassen’s matrix multiplication,
    External Sort: External merge sort, K-Way Merge sorting

    UNIT IV: Greedy method: General method, applications-Job sequencing with deadlines, 0/1,
    knapsack problem, Huffman Codes, Dynamic Programming: General method, applications-
    Matrix chain multiplication, 0/1 knapsack problem, Traveling salesperson problem, Reliability
    design.

    Print to PDF with PDF Writer for Windows 8. This is a free evaluation copy. Buy full version now.
    UNIVERSITY OF MADRAS
    M.Sc. DEGREE PROGRAMME IN COMPUTER SCIENCE
    SYLLABUS WITH EFFECT FROM 2023-2024

    UNIT V: Backtracking: General method, applications-n-queen problem, sum of subsets


    problem, graph coloring, Hamiltonian cycles. Branch and Bound: General method,applications -
    Traveling salesperson problem, 0/1 knapsack problem- LC Branch and Bound solution, FIFO
    Branch and Bound solution. NP-Hard and NP-Complete problems

    Recommended Texts:
    1. Peter Brass; Advanced Data Structures; CAMBRIDGE UNIVERSITY PRESS;2008
    2. S. Dasgupta, C. Papadimitrou, U Vazirani; Algorithms; Mc Graw Hill;2022
    3. J. Klienberg and E. Tardos, Algorithm Design, Pearson
    EducationLimited;2013.
    4. Ellis Horowitz, Sartaj Sahni, Rajasekharan, Fundamentals of Algorithms, 2nd
    Edition, Universities Press, 2009.
    Reference Books:
    1. Sartaj Sahni, Data Structures Algorithms and Applications in C++, 2nd Edition,
    Universities Press, 2007.
    2. Aho V Alfred, Hapcroft E John, Ullman D Jeffry, Data Structures and Algorithms,
    Pearson Education, 2001.
    4. Adam Drozdek, Thomson, Data Structures and Algorithms in JAVA, 3rd Edition,
    Cengage Learning, 2008.
    5. Horowitz, Sahni, Mehta, Fundamentals of Data Structures in C++, 2nd Edition,
    Universities Press, 2007.
    Web References:
    1. https://nptel.ac.in/courses/106102064

    Mapping with Programme Outcomes:

    PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO 10

    CO 1 S M M S M S S S L M

    CO 2 S L S M S L M M S S

    CO 3 M S L M M S L S L S

    CO 4 L S S L S M S L S M

    CO 5 S M M S L S M S S S

    S-Strong M-Medium L-Low

    Print to PDF with PDF Writer for Windows 8. This is a free evaluation copy. Buy full version now.

    You might also like