CO 600s


CO 601 Fundamentals of Enumerative Combinatorics (0.50) LECCourse ID: 012175
Elementary counting, bijections. Sets, weights, decompositions. The ordinary generating series, sum, product, composition and differentiation lemmas; formal use in combinatorial identities. The algebra of formal power series. Strings on a finite alphabet. Unique factorization of strings. Pattern and noncommutative methods. The Maximal Decomposition Theorem. Rational and algebraic generating series, linear recurrence equations. Integer partitions. Functional equation. Ferrers graph, geometric decompositions, Euler's Pentagonal Number Theorem. Vector spaces over GF(q), linear transformations, finite forms of partition theorems, Gaussian coefficients. Inversions in permutations. The exponential generating series, rule of sum and product, composition and differentiation lemmas. Disjoint cycles and permutations, functions, set partitions, graphs. Lagrange's Implicit Function Theorem. Lattice paths, Wiener-Hopf Factorization. Lattice polygons, polyominos, trees and functions. Formal use in combinatorial identities. Enumeration under group action, Orbit-Stabilizer Theorem, Burnside's Lemma, Polya's Theorem. Necklaces, abstract trees and trees embedded in the plane.

CO 602 Fundamentals of Optimization (0.50) LECCourse ID: 012176
Linear Optimization, Convexity (4 weeks): Duality in linear optimization. Farkas' Lemma and the theorems of the alternative. Duality theorem for linear programming. Complementary Slackness theorem. Simplex Method. Polyhedra and elementary convex geometry. Combinatorial Optimization (4 weeks): Linear diophantine equations. Facets of polyhedra. Integrality of polyhedra. Shortest paths and optimal flows. Total Unimodularity. Konig's Theorem. Max. Flow-Min. Cut Theorem. (Hungarian) Bipartite matching algorithm. Continuous Optimization (4 weeks): Convex functions. Analytic characterizations of convexity. Existence and uniqueness of optimal solutions. Separating and supporting hyperplane theorems. Lagrangean Duality. Karush-Kuhn-Tucker Theorem. Conic Optimization problems. Ellipsoild Method.

CO 630 Algebraic Enumeration (0.50) LECCourse ID: 000232
The Lagrange implicit function theorem, hypergeometric series, and the ring of formal Laurent series. The combinatorics of Eulerian generating series, enumeration under the action of a group, the algebra of symmetric functions, the group algebra of the symmetric group, with applications.

CO 634 Combinatorial Designs (0.50) LECCourse ID: 000233
Pairwise orthogonal latin squares. Transversal designs and finite planes. Balanced incomplete block designs, group divisible designs and pairwise balanced designs. Symmetric designs and Hadamard matrices. Recursive constructions. Wilson's fundamental construction.

CO 639 Topics in Combinatorics (0.50) LECCourse ID: 010470
1 Quantum Computing
3 Quantum Error Correction

CO 640 Topics in Graph Theory (0.50) LECCourse ID: 000239

CO 642 Graph Theory (0.50) LECCourse ID: 000245
Connectivity (Menger's Theorem, ear decomposition, and Tutte's Wheels Theorem) and matchings (Hall's Theorem and Tutte's Theorem). Flows: integer and group-valued flows, the flow polynomial, the 6-flow theorem. Ramsey theory: upper and lower bounds, explicit constructions. Extremal graph theory: Turan's theorem, the Erdos-Gallai theorem. Probabilistic methods.

CO 644 Algebraic Graph Theory (0.50) LECCourse ID: 000246
Automorphisms. Cayley graphs and their properties. Arc and distance transitive graphs. Generalised polygons. homomorphisms and covers. Adjacency and incidence matrices. Eigenvectors of graphs. Quotients. Interlacing. Strongly regular graphs. Line graphs and graphs with least eigenvalue -2. Expanders. Shannon capacity.

CO 650 Combinatorial Optimization (0.50) LECCourse ID: 000247
Characterizations of optimalsolutions and efficient algorithms for optimization problems over discrete structures. Topics include network flows, optimal matchings, T-joins and postman tours, matroid optimization.

