| Class meeting | TTh 3:30–4:45pm Austin 302 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Science and Technology C-113 |
| Office hours | M–F 11:00am–12:00pm |
| Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/3650/spr15/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text | Introduction to Algorithms (third edition), by Cormen, Leiserson, Rivest and Stein |
CSCI 3200 or 3300, MATH/CSCI 2427. You should be a competent programmer with a working knowledge of data structures and control structures (such as if-then-else, loops and recursion). 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 computational 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 and cover new material carefully.
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 computational problems. Some problems have simple and straightforward algorithms. Some problems are so difficult that nobody knows how to solve them by an algorithm, and some are provably unsolvable. 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, or to solve problems in much more efficient ways that were apparently possible. 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 performing the algorithm, not the amount of time or effort you spend writing it down.
It is impossible to know whether you are indeed solving a problem efficiently unless you have some way to determine how efficient an algorithm is. Accordingly, a significant part of the content of this course is a collection of methods for analyzing algorithms. An analysis of an algorithm is a determination of the cost of performing it, in terms of time and memory.
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.
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.
After succesfully completing this course, you should be able to do the following.
Define the concepts of time and space cost of an algorithm as it depends on the size of the problem instance. Define and use O, Ω and Θ notation.
Formulate summations or recurrences or other mathematical forms that express the cost of running an algorithm, and solve those mathematical forms for cases that frequently occur in practice.
Recognize the importance of demonstrating that an algorithm correctly solves a given problem.
Apply the most basic lower bound methods and identify some common fallacies regarding lower bounds.
Apply common techniques, including divide-and-conquer and dynamic programming, to the design of efficient algorithms for given computational problems.
Be aware of known efficient algorithms for some important computational problems.
Define the classes P and NP and the class of NP-complete problems, identify some common NP-complete problems, understand the consequences of NP-completeness, and be able to carry out simple reductions between problems.
There will be seven quizzes, on 1/27, 2/10, 2/24, 3/17, 3/31, 4/14 and 4/23, plus a comprehensive final exam from 2:00–4:30pm on Thursday, May 7 in Austin 302.
I will drop your lowest quiz grade, leaving six quizzes. Each of the six quizzes will count for 8% of the grade and the final exam will count for 25%, Additionally, there will be homework that will count a total of 17% of the grade. Attendance will count for the remaining 10%. You will start with 10 points for attendance and lose 2 points for each unexcused absence.
Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.
| A | 93% |
| A– | 90% |
| B+ | 87% |
| B | 83% |
| B– | 80% |
| C+ | 76% |
| C | 72% |
| C– | 68% |
| D+ | 64% |
| D | 60% |
| D– | 56% |
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.
Attend class. Arrive on time. Do not skip class either because you think that you already understand the material or for the opposite reason, that you think you cannot get it.
Do not bring distractions to class. If you read your email, listen to music, or engage in other distracting activities during class, you will get very little out of class.
Ask questions in class. If you do not understand something, ask a question about it.
Do not allow yourself to fall behind. Work on the homework early. Do not wait until just before the deadline. If you start to fall behind, work right away to catch up. If you are falling behind because you do not understand something, ask for help. Do not just give up!
Schedule time to work outside of class.
Read the lecture notes twice. Take a break (like a whole day or longer) in between. Work the exercises. Later in the term, go back over notes that you looked at earlier in the term. You will learn much more that way.
Get adequate sleep. Sleep is important both before and after you learn new concepts. Sleep before enables you to concentrate, and sleep afterwards is critical for moving new information into permanent memory.
If you are having trouble, seek help soon. Do not wait until it is too late.
For information about