Computer Science 431

Algorithms

Spring 2013, The College of Saint Rose

Instructor: | Dr. James D. Teresco, Albertus Hall 400-2, (518) 485-3755 | |

Electronic mail: | terescoj AT strose.edu (best contact method) | |

Class URL: | [Link] | |

Class hour: | Tuesday, Thursday 9:25-10:40, Albertus 205 | |

Office hours: | Monday, 2-3:30, Wednesday 1:30-2:30, and by appointment | |

Disclaimer

Everything on this syllabus is subject to change. Changes will be announced in class and updated in the online version of the syllabus.

Course Objectives

From the course catalog: "This is a course on design and analysis of algorithms. It is organized around algorithm design techniques, including exhaustive search, divide-and-conquer, dynamic programming, greedy algorithms, and backtracking. The mathematical analysis of algorithm complexity is emphasized throughout the course."

Prerequisites

Texts

The required text for the course is * Introduction to The Design and Analysis of Algorithms, Third Edition*
(Addison-Wesley, 2012, ISBN 0-13-231681-1) by Anany Levitin. This is available from
the Saint Rose Bookstore (and elsewhere). If you buy elsewhere,
be sure to get the correct edition.

Lectures

Everyone is expected to attend class and participate in discussions. There is no formal attendance policy, but a lack of regular attendance is certain to result in lower grades on assignments and exams. Do not expect sympathy if you are struggling but are rarely seen in class and during office hours. Supplemental readings are listed on the lecture and reading schedule. Of course you are encouraged to do the reading, and you will benefit from doing so, but all important topics will be covered in class.

Be prompt, prepared, and ready to focus on the day's topics. This
should go without saying, but this means your phones and other devices
not being used *exclusively* to follow along with class materials
and/or to take notes must be powered off. You may bring food or drink
to class, as long as you are not a distraction to your classmates or
instructor.

Most lectures will include a small assignment due at the start of the next class. Some lectures will begin with a short pop quiz. No late submissions of these "lecture assignments" or quizzes will be accepted, as they will often be discussed in class on the due date or immediately following the quiz. Some assignments will be graded for correctness, while others will be graded based on whether an honest effort was made.

The lecture and reading schedule has a link to a web page for each lecture highlighting the day's topics, listing class examples, and the lecture assignment due the next class. The notes used to guide in-class presentations are also available as PDF files linked from the lecture and reading schedule.

Problem Sets

A series of problem sets will be assigned approximately weekly. The number of points available will vary with the complexity of the assignment.

Some problems sets will require programming. For programming
assignments, you may develop your programs anywhere (computers in the
lab, your own PC, *etc.*) but grading will be done using
the Saint Rose Computer Science Linux systems unless otherwise specified. It is your
responsibility to ensure that your program works on the grading
platform. Programming assignments will be graded on design,
documentation, style, correctness, and efficiency.

Most problem sets will require you to analyze algorithms and data structures, often including formal proofs. Your solutions should be written clearly and concisely. You should rewrite your proofs once you have worked them through once to ensure they are clear and flow well.

You are encouraged learn to use the LaTeX mathematical typesetting system. There will be some extra credit opportunities for those who choose to learn and use LaTeX, but you will not be required to use it. LaTeX is a powerful system, especially for typesetting mathematical formulas, and learning it will come in handy for typesetting this semester's assignments, (and hopefully, for much of your career as computer scientists).

Unless otherwise specified, late problem sets may be turned in with a
penalty computed as *1.08 ^{h}%*, where

Exams

There will be two exams during the semester, plus one during finals period. The regular exams are tentatively schedule for late February and early April. The two regular exams will likely include in-class and take-home portions. The final exam will take place on Monday, May 6 at 10:45 AM.

Grading

Grades for individual assignments and exams
are not scaled. Any scaling deemed appropriate will take place at
the end of the semester by adjusting the thresholds. The
following thresholds *may* be adjusted downward (thereby raising
grades) but will never be adjusted upward.

| Scale: | ||||||

Lecture Assignments/Quizzes | 10% | A >= 93% | A- >= 90% | ||||

Problem Sets | 40% | B+ >= 87% | B >= 83% | B- >= 80% | |||

Exam 1 | 15% | C+ >= 77% | C >= 70% | ||||

Exam 2 | 15% | D >= 65% | |||||

Final Exam | 20% | F < 65% | |||||

Attendance

Every college student should be motivated to attend every lecture and
lab meeting for all the right reasons (*e.g.*, desire for knowledge,
desire to get the most out of every very expensive minute, *etc.*). As
college students, you understand that regular attendance is essential
to your ability to master the course material.

Therefore, there is no formal attendance policy. You are expected to attend regularly, and should still see the instructor about any excused absences. An excused absence may be any of the following:

- A documented athletic or academic event that conflicts with a class meeting. The required paperwork must be presented in person at least one week prior to the event.
- A family emergency.
- Personal illness.

While there is no formal penalty for unexecused absences, missing class regularly will be considered a sign that you are not taking the course seriously. History shows that students who are frequently absent perform poorly on graded work. Do not expect compassion when final grades are assigned or extensive extra help if you do not understand a topic that was covered while you were absent without a valid excuse.

Disability Accomodations

If you are a student with a documented disability and require academic accommodations please register with Lynn Cantwell, the Director of Services for Students with Disabilities, located in the Academic Support Center on the 2nd floor of St. Joseph Hall (campus extension 2335 or 518-337-2335, off campus) for disability verification and for determination of recommended reasonable academic accommodations. After you have made arrangements with that office, please see me to discuss your accommodations. Please remember that timely notice will help avoid a delay in your receipt of accommodations.

Academic Integrity

You are encouraged to discuss the concepts related to course assignments and exams with your classmates. This is an essential part of a healthy academic environment. However, work submitted for grading must be your own (or the combined work of group members, for group assignments). Any unauthorized copying or collaboration is considered a breach of academic integrity and will not be tolerated. Academic dishonesty cases are unpleasant and uncomfortable for everyone involved. You are responsible for reading and understanding The College of Saint Rose Policy on Plagiarism and Academic Integrity.

The minimum penalties for a first violation will include failure (0 grade) for the assignment or exam in question and the filing of a Academic Dishonesty Report Form with the Registrar's office. A second violation will result in failure of the course and a second Academic Dishonesty Report Form.

If there is any doubt about the degree of collaboration allowed or the
permitted sources for a particular assignment, please ask for
clarification **before** collaborating or consulting the source.
Any such collaborations or sources must be cited properly.