Computer Science 385
Analysis of Algorithms

Spring 2011, Siena College



Dr. James D. Teresco, Roger Bacon 332, (518) 783-4171
Electronic mail: jteresco AT (best contact method)
Class URL: [Link]
Class hour: Tuesday, Thursday 10:00-11:20, Roger Bacon 328
Office hours: TBA, by appointment


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 course continues previous work in the design and analys of algorithms. Data structures considered may include, for example, binary trees, AVL trees, B-trees, hash tables, and multi-dimensional trees. Algorithms for searching, inserting into, and deleting from these structures will be discussed. A variety of sorting algorithms (possibly including radix sort, heapsort, mergesort and quicksort) will be studied. Algorithms for other problems such as k-selection, minimum cost spanning trees, connectivity, and shortest paths will be analyzed. NP-complete problems will be introduced."

Course Goals

  1. To learn about advanced algorithms and data structures.
  2. To develop the ability to analyze an algorithm for time and space complexity.
  3. To utilize and further develop proof techniques introduced in Discrete Structures to formalize this analysis.
  4. To enhance programming skills by implementing, testing, and utilizing algorithms.
  5. To learn to use LaTeX to typeset a technical document.

Missions and Learning Goals

Please be sure you are familiar with the following statements of mission and learning goals by visiting these links:



The required text for the course is Introduction to the Design and Analysis of Algorithms, Second Edition (Addison Wesley, 2007, ISBN 0-321-35828-7) by Anany Levitin. This is available from the Siena Bookstore (and elsewhere). If you buy elsewhere, be sure to get the correct edition.


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 stuggling 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 approximately 8 problem sets will be assigned. 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 Siena 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 will learn to use the LaTeX mathematical typesetting system in early assignments and make extensive use of it throughout the semester (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.08h%, where h is the number of hours late. Extensions will only be granted in serious situations and requests must be accompanied by written documentation from the appropriate college office (e.g., Academic Affairs for family emergencies, Student Affairs for personal illness). You can find a Java program that prints out a table of the late penalties here. Work turned in after solutions have been made available cannot receive credit. All assignments are to be submitted electronically unless otherwise specified. Please submit plain text where appropriate and PDF otherwise (generated from LaTeX source). Please avoid other formats such as Word documents. If in doubt about a file format, please check first. Keep a copy of all submissions for yourself.


There will be two exams during the semester, plus one during finals period. The two regular exams will be take-home exams. The final exam will be scheduled by the Registrar during the exam period in May.


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 above thresholds. The following thresholds may be adjusted downward (thereby raising grades) but will never be adjusted upward.


Lecture Assignments/Quizzes 10% A >= 93% A- >= 90%
Problem Sets 40% B+ >= 87% B >= 83% B- >= 80%
Exam 1 15% C+ >= 77% C >= 73% C- >= 70%
Exam 2 15% D+ >= 67% D >= 63% D- >= 60%
Final Exam 20% F < 60%

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 Catalog Statement on Academic Integrity and the Computer Science Department's Academic Integrity statement. 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 Integrity Violation Accusation Form. A second violation will result in failure of the course and a formal letter describing your misconduct will be sent to the head of the Computer Science Department and the Office of Academic Affairs.

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.

Additional College Policies

Please be sure you are familiar with the following College policies by visiting these links: