CS 213(M) Data Structures and Algorithms

Syllabus:

Proving correctness of programs. Analysis of algorithms. Review 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.

Texts/References:

1. An introduction to programming through C++
2. Algorithms. Dasgupta, Papadimitrious, Vazirani.
3. Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein.
4. Notes and slides that will be uploaded.

General remarks

1. Approximate Grading scheme: 3 quizzes each of 13.3%, 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:

Introduction. Proving programs correct.

Homework 1.

Binary search, mergesort, 8 queens

Homework 2.

Heapsort

Dynamic memory management, Designing a String class that manages its memory

Quiz 1

Standard Library of C++

Dynamic arrays and analysis

Homework 3.

Representing networked structures/graphs in C++

Binary Search Trees.

Quicksort.

2-3 Trees.

B-trees.

Problem set.

Quiz 2

Line segment Intersection.

Line segment Intersection Code.

Homework 4.

Hash tables.

A challenging problem, not for submission.

Processing math formulae