CS 40 Foundations of Computer Science

CS 40 Foundations of Computer Science

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:00-3:15pm, CHEM 1171
  • Instructor Office Hours: Mon, Wed 3:30-5: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:00-4:50pm, Phelps 2524, EnrlCd: 08557 (Plane)
    Tuesday 5:00-5:50pm, Phelps 2524, EnrlCd: 08565 (Adam)
  • TA Office Hours:
    Jishnu: Tuesday 12:00-1:30pm
    Plane: Tuesday 1:30-3:30pm
    Adam: Thursday 3:30-5: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:00-7: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.1-1.5]

  • Week02 (Oct 3, 5)
    Rules of Inference, Introduction to Proofs, Proof Methods and Strategy. [Sections 1.6-1.8]

  • Week03 (Oct 10, 12)
    Sets and Functions: Sets, Set Operations, Functions, Sequences and Summations, Cardinality of Sets. [Sections 2.1-2.5]

  • Week04 (Oct 17, 19)
    Algorithms, The Growth of Functions, Complexity of Algorithms. [Sections 3.1-3.3]

  • Week05 (Oct 24, 26)
    Modular Arithmetic, Integer Representations and Algorithms, Primes and GCDs, Solving Congruences. [Sections 4.1-4.4]

  • Week06 (Oct 31, Nov 2)
    Applications of Congruences, Cryptography. [Sections 4.5-4.6]

  • Week07 (Nov 7, 9)
    Induction and Recursion: Mathematical Induction, Strong Induction, Recursive Definitions and Structural Induction, Recursive Algorithms, Program Correctness. [Sections 5.1-5.5]

  • Week08 (Nov 14, 16)
    Counting: Basics, Pigeonhole principle, Permutations and combinations, Binomial coefficients and identities. [Sections 6.1-6.4]

  • Week09 (Nov 21, 23)
    Recurrence Relations, Divide-and-Conquer Algorithms, Inclusion-Exclusion. [Sections 8.1-8.3, 8.5-8.6]

  • Week10 (Nov 28, 30)
    Graphs and Trees: Models, Terminology, Euler and Hamiltonian Paths, Shortest Path Problems, Tree Travelsals, Spanning Trees. [Sections 10.1-10.6, 11.1-11.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ç