CSE 21A+B --- Winter 2013
Mathematics for Algorithm and Systems Analysis
Last Modified: 03/06/13
Instructor
Prof. Ron Graham |
Email: |
graham@ucsd.edu |
Office: |
EBU3B 2138 |
Office Hours |
When: |
Mon 2 - 4 and by appointment |
Where: |
CSE 2138 |
Teaching Assistants
Lucia Batman |
Email: |
kbatman@cs.ucsd.edu |
Office: |
EBU3B 2136 |
Office Hours |
When: |
Tue/Thurs 12:45-1:45pm |
Where: |
B240A |
Fjola Bjornsdottir |
Email: |
fbjornsd@eng.ucsd.edu |
Office: |
4254 |
Office Hours |
When: |
Monday 11am - 1pm |
Where: |
B240A |
Tutors
Nathan Chao |
Email: |
knchao@ucsd.edu |
Justin Hung |
Email: |
juhung@ucsd.edu |
Philip Jia |
Email: |
philipjia123@gmail.com |
Lisa Ke |
Email: |
lke@ucsd.edu |
Erik Lowe |
Email: |
ealowe@ucsd.edu |
Ricky Lui |
Email: |
s1lui@ucsd.edu |
Chapman Seto |
Email: |
caseto@ucsd.edu |
Jagtej Sodhi |
Email: |
jsodhi@ucsd.edu |
Hannah Thompson |
Email: |
hnthomps@ucsd.edu |
Matan Vardi |
Email: |
mvardi@ucsd.edu |
Xiaoqi Wang |
Email: |
xiw041@ucsd.edu |
Times and rooms for the tutors are posted in the calendar below. |
Please be aware there are two sections listed here with different times for finals and discussions.
Class Meetings - Section A
| Date | Time | Location |
Lecture |
Tue/Thur | 3:30pm - 4:50pm | PCYNH 109 |
Discussion |
Wed | 4:00pm - 4:50pm | CSB 001 |
Final Exam |
Tuesday 3/19/13 | 3:00pm - 6:00pm | PCYNH 109 |
Class Meetings - Section B
| Date | Time | Location |
Lecture |
Tue/Thur | 5:00pm - 6:20pm | PCYNH 106 |
Discussion |
Mon | 3:00pm - 3:50pm | CENTR 109 |
Final Exam |
Thursday 3/21/13 | 7:00pm-10:00pm | PCYNH 106 |
Forum
Please join class discussion group which is hosted on Piazza.
If you haven't received the email to join Piazza, click here.
Welcome Message
If you ever wondered "What sort of mathematics do I need
for computer science?",
this course will provide some of the answers. In particular, you will have the opportunity
to learn basic concepts about counting, permutations and combinations, decision trees, recurrences,
discete probability and graph theory, among other things. These are some of the essential ingredients
in the toolkit of every computer scientist.
You are welcome to browse around on this website.
There is a lot of useful material on-line. In particular, all homework, homework solutions,
and the midterm exams will be posted here, as will important announcements.
Course Description:
Please click here
for a detailed course description as given in the undergraduate course listing.
Grading:
I will compute a percentage score based on your coursework
and then assign a letter grade as follows:
  A     88.0 - 100%
  B     75.0 - 87.9%
  C     60.0 - 74.9%
  D     50.0 - 59.9%
  F     below 50.0%
