======CMPU 241: Algorithmics ======
Vassar College, Spring 2013
Syllabus / Course Wiki
// Our course syllabus is a wiki. It is subject to update throughout the semester. //
^ Course Wiki: | http://www.cs.vassar.edu/courses/cs241-201301/top |
^ Professor: | James TenEyck |
^ Office: | OLB 106 |
^ Office Hours: | Tue/Thur 1:00 - 2:30 pm (and by appointment) |
^ Phone: | 437 5986 |
^ Email: | [[teneyck@cs.vassar.edu]] |
^ Class Meeting Time: | Tue/Thur 10:30-11:45 am |
Links to Class Project Reports
Found in Project Assignments
\\
=====Text and References =====
Kleinberg and Tardos Algorithm Design, Addison-Wesley c 2009
====Course Description====
Computer Programs contain segments of code that instruct the machine how to perform certain tasks or solve specific problems. A large system may have many smaller sub tasks to perform. The recipe for performing these tasks or solving these problems is called an algorithm. Some tasks are frequently encountered and their algorithms well-known. Sorting is a good example of a task found in many different applications. Here it is the job of the programmer to determne which algorithm best fits the needs of his or her particular data set and determine the run-time efficiency of the choice made. Other tasks are specific to a particular system and the programmer must develop his or her algorithm. He or she must prove that the algorithm written is correct, robust, and efficient. The programmer should be guided in his or her composition of a correct, efficient algorithm by asking two questions:
* Can I solve this problem if I have solved the same problem of smaller size? (by recursion)
* Is this problem like, or can it be transformed into, a problem I already know how to solve?
====Course Objectives====
The course will emphasize the following skills:
- Classification of problems by algorithmic technique: divide & conquer, greedy, dynamic programming, etc.
- Proving the correctness of an algorithm
- Determining the run-time efficiency of an algorithm
- Distinguishing problems for which no known efficient algorithm exists that solves all instances of the problem (problems considered to be intractable)
- Understanding what is meant by the class NP-Complete and how problems are determined to belong to this class
====Course Outline====
- Introduction to Algoritm Design: Stable Matching Text: Chapter 1
- Analysis of Algorithms: Recurrence relations The Master Method Text: Chapter 2
- Divide and Conquer Text Chapter 5
- Sorting Algorithms Instructor's Notes
- Graph Algorithms Text: Chapter 3
- Greedy Algorithms Text: Chapter 4
- Dynamic Programming Text: Chapter 6
- Network Flow Problems Text: Chapter 7
- NP-Complete amd Computational Tractability Text: Chapter 8
====Assessment Activities====
During the course of the semester there will be homework assignments, quizzes, a mid-term exam, a project, and a final. Some of the homework will be graded, but in general it will be just inspected to ensure each individual is making a conscientious effort to understand the material and keep up with the assignments. One difficulty with doing the outside work for this course is that the problems are often sufficiently different from the worked examples and sufficiently difficult that the amount and type of repetition that one gets from say doing max-min or related rates problems in calculus class is not duplicated here. It is much more important that you put in an honest effort of your own or have a productive collaboration with others (for all parties involved) than you turn in a correct solution that is not really yours.
Instead of grading the homework, there will be frequent quizzes based on the homework which will be a substantial component of the grade. You will be vulnerable for a short quiz based on the previous homework on the class immediately following the one in which the homework was discussed and solutions posted. (If an assignment is due on a Tuesday, it will be discussed on Tuesday and you will be vulnerable for a quiz on Thursday.) If there is more than one question on the quiz, each will be graded separately and treated as a separate quiz grade. For every six quiz grades recorded, you get to drop the lowest one.
The midterm will be the traditional closed book exam. The final will be an in-class takehome. You will be given ten problems to prepare in advance, and you will find four of them on the in-class portion of the exam. The in-class exam will be closed book and closed notes.
The class project will be to create a teaching document covering material not directly covered in class. Students will select from a list of topics and present a roughly ten page **//individual//** presentation of the material with some worked examples. The contributions will be submitted electronically and be formed into a class generated //text.//
====Grading Policy====
^Activity ^Percentage^
^Homework | 10 |
^Quizzes | 25 |
^Midterm | 20 |
^Project | 20 |
^Final |25 |
====Attendance====
You are expected to be an adult and attend class unless ill or otherwise unable due to special circumstances. I will take attendance to learn your names and to detect an unusual pattern of absences, but attendance will not directly affect your grade. The penalty for missing class will be missing the immediacy of the class discussion and missing the ability to ask questions of your own or benefit from the questions of others. Missed quizzes will not be made up. Each missed quiz will count as 0 and reduce the number of low quiz grades that you are able to drop. If for any reason you are unable to be in attendance for the midterm, you must notify the office and the instructor **//before the class//** and make arrangements for making it up before the exam is to be returned.
====Special Needs====
Students with special needs should notify the instructor at the beginning of the semester so that appropriate arrangements can be made to accommodate these needs.
====Academic Honesty=====
**Thou shalt not cheat!!** You more than anyone else will know when you are doing it. Collaboration in science is generally a good thing if both parties are benefitting. Stealing somebody else's work is **not** collaboration. Given the format of this class, the opportunities for dishonesty are limited. You will be cheating mostly yourself if you appropriate the homework solutions or the answers to the take home questions from somebody else, because you will be unlikely to recreate them on the quiz or exam if you have not put in an adequate amount of your own thought and effort. The pricipal area for dishonesty in this course arises from the project. You will read and study other material surrounding your topic, but you must not plagarize this material. The project piece is to be in your own words and convey your own understanding of the material. Obviously copying from others or from smuggled in notes or electronically accessible material during a test or quiz is cheating and will be severely punished when detected.