Discrete Structures

Historical Term

N/A

Loyola University Chicago

COMP 163

These are the top 15 topics in Discrete Structures

  1. Logic and Propositional Calculus - Propositions, truth values, logical connectives - Truth tables and logical equivalences - Implication, logical arguments, and proofs - Predicate logic, quantifiers (ACM Knowledge Area: DS - Discrete Structures)

  2. Set Theory - Sets, subsets, set operations, Venn diagrams - Cartesian products, power sets, counting (ACM Knowledge Area: DS - Discrete Structures)

  3. Relations - Relations, properties of relations, closures - Equivalence relations, partial orders (ACM Knowledge Area: DS - Discrete Structures)

  4. Functions - Functions, properties of functions, composition, inverse - Pigeonhole principle (ACM Knowledge Area: DS - Discrete Structures)

  5. Combinatorics - Permutations, combinations - Binomial theorem, Pascal’s triangle - Generating functions, recurrence relations (ACM Knowledge Area: DS - Discrete Structures)

  6. Probability - Basic probability theory, conditional probability, independence - Random variables, expectation, variance - Bayes’ theorem (ACM Knowledge Area: DS - Discrete Structures)

  7. Graph Theory - Graphs, properties of graphs, graph representations - Graph traversals, connectivity, shortest paths - Trees, spanning trees, minimum spanning trees (ACM Knowledge Area: DS - Discrete Structures)

  8. Trees - Tree terminology, types of trees - Traversals, binary trees, binary search trees (ACM Knowledge Area: DS - Discrete Structures)

  9. Matrices and Linear Algebra - Matrices, matrix operations, determinants - Systems of linear equations, Gaussian elimination (ACM Knowledge Area: DS - Discrete Structures)

  10. Number Theory - Divisibility, primes, greatest common divisor, Euclidean algorithm - Modular arithmetic, Fermat’s Little Theorem, Euler’s theorem (ACM Knowledge Area: DS - Discrete Structures)

  11. Cryptography (optional) - Basic concepts, symmetric key cryptography - Public key cryptography, RSA algorithm (ACM Knowledge Area: IAS - Information Assurance and Security)

  12. Automata Theory (optional) - Finite automata, regular expressions, context-free grammars - Turing machines, decidability, undecidability (ACM Knowledge Area: PL - Programming Languages)

  13. Formal Languages and Grammars (optional) - Regular languages, context-free languages, pushdown automata - Chomsky hierarchy, parsing (ACM Knowledge Area: PL - Programming Languages)

  14. Algorithms on Discrete Structures (optional) - Algorithms on graphs, trees, and other discrete structures (ACM Knowledge Area: AL - Algorithms and Complexity)

  15. Computational Complexity (optional) - Time complexity, space complexity, P and NP - NP-completeness, NP-hardness (ACM Knowledge Area: AL - Algorithms and Complexity)