Objectives
In this course, you will learn to design, analyze, and program
sequential and parallel algorithms and data structures. The
emphasis is on fundamental algorithmic concepts applicable across a
wide variety of problem domains, and transferable across a
reasonably broad set of programming languages and computer
architectures. We will in general consider parallel algorithms,
those that do multiple things at once, viewing sequential algorithms
as a special case. The course includes a significant programming
component in which you will program concrete examples from domains
such as engineering, scientific computing, graphics, data mining,
and information retrieval.
By the end of the course, we expect you to:
-
differentiate between problems and algorithms. A problem
defines an interface while an algorithm defines a particular
method to solve the problem. For example, quicksort is an
algorithm to solve the sorting problem. Being able to cleanly
define a problem is key in the process of putting together large
programs and in reusing their components. Similarly, we
distinguish between abstract data types and particular data
structures that implement them.
-
know and be able to apply a toolbox of algorithm design
techniques, such as reduction, inductive techniques
(contraction, divide and conquer, dynamic programming,
greediness), and randomization. We also expect you to
know and be able to apply a toolbox of abstract data
types, such as sequences, sets and tables, and graphs, as
well as implementations thereof.
-
analyze performance in terms of work, span, and space using
big-O asymptotics. We cover a variety of techniques for
analyzing asymptotic performance including solving recurrences,
randomized analysis, and counting arguments.
Prerequisites: COMP 211, COMP 212, and MA 228.
Activities
There will be two lectures per week, Tu-Th 1:20pm-2:40pm in Exley
109. This time will be used for chalk-board lectures, for
interactively coding as a whole class, and possibly for small-group
or individual work. Lectures will be your primary source of
information for the course, and attendance is strongly encouraged.
The textbook we will use is Algorithms:
Parallel and Sequential.
There will be one- to two-week-long written and programming assignments.
Homeworks are designed to help you internalize the course material;
they consist of written problems and short to medium-sized
programming tasks. No credit will be given for homework handins
that do not compile. If you cannot make it to class for some reason, you may
drop the HW off at Dan's office, Exley 633. No late homeworks will
be accepted, except by permission of instructor.
There will be an in-class midterm and final exam. As the only
completely non-collaborative type of assignment in the course, exams
account for a significant portion of your grade. However, lest that
sound too scary, the exams will not ask you to learn new skills,
just to demonstrate that you have acquired the skills we ask you to
practice in homeworks.
Assessment
Your grade will be based on homework assignments
(55%), a midterm exam (20%), a final exam (20%), and class
participation (5%). (Percentages are subject to change.)
Generally, 90%-100% should be interpreted as A work, 80-90% as B,
70-80% as C, 60-70% as D, and below that as failing. However, the
instructor may adjust the final letter grade boundaries (in either
direction) at the end of the semester, to account for differences
between the intended and actual difficulty of the assignments.
Assignments will be graded for correctness, clarity, and efficiency.