| Class meeting | MWF 10:00–10:50 Rivers 226 | |||
|---|---|---|---|---|
| Instructor | Karl Abrahamson | |||
| Office | Science and Technology C-113 | |||
| Office hours |
|
|||
| Phone | 328-9689 | |||
| abrahamsonk@ecu.edu | ||||
| Course web page | www.cs.ecu.edu/~karl/3650/spr19/ | |||
| My web page | www.cs.ecu.edu/~karl/ | |||
| Text | Introduction to Algorithms (third edition), by Cormen, Leiserson, Rivest and Stein |
The prerequisite is CSCI 2530 or 3200. You should be a competent programmer with a working knowledge of data structures and control structures (such as if-then-else, loops and recursion). CSCI 2405 is a plus, but not a requirement.
There will be no programming for this class, but it is important that you can imagine, from a description of an algorithm, how that algorithm might be implemented on a computer. You will need to be able to give a clear sketch of an algorithm.
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 and able 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. Some problems have simple and straightforward algorithms. Some problems are so difficult that nobody knows how to solve them efficiently 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 working out the algorithm or writing it as part of a piece of software.
It is impossible to know whether a given algorithm is efficient unless you have some way to determine how efficient it 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, usually 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 and others.
Algorithm analysis techniques, including solving elementary summations and recurrences.
Exposure to some 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.)
Other topics. We will look at approximation algorithms for difficult problems, string matching, randomized algorithms and algorithms that are fast in an amortized sense.
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 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 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.
There will be six midterm exams, on the following dates.
A comprehensive final exam will take place from 8:00–10:30am on Wednesday, May 1 in the regular classroom.
I will drop your lowest midterm exam grade, leaving five. Each of those five exams will count for 10% of the grade and the final exam will count for 25%, Additionally, there will be homework that will count a total of 25% of the grade.
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% |
| Date | Topics | Reading |
|---|---|---|
| M. 1/7 |
Introduction. Notation and growth of functions. Summations. Elementary summations. |
3.1, 3.2. |
| W. 1/9 |
Splitting summations. Generating functions. Recurrences. Solving recurrences by substitution. |
A.1, 4.3. |
| F. 1/11 | Solving recurrences using the Master Theorem. | 4.5 |
| M. 1/14 |
Multiplying large integers. Algorithms for integer multiplication. |
|
| W. 1/16 |
Homework assignment 1 assigned. Divide and conquer. Fast integer multiplication. |
2.3 (divide and conquer). |
| F. 1/18 |
Dividing integers by multiplying: Newton's method. |
|
| M. 1/21 | Holiday | |
| W. 1/23 |
Homework assignment 1 due. The maximum subarray problem. Matrix multiplication. |
4.1, 4.2. |
| F. 1/25 |
Finding convex hulls in 2 dimensions. Graham scan algorithm. A divide-and-conquer algorithm. |
33.3. |
| M. 1/28 |
Homework assignment 1 returned. Go over assignment 1 and answer questions. |
|
| W. 1/30 |
Homework assignment 2 assigned. Polynomial multiplication. The discrete Fourier transform. |
30.1, 30.2. |
| F. 2/1 | Exam 1. Material related to homework exercise set 1. | |
| M. 2/4 | The FFT algorithm. | 30.2. |
| W. 2/6 |
Homework assignment 2 due. Sorting. Merge sort. Quicksort. |
2.1, 2.3, 7.1, 7.2. |
| F. 2/8 | Finding the k-th smallest value. | 9.2, 9.3 |
| M. 2/11 |
Homework assignment 2 returned. Go over assignment 2 and answer questions. |
|
| W. 2/13 |
Homework assignment 3 assigned. A lower bound for sorting. |
8.1. |
| F. 2/15 | Exam 2. Material related to homework exercise set 2. | |
| M. 2/18 |
Greedy algorithms. Coin changing. The High Degree Subgraph problem. |
16.2. |
| W. 2/20 |
Homework assignment 3 due. The Activity Selection problem. Issues with greedy algorithms. |
16.1. |
| F. 2/22 |
Dynamic programming. The Rod Cutting problem. |
15.1, 15.3. |
| M. 2/25 |
Homework assignment 3 returned. Go over assignment 3 and answer questions. |
|
| W. 2/27 |
Homework assignment 4 assigned. The Edit Distance problem. |
|
| F. 3/1 | Exam 3. Material related to homework exercise set 3. | |
| M. 3/4 – F. 3/8 | Spring break. | a |
| M. 3/11 | The Longest Common Subsequence problem. | 15.4. |
| W. 3/13 |
Homework assignment 4 due. More dynamic programming. |
|
| F. 3/15 |
Overview of NP-completeness. Approximation algorithms. The Vertex Cover problem. |
34.1, 35.1. |
| M. 3/18 |
Homework assignment 4 returned. Go over assignment 4 and answer questions. |
|
| W. 3/20 |
Homework assignment 5 assigned. The Traveling Salesman Problem. |
35.2. |
| F. 3/22 | Exam 4. Material related to homework exercise set 4. | |
| M. 3/25 |
Preprocessing algorithms. String matching. The Rabin/Karp algorithm |
32.1, 32.2. |
| W. 3/27 |
Homework assignment 5 due. The Knuth/Morris/Pratt algorithm. |
32.3, 32.4. |
| F. 3/29 | Amortization. Dynamic tables. | 17.1, 17.2, 17.3. |
| M. 4/1 |
Homework assignment 5 returned. Go over assignment 5 and answer questions. |
|
| W. 4/3 |
Homework assignment 6 assigned. An example of an algorithm that is fast in an amortized sense. |
|
| F. 4/5 | Exam 5. Material related to homework exercise set 5. | |
| M. 4/8 | Randomized algorithhms. Random permutations. | 5.3. |
| W. 4/10 |
Homework assignment 6 due. Checking whether a number is prime. |
31.8. |
| F. 4/12 | Factoring integers by Pollard's algorithm. | 31.9. |
| M. 4/15 |
Homework assignment 6 returned. Go over assignment 6 and answer questions. |
|
| W. 4/17 |
Open. |
|
| F. 4/19 | Holiday | |
| M. 4/22 | Exam 6. Material related to homework exercise set 6. | |
| Tu. 4/23 |
Open. |
|
| W. May 1 | Final exam, 8:00-10:30am. |
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 text messages or email, look at facebook, or engage in other distracting activities during class, you will get very little out of class, and that will adversely affect your grade.
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 relevant sections of the book twice. Take a break (like a whole day or longer) in between. Work the exercises. Later in the term, go back over what you read 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