| Course Description | Grading | Schedule | Instructor/TA | Texts | Lectures | Special needs |
Welcome to CSE 150! Public, mostly static information will be hosted on this page. We will use Blackboard for homeworks and discussions. Please subscribe to the Q&A forum on Blackboard.
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. 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 (from 2020) |
| 1 | Sets | 46 mins 7 mins |
| 2 | Propositional Logic and Proof Techniques, Digital Circuits |
71 mins
18 mins Proof techniques (47 mins, 12mins) |
| 3 | Predicates and Quantifiers | 45 mins 34 mins |
| 4 | Functions and Relations |
Functions 29 mins Intro to Relations 32 mins Relation Types 31 mins |
| 5 | 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 |
| 6 | 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 |
| 7 | 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 |
| 8 | 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 |
| 9 | Proof Techniques II |
Induction proofs 38 mins 31 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 |
| 11 | Recurrences |
Intro to recursion and recurrences 32 mins Solving recurrences: Plug-and-chug 15 mins Homogeneous Linear Recurrences 20 mins 5 mins Asymptotic Complexity 11 mins Master Theorem 17 mins |
| 12 | Functional Programming |
Intro to Standard ML 48 mins Tutorial session with SML 32 mins Induction+Recurrences to Analyze Recursion 13 mins Making programs faster 33 mins Mathematical Data Types 40 mins Programming with Lists and Tuples 45 mins Programming Set operations 18 mins Relations 18 mins Counting 16 mins Recursive Data Types 9 mins Binary Trees 58 mins Propositions 18 mins |
| 13 | Review Session |
Course summary 55 mins Review of Homeworks and Sample Exams 60 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: Tuesdays 3:30pm to 4:30pm, Thursdays 12:50pm to 2:00pm
If you have a conflict at all of the above times, then you can also make an appointment outside of these hours to meet one of the TAs or the instructor.
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.