Discrete Mathematics for Computer Scientists -- Exam Information | DIT980, HT 2015 |
Home | Schedule | Assignments | Exercises | Exam | About | Fire | Forum | TimeEdit | Links | 2014 |
Tentagranskning
Tentan har blivit rättad. Resultat: Utav 50 som lämnade in tentan, var det 15 som fick VG, 16 som fick G, och 19 som fick U. 62% klarade sig alltså. Om du vill titta på din tenta och hur den blev rättad, får du gå till studieadministrationen, på 4:e våningen i EDIT-huset. Om det finns ett rättningsbeslut du inte håller med om, och du vill överklaga, ska du lämna kvar din tenta på studieadministrationen! Du får naturligtvis ta en kopia. Maila i så fall till koen(a)chalmers.se, och ange tydligt vilken uppgift det gäller, varför du inte håller med, och vilket rättningsbeslut borde tagits enligt dig. Jag hämtar då ut tentan och tittar på den. Om nödvändigt kan vi boka en tid för att diskutera. Gör detta bara om det skulle påverkat ditt betyg på tentan. Deadline för detta är slutet på november. Omtenta: Omtentan kommer att ske den 7/1, 2016 på förmiddagen. Jag planerar 2-3 extra övningstillfällen innan dess där jag kommer att erbjuda hjälp för er som inte har klarat tentan och som vill ha hjälp. Fyll i tiderna du skulle vilja utnyttja här:
Deadline för att fylla i detta är slutet på november.
There will be a written exam at the end of the course, on
The contents for the exam is everything we have talked about in any of the lectures and/or exercises. The contents, more specifically:
Sets, functions, relations
You should know what a set is. You should know how the empty set, set union, intersection ("snitt"), difference, and complement work, and what their properties are (commutativity, associativity). The sets I expect you to know about are: 𝔹 (booleans, {false, true}), ℕ (natural numbers), ℤ (integer numbers ("heltal")), ℕ+/ℤ+ (positive integers), ℚ (rational numbers), ℝ (real numbers). You do not have to know about the complex numbers.
You should know what a function is. You should know about injectivity, surjectivity. You should know what a bijection is. You should be able to construct examples of functions that do/do not have these properties. You should be able to reason about whether or not functions have these properties. You should know about function composition. You should know about operators. You should know about commutativity, associativity, unit arguments ("identitet"), involution. You should be able to construct examples of operators that do/do not have these properties. You should be able to reason about whether or not operators have these properties.
You should know what a relation is. You should know about reflexivity, symmetry, transitivity. You should know what an equivalence relation is. You should know about equivalence classes. You should be able to construct examples of relations that do/do not have these properties. You should be able to reason about whether or not relations have these properties.
You should know about Hilbert's hotel and how it can be used to show whether or not a given set has as many elements or more elements than there are natural numbers.
exercises week 1 (sets and functions) and the answers exercises week 5 (arithmetic) and the answers (for relations)
Logic
You should know and understand the logical operators (connectives) and/conjunction, or/disjunction, implication, equivalence, not/negation. You should be able to construct truth tables for logical formulas, and use them to reason about which formulas are equivalent to which other ones, or which formulas follow from other ones, in order to check validity of given arguments. You should understand what universal ("for all") quantification is, and what existential ("there exist") quantification is. You should know and be able to use the proper notation for this. You should be able to understand what is required to prove or disprove logical formulas that are built from these connectives and quantifiers. You should be able to formulate a statement in natural language (Swedish) in terms of a logical formulas, and choose the right connectives. You should be able to construct a proof based on your understanding of what is required to prove/disprove a formula.
predikatlogik övningar, skriva och bevis (pdf) exercises week 2 (logic) and the answers
Invariants and Induction
You should be able to understand induction proofs over natural numbers, both simple induction ("1:a induktionsprincipen") and strong induction ("2:a induktionsprincipen"). You should be able to construct induction proofs, with proper base case and step case. You should be able to be clear about what steps you are taking in an induction proof, and why, and be clear about what the induction hypothesis is and where it is used. You should know what a geometric sum and an arithmetic sum is, and be able to recognize them. You should know (or be able to derive) how to compute these sums. You should know how to prove that this way of computing them is correct.
You should know what an invariant is. You should be able to find simple invariants for given examples.
You should be able to understand induction proofs over recursive structures, using structural induction. You should be able to construct structural induction proofs, with proper base cases and step cases. You should be able to be clear about what steps you are taking in an induction proof, and why, and be clear about what the induction hypothesis is and where it is used.
exercises week 3 (induction) and the answers exercises week 6 (structural induction) and the answers
Arithmetic
You should know about divisability, prime numbers, greatest common divisor. Specifically, you should know about and be able to use lemma ("sats") 5.4, 5.6, 5.9, 5.14, 5.15, 5.22, 5.25, 5.28, 5.30, and be able to construct their proofs by yourself. You should know about and be able to use lemma ("sats") 5.31, 5.32, 5.33, but I will not ask you to reconstruct their proofs. You should know about congruences ("kongruensräkning"), and know about lemma ("sats") 5.38 and 5.43, and be able to prove them. You should be able to compute the following things, and be able to show how you computed them, using methods that we have used in the course:
Sections 5.6 and 5.7 (Euler's phi-function and RSA) are as such not part of the exam. But: you should be able to understand how all the material from 5.1-5.5 is used in RSA cryptography; you don't have to be able to reproduce it yourself.
exercises week 5 (arithmetic) and the answers
Graphs
You should know what an undirected graph is. You should know the definition of degree ("gradtal"), path ("väg"), cycle, simple path ("enkel väg"), simple cycle, connectedness ("sammanhängade"), tree ("träd"), and know and be able to prove basic properties of these. You should know when a graph has an Eulercycle, and be able to find an Eulercycle for a given graph. You should know how to prove things about graphs, paths, etc. by induction on the number of nodes in the graph, or number of nodes in the path. You should know what a directed graph is, and what a path and a cycle is in a directed graph.
You should know what a topological order of a directed graph is. You should know when a graph has a topological order. You should be able to compte a topological order for a given graph.
exercises week 7 (graphs) and the answers
Combinatorics
You should know the additive, multiplikative, subtractive, and divisive principle, and how to apply these to calculate numbers of possibilities. You should know how to count permutations and combinations. You should know basic probability theory: number of possibilities we want / total number of possibilities. You should know about Pascal's Triangle, the law associated with it, and the binomial coefficients. You should understand and be able to reproduce how to compute the numbers in the birthday paradox. You should understand (but do not have to be able to reproduce) the numbers in the 41 students problem (which is the same as the 100 prisoner's problem).
Haskell code for combinatorics (.hs) exercises week 8 (combinatorics)
Exam Rules
|