Gregor Reisch: Madame Arithmatica, 1508

## Administration

Design and Analysis of Algorithms

COMPSCI 330 • Fall 2015

Instructor: Pankaj K. Agarwal

TAs: Aaron Lowe and Stavros Sintos

UTAs: William Victor, Samadwara Reddy, Alexandru Milu, Rex Ying

Times & Locations:

Lectures |
Tue, Thu, 3:05-4:20 French Sci 2231 |

Recitations |
Fri, 11:45-1:05 Soc Sci 139 |

Office Hours:

Agarwal: |
Tue 4:45-5:45 pm Fri 2:00-3:00 pm (D214A-LSRC) |

Lowe: |
Tue 10:00-11:00 am Thu 10:00-11:00 am (N001-North) |

Sintos: |
Wed 5:00-6:00 pm Fri 5:00-6:00 pm (D206-LSRC) |

uTAs: |
Mon 8:00-9:00 pm Wed 8:00-9:00 pm (Link) |

## Overview

This undergraduate course covers techniques for designing and analyzing algorithms and data structures for a wide range of problems. Topics include:

- Design Techniques: Divide-and-conquer, recurrence relations, prune and search, greedy algorithms, dynamic programming, randomization, local search
- Data structures: Skip list, hashing, union-find, hashing, amortization
- Graph algorithms: Graph traversal, strongly connected components, minimum spanning tree, shortest path
- Linear Programming: Modeling, simplex algorithm, duality
- Algebraic algorithms: Polynomial multiplication, FFT
- Intractability: Easy and hard problems, NP-Completeness, reducibility, approximation algorithms

## Prerequisites

CPS201 and 230 or equivalent courses. This course requires undergraduate background in data structures as well as a certain amount of mathematical sophistication.

## Textbooks

[DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.

[KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (optional).

## Reference Books

[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2009.

[Ta] R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial Mathematics, 1987.

## Grading

- Assignments (five out of six): 30%
- Midterm exams (two): 35%
- Final exam: 35%
- Both midterm and final will be in-class closed-book exams.
- For assignments, discussion among students is permitted, but students MUST write up solutions independently on their own and mention who they discussed the problems with. No materials or sources from prior years' classes or from the Internet can be consulted. Review the detailed guideline on collaboration.
- Students are required to use Latex or MS-Word for writing their assignments and to submit pdf files on the course Sakai page.
- No credit is given for late solutions.

page top