Ma/CS 6/106 abc

Introduction to Discrete Mathematics

9 units (3-0-6)  |  first, seconnd, third terms
Prerequisites: for Ma/CS 6 c, Ma/CS 6 a or Ma 5 a or instructor's permission.
First term: a survey emphasizing graph theory, algorithms, and applications of algebraic structures. Graphs: paths, trees, circuits, breadth-first and depth-first searches, colorings, matchings. Enumeration techniques; formal power series; combinatorial interpretations. Topics from coding and cryptography, including Hamming codes and RSA. Second term: directed graphs; networks; combinatorial optimization; linear programming. Permutation groups; counting nonisomorphic structures. Topics from extremal graph and set theory, and partially ordered sets. Third term: elements of computability theory and computational complexity. Discussion of the P=NP problem, syntax and semantics of propositional and first-order logic. Introduction to the Gödel completeness and incompleteness theorems.
Instructors: Conlon, Schülke, Kechris

Please Note

The online version of the Caltech Catalog is provided as a convenience; however, the printed version is the only authoritative source of information about course offerings, option requirements, graduation requirements, and other important topics.