Discrete Mathematics for Computer Scientists -- Exam InformationDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | 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:

Doodle för extra övningstillfällen

Deadline för att fylla i detta är slutet på november.


There will be a written exam at the end of the course, on

Saturday, 24 October, 8:30-12:30

The contents for the exam is everything we have talked about in any of the lectures and/or exercises.

Example Exam Questions

The contents, more specifically:


Sets, functions, relations

  • Chapter 2, all sections.

    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.

  • Chapter 3, 3.1-3.7. (Not: 3.8-3.9)

    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.

  • Hilbert's hotel.

    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.

  • More notes:

    Hilbert's hotel

    exercises week 1 (sets and functions) and the answers

    exercises week 5 (arithmetic) and the answers (for relations)


    Logic

  • Chapter 1: 1.2-1.9. (Not: 1.10)

    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.

  • Some more notes:

    predikatlogik övningar, skriva och bevis (pdf)

    proof methods (pdf)

    proof examples (pdf)

    exercises week 2 (logic) and the answers


    Invariants and Induction

  • Chapter 4: 4.1-4.4.

    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.

  • Invariants (not in book).

    You should know what an invariant is. You should be able to find simple invariants for given examples.

  • Structural induction (not in book).

    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.

  • Some more notes:

    induction proofs

    exercises week 3 (induction) and the answers

    structural induction (pdf)

    exercises week 6 (structural induction) and the answers


    Arithmetic

  • Chapter 5: 5.1-5.5. (Not: 5.6-5.7)

    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:

    • Given two integers a and b, compute the integer division ("heltalsdivision") and remainder ("rest") when dividing a by b.

    • Given two integers a and b, compute their greatest common divisor (gcd, or "sgd") using Euklides method.

    • Given two integers a and b, compute one integer solution to ax + by = gcd(a,b) using Bezouts method. You should also be able to compute all solutions.

    • Given three integers a, b, c, investigate what solutions exist to the diophantine equation ax + by = c by computing gcd(a,b) and using Bezouts method. You should also be able to compute all solutions.

    • Given two integers a and b, and two integers m1 and m2 such that gcd(m1,m2)=1, compute one x such that x ≡ a (mod m1) and x ≡ b (mod m2), using the Chinese remainder theorem ("kinesiska restsatsen"). You should also be able to compute all solutions.

    • You should also be able to compute solutions to the Chines remainder theorem that involve more than 2 congruences.

    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.

  • Some more notes:

    Euklides and Bezout (pdf)

    exercises week 5 (arithmetic) and the answers


    Graphs

  • Chapter 7: 7.1-7.4. (Not: 7.5-7.7)

    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.

  • Topological order (not in the book).

    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.

  • Some more notes:

    Topologisk ordning (pdf)

    exercises week 7 (graphs) and the answers


    Combinatorics

  • Chapter 6: 6.1-6.3. Chapter 9: 9.1.

    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).

  • Some more notes:

    Kombinatorik (pdf)

    Haskell code for combinatorics (.hs)

    exercises week 8 (combinatorics)


    Exam Rules

    • The exam questions will be asked in Swedish.

    • You may take one A4 sheet of paper with handwritten notes on one side only. You have to submit these notes together with your answers.

    • You may use an accepted electronic calculator. Accepted calculators are: Casio FX-82..., Texas TI-30... and Sharp, EL-W531... (There are calculators that can be borrowed on the spot, but it is not sure that there will be enough for everybody.)

    • You may not take a text book with you.