1
$\begingroup$

(YES) - included; (NO) - explicitly excluded;

as stated from the IOI syllabus(2019);

5.2 Discrete Structures (DS)

DS1. Functions, relations, and sets

(YES)Functions (surjections, injections, inverses, composition)

(YES) Relations (reflexivity, symmetry, transitivity, equivalence relations, total/linear order relations, lexicographic order)

(YES) Sets (inclusion/exclusion, complements, Cartesian products, power sets)

(NO) Cardinality and countability (of infinite sets)

DS2. Basic logic

(YES) First-order logic

(YES) Logical connectives (incl. their basic properties)

(YES) Truth tables

(YES)Universal and existential quantification(Note: statements should avoid definitions with nested quantifiers whenever possible.)

(YES) Modus ponens and modus tollens

(YES)Normal forms

(NO) Validity

(NO) Limitations of predicate logic

DS3. Proof techniques

(YES) Notions of implication, converse, inverse, contrapositive, negation, and contradiction Direct proofs, proofs by: counterexample, contraposition, contradiction

(YES) Mathematical induction

(YES)Strong induction (also known as complete induction)

(YES)Recursive mathematical definitions (incl. mutually recursive definitions)

DS4. Basics of counting

(YES) Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers)

(YES) Permutations and combinations (basic definitions)

(YES)Factorial function, binomial coefficients

(YES) Inclusion-exclusion principle

(YES) Pigeonhole principle

(YES) Pascal’s identity, Binomial theorem

(NO)Solving of recurrence relations

(NO)Burnside lemma

DS5. Graphs and trees

(YES)Trees and their basic properties, rooted trees

(YES)Undirected graphs (degree, path, cycle, connectedness,

Euler/Hamilton path/cycle, handshaking lemma)

(YES) Directed graphs (in-degree, out-degree, directed path/cycle, Euler/Hamilton path/cycle) (YES) Spanning trees

(YES) Traversal strategies

(YES) ‘Decorated’ graphs with edge/node labels, weights, colors

(YES) Multigraphs, graphs with self-loops

(YES) Bipartite graphs

(YES) Planar graphs

(NO)Hypergraphs

(NO)Specific graph classes such as perfect graphs

(NO)Structural parameters such as treewidth and expansion

(NO)Planarity testing

(NO)Finding separators for planar graphs

DS6. Discrete probability

Applications where everything is finite (and thus arguments about probability can be easily turned into combinatorial arguments) are (YES), everything more complicated is (NO)

I am preparing for IOI and want a good discrete structure book/resource to learn the above mentioned subjects.

I am currently taking Pre-Calculus relevant Mathematics in my country. I am in 10th grade, India.

I have searched for courses and books but I don't how to find a good one.

Any recommendations and edits are welcome.

$\endgroup$
5
  • 2
    $\begingroup$ I'm using the Levin book. It may not have all the topics. But it's lovely, and it's free. And I will add any topics I need to. discrete.openmathbooks.org/dmoi3.html $\endgroup$ – Sue VanHattum Dec 12 '20 at 7:09
  • $\begingroup$ It is free and it is great. $\endgroup$ – Neelesh V Dec 12 '20 at 8:29
  • $\begingroup$ I'm very happy with Rosen, but it's not open/free. I have lecture slides here. $\endgroup$ – Daniel R. Collins Dec 12 '20 at 20:06
  • $\begingroup$ @DanielR.Collins you teach discrete mathematics right? $\endgroup$ – Neelesh V Dec 13 '20 at 5:15
  • $\begingroup$ @NeeleshV: Yes, I do. $\endgroup$ – Daniel R. Collins Dec 13 '20 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.