CS173: Discrete Structures
Spring 2016, Madhusudan Parthasarathy
Examinations

This page will eventually have information on exams.

You must read the exam instructions before coming to examlets and exams.

FINAL EXAM

The final exam will take plac on Monday, May 9, from 8:00am to 11:00am in room 1320 DCL (where we had lectures).
The final exam will have only this room as venue.

Topics:

In general, the topics of the exam include all topic covered in the course. In particular, they include all topics covered in the examlets and the topics covered after the last examlet.

In terms of material from textbooks/notes, the topics cover all topics in Fleck's textbook, but the following are EXCLUDED:

  • Chapter 16 (on NP), Chapter 19 (State Diagrams), and Chapter 21 (Planar Graphs)
  • Section 13.5 (Context-free grammars) and Sections 13.6-13.7 (Recursion trees).
    • Also, the following material from the MIT Textbook is included:
  • Chapter 5 (Sections 5.1, 5.2, (but not 5.2.3), 5.3), 5.7.1, 5.7.2).
  • Chapter 13
    • Also, make sure you read the following two sets of notes on induction:
  • Madhu's notes on Induction.
  • Chandra Chekuri's notes on induction on structures.
    • Finally, here's a fairly exhaustive SKILLS LIST that covers the various skills and knowledge you need to have for the exam. Though the skills list is at a fairly fine level, this list is NOT meant to be exhaustive. However, it does give you a more detailed description of topics that you definitely should know (and lists some topics that are definitely not covered) for the final exam.

    Sample questions:

    The questions that best represent the questions you would be asked in the final exam are the questions in the examlets in this semester; see them below including the solutions.

    When you look at exams/examlets in other years, remember that other versions of the course have slightly different syllabi and slightly different emphasis. In general, CS173-B course this year focuses more on induction and recursive definitions. And it is guaranteed that there will be a question asking you to prove a property of rooted trees (using typically induction).

    Having said that, the exams/examlets in earlier years are a good source of problems. Look through the prior year websites and look for exams and examlets therein.

    Here are some source for problems from previous semesters:

  • Final Exam from Fall 2014
  • Examlets from Fall 2014
  • Midterm exams from Fall 2013

    • Date Examlet Topics Reading Resources Solutions
    February 18 #1 Basic math (Chapter 1), propositional logic, predicate logic, negating statements, meanings of formulas, manipulation formulas, proof techniques: proving universal statements using direct proofs, proving existential statements, disproving universal statements, disproving existential statements, proving by cases, proof by contrapositive, divisibility, proofs involving divisibility, prime numbers, fundamental theorem of arithmetic, gcd, lcm, division algorithm, sets, cardinality, inclusion, set operations, set identities, size of set union, product rule, proving facts about set inclusion. Chapters 1 to 5, excluding 4.7, 4.8, 4.9, 4.10, 4.11, 4.12, 4.13 Solutions
    March 3 #2 Topics of examlet #1 are included but will not be emphasized.
    Relations (properties of relations, kinds of relations, proving properties and kinds of relations).
    Induction: proofs by induction.     		Chapter 6, Chapter 11, and Induction Notes Solutions         
    March 17 #3 Topics of examlet #1 and #2 are included but will not be emphasized.
    Functions: properties of functions, one-to-one, onto, bijections, and proving properties of particular functions
    Graphs: Simple graphs, kinds of graphs, isomorphism, proving and disproving isomorphism between graphs, subgraphs, walks, paths, cycles, connectivity, distances, dimater, Euler circuits, bipartite graphs, k-coloring. Topics covered after Tue March 8 not included (like bipartite matching, Hall's theorem, etc. There will also be no problem that calls for induction on graphs.     		Chapter 7, 8, 9, and Section 10.3 and 10.4. Material from the MIT textbook *not* included for the exam. Solutions         
    April 7 #4 Topics of previous examlets are included but will not be emphasized.
    Graphs, and induction on graphs. Bipartite matching, Hall's theorem. Trees.     		Chapter 9 and Sections 10.3 and 10.4, Chapter 13 (Section 13,1-13.4). Material from the MIT textbook, Chapter 5 (Sections 5.1, 5.2 (but not 5.2.3), 5.3), 5.7.1, 5.7.2), included for the exam. Solutions         
    April 21 #5 Topics of previous examlets are included but will not be emphasized.
    Induction on trees (free trees as well as rooted trees), Recursive definitions, proving properties of recursively defined functions using induction, proof by contradiction. Two-way bounding and proving a set is a subset of another.     		Chapter 13 (Section 13,1, 13.2, 13,3, 13.4, 13.8, 13.9), Chapter 12(Sections 12.1, 12.4, 12.5, 12.6), Chapter 17, Chapter 10. Also read Chekuri's notes on induction Solutions