CS 213(M) Data Structures and Algorithms

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

Heapsort

Assignment 2: Suppose you have n balls of unit mass and radius positioned on a straight line at specified positions. They are free to move along the line and their initial velocities are also given. Assume there is no friction and that collisions are elastic, i.e. when balls collide their velocities just get exchanged. As you can see, there will be some number of collisions after which the balls will simply escape to infinity on either side of the line. You are to write a program which takes the initial positions and velocities and prints the position and velocities of the balls at the time just after the last collision. Your code should include a binary heap -- it will help in speeding up execution.