Class Notes: Applied Discrete Structures
Spring Semester 1999 - MWF 5th Period CSE/E222, Section 4617X
Exam #1 -- Monday 15 Feb 1999 : 08:20 pm
- Arrangements: Place: Carlton Auditorium
- You may bring one 8-1/2" by 11" information sheet
that is handwritten only. This will be checked.
- ID's will be checked, so bring your Gator-1 ID.
- Material: All concepts up to p.185, as noted in class.
- Read and study Rosen Sections 1.1-1.8, 2.1-2.4,2.6,3.1.
- Not included: Sections 2.5 (Applications of
Number Theory) and 3.2 (Mathematical Induction).
Topics can include:
- Boolean logic -- operands, functions,
propositions, predicates, implications, quantifiers,
identities, and derivations of logic expressions
using identities.
- Sets -- operations and identities, Venn diagrams,
and derivations of set expressions from identities.
- Functions -- mappings (1-to-1, onto, into,
injection, bijection, surjection, definition of a
function), and functional composition
- Sequences and Summation -- definition of a
sequence, how to perform summation or other global
operations (e.g., maximum or minimum) over a sequence,
growth of summations, how to express a summation in
closed analytical form
- Complexity -- Big-Oh notation, how to find the
complexity of an algorithm in terms of Big-Oh notation.
- Integers -- properties of the integers, countability
and infinite sets, primes, modulo arithmetic, the division
theorem, factorization of integers, the fundamental theorem
of mathematics, how to prove and use Euclid's Theorem.
- Congruences -- definition of congruence modulo-n,
how congruences are used in factorization, proofs based
on congruences (but not in Section 2.5)
- Methods of Proof -- Know each method of proof in
Section 3.1, the tautology that underlies the method of
proof, and how to apply it. Study all examples in
Section 3.1 very carefully.
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.