CO 652 Integer Programming (0.50) LECCourse ID: 000248
Formulation of problems as integer linear programs. Solution by branch-and-bound and cutting plane algorithms. Introduction to the theory of valid inequalities and polyhedral combinatorics.

CO 663 Convex Optimization and Analysis (0.50) LECCourse ID: 000250
An introduction to the modern theory of convex programming, its extensions and applications. Structure of convex sets, separation and support, set-valued analysis, subgradient calculus for convex functions, Fenchel conjugacy and duality, Lagrange multipliers, minimax theory. Algorithms for condifferentiable optimization. Lipschitz functions, tangent cones and generalized derivatives, introductory non-smooth analysis and optimization.

CO 664 Quadratic Programming (0.50) LECCourse ID: 000251
A course on theory and solution algorithms for the minimization of a convex quadratic function subject to linear constraints. Karush-Kuhn-Tucker conditions, duality theory. Active set solution algorithms and their parametric extensions. Quadratic programmes as linear complementarity problems. Applications in portfolio optimization and structural analysis.

CO 666 Continuous Optimization (0.50) LECCourse ID: 000252
Geometry and numerical algorithms of nonlinear optimization. Variable metric and conjugate gradient methods. Convex programming. Feasible and nonfeasible direction methods. Recursive quadratic programming, nonorthogonal projections and active set strategies.

CO 671 Semidefinite Optimization (0.50) LECCourse ID: 011371
Optimization over convex sets described as the intersections of the set of symmetric, positive semidefinite matrices with affine spaces. Formulations of problems from combinatorial optimization, graph theory, number theory, probability and statistics, engineering design and control theory. Theoretical and practical consequences of these formulations. Duality theory and algorithms.

CO 681 Quantum Information Processing (0.50) LECCourse ID: 011589
(Cross-listed with CS 667, PHYS 767)
Review of basics of quantum information and computational complexity; Simple quantum algorithms; Quantum Fourier transform and Shor factoring algorithm: Amplitude amplification, Grover search algorithm and its optimality; Completely positive trace-preserving maps and Kraus representation; Non-locality and communication complexity; Physical realizations of quantum computation: requirements and examples; Quantum error-correction, including CSS codes, and elements of fault-tolerant computation; Quantum cryptography; Security proofs of quantum key distribution protocols; Quantum proof systems. Familiarity with theoretical computer science or quantum mechanics will also be an asset, though most students will not be familiar with both.

CO 685 The Mathematics of Public-Key Cryptography (0.50) LECCourse ID: 010331
An in-depth study of public-key cryptography, including: number-theoretic problems - prime generation, integer factorization, discrete logarithms; public-key encryption; digital signatures; key establishment; secret sharing; and security definitions and proofs.

CO 687 Applied Cryptography (0.50) LECCourse ID: 010471
A broad introduction to cryptography, highlighting the major developments of the past twenty years, including symmetric ciphers, hash functions and data integrity, public-key encryption and digital signatures, key establishment, and key management. Applications to internet security, computer security, communications security, and electronic commerce will be studied.

CO 690 Literature and Research Studies (0.50) RDGCourse ID: 000253
Instructor Consent Required
1 Semidefinite Programming
2 Applied Cryptography
3 Enumerative Combinatorics
4 Finite Geometry
5 Knots Quantum Gravity
6 Information Theory
7 Elliptic Curves
8 Boundary Strctr of Convex Sets

CO 700s


CO 730 Asymptotic Enumeration (0.50) LECCourse ID: 000269
Methods of obtaining asymptotic estimates for sums arising in enumeration. Application to Bell numbers, the distribution of balls into cells, and random graphs. Methods for obtaining asymptotic estimates for the coefficients of generating functions. Application to random planar graph problems and to unimodality problems.

CO 734 Topics in Combinatorial Design (0.50) LECCourse ID: 010473

CO 738 Probabilistic Methods in Discrete Mathematics (0.50) LECCourse ID: 011796
The probabilitistic method proves the existence of a combinatorial structure by showing a random element in an appropriate probability space has the desired properties with positive probability. The course will introduce the basic techniques and give applications in graph theory, combinatorics, discrete optimization, theoretical CS. In particular, some of the following will be considered: linearity of expectation; alterations; the second moment method; bounding of large deviations; the local lemma; correlation inequalities; martingales and tight concentration; discrepancy; derandomization.

