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

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

Schedule

Instructors     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-127
Lab: CIC
Teaching Assistants     Aayush Goel
Arnab Dhar
Rahul Katare
Sabyasachi Karati
Suvadeep Hajra

Notices and Announcements

July 24, 2013
The shortlisting of the external (non-CSE) students are done. Other external students will be deregistered by ERP.

Shortisted students

July 20, 2013
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 on Tuesday (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]     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
Warm-up assignment Recursive algorithms July 24, 2013 Not for submission Solution
Assignment 1 Divide-and-conquer algorithms July 31, 2013 July 31, 2013 Solution
Assignment 2 Greedy algorithms August 07, 2013 August 10, 2013 Solution
Assignment 3 Dynamic-programming algorithms August 14, 2013 August 14, 2013 Solution
Assignment 4 Working with graphs August 21, 2013 August 28, 2013 Solution
Assignment 5 Working with heaps September 04, 2013 September 04, 2013 Solution
Assignment 6 Working with binary search trees September 11, 2013 September 18, 2013 Solution
Assignment 7 Algorithms on arrays October 09, 2013 October 09, 2013 Solution
Lab Test 1 Algorithm design and data structures October 23, 2013 October 23, 2013 Solution
Assignment 8 Graph algorithms October 30, 2013 November 13, 2013 Solution

Submission site | Miscellaneous information


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