CS 213(M) Data Structures and Algorithms
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
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.