CS 6117 (Fall 2014) - Category Theory for Computer Scientists
Overview
CS6117 - Category Theory for Computer Scientists is an introduction to category theory, with a focus on material with established applications to computer science. The course will emphasize developing comfort with abstraction and instantiation while not assuming students have a strong background in mathematics.
Class Times: MWF 1:25-2:15
Location: 211 Upson Hall
Instructor:
Ross Tate
Office: 434 Gates Hall
Office Hours: By appointment
Grading There will be a (very) small homework assignment approximately each week, a midterm, and a non-cumulative final:
Assignments: 60% (Each will be worth 5%, and there will be more than 12, so any extra will count as extra credit.)
Midterm: 20%
Final: 20%
Piazza: http://piazza.com/cornell/fall2014/cs6117
Related Reading
- Abstract and Concrete Categories - The Joy of Cats by Jiri Adamek, Horst Herrlich, and George E. Strecker (2004)
- Higher Operads, Higher Categories by Tom Leinster (2003)
- Categories for the Working Mathematician by Saunders Mac Lane (1971)
Schedule
| Date | Topic | Technical Notes | Assignments |
|---|---|---|---|
| Week 1 | |||
| Aug 27 | Goals of the Course Monoids |
Monoids [tex] | Aids: packages.tex def.tex Available: Monoids [tex] |
| Aug 29 | Aggregation | Aggregation [tex] | |
| Week 2 | |||
| Sep 1 | Labor Day | Sep 3 | Homomorphisms | Homomorphisms [tex] |
| Sep 5 | Categories | Categories [tex] | Due: Monoids [tex] Available: Categories [tex] |
| Week 3 | |||
| Sep 8 | Functors | Functors [tex] | |
| Sep 10 | Isomorphisms | Isomorphisms [tex] | |
| Sep 12 | Multicategories | Multicategories [tex] | Due: Categories [tex] Available: Multicategories [tex] |
| Week 4 | |||
| Sep 15 | Internalization | Internalization [tex] | |
| Sep 17 | Enrichment | Enrichment [tex] | |
| Sep 19 | Subobjects | Subobjects [tex] | Due: Multicategories [tex] Available: Transformations [tex] |
| Week 5 | |||
| Sep 22 | Nulls | Nulls [tex] | |
| Sep 24 | Transformations | Transformations [tex] | |
| Sep 26 | Transpositions | Transpositions [tex] | Due: Transformations [tex] Available: Adjunctions [tex] |
| Week 6 | |||
| Sep 29 | 2-Categories | 2-Categories [tex] | |
| Oct 1 | No Lecture | ||
| Oct 3 | Limits | Limits [tex] | Due: Adjunctions [tex] Available: Limits [tex] |
| Week 7 | |||
| Oct 6 | Adjunctions | Adjunctions [tex] | |
| Oct 8 | Colimits | Colimits [tex] | |
| Oct 10 | Monads | Monads [tex] | Due: Limits [tex] Available: Monads [tex] |
| Week 8 | |||
| Oct 13 | Canadian Thanksgiving | ||
| Oct 15 | Monad Algebras | Monad Algebras [tex] | |
| Oct 17 | Kleisli Category | Kleisli Category [tex] | Due: Monads [tex] Available: Effects [tex] Aids: rossbb.pfb rossbb.tfm t1rossbb.fd |
| Week 9 | |||
| Oct 20 | Effectors | Effectors [tex] | |
| Oct 22 | Productors | Productors [tex] | |
| Oct 24 | Noninterference | Noninterference [tex] | Due: Effects [tex] Available: Security [tex] |
| Week 10 | |||
| Oct 27 | Confidentiality and Integrity | Confidentiality and Integrity [tex] | |
| Oct 29 | Types | Types [tex] | |
| Oct 31 | Existential Quantification | Sections 1 and 2 of Inferable Existential Quantification |
Due: Security [tex] Available: Existentials [tex] |
| Week 11 | |||
| Nov 3 | Deciding Subtyping | Section 3 of Inferable Existential Quantification |
|
| Nov 5 | Computing Joins | Sections 4 and 5 of Inferable Existential Quantification |
|
| Nov 7 | Comma Categories | Joy of Cats, Wikipedia, nLab | Due: Existentials [tex] Available: Factorizations [tex] |
| Week 12 | |||
| Nov 10 | Algebras and Coalgebras | Joy of Cats, Wikipedia, nLab | |
| Nov 12 | Implications | Joy of Cats | |
| Nov 14 | Inference | Sections 3.3, 4, and 5.2 of Generating Compiler Optimizations from Proofs |
Due: Factorizations [tex] Available: Proofs [tex] |
| Week 13 | |||
| Nov 17 | Proof Generalization | Section 3.4 of Generating Compiler Optimizations from Proofs |
|
| Nov 19 | Pushout Completions | Section 3.4 of Generating Compiler Optimizations from Proofs |
|
| Nov 21 | Tableaus | Section 5.1 of Generating Compiler Optimizations from Proofs Section 1 of Opfibrations |
Due: Proofs [tex] Available: Databases [tex] |
| Week 14 | |||
| Nov 24 | Opfibrations | Opfibrations [tex] Section 2 of Opfibrations |
|
| Nov 26 | American Thanksgiving | Due: Databases [tex] | |
| Nov 28 | American Thanksgiving | ||
| Week 15 | |||
| Dec 1 | Topoi | Topoi [tex] | Available: Topoi [tex] |
| Dec 3 | The Effective Topos | The Effective Topos [tex] | |
| Dec 5 | Faithful Functors Monoidal Categories Equivalence |
Due: Topoi [tex] | |
Homework Policies
Cornell University has a Code of Academic Integrity, with which you should be familiar. Violations of this code are treated very seriously by Cornell and can have long-term repercussions. In this course, you are encouraged to discuss the content of the course with other students, and you may also discuss homework problems with other students. However, you must do your own work, write up assignments yourself, and if you discuss a problem with another student, you are expected to document this fact in your write-up. It is a violation of the code to copy work, including programs, from other students; it is also a violation to use solutions to homework problems from previous iterations of the same course. Note that Cornell holds responsible for the code violation both the recipient and the donor of improper information.