Course Webpage

Design and analysis of algorithms (DAA)

Course Instructor: Dr. Shreya Ghosh, Assistant Professor, IIT Bhubaneswar

Special thanks to all our dedicated TAs for their contributions and commitment!!!

Ritwik Raghav, Kanishka Maity, Rajnish Maurya, Abhinandan Patra, Choure Anuj Manojkumar, Agamya Yadav

Theory: Tuesday - 15:30-17:30 - SES 318 | Wednesday - 16:30-18:30 - LC11-120-1

Lab: Tuesday - 10:00-12:55 - SES-A209

End-Sem: Highest 72/80 [Great performance, Ravilisetty Makarandh!]

Also good job: Soham Jain, Gudala Geeta Ramcharan and Snehal Kumar.

Mid-Sem: Highest 48/50 [Outstanding performance, Sangam Kumar Mishra!]

Also great job: Ravilisetty Makarandh, Soham Jain, Gudala Geeta Ramcharan, Debargha Nath, Appala Sai Sumanth, Saurav Kumar Singh

Lab Assignment Submission: Guideline Sample PDF

Sample Code: ODD (Q1) [Excellent work Ayush Agarwal!] Also, great job Snehal Kumar!

Sample Code: Even (Q1) [Excellent work, Sanjay Kumar Pandit!] Also, great job Meysakthivelan T!

Sample Code: Even (Q2) [Excellent work, Debargha Nath!]

** There are few other great code+document submitted, I will update the names by the semester end!

Introduction about course structure & Recursive Formulation: Slide

Recursive function and Coin selection problem: Slide

Master Theorem and Merge Sort (Explanation): Slide

More Divide and Conquer Algorithms (Quick Sort, Matrix Multiplication, Closest Pair of Points): Slide

----------------------------------------------------------------------------------------------------------------------

Graph algorithms: Slide

Graph Traversal and Single Source Shortest Path: Slide

More Greedy Algorithms and introduction to DP: Slide

Hashing and NPC problems: Slide

NPC definition and discussions: Slide

Reduction Slide

Reduction (more example) and Flow Network: Slide Slide

Reading List

Textbooks
1. Introduction to Algorithms (3rd Ed), Cormen, Leiserson, Rivest, & Stein
2. Algorithms, Dasgupta, Papadimitriou, & Vazirani
3. Algorithm Design, Kleinberg & Tardos
Few amazing notes
1. Correctness of Sorting, Merge-Sort Detailed discussion: https://stanford-cs161.github.io/winter2023/assets/files/lecture2-notes.pdf
2. A nice and concise description of proving a bound by induction, https://drive.google.com/file/d/1sLQCQGCCC_Pgm7WA-GgfWGW2pwbPg6b9/view?usp=sharing

Few tips

I strongly suggest reading textbooks along with the slides & board work
Try to solve as many as problems you can - it will help you to think and figure out efficient algorithms
There are many online resources where you can copy solutions for lab assignments and DIY problems. Instead, use those resources to solidify your foundation . Try https://leetcode.com/problemset/algorithms/ .
The final score will be normalized for grading. So, if a problem is too hard, don't search online just to get the score; rather, use it as an opportunity to brush up your skills.
Wherever you go (SWE job, research, higher studies..), designing algorithms and providing efficient solution WILL always be a PLUS.

Questions?

Contact shreya@iitbbs.ac.in if you have a specific query related to the course

I will post my office hours here and you can make an appointment if you want to discuss

**Material taken from Online resources (Stanford CS161, CMU, and other popular DSA courses.)

Page updated

Google Sites

Report abuse