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

Information about the Instructor

Catalog Description

Prerequisite: CS155 or instructor consent.

Textbook: Required

• We shall cover topics from chapters 1, 2, 3, 4, 7, 15, 16, 30, 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 around $22. Please have the correct change. Additional lecture notes will be distributed during the semester (free of charge).

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 due Thursday, February 6, 2014.
  
• Homework Two due Thursday, February 20, 2014.
  
• Homework Three due Thursday, March 13, 2014.
  
• Homework Four due Thursday, April 3, 2014.
  
• Homework Five due Thursday, April 24, 2014.
  
• Cover sheet for all assignments
  

Term-Project and In-Class Presentation [ Schedule of Oral Presentations]

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, 2014. The last day to drop with a full refund is February 4, 2014. According to University and Department guidelines, dropping after February 4, 2014, 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.
Students are responsible for understanding the policies and procedures about add/drop, grade forgiveness, etc. Refer to the current semester's Catalog Policies section at http://info.sjsu.edu/static/catalog/policies.html. Add/drop deadlines can be found on the current academic year calendars document on the Academic Calendars webpage at http://www.sjsu.edu/provost/services/academic_calendars/. The Late Drop Policy is available at http://www.sjsu.edu/aars/policies/latedrops/policy/. Students should be aware of the current deadlines and penalties for dropping classes. Information about the latest changes and news is available at the Advising Hub at http://www.sjsu.edu/advising/.

Consent for Recording of Class and Public Sharing of Instructor Material

University Policy S12-7, http://www.sjsu.edu/senate/docs/S12-7.pdf, requires students to obtain instructor's permission to record the course. Common courtesy and professional behavior dictate that you notify someone when you are recording him/her. You must obtain the instructor's permission to make audio or video recordings in this class. Such permission allows the recordings to be used for your private, study purposes only. The recordings are the intellectual property of the instructor; you have not been given any rights to reproduce or distribute the material.
Course material developed by the instructor is the intellectual property of the instructor and cannot be shared publicly without his/her approval. You may not publicly share or upload instructor generated material for this course such as exam questions, lecture notes, hands-on exercises or homework solutions without instructor consent.

Academic Integrity

Your commitment as a student to learning is evidenced by your enrollment at San Jose State University. The University Academic Integrity Policy S07-2 at http://www.sjsu.edu/senate/docs/S07-2.pdf 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 Student Conduct and Ethical Development website is available at http://www.sjsu.edu/studentconduct/. Instances of academic dishonesty will not be tolerated. Cheating on exams or plagiarism (presenting the work of another as your own, or the use of another person's ideas without giving proper credit) will result in a failing grade and sanctions by the University. For this class, all assignments are to be completed by the individual student unless otherwise specified. If you would like to include your assignment or any material you have submitted, or plan to submit for another class, please note that SJSU's Academic Integrity Policy S07-2 requires approval of instructors.

• Anyone caught cheating (including copying the work of others) on any assignment in the class will receive a failing grade for the assignment, in addition to other sanctions that are permitted by the University, including but not limited to the filing of a report with the Dean of Student Services and expulsion from the University.

Campus Policy in Compliance with the American Disabilities Act

If you need course adaptations or accommodations because of a disability, or if you need to make special arrangements in case the building must be evacuated, please make an appointment with me as soon as possible, or see me during office hours. Presidential Directive 97-03 at http://www.sjsu.edu/president/docs/directives/PD_1997-03.pdf requires that students with disabilities requesting accommodations must register with the Accessible Education Center (AEC) at http://www.sjsu.edu/aec to establish a record of their disability.
In 2013, the Disability Resource Center changed its name to be known as the Accessible Education Center, to incorporate a philosophy of accessible education for students with disabilities. The new name change reflects the broad scope of attention and support to SJSU students with disabilities and the University's continued advocacy and commitment to increasing accessibility and inclusivity on campus.