A thorough treatment of various algorithms and data structures
that allow the efficient solution of common problems.
The webpage Topics gives
an outline of a number of algorithms and approaches.
The Calendar webpage gives
a week-by-week list of topics, and the
Lectures webpage will give
a longer week-by-week exposition of topics.
Of course your textbook has a much longer presentation.
Emphasis on intuitive understanding, including the ability to
apply a given approach in a number of contexts.
Emphasis on the asymptotic performance of algorithms,
using especially the "big-O" notation.
Practice coding algorithms into C or Java (or C++).
I intend to require a number of smaller programs.
Of course I want good programming style, including
ADT (abstract data type) development.
Special practice with programs involving linked lists, trees
and graphs, and the use of pointers (in C, references in Java).
Not afraid to do the mathematics when appropriate.
Not Goals:
This is not a software engineering course.
I don't want an emphasis on fancy Java features.
Part of the idea of having you write more programs
is that the programs should not be too long or take too long to write.
Since some of you will be writing in C, good ADT programming
is not possible. (That's why we have Java, C++, Objective-C, and
many other object-oriented languages.)
I want an emphasis on the algorithm, not on the best
possible implementation. I do not want major emphasis
on the generality, modifiability, and usability of the actual code.
This is the approach taken by your textbook with its pseudo-code.
Another current and well-regarded algorithms textbook,
Algorithms (4th Ed.), by Sedgewick and Wayne, takes the opposite
approach, with elaborate Java ADT implementations of
all algorithms (see here
for their Java code). This is not necessarily bad, but it means
students spend time worrying about details of Java
at the expense of time worrying about the algorithms themselves.
For example, Java input can be annoying at times.
You should not spend hours trying to get the end-of-file to
work on Java input and miss the deadline for an assignment.
Instead put in a sentinal at the end of a file, or turn
the data into hard-wired { } initialization. (This mirrors the
situation in industry when you encounter a problem and have
a deadline: find a
workaround
so you can meet the deadline.)
Here's another non-goal: mathematical proofs
of all statements and algorithms. I want you to understand
the various algorithms -- how and why they work, why their
asymptotic performance (more on this later) is what we say it is.
Full mathematical proofs at this level can even get in the way
of these goals.
Revision date:2011-10-01.
(Please use ISO 8601,
the International Standard Date and Time Notation.)