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 (3rd edition). The MIT Press, 2009. ISBN 978-0-262-03384-8.
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 one midterm exam (in-class), one final exam, homeworks, and one project. Grades will be on the following scales:
| Homeworks 20% | Project 10% | Midterm 30% | Final 40% |
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
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.
Assignments
Homeworks will be assigned through blackboard. The assignment will usually be on Friday, and the due date will be on Friday before class.
Late submission will be accepted up untill 5:00 pm of the due date for a penalty of 25% . No submission will be accepted after that time.
Please read the Assignment page carefully for more information on submission, documentation, as well as how we will grade your submission and how to appeal your grades.
Exams
There will be a midterm exam and a final exam.
There will be a one week window of appeal for each exam beginning the day the exam is returned to the students during recitations. An exam appeal must be in writing and provide information to include the number of the question under issue and a brief statement giving the reason for the appeal. This written statement and the original exam must be given to the instructor during the specified appeal period. The whole exams will be regraded.
There will be no curving or adjustment of everyone's scores on any individual exam. Any curving will be done at the discretion of the instructor at the end of the semester, based on the distribution of overall scores.
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.
If you have questions with short answers or you cannot attend any of the office hours, alternatively, you can e-mail us.
Useful Links
- The Standard Template Library (STL) contains implementations of many of the algorithms and data structures studied in class (e.g., merging, quicksort, heaps, and red-black trees), as well as several more primitive, and extremely useful data structures.
- LEDA is a library of data types and algorithms for combinatorial computing, implemented in C++.
- Demo of sorting algorithms