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

DateTimeLocation
Lecture Tue/Thur3:30pm - 4:50pmPCYNH 109
Discussion Wed4:00pm - 4:50pmCSB 001
Final Exam Tuesday 3/19/133:00pm - 6:00pmPCYNH 109

Class Meetings - Section B

DateTimeLocation
Lecture Tue/Thur5:00pm - 6:20pmPCYNH 106
Discussion Mon3:00pm - 3:50pmCENTR 109
Final Exam Thursday 3/21/137:00pm-10:00pmPCYNH 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.

DateDaySubjectNotes
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

Homework will be collected Thursday and solutions will be posted Friday.

Top