CMSC 250:Discrete Structures

Announcements

• (Posted on 07-21): Reminder: Final exam tomorrow at 12:30pm, CSIC 3117 (same class as lectures). First three pages are available here.
• (Posted on 07-11): Midterm 2 grades are available for viewing on the grades server.
• (Posted on 06-24): People that had problem 1, question b9 of their first midterm misgraded can come by any of our office hours, with their midterm sheet, so that we can verify the fact and correct their grade.
• (Posted on 05-31) Here's a direct link to the first homework for those of you who have trouble registering on Piazza. Please register soon (the responses to one of your homework questions can only be found on Piazza)! (link no longer active)
• (Posted on 05-31) First homework has been posted on Piazza!
• (Posted before 05-31) Please make sure you read the syllabus for the class before our first lecture and come to us with questions. We will be going through it at a fast pace before delving into our first lecture on propositional logic.
• (Posted before 05-31) Please register on Piazza, as virtually all of our course discussion will be routed through that platform after lectures, discussion sections and exams.
• (Posted before 05-31) Welcome to the class! For our first week, the first homework will be due one week from our first lecture, on Tuesday 06-07. Miss a day, gain a day.

General Information

CMSC 250 is the first Theory-heavy course in our undergraduate curriculum. We will be covering a variety of topics (see syllabus for a full list). Our major focus will be on Logic, Formal proofs, Induction and Combinatorics. A requirement for CS majors, 250 is a major stepping stone for 351 and 451 ("Algorithms" and "Design & Analysis of Algorithms" respectively), as well as an introduction to subjects discussed more at depth in courses such as 421 (Artificial Intelligence), 430 (Intro to Compilers), 452 (Elementary Theory of Computation), 456 (Cryptology) and 475 (Combinatorics & Graph Theory). It should therefore be clear that it provides the mathematical/theoretical background necessary for a successful career as a student, developer, researcher or teacher of Computer Science!

Our summer section will run from 05-31 to 07-22, with a break on Monday, 07-04 for Independence Day celebrations. All students are expected to read the syllabus very carefully to educate themselves about our policy with regard to religious observances and other forms of excused absences. Some important elements of the syllabus follow:

• Teaching staff:
  • Instructor: Jason Filippou (e-mail:full first name and first three letters of last name at cs, all lowercase).
  • TAs: Parsa Saadatpanah (e-mail: full first name, followed by a dot and full last name at gmail, all lowercase), Yancy Liao (similar).
• Lecture hours / Discussion sections / Location:
  • Lectures: Monday, Tuesday, Wednesday, Thursday, 12:30-2pm, CSIC 3117.
  • Discussion sections: Friday 12:30-2pm, CSIC 3117.
• Office hours:
  • Instructor: Mon,Tue 2-3pm, Wed 2-4pm, AVW 3217 (office will change soon)
  • TAs:
    • Parsa: Tue 10am-12pm (even weeks) or Fri 10am-12pm (odd weeks), Wed 10am-12pm (all weeks), AVW 1112
    • Yancy: Thu 2-4pm, Fri 2-4pm (all weeks), AVW 1112
• Assignments / Grading (policy subject to minor changes):
  • 5 homeworks (handed out on Mondays, due on subsequent Monday): 2% each for a 18% total.
  • 5 quizzes (handed out on discussion sections, completed within 25-30 minutes): 2% each, for a 10% total.
  • 2 in-class midterms (Friday, 06-17 & Friday, 07-08): 20% & 25%, respectively.
  • 1 in-class 2-hour final (Friday, 07-22): 30%.
• Textbooks: There are no required textbooks for the course, but the following ones are recommended:
  • Susanna Epp, Discrete Mathematics with Applications, 4th Edition, Brooks / Code publishing, ISBN-13:978-0495391326. Available on Amazon and Barnes & Noble. Students are not required to work with the 4th edition; in fact, the teaching staff has access to a copy of the 2nd edition.
  • Thomas Koshy, Discrete Mathematics with Applications, 1st edition. ISBN-13: 978-0124211803. Elsevier. Another great book, which can be found cheaper on Amazon and Barns and Noble.

  The Instructor has "adopted" these two textbooks through the University's Faculty Enlight system couple months in advance of the course start date, so a small number of copies of both should be available for renting or borrowing at the University Book Store.

• Excused absences, academic dishonesty, electronic devices policy, students with disabilities: Please see syllabus for details.

Slides

• Combinatorics / Probability (07-12)
• Structural Induction (06-27)
• Mathematical Induction (06-27)
• Countability (06-23)
• Functions (06-22)
• Set Theory Fundamentals( (06-20)
• Formal Proof Methodology (06-09)
• Number Theory Fundamentals (06-08)
• Predicate Logic(06-06)
• Combinational Circuits (06-02)
• Propositional Logic (05-31, 06-01)
• Introduction (05-31)

Resources / Cool Stuff

• Klyde Kruskal's notes on properly writing inductive proofs.
• The instructor’s thoughts on properly authoring proper proofs of Number Theory theorems in 250.
• A great Stack Exchange thread about the utility of free variables in FOL.