# Course Overview

### Summary

The purpose of CS70 is to provide the foundation for algorithms, concepts, and techniques to be expanded upon in further EECS classes. This foundation includes writing proofs (with various proof techniques), Boolean logic, modular arithmetic, basic graph theory, and discrete and continuous probability.

### Prerequisites

• CS61A or E7 Mathematical maturity recommended. Concretely this means having taken a college-level math course (Math 1A/B, 16A/B or other linear algebra). More broadly this means experience in math that doesn’t focus on just plug-and-chug calculations or algebraic manipulations.

### Topics Covered

• Basic logic
• Proofs (direct, by contradiction, by contrapositive)
• Induction
• Stable Marriage
• Graph Theory (hypercubes, Eulerian paths, Hamiltonian paths)
• Modular Arithmetic (Euclid's Algorithm, Extended Euclid's)
• Bijections, RSA, Fermat's Little Theorem
• Polynomials over finite fields (secret sharing, error-correcting codes, Berlekamp-Welsh)
• Countability and Computability
• Counting and Combinatorial Arguments
• Discrete Probability, Conditional Probability, Probabilistic Inference (Bayes Rule), Independence
• Probability: Expectation and Variance (applications with hash tables)
• Law of Large Numbers, Confidence Intervals, Linear Regression
• Distributions (discrete, continuous)
• Bounds (Markov, Chebyshev, Chernoff, Central Limit Theorem)
• Markov Chains

### Course Work

• Weekly problem sets
• Two midterms
• One final

### Time Commitment

There are 3 hours of lecture and 1 or 2 hours of discussion per week. Expect a steady workload from the weekly problem sets taking 10-15 hours.

# Choosing the Course

### When to take

Take this class as soon as possible (after taking CS61A), as it is a prerequisite for many upper division classes.

### What next?

After CS70, it is a good idea to take CS170 (Algorithms), because the class is of a similar format. CS70 is a prerequisite for many other upper division classes, including EE126, CS161, CS162, and CS188.

### Usefulness for Research or Internships

CS70 is somewhat helpful for research and internships -- the problem solving aspect of CS70 might prove helpful for some interviews, as well as understanding more complex research theory. However, CS70 is a prerequisite for CS170, which is a very useful class for computer science job interviews.