CS21003 Algorithms I
 CS29003 Algorithms Laboratory
Autumn 2012, L-T-P: 3-1-0 
L-T-P: 0-0-3 

Schedule | Notices | Syllabus | References | Tests | Assignments | Autumn 11

Schedule

Instuctor     Abhijit Das
        Partha Bhowmick (coinstructor in lab)
Timing     Theory: Slot B [MON(10:30--11:30), TUE(07:30--09:30), THU(11:30--12:30)]
Lab: WED (01:30--04:30), CIC
Venue     Theory: Room No F-232
Lab: CIC
Teaching Assistants     Arnab Dhar
Debajit Dey
Sabyasachi Karati
Souvik Kolay
Viswas Kumar Kushwaha

Notices and Announcements

October 17, 2012
Third (final) set of notes submitted to the photocopy center.
September 07, 2012
Second set of notes submitted to the photocopy center.
July 28, 2012
Roll lists: CS21003, CS29003. Submission server ready. All lab students added.
July 23, 2012
List of shortlisted external (non-CSE) students: This list is based on the registration status at 3:00pm of 23-July-2012. The only selection criterion used was the current performance (latest CGPA). The list is taken to be frozen at this point. Students with high CGPAs who decide to apply later will not be permitted, since students who are not shortlisted should be given time in order to register for other elective/additional subjects.
July 20, 2012
At most ten non-CSE students can be accommodated in the course (theory and lab). Shortlisting, if needed, will be based on the CGPA's of the applicants, and will be carried out in Monday (July 23) afternoon.

Tentative Coverage

Complexity of algorithms Asymptotic notations and their significance, complexity analysis of algorithms, worst case and average case. 2 hours
Algorithmic 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]     Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
[3]     Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
[4]     Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[5]     Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins, 1997.
[6]     Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
[7]     Muhammad H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific, 1999.
[8]     Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1995.
[9]     Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, third edition, Addison-Wesley, 2000.
[10]     Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.

Tests

Programming Assignments

No Topic Start date Due date More info
Warm-up assignment Recursive algorithms July 25, 2012 Not for submission Solution
Assignment 1 Recursive algorithms August 01, 2012 August 01, 2012 Solution
Assignment 2 Designing efficient algorithms August 08, 2012 August 08, 2012 Solution
Assignment 3 Dynamic programming August 22, 2012 August 22, 2012 Solution
Assignment 4 Representation of graphs August 29, 2012 September 05, 2012 Solution
Assignment 4s Supplement to Assignment 4 September 05, 2012 Not for submission Sample animation
Assignment 5 Heaps and priority queues September 12, 2012 September 12, 2012 Solution
Assignment 6 Binary search trees September 19, 2012 September 19, 2012 Solution
Assignment 7 String matching October 10, 2012 October 10, 2012 Solution
Assignment 8 Hash tables October 17, 2012 October 31, 2012 Solution
Assignment 9 Graph-theoretic algorithms October 31, 2012 November 14, 2012 Solution: .c, .h

Submission site | Miscellaneous information


Schedule | Notices | Syllabus | References | Tests | Assignments | Autumn 11