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.

Syllabus:

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.

Texts/References:

  1. An introduction to programming through C++
  2. Algorithms. Dasgupta, Papadimitrious, Vazirani.
  3. Notes and slides that will be uploaded.

General remarks

  1. Approximate Grading scheme: 4 quizzes each of 10%, homeworks + programming assignments 10%, Endsemester exam 50%.
  2. 80% attendance is compulsory. Please come to class on time.
  3. 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