Contents

C241: Discrete Structures for Computer Science

Fall 2009


Announcements

12/17/09Practice test Solutions.
12/14/09For your studying pleasure, here is: a practice test, the first midterm, and the second midterm. Solutions will be posted later this week. The final exam is this friday, 12/18/09, 2:45-4:45pm, in our usual classroom. You can drop by my office (LH310) anytime from 10:30am-7:30pm this wednesday if you'd like help on anything before the final.
12/13/09Solutions to assignments 10 and 11 have been posted to the assignments page.
12/7/09Next Wednesday, 12/18/09, I'll be holding Exam Review Office Hours 10:30am-7:30pm in LH310; come with any questions over material we've covered this semester. The extra credit problems from the honors presentations can be turned in during class Wednesday, during the Recitation Exam Review on Friday, or during Exam Review Office Hours.
12/3/09>Assignment 11, Due Wed 12/9, has been posted on the Assignments Page.
11/30/09Current Course Grades have been posted on Oncourse. These include dropping your lowest homework grade, and extra-credit from honors presentations. They do not include HW10 or extra-credit from the guest lecture. If your grade is a bit lower than you'd like, remember there's still two homeworks and the final exam left; the final is worth 25% of your grade, and if you do well on it it's a great way to bring your grade up. The final will be comprehensive and difficult. But, it will be on the friday of finals week, so you should have ample opportunity to study and get help if you need it. From years of experience with this class, I can attest that if you study diligently , and ask questions about anything you don't understand, there's no reason why you won't do very well on the final. Additionally there will be extra-credit problems handed out during the honors presentations on M and W of next week (the last week of classes).
12/2/09Honors students will find their reference and IU Course information on the updated Project Page.
11/30/09Current Course Grades have been posted on Oncourse. These include dropping your lowest homework grade, and extra-credit from honors presentations. They do not include HW10 or extra-credit from the guest lecture. If your grade is a bit lower than you'd like, remember there's still two homeworks and the final exam left; the final is worth 25% of your grade, and if you do well on it it's a great way to bring your grade up. The final will be comprehensive and difficult. But, it will be on the friday of finals week, so you should have ample opportunity to study and get help if you need it. From years of experience with this class, I can attest that if you study diligently , and ask questions about anything you don't understand, there's no reason why you won't do very well on the final. Additionally there will be extra-credit problems handed out during the honors presentations on M and W of next week (the last week of classes).
11/29/09 H241 students will find that the Project page has been updated with detailed guidelines for the 2-page handout. We'll be meeting during H241 recitation hours this Friday, 12/4, to go over your 2-page handout draft and assign teaching slots for the last week of class.
11/19/09 Assignment 10 has been posted on the the Assignments page. It will be due the monday after Thanksgiving Break, 11/30. This coming monday will be a special guest lecture on NP-completeness (attendance will be extra-credit).
11/19/09 Rebecca will be holding recitation as usual on Friday, November 20 but will not be having office hours next Tuesday. You may pick up your graded midterms in recitation on Friday. Please note that your next homework assignment is due the Monday after Thanksgiving. As such, recitation on Friday will be your last opportunity to ask Rebecca questions about the assignment in person. You may of course e-mail any time during the break.
The review sheet that was handed out during recitation, along with its solutions, can be found on the Resources Page.
Rebecca will be holding special pre-midterm office hours this week, on sunday 6pm-8pm (instead of tuesday). If you haven't picked up your graded homework, or you have any last questions before the test, go see her. The second midterm will in class on monday, and will cover the material on assignments 5-9.
The last two honors presentations will be today, in LH102, from 4pm-5pm. Attendance will count as extra credit for all students.
The afformentioned Computer Science Undergraduate Talent Show, which I'm informed by a reliable source and previous student of mine, will be awesome, has been moved to 5pm. You should attend and/or participate.
11/8/09Question 2a on homework 9 has been changed to extra credit (you can see the revised version on the assignments page). It's a little trickier than the problems we've been covering in class, as you might have noticed, and in order to complete it correctly you need to prove a couple lemmas first (additional small facts). It's not all that much trickier; you should take a shot at it.
11/6/09Homework 9 has been posted on the assignments.html page. It will be due next wednesday, 11/11/09. There is not a reading assignment for next week, but if you'd like a preview of what we'll be covering next, time complexity is covered starting on page 57 of your book.
11/4/09The second midterm will be monday, 11/16 and will cover the material in assignments 5-9. You'll be able to pick up your graded assignment 9 during recitation on friday 11/13. Next wednesday we will begin covering Big-O notation, but this will not be included on the exam. Assignment 10 (covering Big-O) will be due on the monday following thanksgiving.
11/4/09There's been a change in the H241 presentation schedule from what was announced in class: Presentations will be held from 9am-11am this friday (in the same room as c241 recitation), and following class on monday, (from 4pm-5pm, room TBA). Attendance will be counted as extra-credit for C241 students on friday morning, and for all students on monday afternoon.
11/3/09Solutions to assignments 6 and 7 have been posted on the assignments page.
Got Talent? Can you sing, dance, play an instrument, tell jokes, read poetry, perform magic, or anything of the like? We want you to perform in the first ever Undergraduate Computer Science Talent Show, which will be on Saturday, November 21, at 5pm in the Collins Coffeehouse. Please contact Valkyrie Savage (vasavage) right away to get on the schedule. ALL students are warmly invited to attend this event, which promises to be great fun. Pizza and soft drinks will be served. The talent show is sponsored by the Women in Informatics and Computing (WIC) group.
10/28/09 Reading assignment 6 (due monday 11/2) and homework assignment 8 (due wednesday 11/4) have been posted on the assignments page. The second midterm will be monday, 11/16, and will cover sets, functions, relations and induction.
10/22/09 Reading assignment 5 (due monday 10/26) and homework assignment 7 (due wednesday 10/28) have been posted on the assignments page.
10/20/09 Two students have been diagnosed with H1N1 in the past couple weeks (they're both fine), so it seems like it would be useful to make my policy on this clear: If you're sick, stay home. Send me an email. We'll give you the beneifit of the doubt with respect to medically excused absences, so long as there's no blatantly obvious abuse. If you have an assignment completed that you'd like to turn in, but you're too ill to come to class, just consider the homework quarantined and submit an electronic copy to us when you feel able to do so (scan it, or type it up... we'll make allowances for translating math symbols into english as necessary "AND, OR, EXISTS, etc..."). Don't bother coming back to class until you're certain you're feeling healthy enough to do so. If you get behind, the AI, me, the book, and the assignment/pairwork solutions online are great resources for getting caught back up again, just make sure you come check in with us when you're able to return to class. Also, since we've had two students diagnosed with H1N1, if you've been very ill recently you may want to go to the health center for testing. In general, this is not the second coming of the black plague; both students who were diagnosed were unaware that they had anything more interesting than a bad case of the seasonal flu until they were tested. So if you just take good care of yourself when you're sick, and we all take reasonable precuations (wash your hands, avoid making out with your boy/girlfriend who has a bad cough, get rest and take vitamin C if you start feeling ill), this shouldn't be too big of a deal.
10/15/09Homework 6 and Reading Assignment 4 have been posted on the assignments page. The homework is due next wednesday (10/21), the reading is due next monday (10/19).
10/14/09Your course grades up to and including the first midterm have been posted to oncourse. The relative percentages are a little bit off and the lowest homework score hasn't been dropped, but this should give you a decent idea how you're doing in the class. There's still about 65% of the grade points in the course remaning, so if your grade is lower than you'd like, you've got some time to bring it up... if you do well on future homework and espcially if you study carefully and get high grades on the remaining tests. (And similarly, if your grade is higher than you expect, you've got plenty of time for it to drop back down, so don't relax too much.)
10/14/09Lose your textbook? I've got an extra one that was left in the room a few weeks ago.
10/8/09Reading assignment 3 and Homework 5 has been posted to the assignments page. The reading will be due on Monday (10/12), and the homework will be due on Wednesday (10/14).
10/6/09 H241 Students: updated project information has been posted to the H241 page.

General Information

Course Description

Credits: 3
Prerequisites: C211
Textbook: Schaum's Outlines: Discrete Mathematics 3rd Edition Seymour Lipschutz, Marc Lipson
Topics: The mathematical foundations of computer science, including induction, combinatorics, propositional and predicate logic, proofs, sets, functions, relations, running time of programs, trees and graphs.

Time & Location

Lecture:
Monday, Wednesday 2:30pm - 3:45pm
Location BH215

Discussion Sections (Recitation):
C241: Friday 11:15am - 1:10pm, I2 130 (INFO East)
H241: Friday 9:05am - 11:00am, I2 130 (INFO East)

Instructor

Christine Task
LH310
Mailbox: LH215
Office Hours: Monday and Wednesday 4:00pm - 5:00pm

Associate Instructor

Rebecca Ingram
Office: LH310
Office Hours: In LH016 Tuesday 6:00pm - 8:00pm

Undergraduate Instructor

Sourjya Roy