Last Updated:
This is a detailed schedule for the Accelerated section. See CS1800-ACC Overview
| Date | Reading/Regular1800 | Accelerated 1800 | Optional | Assignments |
|---|---|---|---|---|
| Welcome |
WELCOME Website / Canvas, Piazza , Staff Gradescope, Assignments, Exams, Grades |
1800ACC-Gradescope ( code: VDGJWR) | Live honors lectures from previous years (Chrome for 4k video), previous Notes, Team-streams, and other optional material. |
|
|
Part 1: Logic, Proofs, Numbers, Binary
|
||||
|
WEEK 1 Sep 5-17 Logic, Boolean variables Implication Logic Gates, Basic circuits
Boolean Algebra
Lecture 1 Notes |
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
2.4 Binary Arithmetic: Ripple Carry Adders
3.3 Truth Tables
3.4 Logical Equivalence
BookNotes: simple circuits, boolean algebra BookNotes: circuits, logic rules Summary: Binary and Logic |
Teaser: Konigsberg 7 bridges Teaser: Polygon triangulations Teaser: Sorting by digits (Radix Sort) (podcast) |
(part 2, after min 42)Teams Stream
|
Recitation 1 (Logic) due Fri 9/13 HW 1 (Logic) due Mon 9/16 Project 1 : 2-CNF-SAT Due 9/27 |
| WEEK 2 Sep 17-24 Boolean Algebra, Predicates, Quantifiers Propositional and Predicate Logic Logic and Proofs Proofs 1
Negating Quantifiers Sets Intro Lecture 2 Notes |
3.5 Normal Forms
8.1 Set Definition and Examples8.2 Set Basics BookNotes: Predicate logic Quantifiers: Negation Rules |
Proofs and quantifiers Logic basics Proof by Contradiction |
Teams Stream
|
Recitation 2 (Boolean, Logic) due Fri 9/20 HW 2 (Logic, Proofs) due Mon 9/23 |
| WEEK 3 Sep 24- Oct 1 Modulo Arithmetic Prime numbers, gcd Modulo Inverse Number Theory Notes Lecture 4 Notes Lecture 4 Extended Euclid |
Chanpter 5 BookNotes: Modulo Arithmetic BookNotes: Modulo Properties BookNotes: GCD, Euclid |
Proof: divisibility with 3 |
|
Recitation 3 (Modulo) due Fri HW 3 (Modulo) due Tue 9/30 |
| WEEK 4 Oct 1-8 Number Theory Modulo Inverse Number Theory Part 4 RSA Cryptography Lecture 5 Notes |
BookNotes: Ext-Euclid, RSA |
Recitation 4 (Number Theory) due Fri Project 2 : Square Game Due 10 / 29 |
||
|
Binary Representation
Binary to/from Decimal Lecture 6 notes Lecture 6 notes |
Ch. 1 Introduction
1.1 Binary Representation
1.2 Bytes
1.5 Converting Between Decimal and Binary
BookNotes: binary representation |
Geometric Progression, binary base Binary card trick Card trick explained with decimal cards |
Teams Stream
|
Recitation 5 (Binary) due Fri HW 4 (Binary) due Mon 10/14 |
| WEEK 5-6 Oct 8-15 Hexadecimal and Octal
Negative Numbers, Two's Complement Bitwise Operations
Radix Sort
Sum Rule: Independent possibilities vs representation Notes OH |
1.3 Hexadecimal Representation
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement
Binary Search
BookNotes: binary operations, hex, octal BookNotes: Two's complement Representation comparison Binary search optimality |
Bitwise Operations
( code ) Proof basics addl notes on binary, two complement ( podcast ) |
Optional: Fast Inverse Square Root (pdf) (Newton) (code) (first part, up to minute 42) |
|
|
Part 2: Sequences, Induction, Series, Recurrences
|
||||
| WEEK 6 Oct 8-15 Induction Sequences and Series Lecture 7 Notes Lecture 7 Notes |
Ch12: Sequences, Series BookNotes: Sequences + Series Ch12: Sequences, Series Ch13: Induction BookNotes: Induction part 1 |
Induction Handout |
Teams Stream |
Recitation 6 (induction) due Fri HW 5 induction due Mon 10/21 |
| WEEK 7 Oct 22-29 Induction part 2 Inequalities Fibonacci Numbers Harmonic Series, e-limit Lecture 8 Notes |
Book Notes: Induction Part 2 |
Harmonic Series Harmonic Approximation (Calculus) |
Additional Induction Problems |
Recitation 7 (induction) due Fri HW 6 induction due Mon 10/28 |
WEEK 7-8 Oct 22-29 Asymptotic Run Time Solving Recurrences Recurrences and Induction Lecture 24 Notes |
Book Notes: Recurrences |
Function Growth Notation, Algorithms Slides: Searching And Sorting ( part 2) Slides : Recurrences Slides : Linear Recurrences |
|
|
Part 3: Sets and Counting
|
||||
| WEEK 8 Oct 29- Nov 5 Set-Builder Notation Union, Intersection, Set Difference Set Size Power Set Product Rule Disjoint Sets: Sum/partition Rule Cartesian Product Inclusion-Exclusion Principle Pigeonhole Principle Lecture 9 Notes |
Ch. 8 Sets
BookNotes: Sets
BookNotes: Set Counting8.3 Set-Builder Notation 8.4 Venn Diagrams 8.5 Set Operations 8.6 Computer Representation of Sets 9.2 Inclusion-Exclusion Principle 9.3 Pigeonhole Principle BookNotes: Counting |
|
Recitation 8 (sets, counting) due Fri HW 7 (sets, counting) due Mon 11/4 Project 3 : Valid Dates Due |
|
|
Midterm Fri 11/1, 4 hours in class. time: 3:30-7:30, room:RY 159
|
Cheat Sheet allowed whole time: 4pages (2 sheets) Allowed first 60 min: notes/HWs/other written by you. Must be on paper, no electronic devices. Hand calculators: allowed |
|||
| WEEK 9 Nov 5- 12 Product Rule, Permutations Combinations Balls Into Bins Sets vs Sequences Counting Problems Binomial Expansion, Theorem Pascal Triangle PIE general proof Lecture 10 Notes |
Ch. 9 Introduction 9.1 Basic Rules 9.4 Permutations 9.5 Combinations 9.5 Balls in Bins BookNotes: Balls in Bins BookNotes: Binomial Coefficients Summary: Sets and Counting |
Count Sets with one-to-one functions Countable Sets Infinite Enumerable Sets : N, Z, Q Inclusion-Exclusion Proof 9.6 Binomial Theorem, Pascal triangle Inclusion-Exclusion Proof |
More on Inclusion-Exclusion Few Problems like the midterm (?) Optional: Counting, Pascal Triangle Formulas and a lot more Teams Stream Teams Stream |
|
|
WEEK 10 Nov 12-19 Counting Problems Catalan Numbers Lecture 11 Notes |
Catalan Numbers Balls into Bins with Capacity (2nd paper:Counting Multisets) Counting with Generative Functions Permutation Cycles |
More on Generative Functions |
|
Recitation 9 (counting) due Fri HW 8 (adv counting) due Mon 11/18 |
|
Part 4: Probabilities, Random Variables, Expectation, Variance, Entropy
|
||||
| WEKK 11 Nov 19-26 Probabilities Spaces, Events Uniform Probabilities Non-Uniform Probabilites Random variables Joint and Conditional Probabilities Bayes Theorem Lecture 12 Notes |
Ch. 10 Introduction 10.1 Definitions and Basic Properties 10.2 (Probability) Examples 10.3 Conditional Probability and Bayes Theorem BookNotes:Probability Basics Book : Intro to Probabilities |
Probabilities (formal math) Monty Hall Problem (podcast) Zika Conditionals (podcast) |
|
Recitation 10 (probabilities) due Fri HW 9 (probabilities) due Mon 11/26 |
| Week 12 Nov 26- Dec 3 Expectation Variance Entropy Binomial Distribution Markov Chain Lecture 13 Notes Lecture 14 Notes Thanksgiving Break: no class/OH Wed - Sun |
BookNotes:Conditional Probability Conditional and Joint Examples 10.4 Markov Chains BookNotes: Markov Chain BookNotes: Expectation, Variance, Entropy Expectation Counting Summary: Probabilities, Expectation |
Random variables, Expectation, Variance E[] VAr[] proofs Binomial Distribution Geometric distribution Balls-Bins-Coupons podcast Optional: Law of Large Numbers |
|
Recitation 11 (expectation, var) due Fri HW 10 (expectation, entropy, graphs) due |
| Skiplists BST Sampling |
Skiplists Slides BST Slides |
Skiplists Math Binary Search Trees (Cormen book) Sampling Code (Matlab) |
|
Proj 4: Skiplists, BST due |
|
Part 5 : Graphs, Trees, Networks
|
||||
| Week 13-14 Dec 3 - 10 Graphs and Trees Binary Search Trees Skiplists Lecture 20 Notes Lecture 21 Notes |
Book Notes: Graphs 1 Book Notes: Graphs 2 |
Graph Theory Notes Bipartite Graphs, 2-Coloring ( Wikipedia ) Graph Coloring |
|
|
| Week 13-14 Dec 3-10 Graph Traversal Algorithms: BFS, DFS Graph Min Spanning Trees (optional) Graph Shortest Path (Dijkstra) Lecture 22 Notes |
Slides: Graphs,MST (without class annotations) Slides: Graphs Shortest Path |
|
||
|
Part 6: Algorithms for Sorting (Optional)
|
||||
|
Recap : Selection Sort, MergeSort Insertion Sort QuickSort Sorting1_Notes (CS5800) Sorting2_Notes (CS5800) |
Book Notes: Algorithms Book Notes: Algorithms |
|
||
|
Final Sat 12/7 4 hours, in class
|
Cheat Sheet allowed whole time: 4pages (2 sheets) Allowed first 60 min: notes/HWs/other written by you. Must be on paper, no electronic devices. Hand calculators: allowed |
|||
