Introduction to Mathematical Thinking
CS 198087 @ UC Berkeley
Jump to Announcements, Content and Schedule, Course Description, Grading, FAQs, or Staff
Access the notes for this class here.
Announcements
 This course will not be offered in Fall 2019 or Spring 2020. However, all material from Spring 2019 will remain online at this page for selfstudying.
 Please direct all questions to
suraj.rampure@berkeley.edu
.
Content and Schedule
 Homework generally follows a FridayFriday schedule.
 Notes written specifically for this course can be found at notes.imtdecal.org. Other readings will be linked in the table below.
 The schedule is tentative.
Week  Date  Topic  Resources  Homework 

1  Tue. 01/29  Course Overview 
Slides Notebook Video 

Thu. 01/31  Set Theory, Functions 
Slides Video Note: Sets and Set Operations Note: Functions and Bijections 
HW 1 Solutions Video 

2  Tue. 02/05  Bijections, Number Sets 
Slides Video Note: Sets of Numbers 

Thu. 02/07  Number Sets, Propositional Logic 
Slides Video Note: Propositional Logic 
HW 2 Solutions 

3  Tue. 02/12  Propositional Logic 
Slides Video Note: Notation Cheat Sheet 

Thu. 02/14 
Basic Proof Techniques Quiz 1 in class 
Slides Video Note: Foundational Proof Techniques 
HW 3 Solutions 

4  Tue. 02/19  Basic Proof Techniques 
Slides Video 

Thu. 02/21  Induction 
Slides Video Note: Mathematical Induction 
HW 4 Solutions 

5  Tue. 02/26  Strong Induction, Series and Sequences 
Slides Video 

Thu. 02/28 
Series and Sequences Quiz 2 in class 
Slides Video Note: Series and Sequences 
HW 5 Solutions 

6  Tue. 03/05  Division Algorithm and Primality 
Slides Video Note: Primality and Divisibility 

Thu. 03/07  Modular Arithmetic 
Slides Video Note: Modular Arithmetic 

7  Tue. 03/12 
Finding Modular Inverses (Ani Nrusimha*) 
Slides (from Fall 2018) Video (from Fall 2018) 

Thu. 03/14 
Review of NT/MA (Lecture by TAs Adel, Jai, Sagnik) Quiz 3 online 
Refer to Homework 5 solutions  
8  Tue. 03/19 
Counting (Ani Nrusimha) 
Slides by Ani Slides (from Fall 2018) Note: Principle of InclusionExclusion Note: Key Examples in Counting Note: Counting (by Jerry Huang) 

Thu. 03/21 
Counting (Ani Nrusimha) 
Slides by Ani Video (from Fall 2018) Note: Stars and Bars 
HW 6 Solutions 

9  Tue. 03/26  No Class (Spring Break)  
Thu. 03/28  No Class (Spring Break)  
10  Tue. 04/02  Counting Review 
Slides Video 

Thu. 04/04  Counting Review, Combinatorial Proofs 
Slides Video 

11  Tue. 04/09 
Binomial Theorem Quiz 4 in class 
Slides Video Note: Binomial Theorem 

Thu. 04/11  Binomial Theorem, Vieta’s Formulas 
Slides Video Note: Vieta’s Formulas 
HW 7 Solutions 

12  Tue. 04/16  Vieta’s Formulas 
Slides Video 

Thu. 04/18  No Class  
13  Tue. 04/23  Review 
Slides Video 
HW 8 Solutions 
Thu. 04/25  Review 
Slides Video 

14  Tue. 04/30  Quiz 5 in class  
Thu. 05/02  Probability, Closing Thoughts 
Slides Notebook Video 
Extra Credit 
* Ani Nrusimha, aninrusimha@berkeley.edu
, will be covering these lectures. Feel free to reach out to him with any questions.
Spring 2019 quizzes:
 Quiz 1: blank, solutions
 Quiz 2: blank, solutions
 Quiz 3: blank, solutions
 Quiz 4: blank, solutions
 Quiz 5: blank, solutions
From previous semesters:
Additional resources:
 How to Prove It: A Structured Approach, by Velleman (2nd edition) covers the material in our class through mathematical induction, albeit in a slightly different order. link
 Discrete Math and Its Applications, by Rosen (7th edition) is the textbook that Math 55 at UC Berkeley uses. It also covers most of the material in the course, including counting (which the above textbook does not cover). link
 Art of Problem Solving is an online community centered around preparing for math competitions, with several wikis on various topics. These wikis are especially relevant towards the latter part of our course, with some excellent articles on combinatorics, the Binomial Theorem and Vieta’s Formulas. link
 Mathematical Reasoning is a set of lecture notes by Hermish Mehta on some of the earlier topics in the course. link
