Syllabus
CSCI 3650
Design and Analysis of Algorithms
Summer 2000
Instructor: | Karl Abrahamson |
Office: | Austin 233 |
Office hours: | M-F 1:00-2:00 |
Phone: | 328-1879 |
Email: | karl@cs.ecu.edu |
Course web page: |
www.cs.ecu.edu/~karl/3650/sum00 |
My web page: |
www.cs.ecu.edu/~karl |
Text: |
Introduction to Algorithms, by Cormen, Leiserson and
Rivest |
Algorithms
An algorithm is a well-specified method of solving some computational
problem. A great deal of computer science can be though of as
finding algorithms to solve problems.
Some problems have simple and straightforward algorithms. Some
problems are so difficult that nobody knows how to solve them
by an algorithm. The wonderful thing is that there is a vast
area in between, where surprisingly clever algorithms are found
to solve problems whose solutions are far from obvious initially.
The study of algorithms is one of the deepest areas of computer science.
Course objectives
This course is concerned with solving problems efficiently on a
computer. By efficiently, I am referring to the amount of time the computer
spends running the program, not the amount of time you spend
writing the program.
It is impossible to know whether you are indeed solving a problem
efficiently unless you have some way to determine how efficient a program is.
Accordingly, part of the content of this course is a collection
of methods for analyzing algorithm. An analysis of an algorithm
is a determination of its efficiency.
Topics that will be covered are as follows.
- Algorithm design techniques. These will include
divide and conquer, dynamic programming and greedy algorithms,
and possibly some others.
- Algorithm analysis techniques, including solving elementary
recurrences and possibly other techniques such as amortization of cost.
- A brief survey of known algorithms. It is important to know
something about the algorithms that are "off the shelf".
- Lower bounds. Here, we are concerned with showing that an
algorithm cannot be substantially improved on, by demonstrating
that no algorithm can possibly do much better. (We will only do
a very little of this.)
- Introduction to the theory of NP-completeness. This is a
cornerstone of computer science, and concerns problems that are
believed not to have any efficient algorithms.
These topics will not be studied one after another, but will be
interleaved as we examine different problems.
Prerequisites
You should be a competent programmer. There will be no programming
for this class, but it important that you can imagine, from a description
of an algorithm, how that algorithm might be implemented on a computer.
It is important that you understand how to solve elementary
problems, such as addding up a list of numbers. We need to get
beyond those.
You should have good problem solving skills, and be willing to
think out solutions to problems.
Grading
There will be three exams. Each will count 25% of the grade.
Additionally, there will be homework that will count a total of
25% of the grade.
Cutoffs for grades will tentatively by 90% for an A, 80% for a B,
70% for a C and 60% for a D. Those cutoffs will not be raised.
Summer session
The summer session goes by very quickly. In five weeks, we
will cover what is covered in fifteen weeks during the fall
or spring sessions. There are no breaks, and you will have
to work hard. You should count on working more than
three times as hard as during the regular term, because it
takes more work to learn material faster.
Here are some tips on how to do well in the
summer session.
- Attend class. Arrive on time.
- Do not allow yourself to fall behind. Work on the
homework early. Do not wait until just before the deadline.
- Schedule time to work outside of class.
- Read your notes and the book twice. Take a break
in between. You will learn much more this way.
- If you are having trouble, seek help soon. Do not
wait until it is too late.