Finite State Machine (FSM)

Propositional calculus (Propositional logic)

Translation

Circuits

Equivalences

Boolean Algebra

Canonical Forms

Predicate Logic

Proofs for Propositional Logic

Proofs for Predicate Logic

English Proofs

Set theory

Modular arithmetic

Primes

Greatest Common Divisor (GCD)

Euclidian Algorithm

Modular Equations

Modular Exponentiation

Induction

Strong Induction

Recursively Defined Functions

Recursively Defined Sets

Set (mathematics)

Structural Induction

Relation (mathematics)

Nondeterministic Finite Automata (NFA)

More Structural Induction

Directed Graphs

Relating DFAs, NFAs, and REs

Regular expression

Limitations of DFAs, NFAs, and REs

Context-Free Grammar (CFG)

FSM Minimization

CSE 311 Foundations of Computing I University of Washington Autumn 2021 CSE 311 introduces theoretical computer science, the theory background necessary for other CSE courses, and how to construct rigorous, formal arguments. Topics include logic, set theory, modular arithmetic, induction, regular expression, and relations.  1. Teach you the theory background needed for other CSE courses
    – only topics used in many areas of CSE
1. Teach you how to make and communicate rigorous and formal arguments
    – want to know for certain that systems work
1. Introduce you to theoretical CS
    – may be the only theory course you take  There is no required text for the course. For the first 6-7 weeks of the course, the following textbook can be useful: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. (Course materials will reference problem numbers from the 6th edition, but more recent versions include the same material.) It should be available through the bookstore and on short-term loan from the Engineering Library.

On occasion, there may be required readings during the course when there is insufficient time to fully cover the material during lecture. If this occurs, the readings will be posted on the web site and students will be notified of the reading via email or the message board.

CSE 311 Foundations of Computing I

Mathematical Foundations

Theoretical Computer Science

Floating Point

RISC-V Procedures

Loader

RISC-V Single-Cycle Datapath

Caches - Multilevel

Parallelism

Translation Lookaside Buffer (TLB)

Amdahl's law

RAID (Redundant Array of Inexpensive Disks)

Virtual memory

RISC-V Instruction Formats

Combinational Logic

RISC-V Single-Cycle Control

Caches - Set-associative

Thread-level Parallelism

Page faults

Virtual memory performance

Data-level parallelism

Data center

Assembly language

Number Representation

RISC-V

Compiler

Synchronous Digital Systems (SDS) State

RISC-V 5-Stage Pipeline

Performance with Caches

OpenMP

Multilevel

Dependability

Warehouse-scale Computing

Input/output

C (programming language)

RISC-V Data Transfer

Assembler

Hazards

Flynn taxonomy

Cache coherence

Interrupts

MapReduce

Parity

C Memory (Mis)Management

RISC-V Decision Making Logical Ops

Linker

Combinational Logic Blocks

Caches - Direct Mapped

Single instruction, multiple data (SIMD)

Performance

Exception handling

Apache Spark

Error-correcting Codes (ECC)

CS 61C Great Ideas in Computer Architecture (Machine Structures) UC Berkeley Fall 2022 This course deepens students' understanding of computer architecture and the translation of high-level programs into machine language. Emphasis is on C and assembly language programming, computer organization, parallelism, CPU design, and warehouse-scale computing. Prerequisites include CS61A and CS61B or equivalent C-based programming experience. [Official Academic Guide course description](https://classes.berkeley.edu/content/2022-fall-compsci-61c-001-lec-001)

The subjects covered in this course include C and assembly language programming, translation of high-level programs into machine language, computer organization, caches, performance measurement, parallelism, CPU design, warehouse-scale computing, and related topics.  CS61A and CS61B (or equivalents) or experience with a C-based programming language (e.g. Java, C++). There is no official textbook for this class. However, there are three optional textbooks as additional references:

- **P&H**: Second edition of Patterson and Hennessy's *Computer Organization and Design RISC-V Edition* book ("P&H"), ISBN 0128122757.
- **K&R**: *The C Programming Language, Second Edition* by Kernighan and Ritchie. Other C programming books are also suitable if you are already comfortable with them, but our lectures will be based on K&R.
- **WSC**: *The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines*, which is freely available [on our website](https://inst.eecs.berkeley.edu/~cs61c/resources/WSCBarrosoHolzle.pdf).

Please contact staff on Ed if you have trouble finding or paying for these textbooks.

CS 61C Great Ideas in Computer Architecture (Machine Structures)

Computer Systems