CS21003 : Algorithms-I Spring 2020 L-T-P: 3-1-0
Schedule | Notices | Syllabus | References | Online-Sessions | Tutorials | Tests | Lab assignments | Previous Semesters: Theory, Lab

Schedule

Instuctors     Partha Pratim Chakrabarti   and   Aritra Hazra
Timing     Theory: Slot D4 [MON (12:00–12:55), TUE (10:00–11.55), THU (08:00–08:55)]
Lab: Slot L [TUE (14:00–17:00)]
Venue     Theory: Room No. NR321 (Nalanda Complex)
Lab: PC-Lab II + V, CIC (Takshashila Complex)
Teaching Assistants     Theory: Ayan Chandra,  Sudipta Paria.
Lab: Aishwariya Chakraborty,  Aniruddha Roy,  Md. Rasid Ali,  Prajnamaya Dass,  Pritam Pallab,  Rahul Roy,  Rishabh Waman Shahare,  Shivangi Sharma,  Shramona Chakraborty,  Telang Onkar Ajay.

Notices and Announcements

!! DUE TO CLASS SUSPENSION CONSIDERING THE PANDEMIC SITUATION, WE HAVE TO FINISH THE REMAINING PART OF THIS COURSE THROUGH ONLINE MODE ... !!

June 08, 2020      NEW !!

Considering the continuation of pandemic situation, End-Semester and other pending examinations are CANCELLED. Hence, the marking and gradation will be done solely based on all the earlier conducted examinations (Class-Test, Mid-Semester and Online-Test).

March 31, 2020     

We shall conduct an Online Quiz/Test on 08-Wed-2020 (Wednesday). The details will be announced to the students soon (preferably via email).

March 17, 2020     

We shall be arranging next few Class-Sessions online! Recorded videos (topic-wise) will be uploaded periodically. Please Scroll-Down for accessing these Online-Sessions. Students are requested to periodically go through these-sessions.

We shall also put up the Tutorial-Problems online in due time! Please Scroll-Down for accessing these Tutorials. Students are requested to solve these problems by their own.

In case of doubts within lecture sessions and tutorial problems, the students are requested to keep noting down their doubts, if any. We shall arrange doubt-clearing sessions soon, preferably live when we resume our normal classroom-teaching or in some other mode (we'll let you know).

March 14, 2020     

Schedule (earlier announced to be held on 30-Mar-2020) for Class Test – 2 has been postponed and will be announced later.

January 24, 2020

Schedule for Class Test – 1 is announced (to be held on 03-Feb-2020).

January 04, 2020, 08:00pm

CGPA-based screening is made on all the requests available until now. WE WILL PROCESS NO NEW REQUESTS.

We have considered as many student-requests as we can based on the maximum seating capacity available in class and lab (both). Due to capacity constraints, we are UNABLE to consider any further requests!

January 03, 2020

All interested students are requested to apply before tomorrow (04-Jan-2020) 8:00pm. We will not entertain applications that are recorded after that (even in the case that ERP extends its deadline for course registration). We may not respond to individual e-mails about the application and the application-approval processes.

December 26, 2019

Theory classes will commence from 02-Jan-2020 (Thursday). The theory course will run in one classroom (NR321). Though your choice of this course may not be approved by that time (as informed below), but this will be an introductory class.

Lab sessions will commence from 07-Jan-2020 (Tuesday). The lab will run in two side-by-side CIC labs (PC-Lab II and V).

December 11, 2019

Interested students are requested to apply via the ERP portal. Please keep in mind the following requirements.

  • The timings for both theory and laboratory as mentioned above are to be treated as frozen and final. These timings are chosen so as to reduce clashes with other courses. However, it is impossible to find any slot that is free for everybody. So any further change may solve a few cases but will introduce new cases of clash.

  • An applicant must not have any clash with these timings. If so, the students are supposed to make attempts to shift the other courses/labs clashing with these. Many of the lab assignments are to be submitted during the lab hours only. The submission server does not support extended deadlines on a case-by-case basis.

  • The maximum capacity of the theory as well as the lab is 125 (each). If the applicant counts are much more than these, shortlisting will be made based only on CGPA (and on no other criteria). In order that the applicants who are not shortlisted can register for other courses, and keeping in view that the last date for course registration is 05-Jan-2020, We consider only those ERP requests that are recorded by 04-Jan-2020 08:00pm. We shall do the shortlisting (if needed) immediately after that. All approvals by us in ERP will wait until that time.

  • Neither the course nor the lab has any prerequisites (under the assumption that all applicants have cleared PDS theory and lab). Since the theory course and the lab are complementary to one another, it does not make enough sense to register for only one (unless somebody has done the other earlier or plans to do it later).

Tentative Coverage

Complexity of Algorithms Asymptotic notations and their significance, complexity analysis of algorithms, worst case and average case. 2 hours
Algorithm Design Paradigms Recursion, divide-and-conquer, greedy, dynamic programming, lower bounds and optimal algorithms. 8 hours
Basic Data Structures Stacks and queues, graphs and trees, binary trees. 2 hours
Heaps Heaps, priority queues, min-max heaps, heap sort. 4 hours
Dynamic Search Structures Binary search trees, height balancing and AVL trees, B-trees, hashing. 8 hours
Algorithms on Arrays Linear-time median finding, sorting in linear time (counting sort, radix sort, bucket sort), string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms). 8 hours
Graph Algorithms Traversal (BFS, DFS, topological sort), minimum spanning trees (Prim and Kruskal algorithms), shortest paths (Dijkstra and Floyd-Warshal algorithms) 8 hours

