Math review for wannabe computer science student

December 22, 2016 5:41 AM

Next semester, I will be taking a university class on the mathematical methods used in studying computer science. My last math class was a very, very long time ago. What topics should I review in the next month so that I won't be totally lost in my class?

I'm a grownup who works at a university. This semester, I took the Intro to Computer Science class for CS majors. I enjoyed it and did well. Next semester, I'm signed up to take the second class in the CS major, which is a math class. According to the course description, the topics include:

mathematical logic; proof techniques, especially mathematical induction; set theory, functions, and relations; procedures, recursion, and operation counts; recurrence relations; analysis of algorithms; counting methods, permutations and combinations; graphs and trees.

There's no pre-requisite, although calculus is recommended. The prof has indicated that they're using calc as a proxy for being able to think mathematically, and it's not necessary to know calculus to do the work. I think I can do it: I really loved doing proofs in high-school geometry, and I've done well in CS classes that have a reputation for being tough. Even so, I'd like to review some math in the month before the class starts. It's been 20-odd years since my last math class, which was pre-calculus, and I don't remember anything. If I were going to watch some Khan Academy videos and such to prepare for this class, what topics should I focus on? Are there any particularly great resources to use?

posted by ArbitraryAndCapricious to Education (16 answers total)

I have taken a very similar class, also as a university staff member. I also don't think calculus per se was necessary. Linear algebra tends to be most useful, but my forays into machine learning more recently might be coloring that recollection. Number theory is probably closest to what this course will require, but it might be taught. Real vs imaginary numbers, basic algebra (factorization, etc), trig function identities will probably be facts they assume you know. Primes became important in my similar class when we ventured into derivation of cryptography techniques.

I'd try to find proofs that sound like what might be taught and see what techniques they use that you're rusty on.
posted by supercres at 5:52 AM on December 22, 2016 [2 favorites]

If you want to do some pre-reading, check out MOOCs like MIT Open Courseware or Coursera. However, the Coursera course may not release in time before your semester starts.
posted by lucia_engel at 5:59 AM on December 22, 2016

Fwiw, here's the first homework from the most recent iteration of the class that I took. (I actually still have all my old problem set solutions. Wish I still had the lecture notes too.)
posted by supercres at 6:07 AM on December 22, 2016

I took several classes like that as an undergrad CS major with no real math background, and the one thing that I struggled most with was thinking through and writing proofs. Proofs are the lingua franca of upper level math and most of my problem sets were easily 75% proof-writing, so not having that background hurt (luckily I had the help of several more math-inclined friends to get me off the ground).

A mathematician friend of mine lent me a very helpful book on proof writing that I was gonna recommend, but all I remember about it is that it had a yellow cover and none of the books on proofs that people recommend online have yellow covers so now I unfortunately have no clue what the book was. That being said there are a handful of books out there that seem to get recommended repeatedly; I'd suggest checking them out and picking one that looks good.
posted by Itaxpica at 6:30 AM on December 22, 2016

(For what it's worth I was also great at geometry proofs in high school but I found the more abstract nature of proofs in upper-level CS to be an almost entirely different beast)
posted by Itaxpica at 6:31 AM on December 22, 2016

The description is kind of all over the place. It feels an awful lot like a discrete structures class, which is ultimately a class where you learn to represent elements of computer languages as mathematical elements that you can reason about. You can design a for-loop, but can you prove that it is mathematically correct?

I would look at set theory and boolean logic first, then start prepping for how to do proof by induction.
Interestingly enough, many approaches to teaching recursion as a technique to solve problems follow the same pattern as a proof by induction.

For an example of a typical discrete structures curriculum, see this PDF.
posted by plinth at 6:32 AM on December 22, 2016 [2 favorites]

Some of the math would be in textbooks with the words "Finite Mathematics" on the cover. Maybe you can get one in the University library. Permutations and combinations would be in a text on Probability (not Statistics). If the course goes into the problems of using floating point math, you might want to review logarithms since it uses the same ideas, but it's a topic the course may not cover at all. You want to have a firm handle on binary, octal, and hexadecimal (at least enough to see they are all the same thing.
posted by SemiSalt at 6:33 AM on December 22, 2016

i think a rigorous self-paced review of 'college algebra' and 'probability and statistics I' will cover it.

- exponents
- binary, octal, and hex numbers and arithmetic
- functions
- permutations/combinations
- sequences and series
- boolean algebra
posted by j_curiouser at 6:40 AM on December 22, 2016 [3 favorites]

The general umbrella term for the topics you're covering is "discrete mathematics", which over the years has come to mean "mathematics for CS undergrads". I'm sure all of them will be covered well, but I agree that proof-writing is one of the conceptually more difficult ideas, so I would focus on that if you're looking to get a head start. The first three lectures of the MIT OCW mathematics for computer science are a good place to start. If you like the MIT course after that, keep going, because it will be a useful alternative perspective your your own. Khan Academy seems to have a ton of examples of proofs which might be worth watching, but nothing focussed on proofs per se.
posted by caek at 6:48 AM on December 22, 2016 [1 favorite]

I'd recommend looking at discrete math. On preview, what caek said above.
posted by zsazsa at 6:50 AM on December 22, 2016 [1 favorite]

This is the equivalent course in MIT open courseware, which on posting I see is already linked. Sorry folks.
posted by Lazlo Hollyfeld at 8:24 AM on December 22, 2016

You might (eventually) find the 'Sample Proofs' section of this course page helpful. It disabuses you of the idea that proofs are identical to two-column geometry proofs, and gives you checklists for each type of proof.

I would try to be really comfortable with basic number theory (exponents, modulo, divisibility), since that's typical fodder for examples.

Good luck and have fun; this (type of) course is what turned me into half a math major.
posted by batter_my_heart at 8:45 AM on December 22, 2016 [1 favorite]

Take an intro to modern algebra if you want to feel comfortable with proofs.

As a bonus- you'll really really really understand long division!
posted by oceanjesse at 10:11 AM on December 22, 2016

as others said, course sounds very close to discrete structures, does it have a name?

I'd review this course outline/notes from a cornell class http://www.cs.cornell.edu/~rafael/discmath.pdf
posted by czytm at 8:03 AM on December 23, 2016

Response by poster: It is indeed called Discrete Structures. Typically, CS majors take it in the same semester when they're taking Calc II. I don't think that most students in the class will have had Linear Algebra yet, so that's definitely not an expectation.

Incidentally, it used to be a co-req for the Data Structures class that CS majors take, but it looks like they've gotten rid of that requirement this semester. I could conceivably skip Discrete Structures and go straight to the Data Structures class, which I was planning to take in the Fall, but I'm not sure that's a good idea.
posted by ArbitraryAndCapricious at 8:16 AM on December 23, 2016

in the cs program here, Discrete Structures is a pre-req for Data Structures and Algorithms, wouldn't advise skipping discrete even if they let you.
posted by czytm at 8:26 AM on December 23, 2016 [3 favorites]