Your percentage score is the weighted average of your scores in three areas: homework, midterms,
and the final exam. The weights below total 110%, but I'll cut 10% off the weight of
your weakest exam. Scores in the three individual areas are determined as follows:
Homework (15%)
I'll drop your lowest homework score.
Midterms (20% each), Final (55%)
If the class median on an exam is below 75% (which is typical), then
we normalize all scores upward so that the median is 75%. We
normalize by adding a fixed number of points to every score.
Scores are not capped at 100%. If the median on an exam is above 75%--- fantastic!
Extra Credit:
From time to time I will post Extra Credit problems. These will typically be more difficult
than the usual p/oblems, but solving them (or even working on them) could definitely
impress the instructor! Work on these problems can be handed in any time before the end of the Quarter.
Extra Credit problems will be posted
here.
Academic Integrity:
The UCSD policy on Academic Integrity is
here.
You should read it if you haven't already!
Announcements
The most recent announcements will posted first. It is a good idea
to check these from time to
time to be aware of changes in schedule, etc.
3/18/13 I have posted a corrected solution to the Final Practice Problem 24.
(Thanks to the student who pointed out the mistake in the earlier solution. It escaped
the TA's and me!).
3/15/13 I will have extended office hours on next Monday from 1 to 4.
3/13/13 Make sure you know when the
Final Exam for your section is.
As usual, it is a CLOSED BOOK exam but you can bring
two handwriteen sheets of
notes to the exam. You can also bring a calculator although it shouldn't be
needed since answers can be left in unexpanded form (using binomial coefficient
notation, n!, etc.).
3/12/13 I will post solutions to the practice problems tonight.
3/8/13 Some practice problems for the Final Exam are now posted.
Annoted solutions to these problems will
be posted sometime during next week.
2/27/13 I am moving my office hours next from the usual Monday
to
Wednesday, March 6 from 1 to 3.
2/27/13 Midterm #2 will be given on Thursday, 2/28/13. As usual, it will be CLOSED BOOK. However,
you can bring one 8 1/2 by 11 handwritten sheet of notes (written on both sides) to the test.
You can also bring a calculator although it shouldn't be needed since answers can be left
in unexpanded form.
2/25/13 The Practice Midterm #2 solutions are now posted, with a corrected version of Problem 1.
2/21/13 Homework #5 solutions are now posted, as is the Practice Midterm #2.
2/15/13 Homework #5 is now posted. It is fairly tough!
2/14/13 Homework #4 solutions are now posted.
2/7/13 Homework #4 is now posted.
2/6/13 Midterm solutions have been posted:
Section A
and
Section B.
1/31/13 Homework #3 solutions are now posted. Also,
the Midterm wasn't so easy! I'll give the "easy" solutions during the next lecture.
1/31/13 An (impossible) extra credit problem has been posted.
1/30/13 There will be no homework assignment on 1/31.
1/24/13 Don't forget that the
first Midterm will be held next Thursday, Jan. 31,
at the usual time and place. It is CLOSED BOOK but you can bring a single 8 1/2 by 11 handwritten
sheet of notes (both sides) to the exam. Calculators can also be used but shouldn't be needed
since answers can be left in unexpanded form.
1/24/13 Homework #3 and the solutions to Homework #2 are now posted.
1/22/13 The hypothesis in Extra Credit problem #2 has been very slightly modified!
1/17/13 Homework #2 is now posted along with solutions to Homework #1
1/17/13 We have even more tutors. Their hours will be posted on the calendar. Don't let them get lonely!
1/14/13 We now have more tutors. :-) Check out their hours on the calendar below..
1/10/13 The first homework assignment is now posted (in the Homework
Section near the bottom of the page). It is due on Jan. 17.
1/8/13 The first homework assignment will be posted on Thursday, Jan. 10. It is due
at the beginning of class on Jan. 17.
1/1/13 No announcements, so far!
Top
Textbook
The course will be based on material from the (free online) text
Mathematics for Computer Science used at M.I.T. I have posted
the relevant material
here.
The good news is that we will only be covering part of the book, namely the chapters dealing
with counting, generating functions, probability, recurrences and graphs.
(I might point out that one of authors
of our text is the MIT mathematician/computer scientist Tom Leighton,
the founder and CEO of Akamai Technologies
in Cambridge, Mass).
Copies of the relevant material for the course can be purchased at the
AS Soft Reserves.
The plan for the course is the following. For each class, there will be an assigned reading
assignment.
This should be read before the class is held. During the class period, the concepts
of that reading secion will be quickly reviewed and most of the remaining time will be devoted
to seeing how the concepts and techniques of the assignment are applied to actual problems.
The discussion sections will also have a similar format.
Homework
In order to have a deep understanding of the material we cover, it is essential
that you actually solve problems yourself, and not just watch someone else do it! This is the function of
homework. There will be homework assignments each week, usually assigned on Thursday and due the
following Thursday at the beginning of the class. Late homework will not be accepted (unless
there is some really amazing reason!).
It is perfectly acceptable to work in groups on homework assignments, but the homework
you hand in must be entirely your own work. In addition to your name, you should
also include your student ID number (and try to write legibly, please!).
Top
Reading assignment schedule
NOTE: Subject to changes if unavoidable circumstances arise.
Date | Day | Subject | Notes |
1/08/13 |
Tue |
Counting | Sections 15.1, 15.2 |
|
1/10/13 |
Thu |
Counting | Sections 15.3, 15.4 |
|
1/15/13 |
Tue |
More counting - Sections 15.5, 15.6, 15.7 |
1/17/13 |
Thu |
More counting | Sections 15.8, 15.9, 15.10 |
|
1/22/13 |
Tue |
Winding up counting | Sections 15.11, 15.12, 15.13 |
|
1/24/13 |
Thu |
Generating functions | Sections 16.1, 16.2 |
|
1/29/13 |
Tue |
Generating functions | Sections 16.3 |
|
1/31/13 |
Thu |
Midterm 1 |
|
2/05/13 |
Tue |
Probability | Sections 17.1, 17.2, 17.3 |
|
2/07/13 |
Thu |
Probability | Sections 17.4, 17.5 |
|
2/12/13 |
Tue |
Probability | Section 17.6 |
|
2/14/13 |
Thu |
Random Variables | Sections 18.1, 18.2 |
|
2/19/13 |
Tue |
Random variables | Sections 18.3, 18.4 |
2/21/13 |
Thu |
Random variables | Section 18.5 |
|
2/26/13 |
Tue |
Deviation from the mean | Sections 19.1 - 4 |
|
2/28/12 |
Thu |
Midterm 2 |
|
3/05/13 |
Tue |
Recurrences - Sections 21.1, 21.2 |
|
3/07/13 |
Thu |
Recurrences | Sections 21.3, 21.4, 21.5 |
|
3/12/13 |
Tue |
Graph Theory - Section 11.1 - 6 |
|
3/14/12 |
Thu |
Graph Theory | Sections 11.7 - 11 |
Last Class |
3/19/12 |
Tue - 3:00 - 6:00 in PCYNH 109 |
Section A Final Exam |
|
3/21/12 |
Th - 7:00 - 10:00 in PCYNH 106 |
Section B Final Exam |
|
Top
Homework will be collected Thursday and solutions will be posted Friday.
Top