Basic Information Spring 2004 Instructor Russell Impagliazzo Class Tuesday and Thursday 11 12 20 Center 212 Mandatory discussion section Friday 3 4 Solis 104 101 Professor Office Hours MW 12 00 2 00 in 4111 AP M or in 4218 AP M across corridor Note I may need to cancel or delay office hours occassionally for visitor talks Please look at announcements on the class website 202 Professor Office Hours W 2 00 4 00 in 4111 AP M 101 students may attend but 202 students have priority may change email russell cs ucsd edu webpage www cse ucsd edu classes sp04 cse101 TAs Huayong Hu Jia Mao and Sean O Rourke TA Office Hours TBA Prerequisites CSE 21 CSE 12 Text Books Jeff Edmonds Thinking About Algorithms Abstractly Avaiable from class website This is a work in progress Some sections that we won t cover have been omitted from this version Please send comments to jeff cs yorku ca In postscript and pdf You ll need to print it yourself Johnsonbaugh and Schaefer Algorithms This was ordered late so might not be available first week of classes Note There are several topics where you can use either textbook Use the one that makes most sense to you or use both and triangulate on the ideas Abbreviations JS for Johnsonbaugh and Schaefer JE for Jeff Edmonds Assignments There will be a calibration homework not for credit four homework assignments a mid term exam and a final exam Evaluation Homework will account for 30 of the grade the mid term 30 and the final will account for the remaining 40 of the grade The calibration homework does not count for credit The best 3 out of 4 homework assignments will be counted so each homework is worth 10 of grade There will be a practice mid term the mid term grade will be the better of the practice and real mid term grades Sorry no practice final Ethics and Academic Dishonesty In the past there has been epidemic cheating in this class For example dishonesty caused 25 of the class to fail in 1997 For this reason some rather intrusive rules have been instituted Students will be allowed to solve and write up all homework assignments in groups of size up to 4 All names should appear on the assignment Members of a group are responsible for all parts of any assignment with their names on it Problems should be solved by the group not divided up between group members Each member of a group should participate in discussions about each problem The front page should be signed by each member of a group this is interpretted as the statement I participated in discussion for each problem and have read and understood the answers here which are summaries of our discussion If you wish to modify this statement write and sign the modified statement instead If the statement 1 these problems but you also will not bear responsibility for them Students should not look for answers to homework problems in other i e other than the course texts and class notes texts or other sources e g Internet discussion groups or newsgroups However students may use other texts as a general study tool and may accidentally see solutions to homework problems In this case the student should write up the final solution without consulting this text or source and should give an acknowledgement of the text or source on the first page of their solutions Such a solution may be given partial or no credit if it too closely follows the source Not giving an acknowledement is academic dishonesty and will be treated as such This rule applies to any material found on the internet and to conversations with or written material from other people whether or not they are students in the class However it does not apply to material handed out in class or on the class web page for this year or to conversations with the instructor or teaching assistants Be sure to follow the following guidelines 1 Do not discuss problems with people outside your group except during office hours with the TAs or me 2 Do not share written solutions or partial solutions with other groups 3 Prepare your final written solution without consulting any written material except class notes and the class text 4 Acknowledge all supplementary texts or sources that had solutions to homework problems Standards for assignments Most assignments and exam problems will be mathematical or theoretical in nature and will require you to prove your answer correct Grading of all such problems homework and exam will be both on the basis of correctness and on logical consistency and completeness i e mathematical style It is your obligation to provide a compelling argument that forces the reader to believe the result not just notes from which an argument could be constructed In particular correct formulas or pseudo code are not a complete solution by themselves their significance and the logic of their application need to be explained A typical assignment is to design an efficient algorithm for a given problem When giving an algorithm the following two things should always be included unless the problem explicitly says not to a correctness argument showing why the algorithm solves the problem and a time analysis giving the order of the worst case runtime in O notation Some relaxation of this rule will apply to problems of a computational nature where you are merely expected to present a solution and give some informal justification Such problems will be designated by key phrases such as Find a solution and justify your answer One problem on each assignment will involve implementing an algorithm and reporting time usage data on a variety of inputs which will be either completely specified or specified as a distribution on random instances This implementation may be done in any language and be run on any machine Your solution should only include a brief description of your program in particular we will not read actual code so you needn t hand it in You should hand in only a description of your program specifying the basic algorithm used any modifications that you made to this algorithm the language used the performance characteristics of the machine used and timing information for the various inputs you ran the program on Discuss whether the timing results seemed consistent with the asymptotic analysis if not what in your opinion is the reason The TAs or I may ask to see a demonstration of your program on other instances Lateness Policy Late homework will be accepted until I give out an answer key and no later So you have to be no later than me I will also not accept homework