My account Contact me

CEGEP • Montreal

Mathematics for Computer Science, 201-N11

Mathematics for Computer Science, 201-N11, is the foundation course of the CEGEP computer science programs, such as Techniques de l'informatique (Computer Science Technology in English-language CEGEPs): logic, sets, number systems and graphs. The ideas are accessible, but the rigour expected in written answers often catches students off guard.

10 fully corrected exercise sets (116 exercises), 9 revision sheets, and a practice paper. Free, no account needed. The same course in French.

Logic and proof

  1. 1 Boolean and mathematical logic Logical connectives and truth tables, the laws of Boolean algebra and De Morgan, the implication with its contrapositive and converse, quantifiers and their negation, normal forms read off a truth table. Then an exam-level part: a four-variable Karnaugh map, the half adder and the universal NAND gate, an access control system to simplify, and checking an argument with modus tollens. Sheet
  2. 2 Proof techniques The five techniques of the course, and above all choosing the structure before the first line: direct proof, the contrapositive that is not the converse, proof by contradiction with irrationality and the infinitude of primes, proof by cases, disproof by counterexample. Then an exam-level part: the pigeonhole principle proved and then generalized, induction placed among the five, the impossibility of a universal lossless compressor and four write-ups of the same proof to sort out. Sheet

Numbers in a computer

  1. 3 Number systems in computing Positional weights and conversions between binary, octal, hexadecimal and decimal, repeated division, binary arithmetic worked by hand, two's complement and its asymmetric range, overflow versus carry. Then an exam-level part: masks and bitwise operations, ASCII, BCD and Gray codes with parity, a problem on colours and memory, and the IEEE 754 single-precision format. Two complete labs, in base 8 and then in base 16, extend the basics: expanded notation, conversions both ways, addition, 8's and 16's complements, subtraction, long multiplication and a round trip checked in decimal. Sheet
  2. 4 Binary arithmetic and machine numbers Addition and subtraction column by column, borrowing against the two's complement method, multiplication and the two right shifts, the asymmetric signed range, and the difference between a carry out and a signed overflow. Then at exam level: hexadecimal masks on a status register, binary fractions and Q4.4 fixed point, a 12-bit sensor whose sign extension is wrong, and the IEEE 754 single precision format down to the last bit.
  3. 5 Modular arithmetic Two calculation exercises first: nine remainders to compute modulo n and a GCD, then eight inverses and congruences to solve; then Euclidean division and the remainder that is always nonnegative, with the difference in convention between Python and the C language that catches programmers out; congruences, their three equivalence properties and their compatibility with sums and products, proved and then used to reduce before multiplying; the tables modulo 7 and modulo 6, where zero divisors appear, and why a prime modulus changes everything; the Euclidean algorithm justified in one line and illustrated by a tiling with squares, with the worst case of the Fibonacci numbers; the modular inverse, its existence criterion and linear congruences with zero, one or several solutions. Part B establishes Bézout's identity and the extended Euclidean algorithm, Fermat's little theorem and fast exponentiation with its gain in figures, then deals with ISBN check digits and their weakness on transpositions, and finally a complete RSA encryption with small prime numbers. Sheet

Sets, relations and functions

  1. 6 Set theory and relations Membership versus inclusion, the power set, set operations and the Cartesian product, De Morgan's laws by double inclusion and by membership table, Venn diagrams and inclusion-exclusion, binary relations with their Boolean matrix and their directed graph. Then an exam-level part: the four properties, equivalence relations and partitions, a survey with three sets, and a partial order problem with the transitive closure. Sheet
  2. 7 Injective, surjective and bijective functions The function as a relation subject to existence and uniqueness, the image and inverse image of a subset, fibres; then the three natures read on an arrow diagram and on the squaring rule placed between four pairs of domain and codomain, the three standard write-ups, composition and what it inherits. Part B treats the substitution cipher as a bijection with its inverse, counting functions, injections, surjections and bijections with the three cardinality inequalities, a hash function read as a function rather than as a probability computation, and the enumeration of Z by N. Sheet

Induction, graphs and counting

  1. 8 Induction and recursion The principle of mathematical induction and its two steps, with the two counterexamples that show neither one is optional: the property n equals n plus one, whose inductive step is valid, and Euler's polynomial, prime up to thirty-nine; the three families of induction proofs, sums, inequalities and divisibility, and the move specific to each; strong induction applied to the existence of a prime divisor, and two-step induction, which requires two base cases; the translation into recursive functions, the two termination conditions and the role of the call stack; the cost of naive Fibonacci, counted on its tree and then proved equal to twice Fibonacci minus one. Part B solves linear recurrences with the characteristic equation up to Binet's formula, analyzes binary search and merge sort, then takes on the Towers of Hanoi, whose exponential cost is unavoidable this time, which gives the criterion for telling a bad algorithm from a hard problem. Sheet
  2. 9 Introduction to graphs and matrices One set of calculations: ten direct matrix computations, from the product to the 3x3 determinant; then vertices, edges and the handshaking lemma, the adjacency matrix of a directed graph, matrix operations and noncommutativity, powers of the matrix and counting paths, connectivity and the reachability matrix. Then an exam-level part: plane transformations and computer graphics, determinant and inverse matrix, a weighted road network and composing transformations in homogeneous coordinates. Sheet
  3. 10 Counting and probability One calculation exercise: ten counting problems to compute directly, from factorials to the binomial theorem; then the multiplication principle applied to IPv4 and IPv6 addresses, 24-bit colours and identifiers; the four selection models set out in a table, with the counterintuitive finding that forbidding repeated characters weakens a password; Pascal's triangle proved by a splitting argument, the sum of a row equal to two to the power n, and the naive recursive computation that runs into the memoization problem of the recursion chapter; the pigeonhole principle, from thirteen people and twelve months to the proof that no hash function can avoid collisions; uniform probability and the habit of going through the complement. Part B treats Bayes' theorem on a screening test, where only one positive in six is actually sick, and on a spam filter, where the same formula gives ninety-six percent; expected value and the average-case analysis of an algorithm; then two full problems, the strength of a password measured in bits of entropy and the birthday paradox applied to the sizing of cryptographic hashes. Sheet

When the chapters are done

A full paper under exam conditions, on the whole course. Do it once every chapter is behind you: it measures what you can do on a question you have never seen.

Practice exam

Practice final exam, 201-N11

A practice final that covers the seven main themes of the course in ten exercises. Part A: a Karnaugh map simplified into two blocks, the disjunctive normal form, and the contrapositive set against the converse; base conversions, two's complement and signed overflow read on the wheel of the sixteen codes; equivalence relations, partitions and the partial order of divisibility; an adjacency matrix whose square counts the paths of length two; congruences and the affine cipher with its inverse modulo twenty-six. Part B: a complete proof by induction, including the sum of cubes equal to the square of the sum of the integers and a sequence that turns out to be Newton's method; a binary search tree, its height, its degeneration on sorted data and the probability of that worst case; five cross-chapter claims to correct; then two synthesis problems, storing passwords with salt and the cost of analyzing a network.

  • 10 questions
  • 100 points
  • 150 minutes
Sit the paper

Need support and not only exercises? CEGEP tutoring in Montreal

Looking for a tutor in Montreal?

Get in touch for a first session. We work on exercises set at the real level of your CEGEP's exams, in English or in French.

Contact me WhatsApp
Site by Studio Squalli