CO 739 Topics in Combinatorics (0.50) LECCourse ID: 000273
1 Prob Mthds in Discrete Math
2 Random Structures
3 Physical Graph Theory
4 Knots and Physics
5 Partially Ordered Sets in CO
6 Enum Topics in Algebraic Comb
7 Lines

CO 743 Directed Graphs and Applications (0.50) LECCourse ID: 000297
An introduction to the concepts of directed graphs, problems about directed circuits and directed cuts, and minimax equalities relating these and other graphical objects.

CO 745 Graph Theory Algorithms (0.50) LECCourse ID: 010474
A general study of algorithms for the solutions of problems in graph theory. Included are algorithms for graph isomorphism, planarity, connectedness, chromatic number, spanning trees, circuits and many others.

CO 749 Topics in Graph Theory (0.50) LECCourse ID: 000298
1 Introduction to Graph Minors
2 Colouring Embedded Graphs

CO 750 Topics in Combinatorial Optimization (0.50) LECCourse ID: 000304
1 Packing and Covering

CO 751 Matroid Theory (0.50) LECCourse ID: 000310
Study of abstract properties of linear independence, and its applications in combinatorics. Axioms, duality, minors, connectivity, representability.

CO 754 Approximation Algorithms in Combinatorial Optimization (0.50) LECCourse ID: 011797
The course studies some of the successful paradigms for designing approximation algorithms and for proving approximation guaranteees, such as the greedy method, formulating and solving linear programming relaxations, the primal-dual method, randomized rounding, semidefinite programming relaxations, approximation of metrics. Also, the PCP theorem, and its application to the hardness of approximating specific problems, e.g., set covering and shortest lattice vector.

CO 759 Topics in Discrete Optimization (0.50) LECCourse ID: 000311

CO 765 Mathematical Programming (0.50) LECCourse ID: 010475

CO 769 Topics in Continuous Optimization (0.50) LECCourse ID: 000317
1 Num Solution of Optim Probl

CO 771 Mathematical Operations Research (0.50) LECCourse ID: 010476

CO 778 Portfolio Optimization (0.50) LECCourse ID: 011622
(Cross-listed with ACTSC 973)
Basic optimization: quadratic minimization subject to leanear equality constraints. Effecient portfolios: the efficient frontier, the capital market line, Sharpe ratios and threshold returns. Practical portfolio optimization: short sales restrictions target portfolios, transactions costs. Quadratic programming theory. Special purpose quadratic programming algorithms for portfolio optimization: today's large investment firms expect to solve problems with at least 1000 assets, transactions costs and various side constraints in just a few minutes of computation time. This requires very specialized QP algorithms. An overview of such algorithms will be presented with computational results from commercial problems. The efficient frontier, the capital market line, Sharpe ratios and threshold returns in practice.

CO 779 Topics in Operations Research (0.50) LECCourse ID: 010477
1 Semidefinite Optimization
2 Portfolio Optimization

CO 781 Topics in Quantum Information (0.50) LECCourse ID: 011847
1 Quantum Algorithm & Complexity
2 Quantum Error Correction

CO 785 Algorithmic Number Theory (0.50) LECCourse ID: 011299
(Cross-listed with CS 765)
Fundamental problems of elementary and algebraic number theory from an algorithmic and computational complexity point of view with emphasis placed on analysis of algorithms. Topics include basic arithmetic algorithms; computation over finite fields; primality testing; algorithms for integer factorization; algorithms in number fields.

CO 789 Topics in Cryptography (0.50) LECCourse ID: 011277
1 Pairing Based Cryptography

CO 800s


CO 839 Seminar in Combinatorics (0.50) SEMCourse ID: 000332
Department Consent Required

CO 849 Seminar in Graph Theory (0.50) SEMCourse ID: 010479
Department Consent Required

CO 859 Seminar in Discrete Optimization (0.50) SEMCourse ID: 010480
Department Consent Required

CO 869 Seminar in Continuous Optimization (0.50) SEMCourse ID: 010481
Department Consent Required

CO 879 Seminar in Operations Research (0.50) SEMCourse ID: 010482
Department Consent Required