| 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/sum02/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text | Introduction to Algorithms (second edition), by Cormen, Leiserson and Rivest |
CSCI 3510, MATH 2427. 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.
This is a mathematical course, and you should have a good command of fundamental mathematical concepts. We will go over the concepts needed, but you will need to be able to recall them quickly from previous study.
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. These topics will not be studied one after another, but will be interleaved as we examine different problems.
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 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.
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.
I will not take attendance. It is up to you to attend class. You are responsible for announcements and assignments given in class. If you miss a class, it is up to you to obtain notes and any other information that was provided in the class. Excuses that you did not know about something because you did not come to class and did not obtain the information will not count for anything at all.
Those who choose not to attend class can count on doing poorly in this course. If you choose not to attend class, then you must live with the consequences of that decision, however bad they are.
No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you are nearly done already, and have done work of acceptable quality so that it is realistic that you can pass the course.
In the event of a weather emergency, information about ECU can be accessed through the following sources:
| ECU emergency notices | http://www.ecu.edu/alert |
|---|---|
| ECU emergency information hotline | 252-328-0062 |
East Carolina University seeks to comply fully with the Americans with Disabilities Act (ADA). Students requesting accommodations based on a covered disability must go to the Department for Disability Support Services, located in Brewster A-114, to verify the disability before any accommodations can occur. The telephone number is 252-328-6799.