CS 213(M) Data Structures and Algorithms
Proving correctness of programs. Analysis of
recursion, dynamic memory management, class design.
Algorithms for sorting: mergesort, heapsort, quicksort.
Heaps/priority queues, Dynamic arrays, Search trees, hash tables.
Tree based algorithms.
Graph algorithms: depth first and breadth first search. Shortest paths.
- An introduction
to programming through C++
- Algorithms. Dasgupta, Papadimitrious, Vazirani.
- Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein.
- Notes and slides that will be uploaded.
- Approximate Grading scheme: 3 quizzes each of 13.3%, homeworks +
programming assignments 10%, Endsemester exam 50%.
- 80% attendance is compulsory. Please come to class on time.
- The emphasis in the course is as much on reasoning about
programs as writing programs. You may get fewer marks if you are
not able to explain your programs, and in general if you do not
write clearly and neatly.
Notes and assignments:
Introduction. Proving programs correct.
Binary search, mergesort, 8 queens
Dynamic memory management, Designing a String class that
manages its memory>
Standard Library of C++
Dynamic arrays and analysis
Representing networked structures/graphs in C++
Binary Search Trees.
Line segment Intersection.
Line segment Intersection Code.
A challenging problem, not for submission.
Processing math formulae