Books and References

[1]     Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press/McGraw-Hill, 2001.
[2]     Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
[3]     Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
[4]     Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.
[5]     Udi Manber, Algorithms – A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[6]     Jeff Erickson, Algorithms, Prepublication Draft, 2018.
[7]     Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms, Universities Press, 2008.
[8]     M. H. Alsuwaiyel, Algorithms – Design Techniques and Analysis, World Scientific Publishing Co., 1999.
[9]     Mark Allen Weiss, Data Structures and Algorithm Analysis in C, Pearson Education, 1997.
[10]     Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
[11]     Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins, 1997.
[12]     Muhammad H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific, 1999.
[13]     Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1995.
[14]     Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, third edition, Addison-Wesley, 2000.
[15]     Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.

Online-Sessions     

Course-Lectures (in-class) From 02-Jan-2020 to 13-Mar-2020:    Scribe-0

Course-Lectures (via-online) From 14-Mar-2020 to 31-Mar-2020:

Upload-Date Topic Instructor Online-Link Materials
17-Mar-2020 Introduction to Graphs: Definitions, Representations and Examples Prof. P. P. Chakrabarti Video-Link-1  Slide-1 | Scribe-1 
18-Mar-2020 Traversal of Undirected Graphs: Depth-First Search (DFS) and Breadth-First Search (BFS) Prof. P. P. Chakrabarti Video-Link-2  Slide-2 | Scribe-2 
19-Mar-2020 Traversal of Directed Graphs: DFS, BFS, Entry-Exit Node-Numbering, Topological Ordering Prof. P. P. Chakrabarti Video-Link-3  Slide-3 | Scribe-3 
23-Mar-2020 Graph Algorithms: Minimum Spanning Trees – Prim's and Kruskal's Algorithm, Complexity and Correctness Prof. P. P. Chakrabarti Video-Link-4  Slide-4 | Scribe-4 
27-Mar-2020 Graph Algorithms: Shortest Path in Graphs – Dijkstra's Algorithm, Complexity & Correctness and some Variants Prof. P. P. Chakrabarti Video-Link-5  Slide-5 | Scribe-5 
30-Mar-2020 Graph Algorithms: All-pairs Shortest Paths in Graphs – Floyd-Warshall Algorithm, Bellman-Ford Algorithm and their Analysis Prof. P. P. Chakrabarti Video-Link-6  Slide-6 | Scribe-6 
02-Apr-2020 Disjoint-Set Data Structures and Operations Dr. A. Hazra Video-Link-7  Slide-7 | Scribe-7 
03-Apr-2020 String Matching Algorithms: Naive Approach, Knuth-Morris-Pratt (KMP) Algorithm and Rabin-Karp Algorithm Dr. A. Hazra Video-Link-8  Slide-8 | Scribe-8 
05-Apr-2020 Graph Algorithms: Doubt-Clearing Session (Online-Lectures: I – VI) Prof. P. P. Chakrabarti Video-Link  Slide | Scribe 

Tutorials

No Topic Date
Tutorial-1 Algorithmic Time Complexity and Recurrences 13-Jan-2020
Tutorial-2 Divide-and-Conquer Algorithms 30-Jan-2020
Tutorial-3 Greedy Algorithms 06-Feb-2020
Tutorial-4 Dynamic Programming 13-Feb-2020
Tutorial-5 Binary Trees, BSTs, Height-balanced / AVL Trees 05-Mar-2020
Tutorial-6 Heaps and Hashing 19-Mar-2020
Tutorial-7 Graph Traversals 26-Mar-2020
Tutorial-8 Graph Algorithms 31-Mar-2020
Tutorial-9 Disjoint-Set Data-Structure and String Matching Algorithms 06-Apr-2020

Tests

Programming Assignments    [ CS29003 : Algorithms Laboratory | Spring 2020 ]

Schedule | Notices | Syllabus | References | Online-Sessions | Tutorials | Tests | Lab assignments | Previous Semesters: Theory, Lab
 CS21003 : Algorithms-I Spring 2020 L-T-P: 3-1-0