Description
Berkeley’s highly theoretical Computer Science curriculum demands a high level of mathematical maturity. While those with extracurricular math experience from high school are familiar with dense notation, complex mathematical objects, and proof techniques, many students find foundational courses like CS 70, CS 170, and Math 55 confusing and inaccessible.
Introduction to Mathematical Thinking bridges the gap. We teach mathematical maturity. Our curriculum exposes students to familiar concepts in a more precise, generalized way. By the end of our course, students will be able to:
 comfortably read mathematical language, including notation, definitions and proofs
 concisely and clearly express their ideas differentiate between a good proof and a proof with logical gaps
As a result, this course will prepare students for higherlevel mathematics courses, such as CS 70 at Berkeley. However, students can enroll in the course even if they aren’t planning on taking these courses or are not in CS/EECS; these skills and concepts are highly transferrable.
There are no prerequisites for this course. We’re working really hard to make the material accessible for all backgrounds.
Disclaimer: This course is not a prerequisite for CS 70, nor is it affiliated with the CS 70 instructors or course staff in any way. The official prerequisites for CS 70 are specified in the course description. CS 70 staff makes no guarantees regarding the material covered in this course.
Grading
The course will be offered for 2 units, P/NP.
There will be weekly problem sets, which are graded on effort, not correctness. Attendance is mandatory, and NPs will be given to students who have more than 3 unexcused absenses.
The course is graded on a 100 point scale:
 5 quizzes, each worth 12 points, for a total of 60 points
 Quizzes are on Feb. 14, Feb. 28, Mar. 14, Apr. 9 and Apr. 30, in class
 Weekly homeworks, worth a total of 40 points
A passing grade will be given to students with 65 points or more (note the new threshold). We reserve the right to change this threshold, but we would only decrease it (i.e. we will not make it any harder to pass).
Frequently Asked Questions
How do I know that this course is for me?
This course is designed for students without discrete math experience. In general, if you have significant math contest experience, or did well in a discrete math course prior to being at Berkeley, then this course probably isn’t for you. A good diagnostic is last semester’s midterm exam. If a lot of this seems unfamiliar to you, we’d be glad to have you!When should I take this course?
We think this course is best taken the semester before taking CS 70. Therefore, if you plan on taking CS 70 in Summer 2019 or Fall 2019, then Spring 2019 would be the time to take it. With that being said, you can take this course even if you don’t plan on taking CS 70, but due to constraints, we won’t be admitting many students from this category (perhaps in future semesters). This DeCal is not designed to be taken alongside or after CS 70 or Math 55.How much work will it be?
We know you have other courses in which your grade matters. However, the only way to actually develop and retain skills from this course is to put in the time into coming to lecture and discussion, reading the book/watching lecture videos, and (most importantly) doing the homework. Not including time spent in class, a rough estimate is 5 hours per week.Can I audit this course?
Sadly, we won’t have space for that. However, all materials – lecture notes, the textbook, lecture videos, assignments, exams – will be posted online.
Staff
For all course related communications, please email imtdecal@berkeley.edu
.
Instructor
Suraj Rampure (suraj.rampure@berkeley.edu
)
Hey, I’m a third year EECS major from Windsor, Ontario (right across the border from Detroit). I like cars, tech, teaching and rooting for LeBron (go Cavs Lakers!). This is my second semester teaching this course, fifth semester as a part of CSM, and fourth semester as a GSI; currently, I’m TA’ing Data 100, but have TA’d CS 61A and Data 8 in the past. I’m super excited that this course is finally a reality, and I’m hoping you are as well.
Teaching Assistants
Jai Bansal (jaibansal@berkeley.edu
)
Hey everyone! This is my first year at Cal hoping to major in CS and Applied Mathematics. In my free time, I love playing Ultimate Frisbee and watching basketball, football, soccer (or any sport you can name) and listening to way too much Logic. Feel free to talk to me about anything! Excited to TA for the first time!
Sagnik Bhattacharya (sagnick@berkeley.edu
)
I’m a CS and statsintended freshman. You can find me running on the streets of Berkeley when I’m not biking between classes or trying to hack the mainframe. Talk math and computers (and environmental science!) to me.
Alexia Colmenero (acolmenero@berkeley.edu
)
I am a sophomore Computer Science major from San Diego. I am a gemini who likes video games, and is excited to work on this course! I use they/them pronouns.
Divya Mohan (21dmohan@berkeley.edu
)
Heya! I’m a sophomore EECS major, originally from the Bay Area (specifically, Belmont). I am also meme trash; find me on UCBMFET any day, all day. I’m interested in data science, and I love helping my peers :)
Adel Setoodehnia (asetoodehnia@berkeley.edu
)
Hello! I’m Adel, a thirdyear Mathematics and Computer Science student from Union, New Jersey. When I have free time you could probably find me playing soccer, listening to music, playing guitar, chilling with a book, or cooking/eating all types of good food. Looking forward to meeting you all!