CS 1510 Syllabus Fall 2014Course Home Page: https://groups.google.com/forum/#forum/pitt-cs-1510-fall-2014 !This group will be used for announcements. The course group is the best place to ask general questions (e.g.a question about a particular homework problem). This group will be monitored by the instructor, but oftenother students can provide a quicker answer than the instructor.Instructor: Kirk PruhsOffice: 6415 Sennott SquarePhone: 624-8844Email: [email protected] Please use the course group for general questions about assignments, etc. I do notregularly read email at other addresses, such as my gmail account.Office hours: 10:45-12:00 Monday and Friday, and 10:45 - 11:30 on Wednesday. If you can catch me in myoffice on these days, I’m probably happy to talk to you unless I have a paper/grant deadline.TA: Michael NugentOffice: 6406 Sennott SquareEmail: [email protected] Hours: 1:00 -2:30 Tuesday and 10:30-12:00 ThursdayCourse Meeting: The course will meet Mondays, Wednesdays and Fridays from 9:30-10:45 in 5129 SennottSquare. There will be approximately 27 classes, which is standard for a semester course.Text: The official text is Foundations of Algorithms by Neapolitan and Naimipour. Any edition of thetextbook is fine for this class. You are welcome to consult other texts if you prefer. Some other good textsare authored by: 1) Udi Manber, 2) Brassard and Bratley, 3) Cormen, Leiserson, Rivest, and Stein 4) SaraBaase, and 5) Kleinberg and Tardos. Many students don’t find a textbook particularly useful. Disclaimer:If you choose to not follow the official text, then you may not later complain that you were disadvantagedbecause you opted not to use the official text.Prerequisites: CS 1501, and CS 1502. If you take this class without these prerequisites, you forfeit youright to complain that the class is at an inappropriate level.Course Content: The main goal of the course is to learn to think algorithmically like a “real” computerscientist. This course is different than CS 1501 in that we will be designing our own algorithms, as opposedto learning algorithms. Most class time will be devoted to examples of algorithm design for particularlyinteresting problems. There will be homework assignments due almost every class. It is expected that mostof your learning will come from the process of solving the homework problems. Exams will in large part bebased on the homework. We will cover the following topics in the following order:Deciding the Correctness of Algorithms (Chapter 4)Dynamic Programming (Chapter 3)Reductions and NP-completeness (Chapter 9)Parallel Algorithms (Chapter 10)Grading: Grades will be based on homework, classroom participation, and two midterm exams. Homeworkwill constitute 30% of the final grade. Midterm exams will constitute 60% of the final grade. Attendancewill be taken and, along with class participation, will count for the remaining 10% of the grade. In the past,most students have found the course material quite challenging.I will subjectively set the grading scale at the end of the semester. You are not in competition withother students. I have no set numbers of A’s, B’s etc. I strongly suggest you cooperate with each otherto understand the material. This is in all students’ best interests. If a student’s homework scores areconspicuously/suspiciously higher than a student’s exam grades, I reserve the right to base the course gradeon only the exam scores, and classroom participation.Homework Policy: You may do you homework in groups of 2 or 3 people if you wish. Each group needonly provide one write-up. Write-ups must use LATEX, http://en.wikipedia.org/wiki/LaTeX. You maydiscuss problems with any student in the class with the provisos that you shouldn’t feed others completesolutions, and you must acknowledge collaborations in the write-up. You may not seek solutions on thewww, in other books, from friends outside the class, etc.All homework is due at the start of class on the date due. No late homework is accepted. The homeworkwill be graded by the TA. Many students will find some problems demanding. It is not expected that allstudents will be able to answer all the homework questions.Exam Scoring Appeal Policy: You may submit an appeal in writing if you believe that your solutionfor a problem on an exam is ”essentially fully correct”. No appeals are allowed for additional partial credit;Partial credit is too subjective. Appeals will not be accepted earlier than 1 class after the exams werereturned, and will not be accepted later than 2 classes after the exams were returned. Of course any clericalerrors can be corrected. Note that the problem will be regraded, there is a possibility that the new gradewill be lower than the original grade.Disability Policy: If you have a disability for which you are or may be requesting an accommodation,you are encouraged to contact both your instructor and Disability Resources and Services, 216 WilliamPitt Union, (412) 648-7890/(412) 383-7355 (TTY), as early as possible in the term. DRS will verify yourdisability and determine reasonable accommodations for this course.Missing tests: If you are going to miss a test for unavoidable reasons then before the exam (or as soon aspossible) you must contact me. If this is not possible, contact the computer science departmental secretaryat 624-8490.Cheating Policy: I have no tolerance for cheating. If you are caught cheating, you will receive an F gradefor the