Scribd Logo
Upload

Welcome to Scribd!

  • 38 views

    CS103 Syllabus: Date Topics Readings Assignments M January 8

    Uploaded by

    Dupla Palta
    This document is the syllabus for CS103, an introductory course on discrete mathematics and computability theory taught over winter 2018. The course is divided into three parts: (1) discrete mathematics covering topics like logic, sets, functions, and graphs; (2) computability theory on formal languages, automata, and Turing machines; and (3) complexity theory on the P vs NP problem and NP-completeness. The syllabus lists the topics, readings, and assignments for each class meeting over the 15-week quarter.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CS103 Syllabus: Date Topics Readings Assignments M January 8

    Uploaded by

    Dupla Palta
    38 views3 pages
    This document is the syllabus for CS103, an introductory course on discrete mathematics and computability theory taught over winter 2018. The course is divided into three parts: (1) discrete mathematics covering topics like logic, sets, functions, and graphs; (2) computability theory on formal languages, automata, and Turing machines; and (3) complexity theory on the P vs NP problem and NP-completeness. The syllabus lists the topics, readings, and assignments for each class meeting over the 15-week quarter.

    Original Title

    010 Syllabus

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is the syllabus for CS103, an introductory course on discrete mathematics and computability theory taught over winter 2018. The course is divided into three parts: (1) discrete mathematics covering topics like logic, sets, functions, and graphs; (2) computability theory on formal languages, automata, and Turing machines; and (3) complexity theory on the P vs NP problem and NP-completeness. The syllabus lists the topics, readings, and assignments for each class meeting over the 15-week quarter.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    38 views3 pages

    CS103 Syllabus: Date Topics Readings Assignments M January 8

    Uploaded by

    Dupla Palta
    This document is the syllabus for CS103, an introductory course on discrete mathematics and computability theory taught over winter 2018. The course is divided into three parts: (1) discrete mathematics covering topics like logic, sets, functions, and graphs; (2) computability theory on formal languages, automata, and Turing machines; and (3) complexity theory on the P vs NP problem and NP-completeness. The syllabus lists the topics, readings, and assignments for each class meeting over the 15-week quarter.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    CS103 Handout #01

    Winter 2018 January 8, 2018

    CS103 Syllabus
    ________________________________________________________________________________________________________

    Part One: Discrete Mathematics


    Date Topics Readings Assignments
    M January 8 Can computers solve all problems? Notes, Ch. 1
    Set Theory Handouts PS0 Out
    The Limits of Computing Online Guides
    W January 10 How do we prove results with certainty?
    Notes, Ch. 2
    Direct Proofs
    Handouts

    F January 12 How do we prove something without directly proving it?


    Notes, Ch. 2 PS0 Due
    Proof by Contradiction
    Handouts PS1 Out
    Proof by Contrapositive
    M January 15
    Dr. Martin Luther King, Jr. Day
    PS1 Checkpoint Due
    No Class

    W January 17 How can we formalize our reasoning?


    Propositional Logic

    F January 19 How can we reason about collections of objects?


    PS1 Due
    First-Order Logic I
    PS2 Out

    M January 22 How do we rigorously defne key terms?


    Handouts
    First-Order Logic II PS2 Checkpoint Due
    Online Guides

    W January 24 How do we model relationships between objects?


    Binary Relations Notes, Ch. 5
    Equivalence Relations
    F January 26 What does it mean to compare two objects?
    Handouts PS2 Due
    Strict Order Relations
    Notes, Ch. 5 PS3 Out

    M January 29 How do we model transformations and associations?


    Functions Notes, Ch. 6 PS3 Checkpoint Due
    Injections, Surjections, and Bijections
    W January 31 How do we reason about infnity?
    Notes, Ch. 6
    Cardinality
    Online Guides
    Diagonalization
    F February 2 How do we model network structures?
    PS3 Due
    Graphs, Part I Notes, Ch. 4
    PS4 Out

    1/3
    Date Topics Readings Assignments
    M February 5 Is disorder truly possible at a large scale?
    Graphs, Part II Notes, Ch. 4 PS4 Checkpoint Due
    The Pigeonhole Principle
    First Midterm Exam
    7:00PM – 10:00PM, Location TBA
    Covers topics from PS1 – PS2.
    W February 7 How can we reason about sequential processes?
    Mathematical Induction, Part I Notes, Ch. 3

    F February 9 How does recursion relation to mathematical proof?


    Notes, Ch. 3 PS4 Due
    Mathematical Induction, Part II
    Handouts PS5 Out

    Part Two: Computability Theory


    M February 12 How do we mathematically model computers?
    Formal Language Theory Sipser 1.1
    DFAs I
    W February 14 What happens if computation involves choices?
    DFAs II Sipser 1.2
    NFAs
    F February 16 How can we transform machines?
    PS5 Due
    Equivalence of DFAs and NFAs Sipser 1.2
    PS6 Out
    Closure Properties of Regular Languages
    M February 19
    Presidents’ Day
    No Class

    W February 21 Can we generate new programs from old programs?


    Regular Expressions Sipser 1.3
    Equivalence of Regular Expressions and NFAs
    F February 23 Can computers with fnite memory solve all problems?
    PS6 Due
    Nonregular Languages
    PS7 Out
    The Myhill-Nerode Theorem
    M February 26 How do natural and formal languages overlap?
    Context-Free Grammars Sipser 2.1
    Context-Free Languages
    Second Midterm Exam
    7:00PM – 10:00PM, Location TBA
    Covers topics from PS3 – PS5.
    W February 28 How do we model realistic computers?
    Turing Machines Sipser 3.1
    Designing Turing Machines
    F March 2 How powerful are Turing machines?
    PS7 Due
    The Church-Turing Thesis Sipser 3.3
    PS8 Out

    2/3
    Date Topics Readings Assignments
    M March 5 What does it mean to solve a problem with a computer?
    Sipser 4.1
    R and RE Languages
    Sipser 6.1
    The Universal Turing Machine
    W March 7 What is the limit of algorithmic problem-solving?
    Self-Reference Sipser 4.2
    Undecidability
    F March 9 What is the full scope of computing power?
    Online PS8 Due
    Verifers
    Guides PS9 Out
    Unrecognizability
    Part Three: Complexity Theory
    M March 12 How do we measure the difculty of problems?
    Sipser 7.2
    The P versus NP Question
    Sipser 7.3
    NP-Completeness I
    W March 14 What makes hard problems hard?
    NP-Completeness II Sipser 7.4

    F March 16 How does everything ft together?


    PS9 Due
    The Big Picture
    No late submissions
    Where to Go from Here
    M March 19
    Final Exam: 3:30PM – 6:30PM
    Location TBA

    3/3

    You might also like