Indian Institute of Information Technology, Allahabad

Design and Analysis of Algorithms

Jan-May 2022 Semester

Course Information

Course Description: In this course, students deepen their knowledge of the design and analysis of computer algorithms. Advanced topics in algorithms and algorithm analysis covered in the course include algorithmic thinking, complexity analysis, proof of correctness, devide and conquer, searching, sorting, greedy algorithms, string matching and indexing, graphs and graph algorithms, dynamic programming, and complexity classes.

Pre-requisite: Programming and Data Structures

Course Outline (Topics): The following list of topics is tentative. Based on available time slots, some topics may be dropped or added or reordered.

Part 1: Basic Concepts, Definition and Computation of time complexity in asymptotic notations, Heaps, Sorting, Searching, Selection, Hashing Greedy Algorithms - Definition, Designing, Analysis, Proof of Correctness;

Part 2: Dynamic Prograaming - Definiion, Designing, Analysis, Proof of Correctness; Divide and Conquer - Definition, Designing, Analysis; BackTracking Algorithms - Definition, Designing, Analysis;

Part 3: String Algorithms - KMP algorithm, Analysis, Proof of Correctness; Graph Algorithms - Depth First Search, Breadth First Search, Minimum Spanning Trees, Shortest Paths; Complexity Classes - P, NP, Defnitions, NP-hardness and Completeness, Reduction.

Course Instructor

Dr. Shiv Ram Dubey (Part 3)

TAs

  • BULLA RAJESH - RSI2018007
  • SAMBHAVI TIWARI - RSI2018503
  • Naman Goel - MIT2020007
  • ANUBHAB NANDY - MIT2020043
  • SAMIKSHA GUPTA - MIT2020105
  • SPANDAN ROY - MIT2021021
  • ASHUTOSH NAUTIYAL - MIT2021068
  • MONU KUMAR - MIT2021069
  • PRATIK BHANKHODIYA - MIT2021076
  • DHOTE ANURAG RADHESHAM - MIT2021082
  • NEHA - MIT2021083
  • RAJESH KUMAR SAH - MIT2021086
  • NAGMA NAAZ - MIT2021087
  • SAHIL DUBEY - MIT2021088
  • YASH PATEL - MIT2021090
  • VINAY KUMAR - MIT2021091
  • ISHAN SHRIVASTAVA - MIT2021092
  • SHASHANK PAL - MIT2021093
  • ABHINANDAN KUMAR PUN - MIT2021094
  • SANDIPAN DEY - MIT2021095
  • TRINETRA DEVKATTE - MIT2021096
  • RISHABH MAHENDRA SHIRKE - MIT2021098
  • MUTHYAMPALLI AKHIL - MIT2021099
  • AMBUJ KUMAR PANDIT - MIT2021100
  • GOURAB PAL - MIT2021102
  • HIMANSHU JOSHI - MIT2021103
  • SHARMA RAVIKANT PRAHLADRAI - MIT2021104

Class meets
Class: Monday 09.00 AM - 11.00 AM, Tute: Monday 03.00 PM - 05.00 PM, Lab: Friday 05.00 PM - 07.00 PM
Course Ethics
  • Students are strictly advised to avoid the unethical practices in the course including review tests and practice components.
  • It is best to try to solve problems on your own, since problem solving is an important component of the course.
  • You are allowed to discuss class material, problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions you must work/implement by yourself.
  • You are not allowed to take the codes from any source, including online, books, your classmate, etc. in the assignments and exams.
  • You may use free and publicly available sources (at idea level only), such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose marks for using external sources.)
  • You may not use any paid service and you must clearly and explicitly cite all outside sources and materials that you made use of.
  • Students are not allowed to post the code/report/any other material of course project in public domain or share with any one else without written permission from course instructors.
  • We consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the Institute's policies on academic dishonesty.
  • Instances will be dealt with harshly and typically result in a failing course grade.
  • Cheating cases will attract severe penalties.

Schedule

Date Topic Class Material Recorded Lecture
L01: March 21, 2022 String Matching Algorithms, FSM, KMP, Trie based Algorithms Slide (String+Trie) Recorded Video
L02: March 28, 2022 Graphs, DFS and BFS Slide (Graph, DFS, BFS) Recorded Video
L03: March 28, 2022 Minimum Spanning Tree Slide (MST) Recorded Video
L04: April 04, 2022 Shortest Paths Slide (Dijkstra), Slide (Bellman Ford) Recorded Video
L05: April 11, 2022 All-Pairs Shortest Path Slide (DP+FloydWarshall) Recorded Video
L06: April 11, 2022 Computational Complexity - P, NP, NP-Complete, NP-Hard, Reductions Slide (Computational Complexity) Recorded Video

Grading

  • C1 (30%)
  • C2 (30%)
  • C3 (40%)

Prerequisites

  • Computer Programming
  • Data Structures
  • Problem Solving
  • Ability to deal with abstract mathematical concepts

Books/References

  • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Third Edition, The MIT Press
  • Algorithms Design by Jon Kleinberg and Eva Tardos, Pearson
  • The Design and Analysis of Algorithms by A V Aho, J E Hopcroft, and J D Ullman, Pearson
  • Data Structures and Algorithm Analysis in C (DSAC) by Mark Allen Weiss, Second Edition
  • Data structures and Network Algorithms by Robert Endre Tarjan, Society for Industrial and Applied Mathematics Philadelphia, PA, USA, 1983, ISBN:0-89871-187-8
  • Knapsack Problems - Algorithms and Computer Implementations by Silvano Martello and Paolo Toth, John Wiley & Sons, West Sussex, UK, 1990, ISBN: 0471924202

Disclaimer

The content (text, image, and graphics) used in this slide are adopted from many sources for Academic purposes. Broadly, the sources have been given due credit appropriately. However, there is a chance of missing out some original primary sources. The authors of this material do not claim any copyright of such material.