| Class meeting | 11:20-12:50 M-F Austin 304 |
| Instructor | Karl Abrahamson |
| Office | Austin 233 |
| Office hours | M-Th 1:15-2:00 |
| Phone | 328-1879 |
| karl@cs.ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/3650/sum01/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Texts | Introduction to Algorithms, by Cormen, Leiserson and Rivest and Programming Pearls by Bentley |
An algorithm is a well-specified method of solving some computational problem. A great deal of computer science can be viewed 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.
This course is concerned with solving problems efficiently on a computer. By efficiently, I am referring to the amount of time or space the computer spends running the program, not the amount of time or effort 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.
You should be a competent programmer with a working knowledge of data structures. 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 to more interesting problems.
You should have good problem solving skills, and be willing to think out solutions to problems.
There will be three exams. Each will count 25% of the grade. The final exam will be the third of those exams. 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.
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.