Final Exam Topics:
Cumulative: See topics for prelim 1 plus those for
prelim 2. In addition,
Relations: Definitions and
properties (reflexive, symmetric, transitive), compositions, representations
(matrix, digraph), closures, equivalence relations, equivalence classes, partial
orders, Hasse diagrams, maximal and minimal
elements.
Graphs: Definitions (simple graph,
multigraph, directed graph) and terminology, representations (adjacency
matrix, incidence matrix), graph isomorphisms, connectivity, Euler and
Hamiltonian paths and circuits, shortest path, planarity, graph coloring.
Trees: Definitions and properties (m-ary tree,
counting leaves and vertices, etc), binary search and decision trees, tree
traversal, bubble sort, merge sort.
Boolean algebra:
Boolean functions, sum-of-products expansion, logic gates, converting a function into a logic circuit, circuit
minimazation.
| Final exam |
Wednesday, December 19, Uris Auditorium Early Seating: Wed, Dec 19, 12-2:30pm, Philips 203. Send email to cs280@cs.cornell.edu by Tuesday at noon to be included in this seating. |
practice final 1 (= final from
fall 1999) practice final 2 (=
final from spring 2001) |
Prelim 1 Topics:
Propositional logic and tautologies
Predicates and quantifiers and
logical equivalences
Sets and set operations
Functions
Sequences and series, including basic formulas
Algorithms and big-O
notation
Number Theory: gcd/lcm, different bases, Chinese Remainder Theorem
Matrices
Proofs: direct, indirect, contradiction, induction, logic
proofs
Recursion: definitions and algorithms
|
Prelim 1
|
Tuesday, October 16, Rooms: |
actual prelim 1 The maximum possible was 75, the median was 64, the mean was 62, and the standard deviation was 7.5. As a rough guide to grades, practice exam 1 (= prelim 1 from fall 1999)
practice exam 2 (=prelim1 from spring
2001) |
Prelim 2 Topics:
Counting: Pigeonhole principle,
inclusion-exclusion (general version), permutations and combinations, binomial
theorem, permutations and combinations with repetitions, distributing objects
into boxes.
Probability: Basic probability,
conditional probability, independence, bernoulli trials, random variables and
expected value, variance.
Recurrence relations:
Defining a recurrence relation, initial conditions, calculating values
using a recurrence relation.
|
Prelim 2
|
Tuesday, November 13, Rooms: Early seating: 205 Upson, Tuesday, November 13, 5-6:30 |
actual prelim 2 The maximum possible was 75, the median was 62, the mean was 62, and the standard deviation was 8.5. As a rough guide to grades, find the total of your two prelim grades,
then use the table below: Prelim 2 will concentrate primarily on chapters 4 and 5, although topics from previous chapters are fair game. practice exam 1 (= prelim 2 from fall
1999) practice exam 2 (=prelim2 from spring
2001) |