YESYES means YES, even more so. OF COURSE! means that no person who doesn't know that stuff shouldn't even consider taking any CS course. IN 456 means that it is a subject material of 456 and I do not assume that they already know it, but it doesn't hurt if they have already seen it. The answers given here a *spefically* for 456. For example, everyone should know elementary probability theory, but it's never used in 456. For many sections, the answer would be "YES" for 477 even if it's "NO" for 456. #Chapter 1: Fundamentals of Discrete Mathematics OF COURSE! #1.1 The rules of sum and product OF COURSE! #1.2 Permuations (That's spelled "permutations" in America.) NO #1.3 Combinations: the binomial theorem NO #1.4 Combinations with repition (Do you mean "repitition"? NO #1.5 The catalan numbers (optional) #Chapter 2: Fundamentals of Logic COMMENT: Failure to understand this material is the greatest problem in 456. YESYES #2.1 Basic connectives and truth tables YESYES #2.2 Logical equivalence: the laws of logic YES #2.3 Logical implication: rules of inference YESYES #2.4 The use of quantifiers YES #2.5 Quantifiers, Definitions, and the proofs of theorems #Chapter 3: Set Theory OF COURSE! #3.1 Sets and Subsets OF COURSE! #3.2 Set operations and the laws of set theory OF COURSE! #3.3 Counting and venn diagrams NO #3.4 A first word on probability NO #3.5 The axioms of probability (optional) NO #3.6 Conditional Probability: independenc3 (optional) NO #3.7 Discrete random variables (optional) #Chapter 4: Properties of the Integers: Mathematical Induction NO #4.1 The well-ordering principle: YES mathematical induction IN 456 #4.2 Recursive definitions NO #4.3 The division algorithm: prime numbers (What do you mean?) NO #4.4 The greatest common divisor: the euclidean algorithm (What do you mean? Every grade school child knows what the gcd is.) NO #4.5 The fundamental theorem of arithmetic But Ruth, in the 5th grade, is doing this in her homework. #Chapter 5: Relations and Functions YES #5.1 Cartesian products and relations YES #5.2 Functions: plain and one-to-one YES #5.3 Onto functions: NO stirling numbers of the second kind NO #5.4 Special functions IN 456 #5.5 The pigeonhole principle YES #5.6 Function composition and inverse function YES #5.7 Compuational complexity (It is a main subject in 456) NO #5.8 Analysis of algorithms #Chapter 6: Languages: Finite State Machines IN 456 6.1 Language: the set theory of strings IN 456 #6.2 Finite state machines: a first encounter NO #6.3 Finite state machines: a second encounter #Chapter 7: Relations: The Second Time Around YES #7.1 Relations revisited: properties of relations NO #7.2 Computer recognition: zero-one matrices and directed graphs NO #7.3 Parial orders: hasse diagrams (What's a parial order?) YES #7.4 Equivalence relations and partitions IN 456 #7.5 Finite state machines: the minimization process #Part 2 #Further Topics in Enumeration I spend time on the three kinds of enumeration: 1) A set is enumerable, i.e., countable. 2) A set is recursively enumerable, i.e., a machine can be built that runs forever printing out all the members of the set. 3) A set is recursively enumerable in canonical order, i.e., a machine can be built that runs forever printing out all the members of the set in canonical order. Every langauge us enumerable, but most are not recursively enumerable. The halting problem is recursively enumerable but not recursively enumerable in canonical order. Recursively enumerable in canonical order is equivalent to decidable. #Chapter 8: The Principle of Inclusion and Exclusion NO #8.1 The principle of inclusion and exclusion NO #8.2 Genearlizations of the principle NO #8.3 Derangements: nothing is in its right place NO #8.4 Rook polynomials NO #8.5 Arrangements with forbidden positions #Chapter 9: Generating Functions NO #9.1 Introductory examples NO #9.2 Definition and examples: calculational techniques NO #9.3 Partitions of integers NO #9.4 The exponential generating function NO #9.5 The summation operator #Chapter 10: Recurrence Relations NO #10.1 The first-order linear recurrence relation NO #10.2 The second-order linear homogeneous recurrence relation with constant coefficients NO #10.3 The nonhomogeneous recurrence relations NO #10.4 The method of generating functions NO #10.5 A special kind of nonlinear recurrence relation (optional) NO #10.6 Divide-and-conquer algorithms (optional) #Part 3 #Graph Theory and Applications YES #Chapter 11: An Introduction to Graph Theory YES #11.1 Definitions and examples NO #11.2 Subgraphs, complements, and graph isomorphism NO #11.3 Vertex degree: euler trails and circuits NO #11.4 Planar graphs NO #11.5 Hamilton paths and cycles NO #11.6 Graph coloring and chromatic polynomials #Chapter 12: Trees NO #12.1 Definitions, properties, and examples NO #12.2 Rooted trees NO #12.3 Trees and sorting NO #12.4 Weighted trees and prefix codes NO #12.5 Biconnected components and articulation points #Chapter 13: Optimization and Matching NO #13.1 Dijkstra's shortest path algorithm NO #13.2 Minimal spanning trees: the algorithms of kruskal and prim NO #13.3 Tranport networks: the max-flow min-cut theorem #Part 4 #Modern Applied Algebra #Chapter 14: Rings and modular arithmetic NO #14.1 The ring structure: definitions and examples NO #14.2 Ring properties and substructures YES #14.3 The integer modulo n (They learned this in 135, didnt they?) NO #14.4 Ring homomorphisms and isomorphisms #Chapter 15: Boolean Algebra and Switching Functions YES #15.1 Switching functions: disjunctive and conjuctive normal forms NO #15.2 Gating networks: minimal sums of products: karnaugh maps NO #15.3 Further applications: don't-care conditions NO #15.4 The structure of boolean algebra (optional) #Chapter 16: Groups, Coding Theory, and Polya's Method of Enumeration NO #16.1 Definition, examples, and elementary properties NO #16.2 Homomorphisms, isomorphisms, and cyclic groups NO #16.3 Cosets and lagrange's theorem NO #16.4 The RSA cryptosystem (optional) But this is the subject of an extra credit problem. (Every 656 student is required to turn in one extra credit problem of his choice.) NO #16.5 Elements of coding theory NO #16.6 The Hamming metric NO #16.7 The parity check and generator matrices NO #16.8 Group codes: decoding with coset leaders NO #16.9 Hamming matrices NO #16.10 Counting and equivalence: burnside's theorem NO #16.11 The cycle index NO #16.12 The pattern inventory: polya's method of enumeration #Chapter 17: Finite Fields and Combinatorial Designs NO #17.1 Polynomial rings NO #17.2 Irreducible polynomials: finite fields NO #17.3 Latin squares NO #17.4 Finite geometrics and affine planes NO #17.5 Block designs and projective planes