DMA: The final exam–test

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 Zn, congruence equation, or finding an inverse in Zn.

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.