Discrete Structures

Computer Science 280
Spring 2005

Announcements

• (May 13, 2005) The final exam is graded and the grades are available on CMS. The answer sheets can be seen next week Monday through Friday between 1:00 p.m. and 3:00 p.m. in Cindy Robinson's office, 4146 Upson Hall.
• (May 10, 2005) Kevin's Wednesday office hour has been changed from 2-3 to 1-2. 
• (May 9, 2005) The venues for this week's office hours are finalized. You can find them in the table below.
• (May 8, 2005) There is a change in Tom's Tuesday office hour, now the time is 3-4 instead of earlier 2-3.
• (May 8, 2005) Graders' comments (for last problem set) can be viewed on the comments page and the solutions are available on CMS.
• (May 5, 2005) Problem set 11 is graded and the grades are available via CMS. The solutions and graders' comments will be available soon.
• (May 5, 2005) Following is the office hours schedule for the week of May 9--May 13. The older office hours schedule will not be followed for the coming week. The missing venue(s) will be announced soon.
  

  When	Who	Where
  Monday (May 9)
  Monday, May 9 (1:30-2:30)	Eva	Upson 5153
  Tuesday (May 10)
  Tuesday, May 10 (1:00-2:00)	Kevin	328B
  Tuesday, May 10 (3:00-4:00)	Tom	328D
  Wednesday (May 11)
  Wednesday, May 11 (11:00-12:00)	Yogi	328B
  Wednesday, May 11 (1:00-2:00)	Kevin	328A
  Wednesday, May 11 (3:30-4:30)	Hari	328B
  Wednesday, May 11 (5:30-6:30)	John	328B
  Thursday (May 12)
  Thursday, May 12 (11:00-12:00)	Zach	328C
  Thursday, May 12 (2:00-3:00)	Eva	Upson 5153
  Thursday, May 12 (3:30-4:30)	Joel	328B
  Thursday, May 12 (5:30-6:30)	Yogi	328B

   
• (May 4, 2005) The final will be Friday May 13th at 9-11:30 am in room Phillips 101. It is cumulative, covers all of the material of the course.. More information about the final, and practice questions for the material since the second prelim are posted here.
• Regrade request are accepted till the final, Friday May 13th.
• Please fill out the on-line course evaluation form.
• (May 4, 2005) An article in Science about The Structure of the Web by Jon Kleinberg and Steve Lawrence.
• (May 2, 2005) A couple of you asked me about the random process that creates the random graph in question 1 of problem set 11. Here it is.

We use C(n,2) (n choose 2) coins each has probability p of being head, and each coin independent. There is a coin associated with every possible edge. For any pair of nodes v and w, we look at the corresponding coin , and add edge (v,w) if the coin is Head, otherwise we have no edge connecting v and w.

• (May 2, 2005) For question 3: the root of a tree is not a leaf, even if it has degree 1.
• (April 28, 2005) Problem set 10 is graded. The solutions and grades are available on CMS. The graders' comments will soon be available on the comments page.
• (April 27, 2005) Problem Set 11 is now posted. It is due on Wednesday, May 4th, 2005.
• (April 27, 2005) The final exam will be on Friday May 13th at 9-11:30am in room Phillips 101.
• (April 24, 2005) The schedule of lectures in now posted for the remainder of the semester.
• (April 24, 2005) The graders' comments for problem set 9 can be viewed at the comments page.
• (April 21, 2005) Problem set 9 is graded and the grades and the solution can be seen on the CMS.
• (April 20, 2005) Problem Set 10 is now posted. Its due on Wednesday, April 27, 2005.
• (April 18, 2005)  A mistake corrected in Problem 2c of Problem Set 9: In question 2c we need to consider x in U': here x needs to be a vector, just as in part (d).
• (April 17, 2005)  A mistake corrected in Problem 2 of Problem Set 9: In question 2 the size of the hash-table is the prime p (and there is no q in the question).
• (April 15, 2005) We will have regular office hours starting today. The schedule posted for prelim week is not longer valid.
• (April 15, 2005) Old announcements (before prelim 2) have been moved to the old announcements page. 
• (April 14, 2005)  We added a new optional problem to Problem Set 9 .
• (April 14, 2005) Prelim 2 is graded. You can see the grades in CMS. The solutions are also available via CMS. Many problems contains more than one solutions, you might want to go over more than one of the solutions to get an idea of various ways to solve the same problem. The comments for prelim 2 will also be available soon and can be viewed on the comments page.
• (April 13, 2005) Problem Set 9 is now posted. It was due on Wednesday, April 20, 2005.
• (March 9, 2005) The old announcements made before the first prelim have been moved to old announcements page. Please check that page if you want to look for something.
• (March 6, 2005) The comments on the common mistakes in problem set 5 can be viewed on the comments page. 
• Link to old announcements.

