| Course Description | Grading | Instructor/TA | Texts | Lectures | Special needs |
Welcome to CSE 150! Public, mostly static information will be hosted on this page. We will use Brightspace for homeworks.
This course introduces Computer Science Honors students to the logical and mathematical foundations of computer science. From time to time, we will also discuss problem solving strategies and techniques.
New for this year: We are going to use DML, a programming language that has been custom-designed for this course. Many of the concepts developed in this course are directly expressible in this language. As a result, you not only learn to write mathematical formulas but also "execute" them in many cases. This will enable you to "debug" your formulas and definitions, and deepen your understanding. Please follow these instructions to download and install DML on your laptop. DML language documentation is available here in PDF.
The main topics covered in this course are:
Eric Lehman, F Thomson Leighton and Albert R Meyer, Mathematics for Computer Science
Videos from a previous offering of this course are available. However, the material covered in the video won't always be an exact match for the material we are teaching in class this year.
| # | Topics and Slides | Recordings |
| 1 | Series and Summations |
Intro to Summations 27 mins Perturbation method 35 mins Summing by integration 34 mins Computing products 12 mins Harmonic series 23 mins |
| 2 | Sets | 46 mins 7 mins |
| 3 | Propositional Logic and Proof Techniques, Digital Circuits |
71 mins
18 mins Proof techniques (47 mins, 12mins) |
| 4 | Predicates and Quantifiers | 45 mins 34 mins |
| 5 | Proof Techniques |
Induction proofs 38 mins 31 mins |
| 6 | Functions and Relations |
Functions 29 mins Intro to Relations 32 mins Relation Types 31 mins |
| 7 | Relations and Graphs |
Relational composition and inversion 6 mins Intro to Graphs 15 mins Examples of Composition 25 mins Graphs 15 mins Walks and Paths 15 mins Euler and Hamiltonian Circuits 12 mins Walks and Paths II 9 mins Euler's Tour 15 mins Hamiltonian Tour 10 mins Graphs and Composition 10 mins Reflexive/Symmetric/Transitive Relations 11 mins Closure operations 10 mins Partial orders 8 mins Closure operations II 17 mins Partial Orders and DAGs 25 mins |
| 8 | Counting |
Basic counting techniques 55 mins Counting using binary strings 12 mins Counting using bijections 20 mins Sequences of subsets 7 mins Word permutations 4 mins Poker hands 50 mins Pigeonhole principle 26 mins Inclusion-Exclusion Principle 15 mins More examples 54 mins |
| 9 | Probability |
Monty Hall Problem 29 mins Strange Dice 43 mins Birthday paradox 23 mins Probability and Set Theory 12 mins 15 mins Infinite probability spaces 9 mins Conditional probability 36 mins Rules for conditional probability 7 mins Medical testing 11 mins 6 mins |
| 10 | Infinite Cardinality |
Infinite Sets 38 mins Countable Sets 31 mins 40 mins Uncountable Sets 40 mins Recap: Uncountability of infinite binary strings 15 mins Cantor's theorem and proof 42 mins (Note: Cantor's proof was not covered in class this year.) |
| 11 | Recursion and Functional Programming |
Intro to recursion and recurrences 32 mins |
| 12 | Recurrences and Algorithmic Complexity |
Solving recurrences: Plug-and-chug 15 mins Homogeneous Linear Recurrences 20 mins 5 mins Asymptotic Complexity 11 mins Master Theorem 17 mins |
| 13 | Review Session |
Course summary 55 mins |
There will be about one homework every other week, excluding the ethics homework that will be due in the first week of classes. Each homework will be worth between 3% and 5% of the final grade.
Any form of copying in the course, and all forms of academic dishonesty, are considered serious offenses, and will be prosecuted to the maximum extent permitted by university policies. The minimum penalty for any form of copying, whether from your friends, the Internet or outside sources, or from previous offerings of the course, will be an F-grade. Note that it is a "one strike and you are out" policy, i.e., you end up with an F-grade regardless of how well you have done in the course until then. There will be no exceptions.
R. Sekar
Office: 364 New Computer Science
Office Hours: Posted on Piazza
If you have special needs, concerns or a disability, please contact the staff at Student Accessibility Support Center (SASC). SASC staff will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation will remain confidential.