|
|
Introduction
The topics that we will be discuss in this course fall into two main categories.
First, we will look at techniques that we can use to design efficient data structures
and algorithms. Second, we will learn tools that make it possible to prove the
correctness and the efficiency of the algorithms and data structures that we designed.
More specifically, we will look at the following broad topics (not necessarily in this
order):
- Searching and sorting;
- Data structures, such as skip lists.
- Mathematical tools, like O notation, recurrence relations, and
amortized analysis;
- Algorithm design techniques, for instance randomization, greediness and
dynamic programming.
Much of the material is formal (mathematical) in nature, and hence proofs will
constitute an important part of the course.
At the end of the course, you will be able to:
- Recognize which algorithm design technique(s), such as divide and conquer,
prune and search, greedy strategies, or dynamic programming was used in a given
algorithm.
- Select and judge several promising paradigms and/or data structures
(possibly slightly modified) for a given problem by analyzing the problem's
properties.
- Implement a solution to a problem using a specified algorithm design
paradigm, given sufficient information about the form of that problem's
solution.
- Select, judge and apply promising mathematical techniques (such as
asymptotic notations, recurrence relations, amortized analysis and decision trees)
to establish reasonably tight upper and lower bounds on the running time of
algorithms.
- Recognize similarities between a new problem and some of the problems they
have encountered, and judge whether or not these similarities can be leveraged
towards designing an algorithm for the new problem.
A more detailed list of topics-level learning goals can be found here.
Prerequisites
The prerequisites for this course are:
- Either
or
- At least 3 credits of MATH/STAT courses numbered 200 or above
- If you completed only 3 credits of MATH/STAT courses numbered 200 or above,
then you must have obtained 72% (or better) in that course.
- If you completed 6 or more credits of MATH/STAT courses numbered 200 or
above, then it doesn't matter what your marks in these courses was.
A few courses offered by other departments (for instance, BIOL 300) can also be
used to satisfy this requirement.
Finally, basic knowledge of probability theory would be helpful, although the
little we need can be learned as the term progresses.
|
