home & syllabus
The Final Exam will be given on Thursday, Dec. 11, from 7:00 to 10:00 p.m.
in the usual room WLH 2205. It will be a CLOSED BOOK exam. However, you can
bring two 8 1/2 by 11 sheets with hand-written notes (on both sides) if
you want. You can also use calculators if you would like, but they won't
really be necessary.
- Time
& Place
- M / W 5:00 - 6:15; WLH 2205 (lecture)
- M 2:00 - 2:50; CENTR 214 (discussion section)
- Instructor
- Professor Ron Graham (graham@ucsd.edu)
- office hours: W 3:00-4:00; CSE bldg (EBU3B) 2138
- Teaching Assistant
- Ling Zhang (lizhang@cs.ucsd.edu)
- office hours: M/Tu 3:00-4:00; CSE bldg (EBU3B) B240A
- 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.
- Course Description
- This course will provide an introduction to the discrete mathematical tools needed to analyze algorithms and systems. Enumerative combinatorics: basic counting principles, inclusion-exclusion, discrete probability, decision trees, functions, asymptotics.
- Textbook
- Required: Susan Epp, Discrete Mathematics with Applications, 3rd ed.
- Recommended: Probability, 2nd ed. in Schaum's Outlines series.
- Grading
- There will be a midterm and a final for the course. The midterm will count for 30% of the total grade and the final will count for 70%. Homework problems will be assigned each Monday, but will not be collected or graded. Solutions to the homework problems will be posted a week after the problems are assigned. It should be pointed out that since most of the test questions will be strongly based on these homework problems, it is definitely in your best interest to have a complete understanding of how to solve such problems.
- In addition, from time to time I will assign extra credit problems. These problems will be more challenging than the usual homework problems, and offer you a chance to really impress the instructor!
- Approximate Schedule
-
Date Topic Reading (Epp) 9/29 - 10/1 Sequences, Induction 4.1 - 4.4 10/6 - 8 Counting 6.1 - 6.3 10/13 - 15 Combinations 6.4 - 6.5 10/20 - 22 Binomial Coefficients 6.6 - 6.7 10/27 - 29 Probability 6.8 - 6.9 11/3 - 5 Decision Trees, Midterm Schaum, Chap. 4 11/10 - 12 Functions 7.1 - 7.4 11/17 - 19 Recursions 8.1 - 8.4 11/24 - 26 Growth of Functions, Efficiency of Algorithms 9.1 -9.5 12/1 - 3 Graphs, Trees 11.1 - 11.2, 11.5 12/11 Final exam -