| Class meeting | TTh 11:00-12:15 Austin 307 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Science and Technology C-113 |
| Office hours | TTh 9:30am-11:00am, TTh 5:30pm-6:30pm |
| Phone | 328-9689 |
| karl@cs.ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/3650/spr05/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text | Introduction to Algorithms (second edition), by Cormen, Leiserson, Rivest and Stein |
CSCI 3510, MATH/CSCI 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 adding 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 some of 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 a 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, a significant 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, greedy algorithms, scan algorithms, and possibly some others.
Algorithm analysis techniques, including solving elementary summations and recurrences, and 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 four exams. each counting 18% of the grade. The final exam will be the fourth of those exams. Additionally, there will be homework that will count a total of 20% of the grade. Attendance will count for the remaining 8%.
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.
You are expected 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. 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.