Algorithm Design and Analysis

Algorithm Design and Analysis (CSC14102) (3-1-0)

[Jointly with Prof Prasanta K Jana]

IV BTech (CSE) & IV Dual Degree (CSE)

(Venue: NLHC Gallery 9)

Attention: Students having attendance below 75% will not be allowed to appear in End Semester Exam.

Class Timing:

Thursday: 10:00 - 10:50 AM

Friday: 09:00 - 09:50 AM

Marks Distribution:

Mid Sem Exam

15

End Sem Exam

30

Class Test & Assignment

5

Exam Schedule:

Mid Sem Exam

21 Feb 2019

Time: 8:30-10:30 AM

Venue: NLHC G 01-04 (BTech)

NLHC G 05 (Dual)

End Sem Exam

18 Apr 2019

Time: 9:00-12:00 PM

Venue: NLHC G 01-04 (BTech)

NLHC G 05 (Dual)

Class Test-I

15 Feb 2019

Time: 8:45-09:50 AM

Venue: NLHC Gallery 09

TA Assigned:

PhD Students: Anuja Dixit | Deepak Kumar Rakesh |

MTech Studnets: Shubhi Shukla | Parul Verma | Prateek Gedam |

Course Content:

Introduction: Notions of Algorithms, Algorithm Paradigms, Complexity Analysis, Asymptotic Notations, Practical Complexities.

Divide and Conquer Paradigm: Recurrence Relations.

<Mid Semester Examination>

Divide and Conquer Paradigm: Finding Maximum and Minimum, Kth Smallest Selection, Strassen's Matrix Multiplication.

Greedy Algorithms: Knapsack Problem, Tree Vertex Splitting, Job Sequencing with Deadlines, Activity Selection Problem, Minimum Cost Spanning Tree, Optimal Storage on Tapes.

Text and Reference Books:

    1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to Algorithms”, Prentice Hall of India.

  1. E. Horowitz, S. Sahni, and S. Rajasekaran, “Fundamentals of Computer Algorithms”, Universities Press.

  2. J. Kleinberg and E. Tardos, “Algorithm Design”, Pearson Education.

  3. M. T. Goodrich and R. Tamassia, “Algorithm Design”, Wiley Student Edition.

  4. S. Dasgupta, C. Papadimitriou, and U. Vazirani, “Algorithms”, McGraw Hill Education (India) Pvt. Ltd.

  5. Aho, Hopcraft, and Ullman, “The Design and Analysis of Computer Algorithms”, Addison Wesley.

Tutorials & Assignment:

  1. Tutorial I: Asymptotic Notations

  2. Tutorial II: Time Complexity Analysis

  3. Assignment | Submission Deadline 03.04.2019

  4. Tutorial III: Asymptotic Notations & Greedy Method

  5. Tutorial IV: Greedy Method, Recursion & Asymptotic Notations

Examination Questions & Answers:

  1. Class Test | Question Set | Answer Set

  2. Mid Semester Examination | Question Set | Answer Set

  3. End Semester Examination | Question Set | Answer Set

Course Reference Materials:

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to Algorithms”, Prentice Hall of India.