Syllabus

DESIGN AND ANALYSIS OF ALGORITHMS
Com S 311

Course Syllabus

Introduction and Objective

Algorithms are recipes for solving computational problems, for example, finding the cheapest ticket from Boston to Bombay or programming a robot to navigate in an environment filled with obstacles. The goal of this course is to introduce the basic techniques used to design and analyze efficient algorithms for solving real-world problems. Since the range of applications of computers is broad, the course will cover a variety of topics, including sorting, searching, dynamic programming, greedy algorithms, graph algorithms, string processing, computational geometry, and NP-completeness.

Given the time limitations, it will only be possible to skim the surface of each of these subjects. Nevertheless, upon completion of the course, you should understand the basic principles underlying the field and be able to apply them in specific instances.

Textbook

T.H. Cormen, C.E. Leiserson, R. Rivest, and Clifford Stein. Introduction to Algorithms (2nd edition). McGraw-Hill, 2001. ISBN 0-07-013151-1.

Prerequisites

(i) Math 166, (ii) Com S 228, (iii) Com S 330 or Cpr E 310.

All undergraduates will need to have these three pre-requisites before they can take Com S 311. In addition, both Computer Science and Computer Engineering undergraduates will need to have at least a C- in these courses. Graduate students may have some or all of these courses waived at the discretion of the instructor, if they can show proof of having taken the equivalent courses elsewhere.

Because of the high demand for the course, Com S 311 is open only to Computer Science and Computer Engineering Undergraduate Majors, as well as Computer Science Graduate Majors and Minors. Therefore, any graduate students in other disciplines who would like to take this course should first attain Computer Science Undergraduate Major status or Computer Science Graduate Minor status. It is important that all paperwork (to obtain status) is complete before the registration can take place.

Grading Policy

Grading will be based on homeworks and three mid-term exams. There will be no comprehensive final exam.

Homeworks 25%

Midterms (25% each)

Your final grade will be decided by an absolute grading scale as following:

 

Score Grade
at least 90 A
at least 85 but less than 90 A-
at least 80 but less than 85 B+
at least 75 but less than 80 B
at least 70 but less than 75 B-
at least 65 but less than 70 C+
at least 60 but less than 65 C
at least 55 but less than 60 C-
at least 50 but less than 55 D
less than 50 F

Assignments

Assignments will be posted on the website every Tuesday, and will be due the following Tuesday, except on weeks when exams are held.

Assignments must be submitted to the wooden drop-box located in the first floor of Atanasoff Hall by noon on the Tuesday it is due. Graded homework will be returned in class the next week. Late homework, turned in at the wooden drop-box by noon on the Thursday after the due date will incur a 25% penalty. No late homework beyond this time will be accepted.

Academic Honesty

In this course, you may discuss assignments with other students. (Do not assume this is true in all your courses!) We expect you to think through and full understand assignment solutions. Thus, the solutions you turn in must be written individually, based on your own understanding. Plagiarism will be dealt with harshly. You should consult the University Policy for details regarding academic misconduct and its consequences.

Exams

There will be three mid-term exams. The first two exams have been tentatively scheduled for Tuesday, October 5 and Monday, Novenmber 8 from 6:30 to 8:30 pm in Hoover 2055. The third exam will be in class on Friday, December 10. Further information on the exams, including confirmed dates, will be posted on the Exam page.

Programming Project

A programming project may be given as an extra credit assignment. It is therefore not mandatory.

Reference Books

The following book contains very clear descriptions and analyses of most (if not all) of the algorithms to be presented in this course.

Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java. Wiley, 1998. ISBN 0-471-19309-9.

The following books are on 2-hour-reserve:

Udi Manber. Introduction to Algorithms: A Creative Approach. Addison Wesley, 1989.

Robert Sedgewick. Algorithms in C++. Addison-Wesley, 1992. ISBN 0-201-51059.

Sara Baase. Computer Algorithms : Introduction to Design and Analysis. Addison-Wesley, 1988.

Office Hours

Office hours are provided to answer any questions that you have regarding lecture material, exams or homework. Please take advantage of this opportunity.

E-mail

If you have questions with short answers or you cannot attend any of the office hours, alternatively, you can e-mail us at cs311staff@iastate.edu.

Web page

The class web page is located at the following URL : http://www.cs.iastate.edu/~cs311/. You should check the web page constantly for announcements regarding homeworks, exams and other information about this course.

Useful Links