CS271: Discrete Methods in Computer Science (Spring 2013)

Most recent message posted: 5/13/2013

Administrativa

  • Course Staff:
    Instructor Teaching Assistant Teaching Assistant Sherpa Sherpa Sherpa Sherpa
    Name David Kempe Gene Kim Lian Liu Brooke Hubert Sina Rezaimehr Jay Whang Rhys Yahata
    Office SAL 232 SAL 219 SAL 219 N/A N/A N/A N/A
    Office Hours Wednesday, 2:00-3:30 Tuesday, 9:30-10:30
    Thursday, 12:30-1:30    		 Wednesday, 10:00-11:00
    Friday, 9:30-10:30    		 N/A N/A N/A N/A
    Phone (213)-740-6438 TBD TBD N/A N/A N/A N/A
    e-mail

  • There will be one midterm, on Tuesday, March 12, during class time. The midterm will be in MHP 101, which is different from our usual class location. The midterm will be open book, open notes. Make sure to bring a blue book.
  • The final exam will be on Thursday, May 9, from 2:00pm-4:00pm. The location is our classroom, WPH B27. The final exam will be cumulative, i.e., cover the material of the entire semester. The final will be open book, open notes. There will be no make up date for the final.
  • There will be several quizzes in class, which will be announced beforehand.
  • Homework will be assigned and graded.
  • The final grade will be calculated as 15% homeworks, 15% quizzes, 40% final exam, 30% midterm. Class participation, while strongly encouraged, does not affect grades. (Neither does attendance, though experience tells that attendance and participation correlate highly with success in classes.) The grading will not be done to a curve: the grading scale is given below.
  • Open laptops are strongly frowned upon in class.

    • The grading scale is given here. These are not curves or class percentages, but your percentages. For instance, if the weighted average percentage of your grades is 55%, then you get at least a B. As indicated by the scale, the assignments, exams, and grading will be fairly demanding; the scale reflects this.

    p Grade
    80%A+
    73%A
    67%A-
    61%B+
    55%B
    50%B-
    44%C+
    40%C
    35%C-
    30%D

    Homework will be assigned roughly once per week, and graded. Of all assignments, the worst one will be dropped in calculating your grades. Homeworks are due in class on the date specified. Each student can submit up to 3 homeworks up to one day late. Late submissions should be made to a TA or instructor in office hours, no later than office hours on the day after the due date. Submissions more than one day late will not be accepted. Once 3 homeworks have been submitted late, subsequent late submissions will not be accepted.

    Three of the early homeworks will assign you in random groups of three. For those homeworks, all members of the group will obtain the same grade. Subsequent homeworks will be asking you to solve problems individually. Read the policy below about what is and is not appropriate collaboration behavior on homeworks.

    Homeworks will from time to time contain "chocolate problems". Chocolate problems do not affect your grade in the course. They are intended to be significantly more challenging, for students looking for a challenge. Chocolate problems will be marked with a number of chocolate bars. Solutions that are (mostly) correct will lead to the solvers getting that number of chocolate bars. Chocolate problems can be solved in groups of up to 3 students (who will then share the chocolate). Chocolate problem submissions should be on separate sheets of paper, as they will be graded by the instructor, not the TAs/grader. Feel free to mark your preferred type of chocolate with your submission, though we won't promise that we will meet all requests.

    Course Overview, Syllabus, Textbook, Prerequisites

    The course covers the fundmantals of discrete mathematics as they relate to computer science. Many of the problems computer scientists are most frequently called upon to solve involve discrete structures such as trees, graphs, and - even more fundamentally - natural numbers. Furthermore, since execution of programs necessarily proceeds in discrete time steps, to truly understand what it means for a computer program to solve a problem correctly and efficiently, it is necessary to have a solid understanding of the tools used in program analysis. The topics that will be covered in depth in this class are:

    While each of these topics is important in its own right, the main goal of the class is to familiarize students with a mathematical mindset in thinking about problems, and the precision and clarity of thinking promoted by proving mathematical statements.

    The textbook is

    The textbook is required. Many homework problems will be assigned from the textbook. While the class will not always follow the order or presentation style of the textbook, the textbook is very encyclopedic and will be an excellent source of additional information. Students can use older versions of the textbook if they so desire. The material covered is essentially the same; however, the numbering of chapters and exercises is different. It is the students' responsibility to ensure that they solve the correct exercises.

    The (rough) syllabus for the course is as follows. Topics may be added or removed depending on available time:

    1. What happens when you type a query into Google: How the topics of this course relate to core CS. [1 lecture]
    2. A review of the basics: sets, sequences, functions, sums, products, and algorithms (Chapters 2 and 3.1). [1 lecture]
    3. Propositional Logic, First-Order Logic and Basic Proof Techniques (Chapter 1). [4 lectures]
    4. Proofs by Induction and Program Correctness (Chapter 5). [4 lectures]
    5. Pigeon Hole Principle (Chapter 6.2) [2 lectures]
    6. Big-O Notation and Runtime Analysis (Chapter 3) [2 lectures]
    7. Counting and Basic Discrete Probability (Chapters 6 and 7). [6 lectures]
    8. Graphs and Trees (Chapters 10 and 11). [6 lectures]
    9. Number Theory and applications (Chapter 4). [2 lectures]

    Academic Integrity, Collaboration

    All students are expected to maintain the utmost level of academic integrity. Any attempts to cheat will lead to appropriate sanctions. Please consult the USC Student Conduct Code for details on what is and is not appropriate, and for the possible consequences of infractions.

    The class will have two types of homeworks. Some of the early homeworks are explicitly group homeworks: for those, you will be assigned random classmates to work with, and you can only submit one solution for your entire group; all three will receive the same grade.

    For other homeworks, you should follow the "Gilligan's Island" rule. You are allowed to collaborate with your classmates as a group of up to three students. However, you should not take any mementos away from your collaboration meeting. (No paper notes, no typed-up notes on your laptop, no photographs, etc.) Your writeup will have to be entirely your own; you should not look at the writeups of your classmates, either in your group or others. You should also mark clearly the names of the classmates you collaborated with. Between your group meeting and beginning your writeup, you should let at least one hour elapse during which you pursue an activity entirely unrelated to the class (such as watching "Gilligan's Island"; hence the name).

    If you need hints for problems, your instructor, TAs and sherpas will be there to help you. It is never appropriate to search online (or in books, etc.) for solutions to homework questions and try to pass them off as your own work. That constitutes plagiarism.

    Messages