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:252: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 noncumulative 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  2Categories  2Categories [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 longterm 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 writeup. 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.