Courses taught by
David Casperson |
|
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).
fall-2024