Syllabus
CSCI 3650
Design and Analysis of Algorithms
Spring 2012

Prerequisites

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 and loops). 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.

Algorithms

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. 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.

Course objectives

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 the cost of running 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.

1. Algorithm design techniques. These will include divide and conquer, dynamic programming, greedy algorithms, scan algorithms, and possibly some others.

2. Algorithm analysis techniques, including solving elementary summations and recurrences.

3. A brief survey of known algorithms. It is important to know something about algorithms that are "off the shelf".

4. 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.)

5. 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.

Competencies

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.

Grading

There will be seven quizzes, on 1/20, 2/3, 2/17, 3/2, 3/23, 4/9 and 4/20, plus a comprehensive final exam from 8:00am-10:30am on Friday, April 27 in the regular classroom.

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%.

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.

Attendance policy

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.

Incompletes

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.

Recommendations for success

1. Attend class. Arrive on time.

2. Avoid distractions during class. Do not send or receive text messages, read your email, play games, etc.

3. Read your notes and relevant chapters of the book twice. Take a break (like a whole day) in between. You will learn much more that way.

4. Do not allow yourself to fall behind. Work on the homework early. Do not wait until just before the deadline.

5. Schedule time to work outside of class.

6. If you are having trouble, seek help soon. Do not wait until it is too late.

7. 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.

Weather emergencies

In the event of a weather emergency, information about ECU can be obtained through the following sources:

ECU emergency notices	http://www.ecu.edu/alert
ECU emergency information hotline	252-328-0062

Students with disabilities

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 Slay 138, before any accommodations can occur. The telephone number is 252-737-1016.

Retention Requirements

Academic requirements for retention have changed. Please be aware of the following new GPA requirements. Please discuss the retention requirements, entrance to major requirements, and your goals with your academic advisor.