Staff

CS 280 STAFF	Name	Email (append .cornell.edu)	Office
Instructor	Éva Tardos	eva@cs	5153 Upson Hall
TAs	Kevin Canini	krc25
	Tom Church	tfc23
	John Roberts	jwr23
	Hari Nathan	hsn4
	Joel Ossher	jpo5
	Zachary Scherr	zls2
	Yogi Sharma	yogi@cs	5132 Upson Hall

Textbook

• Rosen, Discrete Mathematics and Its Applications, Fourth Edition, McGraw-Hill, 1999.
• Additional material is available at the associated web site: http://www.mhhe.com/rosen
• Another book is on reserve in the Engineering Library as a background text:
  • S. Maurer and A. Ralston. Discrete Algorithmic Mathematics (3rd edition). A. K. Peters.

   

Office Hours

• Office hours will listed below. You can also use the course newsgroup (cornell.class.cs280) to ask questions or to discuss the course. You should subscribe to the newsgroup. Post questions to the newsgroup regarding homework (or anything else relevant to the course), and I or one of the TAs or graders will try to answer it, usually the same day that you post it. You can also make an appointment with any member of the course staff. The best way to set up an appointment is via email.

CS280  Office Hours	Monday	Tuesday	Wednesday	Thursday	Friday
10:00a-11:00a
11:00a-12:00p					Eva Tardos (5153 Upson)
			Yogi Sharma (328A Upson)
12:00p-01:00p
			Joel Ossher (328A Upson)
01:00p-02:00p		Kevin Canini (328C Upson)
	Lecture (KL B11)		Lecture (KL B11)		Lecture (KL B11)
02:00p-03:00p		Tom Church (328C Upson)
	Eva Tardos (5153 Upson)
03:00p-04:00p
		John Roberts (328C Upson)
04:00p-05:00p
	Zachary Scherr (328C Upson)	Hari Nathan (328C Upson)
05:00p-06:00p
CS280  Office Hours	Monday	Tuesday	Wednesday	Thursday	Friday

Homework Information

• There will be weekly problem sets, due (usually) on Wednesday at the beginning of class.
• Late Homework Policy: It is expected that homework will be turned in in class and on time. Every day or part of a day that homework is late, 20% will be deducted from the grade. If a genuine emergency situation exists you must inform the course staff as soon as possible. I will NOT drop any homework in computing the course grade.
• Optional Homework Questions: Some homeworks will have an extra optional part D. Optional homeworks may be harder, and we will not award partial credit (no credit is awarded unless the solution is at least 90% correct).
• Homework Privacy: Normally, graded homework is handed back in a self-service stack.  In other words, your homework grade is not private. If you prefer more privacy, clearly mark HOLD at the top of the first page of each piece (A, B, and C) of your homework. Homework not picked up in class will be available in Upson 363C.
• Regrade Policy: Regrade requests must be made within one week of the time that homework or exams are returned to the class.  It's not fair to the graders to ask them to explain details of their grading scheme for an assignment from 5 weeks ago.  Also, this rule prevents a pileup of such requests at the end of the semester.
• Grading Criteria: 
  • Correctness and Completeness (i.e., answer the question)
  • Clarity, Precision, and Conciseness (i.e., don't use 2 pages when 2 lines will do)
  • Optimality of Result (i.e., find the "best" answer)
• Warning: It is unlikely that you will learn the material in the course unless you do the problem sets. Those who skip a significant number of them are likely to earn poor grades on the exams (as well as receiving a low homework grade).
• Academic Integrity: It's OK to discuss the problems with others, but you MUST write up solutions on your own, and understand what you are writing. You may not copy any part of someone else's code or written homework. To do so is a violation of the Academic Integrity Code. See  http://www.cuinfo.cornell.edu/Academic/AIC.html for Cornell's Code of Academic Intergity.

Exam Information

There will be two prelims and one final in the course. The dates follow.

• Prelim I  (Tuesday, March 8th, 7:30-9)
• Prelim II (Tuesday, April 12th, 7:30-9)
• Final Exam (Friday, May 13th, 9-11:30)

Grading

• Your grade will be based on homework (due each Wednesday), two prelims (given at the scheduled evening-exam time), and a final exam (given at the scheduled final-exam time). Weighting will be roughly as follows:
  • 30% homework (no homework grade will be dropped)
  • 40% prelims (20% each)
  • 30% final exam
• Optional homeworks help improve the grade, but they are not required for full credit.
• We are using the CS course management system at https://cms2.csuglab.cornell.edu/ to manage course grades. Please check your grades regularly, to make sure we are recording things properly. The system also has general course statistics.

Course Description