CS21003 Algorithms – I
 CS29003 Algorithms Laboratory
Spring 2019

Schedule | Notices | Syllabus | References | Tests | Lab assignments | Previous Semesters: Theory, Lab

Schedule

Instuctor     Abhijit Das 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 (02:00–05:00)]
Venue     Theory: Room No NC233 and NC331 (Sectioning)
Lab: PC LAB II and V, CIC
Teaching Assistants     Akshay Patil, Anirban Chakraborty, Ashwin Sudhakar Bhoyar, Bhanupriya Pegu, Bijoy Das, Gagan Sharma, Prajnamaya Dass, Pritam Pallab, Ronit Nath, Sayandeep Sanyal, Souvik Sur

Notices and Announcements

January 05, 2019

Sectioning done as per institute policy. Look at the links below.
Student-wise allocation | Room-wise allocation

January 03, 2019, 08:25pm

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

The theory course will run in two classrooms with half the registered population in each classroom. One classroom is NC233. The other will be announced after it is arranged centrally. The lab will run in two side-by-side CIC labs (PC LAB II and V). The split of the students will later be announced in this web page.

January 02, 2019

All initerested students are requested to apply before tomorrow 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 do not respond to individual e-mails about the application and the application-approval processes.

December 15, 2018

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 is 100 and of the lab is 125. 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 04-Jan-2019, I consider only those ERP requests that are recorded by 03-Jan-2019 08:00pm. I will do the shortlisting (if needed) immediately after that. All approvals by me 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, B-trees, skip lists, 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]     Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.
[3]     Jon Kleinberg and √Čva Tardos, Algorithm Design, Pearson, 2005.
[4]     Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
[5]     Udi Manber, Algorithms – A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[6]     Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins, 1997.
[7]     Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
[8]     Muhammad H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific, 1999.
[9]     Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1995.
[10]     Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, third edition, Addison-Wesley, 2000.
[11]     Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.

Tests

Programming Assignments

No Topic Start date Due date More info
A0 Brush up your PDS skills 08-Jan-201908-Jan-2018 Solution
A1 Polynomial vs logarithmic running times 15-Jan-201915-Jan-2018 Blackbox: gcc, g++ | Solution
A2 Divide-and-conquer algorithms 22-Jan-201922-Jan-2018

Submission site | TA Allocation | Miscellaneous information


Schedule | Notices | Syllabus | References | Tests | Lab assignments | Previous Semesters: Theory, Lab