CPS130

Erik Halvorson

Introduction to the Design and Analysis of Algorithms

Duke University
  • Course Essentials

Instructor: Erik Halvorson
Time: 3:30-4:45 PM, MTWRF
Location: LSRC D243
Office Hours: 2:30-3:30 PM, MTWRF
  or by appointment

  • Course Description

This course provides an introduction to the design and analysis of algorithms, with particular emphasis on the analysis. We will focus on the mathematical basis of computer science; not just how a computer works, but the nature of computation, the inherent difficulty of various problems, and how to measure the performance of an algorithm. Algorithms will be presented at an abstract level and rigorously analyzed, both in terms of runtime and correctness. We will be building on knowledge of data structures and basic analysis from CPS100 and applying the material learned in CPS102.

The class will cover algorithms for Sorting, Searching, and several different graph problems. We will introduce techniques for addressing specific kinds of problems, such as Divide and Conquer, Greedy, Dynamic Programming and Randomized strategies. We will present many different analysis methods, including recurrence relations, amortized analysis and randomized techniques. For a more detailed list of topics, see the lectures page.

  • Textbook

The textbook for this course is Introduction to Algorithms, by Thomas H. Cormen, et al. Many homework problems will be drawn from the book, and material from the book may be included on tests and quizzes. There will be an associated reading (roughly) corresponding with each lecture.

Erik Halvorson, 07 May, 2007