Topic.md

Hey guys, as it turns out nothing gets me more erect than helping others so here's an extensive list of the topics in past papers so you can refer to them while you're studying.

Bear in mind: When you see the word "typical" it means it's really worth learning. You don't want to lose marks because you couldn't be bothered to learn how to do a "typical" question that repeats itself all over the place.

Some "typical" questions include: Probability of certain substrings of binary strings, biased coins, Fermat's little theorem, "How many ways can we choose 3 representatives out of 8 students". There are plenty of examples of these in the textbook, learn them.

Ctrl + F is your best friend.

Dec 12

Question 1:

• Relations (don't worry about partial ordering)
• Proof by induction involving a function
• Sets, subsets, cardinality, set notation
• Fermat's little theorem

Question 2:

• Typical bit string probability question
• Typical "How many ways can you distribute this" question
• Directed graph question; what it means for a directed graph to be "strongly connected"
• Typical biased coin probability question

Question 3:

• Proof involving antisymmetric binary relations
• Big O proof question
• "Prove that 21 divides n^7 - n for all +ve integers n". Fermat's little theorem / Chinese remainder theorem

Question 4:

• Proof involving undirected graphs, degrees, vertices
• Isomorphism
• Big 9 mark coin probability question

Aug 13

Question 1:

• Equivalence relation, equivalence class definition
• Proof involving equivalence relations
• Nasty injective function proof

Question 2:

• Typical "7 employees in a company, how many ways can we choose them to do this and that" question
• Bipartite graph question
• Typical biased coin probability question

Question 3:

• A couple of "total function" questions, don't think we've covered it but don't quote me on that
• Typical Mod question (Fermat's little theorem, chinese remainder theorem)

Question 4:

• Couple of undirected graph questions
• Jane flips a coin for 9 marks

December 2013:

Question 1:

• Proof involving bijective functions
• Proof involving binary relations, antisymmetric

Question 2:

• Typical "How many ways can we choose some students to be representatives" question
• Typical "How many different strings can we form with this set of strings where this is a capital T or something" question
• Integer proof question, crazy stuff
• Proof involving undirected bipartite graphs, Hamiltonian

Question 3:

• Big theta/omega question not sure which one but you know what I mean (Chapter 3 stuff)
• Typical Computing Mods question Fermat's theorem you get the idea

Question 4:

• Proof involving undirected graphs, isomorphism
• Binomial coefficient proof
• Random Variable probability question, variance
• Typical biased coin question

August 2014:

Question 1:

• Definition of injective, surjective, bijective
• Prime factor, binary relation
• Proof involving all of the above

Question 2:

• Typical "How many binary strings of length 8 can we do this and that" question
• "How many solutions (x1, x2, x3) are there to the following inequality x1 + x2 + x3 < 8" I'm not sure, think this is chapter 3?
• Polynomials or something I have no idea what's going on there
• Bipartite graphs, Hall's Theorem

Question 3:

• Proof by induction
• Primes, gcd

Question 4:

• TREES!
• Colourings of graphs, chromatic number
• N-cube graph
• Probability question, sample space (probability)
• Biased coin

December 2014

Part A

Question 1:

• Proof involving permutations
• Typical permutations question

Question 2:

• Typical biased dice probability question
• Typical fair coin random variable question

Question 3:

• Gcd and stuff, not sure
• mods

Question 4:

• Some predicate question, P(1) or something
• Fibonacci sequence!

Question 5:

• Algorithms!

Part B

Question 1:

• Relations; irreflexive, symmetric, symmetric, proofs involving
• Proofs involving sets, relations

Question 2:

• Giant graphs question, all kinds of things Morty

Question 3:

• Massive probability question, all this stuff is really worth learning. Bayes' theorem.

Really hope this helps. Good luck guys.