San José State University
Computer Science 255
Design and Analysis of Algorithms

Information about the Instructor

Catalog Description

Prerequisite: CS155 or instructor consent.

Textbook

• We shall cover topics from chapters 1, 2, 3, 4, 7, 15, 16, 34, and 35 from the textbook.
• We shall also cover some topics that are not in the textbook.
• Before reaching the end of a chapter, I shall announce which topics from the following chapter we shall cover.
• A copy of my notes will be sold at the begining of the semester. The first part of the lecture notes will cost $8. Please have the correct change. Additional lecture notes will be distributed during the semester (free of charge).
• Introduction (6 slides per page)
• Introduction (2 slides per page)

Learning Outcomes

• know how to analyze algorithms using mathematical tools, such as asymptotic analysis, induction, recurrence relations, etc.
• have a full understanding of the four algorithmic techniques: greedy, divide-and-conquer, dynamic programming, and branch-and-bound
• have studied a range of probabilistic algorithms, such as genetic algorithms, and seen how they can be used to solve optimization problems
• understand the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction
• know how to prove that certain problems are NP-complete
• know when to use and also how to analyze approximation algorithms
• understand the importance of randomized, parallel and distributed algorithms
• appreciate the beauty of algorithms

Course Requirements

• Homework One Thursday, February 14, 2008.
  
• Homework Two Thursday, February 28, 2008.
  
• Homework Three Thursday, March 20, 2008.
  
• Homework Four Thursday, April 10, 2008.
  
• Homework Five Thursday, May 1, 2008.
  
  
• Cover sheet for all assignments
  

Term-Project and In-Class Presentation

Schedule of Oral Presentations
There will be a group project. Each group consists of two or three students. The group chooses a topic, writes a term-project, and gives an in-class, 20 or 30 minute presentation (10 minutes per student) at the end of the semester during class time (dates to be announced later in the semester). A typical term-paper will involve a literature search on the proposed problem and the comparison of several algorithms to solve the chosen combinatorial optimization problem. It will definitely include the implementation and the testing of the different heuristics on a large number of problem instances of the chosen optimization problem. A two-page proposal of the student's chosen topic is due by Tuesday, March 11, 2008. The term-paper is due on Tuesday, May 6, 2008.

Exams:

The Midterm is one hour and 15 minutes long, and all exams are in-class, closed-book and comprehensive. You will get back your exam one week later. We will go over it in class and then I will collect it again and it will stay with me.

Class Attendance

• Class attendance is strongly encouraged. In class, we shall cover many topics and examples that are neither in the class notes nor in the textbook. If you miss a lecture, it is your responsibility to find out what was covered in class (this includes: handouts given out during your absence, corrected typos and errors, examples discussed in class - that are neither in the book nor in the notes - clarifications and changes made to assignments or the project, etc...).
• You are required to turn off and not use your cell phone in class. You are also required to turn off your computer and put it away since you will not need it during class.

Grading Policy

Assignments 15%
Term-project 25%
In-class Presentation 5%
Midterm Exam 25%
Final Exam 30%

[97, 100] A+
[90, 97) A
[87, 90) A-
[85, 87) B+
[80, 85) B
[77, 80) B-
[75, 77) C+
[70, 75) C
[65, 70) C-
[56, 65) D+
[53, 56) D
[50, 53) D-
[0, 50) F

Add/Drop Policy

For those wishing to add this course, the deadline is February 11, 2008. The last day to drop with a full refund is February 4, 2008. According to University and Department guidelines, dropping after February 4, 2008, requires a serious and compelling reason to drop a course. Grades alone do not constitute reason to drop a course. Students who stop attending without officially dropping will be issued a U at the end of the semester which is counted as an F in calculations of GPA. See University Catalog.

Academic Integrity

Your own commitment to learning, as evidenced by your enrollment at San José State University, and the University's Academic Integrity Policy requires you to be honest in all your academic course work. Faculty members are required to report all infractions to the Office of Student Conduct and Ethical Development. The "Policy on Academic Integrity" can be found here.

Disability Resource Center

If you need course adaptations or accommodations because of a disability, or if you need special arrangements in case the building must be evacuated, please make an appointment with us as soon as possible, or see us during office hours. Presidential Directive 97-03 requires that students with disabilities requesting accommodations must register with DRC to establish a record of their disability. (Please let us know as soon as possible in order to more effectively accommodate your needs.)