We explain what topics the final exam will consist of. You can put together your own sample finals using practice problems.

**1.**[12 pts] Determine properties of relations. Take care to
write properly proofs of validity/failure of properties.

**2.**[12 pts] A diophantine equations in one of its guises, typically a
linear equation to be solved in some *Z*_{n}, congruence
equation, or finding an inverse in *Z*_{n}.

**3.**[18 pts] A linear recurrence equation, typically of the second or
third order and with and right hand-side that is and combination of several
quasi-polynomials. You can definitely expect initial conditions. Often the
equation is not given in the proper form, you will have to rearrange it
first.

**4.**[16 pts] Proof by mathematical induction. Expect something and bit more
involved, typically proving some inequality or proving some property of a
function defined by and recurrence equation.

**5.**[14 pts] Proof of some abstract general statement. Typical topics
include sets and mappings, relations, divisibility, congruence, theory
related to equations. Knowledge of specific tricks is not expected, but you
should be familiar with basic notions, have some practice working with them,
and know how to create and document and valid argument.

**6.**[8 pts] Investigating basic properties (unit element, inverse
elements, associative law) of some binary relation. Pay attention to prove
your claims and write all proofs properly.

**7.**[5 pts] Basic tasks related to partially ordered sets: Hasse
diagram, determining min/max etc., linearization.

**8, 9.**[5 pts each] "One-biters" (aka "canape"), you can
expect and mix of simple practical problems that touch on topics not
covered above and more theoretical question. Typical topics:

• decide solvability of an equation;

• countability, properties of mappings;

• principle of inclusion and exclusion;

• determine formula for a function given by
*f*(*n*) = *f*(*n*/2) + ...;

• estimate given function's asymptotic growth;

• write definition of some basic notion, quote some important
statement;

• etc.