Final structure
The final exam will follow the structure of Midterm II.
There will be 13 problems with a total of 220 points. Similarly to Midterm II, you can choose up to
| Problem | Points |
|---|---|
| 1 | 7 |
| 2 | 10 |
| 3 | 10 |
| 4 | 10 |
| 5 | 13 |
| 6 | 15 |
| 7 | 15 |
| 8 | 15 |
| 9 | 20 |
| 10 | 20 |
| 11 | 25 |
| 12 | 30 |
| 13 | 30 |
| I highly advise you to calculate the number of points necessary for you to achieve the minimum goal you are going for, and decide on a subset of the simpler problems to jumpstart your final. In my opinion, the problems worth 30 points are challenging: you should not define your strategy on solving them. |
Notable changes
- Euclid’s algorithm is no longer required for the final. After a thorough check of Midterm II, I have decided that this learning objective has been satisfied for an overwhelming majority of the students who decided to solve the problem. Direct computations using Euclid’s seem time-consuming while not checking for explicit reasoning: the final will contain some simpler questions on divisibility though to have a “soft start”.
- Cardinalities are not required for the final. We did not have enough (if any) practice problems on cardinalities, so this topic stays out of assessments.
- Invertibility in moduli arithmetic is no longer a separate learning objective. I decided to remove this as invertibility appears now in group theory. More elementary aspects of moduli arithmetic will be present in the final, especially useful in solutions.
- Number systems will not be part of the final. I believe that number systems were overwhelmingly present in Midterm II. Understanding number systems is still useful as practice of division with remainder and some moduli arithmetic, but I decided to disclose that they will not be explicitly present in final problems.
Proof techniques
- I can recognize settings where a proof by contradiction is appropriate Usually, you expect the statement to prove to be a negated statement that is hard to check by itself, but the negation is simpler to work with.
- I can recognize settings where a proof by contrapositive is appropriate Usually, you expect the assumption of the implication to be hard to use, but the contrapositive statement has an easier assumption with easier direct conclusions.
Induction
- I can write the assumptions and conclusions of mathematical induction as a predicate logic inference
- I can apply mathematical induction to prove numerical identities and inequalities depending on a parameter
An example would be proving that
. Other examples are also present in the practice set. - I can recognize if a mathematical proof using induction applies it correctly See problems 4 and 8 and 11 in the practice set.
- I can apply complete induction, and understand an example of a proof using complete induction instead of usual induction. See the proof of existence of the fundamental theorem of arithmetic.
Divisibility, GCD and LCM; fundamental theorem of arithmetic
- I can check whether a number divides another number
- I can apply the basic properties of divisibility to numbers See Properties of divisibility
- I understand the connection between the GCD and LCM of two numbers See this page.
- I can compute the
and of two numbers using prime factorization See Prime factorization method.
Division with remainder
- I can perform division with remainder for any reasonable numbers (for example, using long division)
- I understand the sequence of divisions with remainder leading to Euclid’s algorithm
- I understand the sequence of divisions with remainder leading to a number being expressed as a sum of powers of a base (rewriting a number in a given base)
Prime numbers and factorization
- I can factorize a (reasonably small) number in its prime factors
- I understand the meaning of unique factorization in the formulation of the fundamental theorem of arithmetic
- I can use prime factorization to determine if a number is a divisor of another number
- I know and can apply simple divisibility criteria in base
(divisibility by , , , , , ), and create divisibility criteria for numbers built out of those (for example, or ).
Modular arithmetic, congruences
- I can perform arithmetic operations in modular arithmetic See Congruences
- I can evaluate remainders of powers of numbers using moduli arithmetics and recognize patterns in power remainders.
For example, what is the remainder of
when divided by ? Try various numbers. - I can rewrite the set of integers satisfying
as the set of integers . - I can imply a congruence from an equality when solving a diophantine equation.
This sounds complicated, but this is just an explicit mention of the implication from
to for any . See Tricks in diophantine equations for some examples of problems. - I can perform operations in
and understand the meaning of these operations - I can solve non-linear diophantine equations by factoring or creating factoring
See Tricks in diophantine equations, in particular, Simon’s favorite factoring trick.
Solve
in integers. Solve in integers. What is the main difference between solving those in integers versus reals? You get a divisibility restriction.
Sets
- I can define a set using the set builder notation
- I can define a set using the list notation
- I can establish if two sets are equal
- I can perform usual operations on sets: union
, intersection , difference , Cartesian product - I can interpret the set operations logically Say, belonging to the union is equivalent to belonging to either of the sets. For the cartesian product, the cartesian product can be interpreted as choosing
- I know the definition of a power set and can construct the power set of a finite set. I can recognize elements of a power set.
Maps
- I can build and recognize maps between sets This includes the definition of a map, the domain and codomain of a map, and the image of a map.
- I can recognize an injective, surjective or bijective map between sets.
Graph theory
- Given a graph
, I can draw a representation of this graph (possibly, with self-intersections) - Given a drawing of a graph with vertex notations, I can recover the set-theoretic definition of the graph in the form
- I can recognize if a given simple graph is planar
- I can apply Euler’s formula and the inequality
to a planar graph to obtain new restrictions on planar graphs Examples include the statement that any (non-empty) planar graph has a vertex of degree at most . - I can use the handshake lemma to connect degrees of vertices to the number of edges in a graph
- I can recognize if a given graph admits a Eulerian path or a Eulerian cycle
Group theory
- I can check if a set with given operations is a group.
- I know the definition of
, the symmetric group of degree (the group of permutations of elements), and I can apply operations in this group to given elements. - I can find the inverse permutation to a given permutation in
. - I can recognize the group of symmetries of a geometric object and can perform operations in it
The model example here was the “mattress group”. Exercises include investigating the group of symmetries of a regular polygon.
For example, try investigating
, the group of symmetries of the square. What elements are there? How do operations work? Is the group abelian (is multiplication commutative)? - I can represent symmetries of a geometric object as permutations on the set of vertices
Complex numbers
- I can perform arithmetic operations in
.