# Algorithms

Fall semester 2011-12

Department of Informatics and Telecommunications

University of Athens

Professor: Elias Koutsoupias

## Table of Contents

## News

#### Η εξέταση της 14/09 θα γίνει κανονικά, παρά την προκήρυξη απεργίας.

#### The last homework set is due 13/02

#### The midterm will take place on Wednesday 11/01

#### homework sets

Announcement of the first two#### Classes begin on Wednesady Nov 02/10

## General Information

### Rooms and Hours:

- Wednesday 3-5, Room Α1
- Thursday 1-3, Room ΣΤ

#### Office hours:

- Wednesday 1:30-2:30 (Room B7)

### Description

This is a graduate course on algorithms that can also be taken by interested undergraduate students. The official title of the course is

- Αλγόριθμοι, for the graduate students of the department of Informatics and Telecom.
- Αλγόριθμοι και Πολυπλοκότητα Ι, for the graduate students of ΜΠΛΑ
- Προηγμένα Θέματα Αλγορίθμων, for undergraduate students

This course is for graduate and undergraduate students with sufficient background in mathematics and algorithms. The only prerequisites are a basic knowledge of design methods and analysis of algorithms and basic knowledge of data structures. If you have not taken an algorithms course before, you should expect to do some independent reading to catch up with the class.

The textbooks of the course are

- S. Dasgupta, C. H. Papadimitriou, and U.V. Vazirani. Algorithms. Available online
- J. Kleinberg and E. Tardos. Algorithm Design
- Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms

### Grading

The final grade will depend on

- midterm exam (25%)
- final exam (45%)
- homework (30%)

A passing grade is required for both the homework and the combined exams.

## Homework

- The problems are from the online version of the Dasgupta-Papadimitriou-Varizari book.
- There are two types of problems:
- "Turn in" problems are those that you have to turn in
- "Practice" problems are those that I strongly suggest to solve; you should not turn them in. To motivate you to try these problems, I indent to include in the final exam 1 or 2 of these problems.

- For the problems that you have to turn in, write short, yet complete, answers.
- Don't submit electronic answers (by email).
- You can turn in either printed or legible handwritten homework. (I suggest not to waste your time to type the answers, unless you want to practice preparing typed documents.)
- No late answers will be accepted.

### Problem set 1

#### Turn in by Wednesday 21/12

- 2.23, 2.26, 2.32

#### Practice

- 0.2, 0.4, 2.22, 2.24

### Problem set 2

#### Turn in by Wednesday 11/01

- 6.6, 6.12, 6.20, 6.21

#### Practice

- 6.2, 6.8, 6.14, 6.25, 6.30

### Problem set 3

#### Turn in by Thursday 13/02, 6pm

- 8.8, 8.13, 9.6, 9.9

#### Practice

- 8.1, 8.4, 8.10, 8.20