Algorithm Design and Analysis August 25, 2008Pennsylvania State University CSE 565, Fall ’07Adam Smith Handout 1Course InformationCourse Staff Room Email Office HoursProf. Adam Smith IST 338K [email protected] Wed. 1:00-3:00pmT.A. Xingjie Liu [email protected] TBDLectures MWF 11:15-12:05pm, Osmond Building, Room 109.Webpage http://www.cse.psu.edu/~asmith/cse565/ Check it often.Angel: http://cms.psu.edu/ Make sure you read Angel mail often.Syllabus Classical algorithms; techniques for the design and analysis of efficient algorithms. Top-ics include graph algorithms; divide-and-conquer algorithms and recurrences; dynamic pro-gramming; greedy algorithms; amortized analysis; network flow; randomized and approxima-tion algorithms; parallel algorithms; non-determinism and NP-completeness.Prerequisite An undergraduate level course in algorithms and data structures, such as CSE 465.This is not an introductory course. Students who have not previously taken an algorithmsclass should take CSE 465 instead. You should also be comfortable reading and writingmathematical proofs.Background Survey and Photograph The Angel page for this course contains a short surveyon your background, goals, and knowledge. One of the survey’s requirements is that you posta recognizable photo of yourself on your Angel account. This helps us get to know you.Please complete the survey by Friday, August 29 (or within a week of enrolling in the course,whichever is later). The survey counts as your first assignment.Textbook Jon Kleinberg and´Eva Tardos, Algorithm Design, Addison-Wesley, 2005.A useful (but not required) reference for background material is: Cormen, Leiserson, Rivestand Stein, Introduction to Algorithms, MIT Press, 2001.Evaluation The grade will be calculated as follows:Weekly homework 40%Midterm exam 1 20% (Tue, Sep. 30, 8:15pm)Midterm exam 2 20% (Tue, Nov. 18, 8:15pm)Final exam 20% (t.b.d.)Homework There will be weekly problem sets, due Fridays before the beginning of class.Late homework will generally not be accepted. If there are extenuating circumstances, youshould make arrangements at least 48 hours in advance with the instructor. Only seriousexcuses will be considered in cases where prior arrangements were not made.You should be as clear and concise as possible in your write-up of solutions. Understandabilityof your answer is as desirable as correctness, because communication of technical material is1an important skill. A simple, direct analysis is worth more points than a convoluted one, bothbecause it is simpler and less prone to error and because it is easier to read and understand.Points may be subtracted for illegible handwriting and for solutions that are too long.Programming Assignments Some of the problems on the problem set may take the form ofprogramming assignments. Details of language and platform will be provided closer to theassignments’ due date.“I’ll take 20%” option Partial credit is only given for answers that make significant progresstowards correct solution. Understanding whether a solution is correct is an important skill.If you realize that you cannot solve a problem, you have an option of writing “I’ll take 20%”instead of your answer. In this case, you will get 20% for this problem (or part of the problem).If you do write an answer, that answer will be graded and your score will be 0 if your solutionis completely wrong. You cannot use the 20% option on programming problems.Optional problems Some homework assignments will include optional problems, marked by ?.Later, if you ask me for a recommendation or express an intrest in working on a researchproject with me, I will definitely check how well you did on the optional problems. “I go for20% option” is not available for optional problems.Partial Grading Homework assignments will each consist of several problems. We will providesolutions to all problems but will only grade a subset of the problems (not known to you inadvance). You are welcome to ask for feedback on ungraded solutions after you have read theofficial solutions. All optional problems will be graded.Collaboration and Honesty Policy Collaboration on homework problems, with the exceptionof programming assignments, is permitted, but not encouraged. If you choose to collaborateon some problems, you are allowed to discuss each problem with at most 3 other studentscurrently enrolled in the class. Before working with others on a problem, you should thinkabout it yourself for at least an hour. Finding answers to problems on the Web or from otheroutside sources (these include anyone not enrolled in the class) is strictly forbidden.You must write up each problem solution by yourself without assistance, even if you collaboratewith others to solve the problem. You must also identify your collaborators. If you did notwork with anyone, you should write ”Collaborators: none.” It is a violation of this policy tosubmit a problem solution that you cannot orally explain to an instructor or TA.No collaboration whatsoever is permitted on exams or quizzes.Violations of this policy will be dealt with according to University