Discrete Math Syllabus
This syllabus is subject to change.
Some of the more advanced topics listed on this syllabus will be covered only in brevity and are presented to allow the class an understanding of some of the applications of the topics learned.
Readings indicated by a bullet are not in any way required. They are interesting readings for your enjoyment only.

Logic

May 25, 1999:
Course Introduction
Propositional Calculus $1.1 $1.2 (truth tables, negation, converse, contrapositive, biconditional, tautology, contradiction, equivalence)
Predicate Calculus $1.3 (universal quantification, existential quantification)
Proofs $3.1 (rules of inference, modus ponens, modus tollens, fallacies, direct proof, indirect proof, proof by contradiction, proof by cases, existence proof, constructive, nonconstructive, halting problem)
  • Godel, Taski, Church, and the Liar
  • Rosencranz and Guildenstern are Dead - Tom Stoppard

    May 27, 1999:
    Review Proofs
    Induction $3.2 (well-ordering property)
    Boolean Algebra $9 (complement, boolean expressions, equivalent, complement, sum, product, identities, duality, sum-of-products, circuits, inverters, minimization, Karnaugh maps)

    Sets, Number Theory and Probability

    June 1, 1999:
    Sets $1.4 $1.5 (elements, equality, subsets vs. proper subsets, venn diagrams, cardinality, proper set, ordered set, ordered pairs, cartesian product, union, intersection, disjoint, complement, set identities)
    Functions $1.6 (mapping, injection, surjection, bijection, inverse function, composition, graph, floor, ceiling)
    Number Theory $2.3 $2.4 $2.5 (divisibility, primality or compositeness testing, division algorithm, gcd, relatively prime, lcm, modular arithmetic, hashing functions, z generator, Euclidean algorithm, integer representation - multiplication, addition, subtraction, linear congruence, Fermat's little theorem)

    June 3, 1999:
    Midterm Review
    Midterm 1

    June 8, 1999:
    Cardinality
    Number Theory (Chinese Remainder Theorem, RSA)
    Sequences and Summations $1.7
    Algorithms $1.8 $2.1 $2.2 (Big-O notation, worst case time analysis, average case time analysis, time complexity, binary search)
    Matrices $2.6 (arithmetic, transposes, powers, symmetric, identity, zero-one)

    June 10, 1999:
    Counting $4.1 $4.2 $4.3 (sum rule, product rule, inclusion-exclusion principle, tree diagrams, pidgeonhole principle, combinations, permutations, binomial coefficients, Pascal's identity, Binomial theorem)
    Probability $4.4 $4.5 $4.6 (complement, combination, conditional, independent, bernoulli trials, expected value, repitition, distributing objects into boxes)

    Recursion, Relations, Recurrance Relations

    June 15, 1999:
    Recursion $3.3 (recursively defined functions, iteration vs. recursion)
    Recurrence Relations $5.1 $5.2 (fibonacci, solving recurrence relations, divide and conquer relations)
    Relations $6 (reflexive, symmetric, transitive, equivalence, composite, n-ary, tables, projections, joins, digraphs, reflexive closure, paths, connectivity relation, Warshall's algorithm, partial ordering, Lexographic ordering, Hasse diagrams, minimal and maximal elements, topological sorting)

    June 17, 1999:
    Midterm Review
    Midterm 2

    Graphs and their Applications

    June 22, 1999:
    Graphs $7 (simple, multi, pseudo, directed, directed multi, niche overlap, influence, round-robin tournament, precedence, adjacent, degree, Handshaking theorem, undirected graph, initial, terminal, in-degree, out-degree, complete graphs, wheels, n-cubes, bipartite, isomorphism, connectivity, Eulerian path, Hamiltonian path, Dijkstra's algorithm, TSP, planarity, Kuratowski's theorem, graph coloring)

    June 24, 1999:
    Trees $8 (m-ary, binary, decision, prefix codes, universal address, traversals, infix, prefix, postfix, polish notation, sorting - bubblesort, merge sort, spanning tree, backtracking, prim's algorithm)

    June 29, 1999:
    Languages and Grammars $10
    Finite State Machines (regular expressions, Kleene's theorem)
  • A Computer Scientist's View of Life, the Universe, and Everything
    Special Material if time allows

    July 1, 1999:
    Final Exam

    Return to Main page
    Questions: tah10@columbia.edu