Ecoe 556: Algorithms and Computational Complexity Fall 2007 Course Information



Download 24.02 Kb.
Date07.08.2017
Size24.02 Kb.
#29129

ECOE 556: Algorithms and Computational Complexity

Fall 2007 Course Information





Instructor: Serdar Taşıran

Contact info: ENG 226, stasiran@ku.edu.tr, 212-338-1748




Office hours: To be announced.

Lectures:

Mondays and Wednesdays 2-3:30 pm, ENG B21

Course home page:

http://ais.ku.edu.tr/course/12623/Default.html



Textbook:

Cormen, Leiserson, Rivest and Stein Introduction to Algorithms,
McGraw-Hill

Recommended
reading:


Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co.
Papadimitrou and Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover.

Course content:

This is a broad graduate level introductory course on efficient algorithms and data structures addressing problems commonly encountered in engineering and computer science. We will emphasize complexity analysis of algorithms. The aim of the course is to bring you a point where, when you come across an engineering and/or research problem, you:

  1. can identify the computational complexity class of the problem

  2. know or can find out about related algorithms and data structures, and

  3. can integrate them into an efficient algorithm and analyze the performance of your solution.

Grading policy:

The breakdown of your course grade is as follows.

Weekly problem sets: 25 %

Two midterm examinations: 15 % each
Final examination: 25 %

Project: 20 %

Any duplication in problem solutions or your project will be prosecuted to the fullest extent allowed by university policy regarding academic dishonesty.


Weekly Problem Sets

Each week, you will be assigned a set of problems. Solving these problems and writing the solutions down on your own, without referring to the solutions or other people will be the best way to prepare for the examinations.

You are encouraged to discuss problems with your classmates and to consult other sources. However, trying to solve problems on your own is a very important learning tool for this course, and you are recommended to approach this matter very seriously.




Project

You will be required to carry out a programming project for this course. This project will give you the opportunity to use and integrate the algorithms, data structures and analysis methods that you learn in this course. The project will be due the week of the final examinations and will be carried out individually.

Sometime near the middle of the semester, you will be given a detailed handout explaining the problem you are asked to solve. You will be free to use any programming language and platform, and any standard data structure and algorithm implementations available as libraries. Your grade will be based on the performance of your program on a number of benchmarks, as well as a project report in which you analyze your solution.






Topics

Reading1




1

Introduction. Asymptotic notation. Solving recurrence equations.

CLR* 1-4

2

Heaps, heapsort

CLR 6

3

Quicksort, linear-time sorting.

CLR 7, 8

4

Hash tables, binary search trees, augmenting data structures.

CLR 11, 12, 14

5

Dynamic programming

CLR 15

6

Greedy algorithms

CLR 16

7

Graph representations: Adjacency matrices and lists.
Depth- and breadth-first search.

CLR 22

8

Topological sort. Strongly connected components.

CLR 22

9

SPRING BREAK

10

Minimum spanning trees.

CLR 23

11

Single-source shortest paths

CLR 24

12

Flow networks. Maximum flow.

CLR 26

13

NP-complete problems, proving NP-completeness

CLR 34, G&J**

14

NP-complete problems, proving NP-completeness

CLR 34, G&J**

15

Approximation algorithms for NP-complete problems

CLR 34, G&J**




1* : Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms.

** : Garey, Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness



Download 24.02 Kb.

Share with your friends:




The database is protected by copyright ©ininet.org 2024
send message

    Main page