CS 213(M) Data Structures and Algorithms
Anyone is allowed to join the course provided...
I am opening up the course to anyone who wishes to
take it, without any CPI restriction. However I would like to have
an undertaking from you that you will attend at least 80% of the
classes, come to lectures on time, and put effort into the course
sincerely. Please bring me such an undertaking (handwritten) and a
course add-drop form between 12 noon and 1pm on Monday Jan 15, and I
will sign it.
Review of recursion. Techniques for proving
correctness of programs. Analysis of time taken by a program.
Algorithms for sorting. Quicksort with analysis. Sorting lower bounds.
Dynamic memory management and class design in C++. Heaps, balanced search trees. Implementation of vector class from
C++. Implementation of iterators.
Representing graphs. Algorithms based on depth first and breadth
first search. Shortest path algorithms.
- An introduction
to programming through C++
- Algorithms. Dasgupta, Papadimitrious, Vazirani.
- Notes and slides that will be uploaded.
- Approximate Grading scheme: 4 quizzes each of 10%, 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:
Proving programs correct.
Binary search, mergesort, 8 queens
Assignment 1: Write a program to solve the SEND + MORE = MONEY
problem, problem 9 of Chapter 16 of Text 1. Instructions for
uploading on Prutor will be put up shortly.
Analysis of Running Time (Slides)
Insertion sort code