CSE 21: Math for Algorithm & System Analysis

Course Objectives: This course introduces mathematical tools for the qualitative and quantitative analysis of algorithms and computer systems. It also explores the mathematical theory of discrete structures useful in modeling computational processes and hence in designing the same. Topics to be covered include basic enumeration and counting techniques; recurrence relations; graph theory; asymptotic notation; elementary applied discrete probability. Other related topics will be presented as time permits.

Textbook: Discrete Mathematics with Applications (3rd Edition) by Susanna S. Epp

We'll be focusing on the following topics:

• Basic counting
• Discrete probability
• Recursion
• Efficiency of algorithms
• Basic graph theory

Lecture notes: see schedule

WebBoard: webboard.ucsd.edu

Gradesource: CSE 21 summer 2006

Grading:

• Homework (0%)
• Homework will not be graded. However, most of the test problems are directly from homework (or with trivial alternations). So doing the homework problems is a good way to secure your score in the tests.
• Homework assignment on web.
• Homework solutions: on the back of the textbook, or on web.
• quizzes (30%)
• There is a quiz at the beginning of almost every lecture day.
• Two types of quizzes: individual & teamwork.
• For individual quizzes you'll have to work on your own, close-book and close-note. Individual quiz problems are very similar to the homework problems.
• For teamwork quizzes you'll work on a team of 2-3 people, open-book, open-note with loud discussions. Teamwork quiz problems are more challenging.
• You can drop the lowest 2 scores of your quizzes.
• 2 midterms (30%)
• 15% each
• Aug 21 and Aug 31, on class.
• No book, no calculators. You can bring one double-sided 8.5x11 page of handwritten notes.
• 1 final (40%)
• Sep 9 (Saturday) 7pm - 10pm @ WLH 2112
• No book, no calculators. You can bring one double-sided 8.5x11 page of handwritten notes.

Regrading policy: You have the right of appeal for grading on all tests; however, an appeal (except for addition errors) covers the entire test, and may result in an unfavorable judgment on another problem. You have one week from the time the tests are returned to make appeals, including addition errors on your score. Appeals must be made in writing and turned in to the TA.

Academic honesty: All students are expected to be familiar with and abide by the rules of UCSD Policy on Integrity of Scholarship as described in the UCSD General Catalog. In case of cheating, such policy will be enforced. This means an F grade in the course, and action by the Dean of your college (probation or suspension from UCSD). You are allowed (and encouraged) to collaborate with other students in doing the homeworks. Discussion is allowed within your 2-3 member group for teamwork quizzes. No form of collaboration is allowed during the individual quizzes, midterms and final exam.