DOC PREVIEW
UCSD CSE 101 - Course Description

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Design and Analysis of Algorithms – CSE 101Basic Information: Spring 2004Instructor: Russell ImpagliazzoClass: Tuesday and Thursday, 11-12:20 Center 212;Mandatory discussion section: Friday, 3-4, Solis 104101 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 atannouncements on the class website.202 Professor Office Hours : W 2:00-4:00, in 4111 AP &M . 101 students may attend, but 202students have priority (may change)email: [email protected]: www-cse.ucsd.edu/classes/sp04/cse101TAs: Huayong Hu, Jia Mao, and Sean O’RourkeTA Office Hours: TBA.Prerequisites: CSE 21, CSE 12.Text Books: Jeff Edmonds, Thinking About Algorithms Abstractly, Avaiable from class website. Thisis a work in progress. Some sections that we won’t cover have been omitted from this version.Please send comments to [email protected]. (In postscript and pdf. You’ll need to print it yourself.)Johnsonbaugh and Schaefer, Algorithms. This was ordered late, so might not be available firstweek of classes.Note: There are several topics where you can use either textbook. Use the one that makes mostsense 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, amid-term exam, and a final exam.Evaluation: Homework will account for 30 % of the grade, the mid-term, 30%, and the final will accountfor the remaining 40 % of the grade. The calibration homework does not count for credit. Thebest 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 realmid-term grades. Sorry, no practice final.Ethics and Academic Dishonesty In the past, there has been epidemic cheating in this class. Forexample, dishonesty caused 25 % of the class to fail in 1997. For this reason, some rather intrusiverules 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. Problemsshould be solved by the group, not divided up between group members. Each member of a groupshould participate in discussions about each problem. The front page should be signed by eachmember of a group; this is interpretted as the statement: ”I participated in discussion for eachproblem, and have read and understood the answers here, which are summaries of our discussion.” Ifyou wish to modify this statement, write and sign the modified statement instead. If the statement1is not true of some of the problems, add ”except for problems ...”. You will not receive credit forthese 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 coursetexts 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 tohomework problems. In this case, the student should write up the final solution without consultingthis text or source, and should give an acknowledgement of the text or source on the first page oftheir 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 orwritten 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-pagefor 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 theTAs 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 notesand 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 theoret-ical 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 andcompleteness, i.e., “mathematical style”. It is your obligation to provide a compelling argumentthat forces the reader to believe the result, not just notes from which an argument could be con-structed. 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 analgorithm, the following two things should always be included, unless the problem explicitly saysnot 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 aremerely expected to present a solution and give some informal justification. Such problems will bedesignated 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 usagedata on a variety of inputs (which will be either completely specified or specified as a distributionon random instances). This implementation may be done in any language, and be run on anymachine. Your solution should only include a brief description of your program; in particular, wewill not read actual code, so you needn’t hand it in. You should hand in only a description of yourprogram, 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 forthe various inputs you ran the program on. Discuss whether the timing results seemed consistentwith the asymptotic


View Full Document

UCSD CSE 101 - Course Description

Download Course Description
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Course Description and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Course Description 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?