CS 515 - Algorithm Design

Bulletin Description

The design and analysis of efficient algorithms on data structures for problems in sorting, searching, graph theory, combinatorial optimization, computational geometry, and algebraic computation. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy method, and randomization, approximation algorithms.

Prerequisites

CS 315 and engineering standing.

Expected Preparation

Students need to be familiar with basic data structures and algorithms. Students should be adept in programming in a modern object-oriented language.

Student Learning Outcomes

A successful student will develop knowledge of various mathematical tools and algorithmic methods that are applicable in computer science. Specifically, students will be able to:

  1. Prove algorithms correct
  2. Analyze the computational complexity of algorithms
  3. Design algorithms for complex problems
  4. Select and apply the best algorithmic approach for practical problems algorithms

Measures

Direct Measures:

Students are evaluated on their work (homeworks, exams). Students receive back their homework and exams. These papers are marked to indicate problems, point out correct or better solutions, and improve the quality of presentation. Problems that turn out to be especially difficult are discussed in class during lectures.

NOTE: 100% lecture - 0% recitations

Indirect Measures:

These four specific outcomes will be evaluated on the basis of student work (homeworks, programming assignments, and exams) that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the four outcomes performed at the end of the semester.

Syllabus Information

Possible Textbooks:

Introduction to Algorithms, Second Edition
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Clifford Stein
MIT Press, 2001.

Introduction to Algorithms: A Creative Approach
U. Manber
Addison-Wesley, 1989.