Skip to main content

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

Schedule

DateTopicTechnical NotesAssignments
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.