CS 40 Foundations of Computer Science
Fall 2016  EnrlCd 08540
Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/cs40
Course Information
 Instructor: Professor Koç
→ Koç is pronounced as "Coach"
 Class Schedule and Room:
Monday, Wednesday 2:003:15pm, CHEM 1171
 Instructor Office Hours: Mon, Wed 3:305:00pm
 Instructor's Office: HFH 1119
 Teaching Assistants:
Plane Janthong (abhabongse@cs.ucsb.edu)
Adam Ibrahim (adamibrahim@umail.ucsb.edu)
Jishnu Dante (jdantu@umail.ucsb.edu)
 Recitation Schedules and Rooms:
Tuesday 4:004:50pm, Phelps 2524, EnrlCd: 08557 (Plane)
Tuesday 5:005:50pm, Phelps 2524, EnrlCd: 08565 (Adam)
 TA Office Hours:
Jishnu: Tuesday 12:001:30pm
Plane: Tuesday 1:303:30pm
Adam: Thursday 3:305:30pm
 TA Office: Trailer 936 Room 104
 Please join the
Piazza page
for cs40 class discussions and announcements.
←
 Check the class website and the Piazza page once a day.
 Course material (slides, papers, notes)
is in the folder docx
Exams
 There will be two Midterm Exams and one Final Exam.
 The Midterm 1 will be in class on Wednesday October 26
 The Midterm 2 will be in class on Wednesday November 16
 The Final Exam will be at 4:007:00pm on Monday December 5
 No repeat or remedy exam can be given.
Homework Assignments
We will have one homework assignment every week.
The homework assignments are due 6pm on Wednesdays, and are to be
delivered to the CS40 homework box in the CS Mail Room (HFH 2108).
No late homework is accepted.
Weekly Course Plan
 Week01 (Sep 26, 28)
Logic & Proofs: Propositional Logic, Propositional Equivalences,
Predicates and Quantifiers, Nested Quantifiers.
[Sections 1.11.5]
 Week02 (Oct 3, 5)
Rules of Inference, Introduction to Proofs, Proof Methods and Strategy.
[Sections 1.61.8]
 Week03 (Oct 10, 12)
Sets and Functions: Sets, Set Operations, Functions, Sequences
and Summations, Cardinality of Sets.
[Sections 2.12.5]
 Week04 (Oct 17, 19)
Algorithms, The Growth of Functions, Complexity of Algorithms.
[Sections 3.13.3]
 Week05 (Oct 24, 26)
Modular Arithmetic, Integer Representations and Algorithms,
Primes and GCDs, Solving Congruences.
[Sections 4.14.4]
 Week06 (Oct 31, Nov 2)
Applications of Congruences, Cryptography.
[Sections 4.54.6]
 Week07 (Nov 7, 9)
Induction and Recursion: Mathematical Induction,
Strong Induction, Recursive Definitions and Structural Induction,
Recursive Algorithms, Program Correctness.
[Sections 5.15.5]
 Week08 (Nov 14, 16)
Counting: Basics, Pigeonhole principle, Permutations and combinations,
Binomial coefficients and identities.
[Sections 6.16.4]
 Week09 (Nov 21, 23)
Recurrence Relations, DivideandConquer Algorithms,
InclusionExclusion.
[Sections 8.18.3, 8.58.6]
 Week10 (Nov 28, 30)
Graphs and Trees: Models, Terminology, Euler and Hamiltonian Paths,
Shortest Path Problems, Tree Travelsals, Spanning Trees.
[Sections 10.110.6, 11.111.5]
Textbook
Grading Rules
 Homework Assignments: 30 %
 First Midterm Exam: 20 %
 Second Midterm Exam: 20 %
 Final Exam: 30 %
Catalog Specification
Introduction to the theoretical underpinnings of computer science.
Topics include propositional predicate logic, set theory, functions
and relations, counting, mathematical induction and recursion
(generating functions).
Prerequisites
Computer Science 10 or 12 or 16 and Mathematics 3C.
Academic
Integrity at UCSB ←
Dr. Çetin Kaya Koç
