IMT DeCal, Fall 2018

Introduction to Mathematical Thinking

CS 198-087 @ UC Berkeley, Fall 2018

Jump to Announcements, Course Description, Content and Schedule, Grading, FAQs, or Staff
Read the textbook here

Lecture: Wednesdays, 6:30-8:00 PM, LeConte 3
Discussion: Mondays, 6:30-8:00 PM, LeConte 3
Office Hours: Tuesdays 2-3PM and Thursdays 5-6PM, Cory 299

Piazza: http://piazza.com/berkeley/fall2018/cs198087
Gradescope: 9XVEPJ

Announcements

Spring 2019: This course will be offered in Spring 2019. It will be held on Tuesdays and Thursdays from 3:30-5PM in LeConte 2. Applications will be released soon, as soon as the enrollment process is finalized. Next semester's site can be found here, along with the application.

Course 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 higher-level 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.

Content and Schedule

A textbook is being written specifically for this course. It is available for free at book.imt-decal.org. There will also be lecture videos embedded into the textbook; this is still a work in progress.

Each "week" in this course starts on a Wednesday (with the exception of the final week). This is because the material presented in lecture on Wednesday is covered in the following Monday's discussion.

Week	Lecture (W)	Discussion (M)	Topic	Homework
1	Sept. 5	Sept. 10	Course Overview, Intro to Set Theory, Functions Why does this class exist? Overview of the topics covered throughout the course. Definition of a set. Set operations. A general definition of functions. Domain, range. Reading: 1.1, 1.2 Slides Video	HW 1 Solutions
2	Sept. 12	Sept. 17	Bijections, Number Sets, Propositional Logic Bijections. Construction of natural numbers, integers, rationals, reals and complex numbers. Introduction to propositional logic. Reading: 1.3, 1.4 Slides (9/12) Slides (9/17) Video	HW 2 Solutions
3	Sept. 19	Sept. 24	Proof Techniques Presentation of various proof techniques, and examples of each. How to read proofs. Faulty proofs. Reading: 2.1 Slides Video	HW 3 Solutions
4	Sept. 26	Oct. 1	Proof Techniques, Continued Analysis of proof techniques, continued. Mathematical induction. Reading: 2.2 Slides Video	HW 4 Solutions
5	Oct. 3	Oct. 8	Midterm Review Note: This week's homework is not to be submitted, rather it is meant to be preparation for the upcoming midterm. Slides Video	HW 5 Solutions
6	Oct. 10	Oct. 15	Midterm In-class midterm on October 10th. Discussion on October 15th will be taking up midterm. Exam Solutions
7	Oct. 17	Oct. 22	Number Theory Division algorithm. Introduction to modular arithmetic. Slides Video Slides (10/22) Video (10/22)	HW 6 Solutions
8	Oct. 24	Oct. 29	Counting Thinking about the "number of ways" to do something. Permutations and combinations. Stars and bars. Principle of Inclusion-Exclusion. Slides Slides (10/29) Video (10/29)	HW 7 Solutions
9	Oct. 31	Nov. 5	Pascal's Triangle, Combinatorial Proofs, Binomial Theorem Properties of Pascal's triangle. Combinatorial proofs. Introduction to the binomial theorem. Slides Video	HW 8 Solutions
10	Nov. 7	N/A (Veteran's Day)	Vieta's Formulas Vieta's formulas for polynomials of degree 2, 3, 4. Generalized Vieta's. Examples. Slides Video	HW 9 (11/14)
11	Nov. 14	Nov. 19	Polynomial Interpolation, with Modular Arithmetic Lagrange Interpolation. Lagrange Interpolation under modular arithmetic. Notebook (html) Notebook (ipynb)	HW 10 Solutions
12	N/A (Thanksgiving)	Nov. 26	Final Review No class Wednesday of Thanksgiving. In-class final review Monday, Nov. 26.
13	Nov. 28	N/A	Final In class final on Wednesday, November 28th. Exam Solutions	Extra Credit

Grading

The course will be offered for 2 units, P/NP. There will be one 1.5h lecture each Wednesday, and one 1.5h discussion each Monday.

There will be weekly problem sets, which are released on Wednesdays after lecture and due the following Monday at 6:30PM, at the start of discussion. Problem sets are graded on effort. The problem set will be taken up in that Monday's discussion section; the idea is that students will discuss amongst each other their approaches to the problems, and the staff will facilitate this discussion.

Your grade in this course is calculated on a 100-point scale.

Problem sets (5 points x 10 problem sets = 50 points): Homeworks are graded on effort. We feel like the best way for you to learn is by doing practice.
Midterm (20 points): October 10th, in class.
Final (30 points): November 28th, in class.

Attendance to both lecture and discussion is mandatory. If you have more than 3 unexcused absenses, you will receive an NP in the course. You will need 70 points to pass the course, which roughly corresponds to a 5 on nine problem sets and earning half of the points on both exams. As this is a new course, we reserve the right to adjust this boundary and the point system as a whole as the course progresses, but we will do so in a fair way.

Frequently Asked Questions

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 Spring 2019, Fall 2018 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.

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. Take a look at this diagnostic assessment. If a lot of this material seems unfamiliar to you, we'd be glad to have you!

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 imt-decal@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, men's fashion, teaching and rooting for LeBron (go ~~Cavs~~ Lakers!) I'm super excited that this course is finally a reality, and I'm hoping you are as well. Click the picture of me for a surprise.

Teaching Assistants


	Edward Im (edwardim@berkeley.edu) Hi! I'm a third-year studying Economics and Computer Science. I love math, and I hope to help you love it too. In my free time, I love running, overeating, and singing in the shower (ask my roommates!)
	Ziv Lotzky (zivlotzky@berkeley.edu) Hey I’m Ziv! I’m a senior math major originally from New York (go yankees!). I love logic puzzles, riddles, and quantitative finance.
	Josh Geng (joshgeng@berkeley.edu) I'm a second year Statistics and Econ major from Calgary, Canada. I did math competitions for the majority of my life and I was able to travel the world because if it. Come to RSF after discussion to get swole with me!