| Course Description and
Objectives |
At the heart of computer science is the
development of efficient algorithms for solving problems. This
course focuses on the design and analysis of data structures and
algorithms, continuing the study of data structures begun in CPSC
225 with a focus on more advanced structures (hashtables, heaps,
balanced binary trees, graphs, and building your own data structure
for a particular application), common algorithmic approaches
(iterative, recursive, divide-and-conquer, greedy, backtracking,
branch-and-bound, dynamic programming), and covering topics such as
correctness, efficiency, complexity, and NP-completeness.
The course has three main goals (and several subgoals):
- developing the skill of analyzing a problem and creating
an efficient and provably correct solution to that problem, which
includes:
- gaining a
working knowledge of algorithmic efficiency, to inform
the algorithm- and
program-design process by providing a basis for comparing solutions and
defining good solutions
- developing a toolbox of known data structures and algorithmic strategies
which can be used to solve many common problems
- developing the knowledge of
how to think about algorithms and data structures, for when a
"canned" data structure or algorithm might not be sufficient
- fostering an appreciation for the practical value of studying
algorithms and data structures
- developing other skills useful in computer science: abstract
thinking, comfort with the idea of tradeoffs, and a habit of critical
reflection
By the end of the course, the successful student should be able to:
- describe and discuss different ways in which the efficiency of an
algorithm can be determined
- define big-Oh notation
- discuss the pros and cons of asymptotic measures (big-Oh) and
experimental measures of algorithm efficiency
- define the difference between best case, worst case, and average
case running time/space
- determine the (best, worst, average) running time/space of an
iterative or recursive algorithm
- arrange algorithms from fast to slow based on their asymptotic
running times
- define: iterative algorithm, recursive algorithm,
divide-and-conquer, greedy, recursive backtracking,
branch-and-bound, dynamic
programming
- give examples of algorithms utilizing each approach
- for each approach, identify the problem characteristics that make
that approach suitable (or not suitable)
- identify the steps for developing algorithms of each type
- develop algorithms for a new problem using suitable approach(es)
- convincingly justify the correctness of the resulting algorithm
- identify the key properties and typical operations of common ADTs
for collections, sorting, and lookup
- give examples of applications of each ADT
- match the needs of the problem to an appropriate ADT
- compare and contrast the time- and space-efficiency of
different implementations of ADTs
and discuss situations in which each implementation is most appropriate
- define and implement basic graph algorithms (e.g. depth-first
search, breadth-first search, topological sort, shortest path),
determine their running times, and discuss their applications
- define P, NP, NP-hard, and NP-complete and give examples of
relevant problems
- describe several important NP-complete problems (e.g. 3SAT,
vertex cover, clique, knapsack, TSP)
- discuss and apply algorithmic strategies (e.g. backtracking,
branch-and-bound) for dealing with NP-complete problems
|
| Class Format and Expectations |
This is primarily a lecture-based class with
three class meetings per week, weekly written homeworks, several
programming assignments, and in-class exams. In addition, there
will be four one-hour lab sessions scheduled over the course of
the semester (one for each programming assignment) as well as
four 15-minute interviews (again, one for each programming
assignment).
You are expected to attend all scheduled class meetings,
including the lab sessions, and the interviews. The timing of
the lab sessions will be set early in the semester and effort
will be made to schedule them at times when as many people as
possible can attend. If you cannot attend a scheduled lab, it
can be made up by coming to office hours instead. The interview
schedule for each programming assignment will be set closer to
the respective due dates.
You should expect to spend approximately 8-10 hours per week on
average on additional work (readings, homework, studying) outside
of class. While your experience may vary from topic to topic or
from week to week, if you routinely spend substantially more time
or you feel like you are spinning your wheels and not making
progress, you should visit office hours for help.
|
| Prerequisites |
CPSC 225 is required.
This course builds
directly on the material in CPSC 225 (and 124): programming in
Java, fundamental program constructs such as loops and
conditionals, basic abstract data types (lists, stacks, queues,
and binary trees), how those data types are implemented (using
arrays, linked lists, and other linked structures), and
recursion.
CPSC 229 is helpful, but not essential.
The most relevant
topics from 229 are the idea of a formal mathematical proof, and
specific proof techniques such as induction and proof by
contradiction. The topics of Turing machines and computability
will also make an appearance. While prior exposure to this
material is helpful, no knowledge is assumed and all of these
topics will be introduced as needed.
|
| Required Materials |
Textbook
The Algorithm Design Manual (3rd ed)
Steven S Skiena
Springer, 2020
ISBN 978-3030542559 (hardcover), 978-3030542580 (softcover),
978-3030542566 (ebook)
This is both a textbook for learning how to design algorithms and
data structures, and a useful reference with an extensive
catalog of algorithmic problems that arise in practice. I hope that
you will enjoy reading the book during the course and that you will
want to hang on to the book afterwards to use in your future
algorithmic endeavors.
If you are buying the book on Amazon or elsewhere, note
that the third edition has a very similar-looking cover to the
second edition. Look for "Third Edition" on the cover and/or check
the ISBN to make sure you are getting the right version.
Additional material will be handed out or posted on the
course webpage.
Software
There will be several programming assignments which involve
programming in Java. The tools that you need are available within
the campus Linux environment (accessible in Demarest 002 or remotely
through the Linux DVI).
|