Class Notes: Applied Discrete Structures

Spring Semester 1999 - MWF 5th Period CSE/E222, Section 4617X

Instructor: M.S. Schmalz -- TAs: James Jeffers, Yasmeen Fatimah, Jang-Uk In, Arun Srinivasan, Jing Zhao

Exam #2 -- Monday 22 Mar 1999 : 08:20 pm

• Arrangements:
  • Location:
    • Period 3: (Section 1088) Weimer 1064
    • Period 4: (Section 1089) Weimer 1064
    • Period 5: (Section 4617) Weil 270

    Directions to Weil 270: Starting at the CSE building, go West on the street to the stadium, until you pass Weimer Hall (College of Journalism) on the left. This is just before you get to the stadium, which is on your right. On your left, there is a curving driveway that goes to the Nuclear Engr. Building. Follow the curving driveway as it goes South. On the right, tucked up against a large brick building is a small concrete building with two metal doors, and a concrete awning over the doors. This is Weil 270, but it is marked G0270. Don't ask me why.

    Do not enter the room until 8:15pm, as we will be numbering the seats, like we did for Exam #1. When you receive your exam booklets, match the number on the booklet with the seat number, sit down, and keep your exam booklet closed. The sooner everybody is situated, the quicker we can begin. Exam duration will be 90 minutes, as before.

  • Crib Sheet: You may bring one 8-1/2" by 11" information sheet that is handwritten only. This will be checked.

  • Identification: ID will be checked when you hand in your exam, so bring your Gator-1 ID.
• Material: The exam will primarily emphasize all concepts from p.186 through p. 331.

  Note: It may be necessary to ask a question that requires you to use concepts that we covered prior to p. 186. However, you will probably not be tested directly and explicitly on concepts that we covered prior to p. 186.

  • Read and study Rosen Sections 3.1-3.5, 4.1-4.4, and 5.1-5.2. Work through all examples in the book, and work through the exercises at the back of each section.

    Not included: Sections 4.5-4.7 (Probability Theory, Generalized Permutations, etc.)

  • Topical areas of Exam-2 include:

    1. Topic 1 -- Proof Techniques:
       1. Know each method of proof (e.g., modus ponens, modus tollens), how it is used, and how it can be misapplied;
       2. Be able to construct a proof using different steps, and tell what method you used at each step, and why you used it. Study examples in the book!
       3. Know math induction - both the first and second principles. Be able to prove a variety of examples in the book using math induction. For example, given a proposition P(n), be able to prove P(n) for n greater than a given value.
       4. Be able to construct math induction proofs for operations that we studied prior to Chapter 3, namely, set, string, and matrix operations, as well as operations over sequences.
    2. Topic 2 -- Proof of Correctness
       1. Know the proof of correctness for each program construct (e.g., while loops, if..then..else, composition, etc.);
       2. Be able to compose proofs of correctness for each subordinate statement type (as above) to yield a proof for a given algorithm.
       3. Know how to construct statements p (or q) for assertions of form p {S} q, given q (or p). Here p denotes initial conditions, and q denotes final or termination conditions.
    3. Topic 3 -- Combinatorics
       1. Know the difference between C(n,k) and P(n,k), and be able to describe how they are related, especially in terms of Pascal's triangle and the coefficients of binomial expansions.
       2. Be able to determine the number of possible combinations using the product or sum rules, as well as rules for combining probabilities. Study all examples in Chapter 4!
       3. Know the inclusion-exclusion principle, in its particular and generalized forms. Know how to apply this principle to solve practical problems, and practice solving such problems.
    4. Topic 4 -- Recursion Relations
       1. Know the different methods for solving linear homogeneous recursion relations with constant and non-constant coefficients. Be able to apply each method to examples and exercises in the book.
       2. Be able to construct a recursion relation for a given practical problem (e.g., selecting tennis players for a team, or tiling a chessboard) and be able to produce a concise, rigorous proven solution to the recursion relation.
       3. Know when (and when not) to use math induction in proving the correctness of solutions to recursion relations.

Show your work on all questions to get full credit. Any copying will be construed as cheating, and will be severely dealt with.

Copyright © 1999 by Mark S. Schmalz.