Skip to main content

Class Review: Discrete Math and Probability Theory (CS70)

Image
By
CS70 at UC Berkeley during Summer 2019 was the hardest class I've ever taken. It takes centuries of development in Discrete Mathematics and Probability Theory (some theories took decades to prove or refine) and shoves abstract concepts down your throat in a span of 8 weeks.

French is beautiful
I believe that there is no other class at Berkeley in which the disparity between the ability of the students in the course is so stark - students range from International Math Olympiad medalists who have years of rigorous contest math experience to beginning computer science students who hate math and just want to declare the major (a pity that this course is required for that purpose). I fall somewhere in the middle, a math-loving CS student with a bit of contest math background, but little experience in formal proof writing or anything beyond basic probability.

The course is divided into two parts: Discrete Mathematics and Probability Theory (as can probably be inferred by my previous 2 references to the class title). Each section was covered in a span of around 3 and a half weeks, with the last week being final review and special topics. The only graded materials in the class were distributed as follows - Homework (10%), Midterm 1 (22%), Midterm 2 (22%), Final (45%) and Participation (1%, hell yea!). This meant the time you spent on the course was really up to your own ability - certain people breezed through the problem sets in 5 hours and spent minimal time studying for exams, while others spent upwards of a couple dozen hours on problem sets and another couple for exams (a full-time job, for some!). Homeworks were ridiculously difficult at times, as were some exam problems, but overall I felt the exams were structured to accurately reflect your knowledge of the material based on easier homework problems and discussion questions, as well as conceptual facts from lecture. 

Here are a few of my favorite and least favorite topics from each section:

Discrete Math - Favorites:

  • Graph Theory (hated graph-coloring, but everything else was super cool especially hypercubes)
  • Public Key Cryptography (who knew so much of our lives revolve around prime numbers?)
  • Infinity and Uncountability (super unintuitive but fascinating, ex. real numbers between 0 and 1 have the same cardinality as a set of all real numbers)

Discrete Math - Least Favorites:

  • Polynomials (Hey, I learned this in Algebra I! Nvm...)
  • Self-Reference and Uncomputability (I still love Turing, but I did not understand a single question on this topic) 
  • Propositional Logic (I thought this was a math course, not a language course)

Probability Theory - Favorites (I mostly just enjoy the names of the mathematicians):

  • Geometric and Poisson Distributions (I swear the coolest thing about France are the names of their mathematicians)
  • Markov Chains (Drawing pictures on exams actually warrant points!)
  • Concentration Inequalities (A love-hate relationship, I thought I hated this topic but then did well on the final exam so now I love it, plus Chebyshev is such a cool name)

Probability Theory - Least Favorites:

  • Counting (I thought I knew how to count. I was wrong)
  • Joint Probability (One random variable is bad enough, now you add 2??)
  • Continuous Probability in General (The mecca of complained-about topics in CS70. Brush up on your Calculus)

Final Verdict:

I probably have never felt as braindead in my life as I did trying completing some of these homework assignments, especially the ones on Concentration and Continuous Probability. The exams show no mercy either, even if it's on a topic as "simple" as counting. However, I also did not get to spend as much time as I wish I could have, really trying to internalize and grasp the material. I strongly believe to build a solid foundation through CS70, it is not worth taking it over the summer. It requires a level of mathematical maturity that is difficult to build up in such a short period of time, especially without formal proof writing experience or well-tuned calculation skills. Visualizing each topic, especially in probability, is TREMENDOUSLY important in developing an intuition for these abstract concepts - a website that really helped me is Seeing Theory. 

Most people view this course as an obstacle between them and declaring the CS major, and it is true that the summer version of CS70 is curved more nicely. However, looking back, I would have enjoyed the course a lot more if I had more free time to delve into the topics in my own free time without the pressure of deadlines - the course really is a basis for CS Theory, Security, and Artificial Intelligence, and its beautiful topics should not be ignored.

Comments

Post a Comment

Popular posts from this blog

The First Post

By
I still remember the first time I read a blog.  Towards the end of freshman year in high school the college admissions bug had really bit me and I would obsessively read  MIT Blogs  every day. I was always excited to hear about the amazing experiences these amazing people across the country were having. Eventually I discovered a man on YouTube that would go on to waste way too many hours of my life. Every single day I would watch  Casey Neistat 's vlog and get to see a glimpse of his awesome life.  Today I've decided to take a step in the right direction and create my own blog alongside my good friend Owen. I'm hoping to use this blog as a platform to discuss ideas I've been formulating, commit to the goals I should've years ago, jot down notes I think are important, and most importantly, leave behind a piece of myself on the internet.  Most of my content will fall under a couple of categories: School - an all-encompassing part of life Economics/Bus
3 comments
Read more

Jack of All Trades or Master of One?

By
What does it mean to be the best at something? Einstein. Mozart. Jordan. Aristotle. These are often the most recognized names in their respective field of work, looked up to by millions every day.  But out of the billions of people who have ever lived in this world, how many of us can reasonably expect to live up to their status and ability? Short answer: the vast majority can't, and won't ever. But that doesn't stop us from aspiring to be the best at whatever we pursue, including me. Why do some people appear more successful than others? A short formula for our ability to do something is as follows (note that this may not be comprehensive, or entirely accurate, but is meant for simplicity's sake): Ability = Talent x Efficient Work where "Efficient Work" can be further broken down into time spent x quality of work . Making lots of different mistakes and reflecting on them counts as quality work. Gazing at your phone every 5 minutes while practicin
1 comment
Read more

The First .5 Post

By
They say a picture is worth 1000 words... here's to upping my word count | Source:  Unsplash I don't remember the first time I read a blog. And unlike Dhaval, I never really enjoyed writing. From the age of five years old until eighth grade, my father encouraged me to write a journal entry every Sunday, one paragraph in Mandarin, then translated into English - by far my least favorite "homework" I've ever had to do. An authentic 4th grade Owen journal entry So what am I doing creating a blog? It will serve as a breeding ground for thoughts I've never spoken aloud, ideas that usually quickly fade from recollection, as well as memories to be re-traced in the future. It will also force me to write more and communicate more eloquently, while hopefully still coming off as casual conversation. (I am quite embarrassed to say this is the most words I've written on anything in 2019). I have no particular topics in mind, but expect content to range an
1 comment
Read more