Scribd Logo
Upload

Welcome to Scribd!

  • 30 views

    Birla Institute of Technology and Science, Pilani: Pilani Campus AUGS/ AGSR Division

    Uploaded by

    Tussank Gupta
    This document provides details for the course "Design & Analysis of Algorithms" including: 1. The course description, scope, and objectives which are to learn basic and advanced algorithm design techniques like divide and conquer, greedy algorithms, etc. 2. The textbook and reference books for the course. 3. The course plan which lists the topics to be covered over 40 lectures. 4. The evaluation scheme including a mid-semester test, comprehensive exam, and tutorials with their weightages and dates. 5. Information on consultation hours, notices, make-up policy, and open book policy for the course.

    Copyright:

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

    Birla Institute of Technology and Science, Pilani: Pilani Campus AUGS/ AGSR Division

    Uploaded by

    Tussank Gupta
    30 views5 pages
    This document provides details for the course "Design & Analysis of Algorithms" including: 1. The course description, scope, and objectives which are to learn basic and advanced algorithm design techniques like divide and conquer, greedy algorithms, etc. 2. The textbook and reference books for the course. 3. The course plan which lists the topics to be covered over 40 lectures. 4. The evaluation scheme including a mid-semester test, comprehensive exam, and tutorials with their weightages and dates. 5. Information on consultation hours, notices, make-up policy, and open book policy for the course.

    Original Description:

    handout

    Original Title

    CS_F364

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides details for the course "Design & Analysis of Algorithms" including: 1. The course description, scope, and objectives which are to learn basic and advanced algorithm design techniques like divide and conquer, greedy algorithms, etc. 2. The textbook and reference books for the course. 3. The course plan which lists the topics to be covered over 40 lectures. 4. The evaluation scheme including a mid-semester test, comprehensive exam, and tutorials with their weightages and dates. 5. Information on consultation hours, notices, make-up policy, and open book policy for the course.

    Copyright:

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

    Birla Institute of Technology and Science, Pilani: Pilani Campus AUGS/ AGSR Division

    Uploaded by

    Tussank Gupta
    This document provides details for the course "Design & Analysis of Algorithms" including: 1. The course description, scope, and objectives which are to learn basic and advanced algorithm design techniques like divide and conquer, greedy algorithms, etc. 2. The textbook and reference books for the course. 3. The course plan which lists the topics to be covered over 40 lectures. 4. The evaluation scheme including a mid-semester test, comprehensive exam, and tutorials with their weightages and dates. 5. Information on consultation hours, notices, make-up policy, and open book policy for the course.

    Copyright:

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

    BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, Pilani

    Pilani Campus
    AUGS/ AGSR Division

    SECOND SEMESTER 2019-20


    COURSE HANDOUT
    Date: 06.01.2020

    In addition to part I (General Handout for all courses appended to the Time table) this portion gives further
    specific details regarding the course.
    Course No : CS F364

    Course Title : Design & Analysis of Algorithms


    Instructor-in-Charge : Abhishek Mishra
    Instructor(s) : Kamlesh Tiwari
    Tutorial/Practical Instructors: Ravi Kant
    1. Course Description: The course gives an introduction to some algorithm
    design techniques.

    2. Scope and Objective of the Course: To learn about some basic algorithm design
    techniques like Divide and Conquer, Greedy Algorithms, Dynamic
    Programming, and Network Flow Algorithms. To learn about Computational
    Complexity. To learn about some advanced algorithm design techniques
    like Approximation Algorithms, and Randomized Algorithms. To learn about
    Number Theoretic Algorithms.

    3. Text Book:
    [T1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to
    Algorithms, 3rd Edition, PHI, 2012.
    4. Reference Books:
    [R1] J.Kleinberg, E. Tardos, Algorithm Design, Pearson, 2013. Lecture
    slides of the book are available online at: http://www.cs.princeton.edu/
    ~wayne/kleinberg-tardos/pearson/

    [R2] D.P. Williamson, D.B. Shmoys, The Design of Approximation


    Algorithms, Cambridge University Press, 2010. Available online at:
    http://www.designofapproxalgs.com/book.pdf

    [R3] S. Arora, B. Barak, Computational Complexity: A Modern Approach,


    2009, Cambridge University Press. Available online at:
    http://theory.cs.princeton.edu/complexity/book.pdf

    [R4] E. Horowitz, S. Sahni, S. Rajasekaran, Fundamentals of Computer


    Algorithms, Second Edition, 2007, Universities Press.
    1
    BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, Pilani
    Pilani Campus
    AUGS/ AGSR Division

    5. Course Plan:

    Lectur Topics
    es
    1 Introduction, Asymptotic Notations, Analysis of Insertion
    sort and Merge Sort.
    2 The Defective Chessboard Problem. Karatsuba’s
    Multiplication Algorithm.
    3 Strassen’s Matrix Multiplication Algorithm.
    4 Polynomial Representations, Evaluating a Polynomial using
    Horners’ Rule, Interpolation using Gaussian Elimination.
    5 Discrete Fourier Transform. Fast Fourier Transform
    Algorithm.
    6 The Fractional Knapsack Problem.
    7 Huffman Encoding.
    8 Optimality of Huffman Encoding.
    9 Matroids.
    10 Application of Matroids.
    11 The 0/1 Knapsack Problem.
    12 The Traveling Salesman Problem.
    13 Matrix Chain Multiplication.
    14 Longest Common Subsequence.
    15 Optimal Binary Search Trees.
    16 Flow Shop Scheduling.
    17 The Maximum Flow Problem and the Ford-Fulkerson Algorithm.
    18 Maximum Flows and Minimum Cuts in a Network.
    19 The Bipartite Matching Problem.
    20 Disjoint Paths in Directed and Undirected Graphs.
    21 The Complexity Class P.
    22 The Complexity Class NP.

    2
    BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, Pilani
    Pilani Campus
    AUGS/ AGSR Division

    23 Polynomial Time Reductions. The Complexity Classes NP-


    Complete and NP-Hard. The Satisfiability Problem.
    24 Cook-Levin Theorem.
    25 NP-Completeness of 3SAT, 0/1 Integer Programming, and
    Independent Set.
    26 NP Optimization Problems. Definition of Approximation
    Algorithms. A 2-approximation Algorithm for the Cardinality
    Vertex Cover Problem. A 2-approximation Algorithm for the
    Weighted Vertex Cover Problem.
    27 LP-Rounding Algorithm for Set Cover. Primal LP, Dual LP,
    LP-Duality Theorem, Weak Duality Theorem, and Complementary
    Slackness Conditions.
    28 Dual-Rounding Algorithm for Set Cover. Primal-Dual
    Algorithm for Set Cover.
    29 PTAS and FPTAS. FPTAS for the 0/1 Knapsack Problem.
    30 Complexity Classes for Approximation.
    31 Probability, Random Variables, and Expectation. Linearity
    of Expectation.
    32 The Randomized Complexity Classes BPP, RP, co-RP, and ZPP.
    33 Markov’s Inequality, Chebyshev’s Inequality, and Chernoff’s
    Bounds.
    34 Atlantic City, Monte Carlo, and Las Vegas Algorithms.
    35 The Birthday Paradox.
    36 Divisibility.
    37 Euclid’s Extended GCD Algorithm.

    38 Congruences, Fermat’s Theorem, and Euler’s Theorem.

    39 Modular Exponentiation Algorithm.

    40 Pollard’s Rho Factorization Algorithm.

    6. Evaluation Scheme:
    Component Duration Weightage Date & Time Nature of component

    3
    BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, Pilani
    Pilani Campus
    AUGS/ AGSR Division

    (%) (Close Book/ Open Book)


    th
    Mid-Semester 90 Min. 28 5 March, 14:00 Open Book
    Test – 15:30

    Comprehensiv 3 H 40 11th May, 8:00 – Open Book


    e 11:00
    Examination
    Tutorials 40 Min. 32 Open Book. There
    will be twelve
    tutorials. In each
    tutorial, a
    randomly and
    independently
    selected problem
    will be given for
    solving. One out
    of tutorials 1 to
    3, one out of
    tutorials 4 to 6,
    one out of
    tutorials 7 to 9,
    and one out of
    tutorials 10 to 12
    will be evaluated
    (each having 8%
    weightage). Each
    student can decide
    which tutorials to
    evaluate.

    7. Chamber Consultation Hour:


    Abhishek Mishra: 15:00 to 16:00 on Fridays (6121S).
    Kamlesh Tiwari: 15:00 to 16:00 on Mondays / Fridays (6120N).

    8. Notices: All notices will be posted on Nalanda.


    9. Make-up Policy: Make-up exam may be arranged only in genuine cases with
    prior permission. No makeup for Tutorial test.

    4
    BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, Pilani
    Pilani Campus
    AUGS/ AGSR Division

    10. Note (if any): There is no makeup for tutorials. Students are not allowed
    to sit in different tutorial sections.
    11. Open Book Policy: Only hard copies are allowed (lecture notes, text
    book, or reference books). Abhishek Mishra

    Instructor-in-charge
    Course No. CS F364

    You might also like