Last modified: 2023-12-09
Courses taught by
David Casperson
CPSC 200

CPSC 200-3
Algorithm Analysis and Development

Formally, the goals of this course are to teach students the concepts of algorithm analysis and asymptotic complexity notation.

Informally, this course ups the ante for what constitutes a good program. In CPSC 100 and CPSC 101 a good program is one that validates users’ input, is neatly written, and that works correctly. In CPSC 200 a good program is a program that works efficiently (whatever thata means).

In CPSC 100 and CPSC 101 finding an algorithm that worked consists of “random” hacking on nested for-loops to find something that accomplishes the goal. CPSC 200 attempts to make the process of finding an algorithm more methodical by carefully examining notions such as loop invariants.

This course studies the classic sorting algorithms as case studies. It also looks in depth at the coding of list classes, and briefly (ideas not code) at trees, binary search trees, and the need for balance.

It also explores the notions of containers, iterators, and generic programming. (When taught in C++ it provides a high-level introduction to the Standard Template Library. When taught in Java it introduces the corresponding concepts from the java.util packages. )

This course was first taught in Java in 2009. The first time that I taught this course in Java was 2010 (co-taught with Arbër Borici).

Links

Course Outlines (pdf files)
Semester Web Pages
  • 2024
  • 2022
  • 2021
  • 2018
  • 2010 (co-teacher: Arbër Borici)
  • 2009 was taught by Wenbao Jang
  • 2008 was a sabbatical semester
  • 2007
  • 2006
  • 2005
  • 2004 was a sabbatical year
  • 2003 (a strange web-page)
  • I didn't start constructing Semester web-pages until Fall 2003.

fall-2024