Mason Ziedonis

Grab a copy of my resume!

Courses

Filter By Subject

CS170

Efficient Algorithms and Intractable Problems

Computer Science

Description

Provide familiarity with algorithms for recurring basic problems. Learn to design algorithms to solve novel problems. Learn about the concept of the intrinsic difficulty of certain computational problems.

Topics Covered

  • Divide and conquer
  • Graphs and trees
  • Depth-first search
  • Topological sort; strongly-connected components
  • Breadth-first search
  • Shortest paths; Dijkstra and Bellman-Ford
  • Minimum spanning trees
  • Union/find analysis
  • Hufmann codes
  • Lempel-Ziv codes
  • Randomized min-cut
  • Hashing
  • Bloom filters
  • Dynamic programming
  • Linear programming; posing of combinatorial problems as LP problems
  • Duality
  • Network flows
  • NP completeness
  • Approximation algorithms
  • Fast Fourier transform

CS161

Computer Security

Computer Science

Description

Introduction to computer security.

Topics Covered

  • Cryptography
  • Encryption
  • Authentication
  • Hash functions
  • Cryptographic protocols
  • Applications
  • Operating system security
  • Access control
  • Network security
  • Firewalls
  • Viruses
  • Worms
  • Software security
  • Defensive programming
  • Language-based security
  • Case studies from real-world systems

EE16A

Designing Information Devices and Systems I

Electrical Engineering

Description

The EECS 16 series (Designing Information Devices and Systems) is a pair of courses introducing students to EECS, with a particular emphasis on how we deal with systems interacting with the world from an information point of view. Mathematical modeling is an important theme throughout these courses, and students will learn many conceptual tools along the way. Throughout this series, generally applicable concepts and techniques are motivated by, and rooted in, specific exemplary application domains. Students should understand why they are learning something.

In EECS 16A, we will use the application domains of imaging and tomography, touchscreens, and GPS and localization to motivate and inspire. Along the way, we will learn the basics of linear algebra and, more importantly, the linear-algebraic way of looking at the world. We will emphasize modeling and using linear structures to solve problems---not on how to do computations per se. We will learn about linear circuits, not merely as a powerful and creative way to help connect the physical world to what we can process computationally, but also as an exemplar of linearity and as a vehicle for learning how to do design. Circuits also provide a concrete setting in which to learn the key concept of "equivalence" --- an important aspect of abstraction. Our hope is that the concepts you learn in EECS 16A will help you as you tackle more advanced courses and will help form a solid conceptual framework that will help you learn throughout your career.

Topics Covered

  • Intro to Imaging/Tomography
  • Vectors and Systems of Equations
  • Linear Dependence
  • Rank
  • Span
  • Inverses
  • Vector Spaces
  • Basis
  • Nullspaces
  • Graphs
  • Circuits
  • Kirchhoff’s Law
  • Design and Touchscreen
  • Equivalence
  • Superposition
  • Power
  • Capacitors
  • Op-Amps
  • Inner Products and Orthogonality
  • Correlations
  • Trilateration
  • Least Squares
  • QR Factorization
  • PageRank
  • Diagonalization

CS70

Discrete Mathematics and Probability Theory

Computer Science

Description

The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in Electrical Engineering and Computer Sciences. The course aims to present these ideas "in action"; each one will be geared towards a specific significant application. Thus, students will see the purpose of the techniques at the same time as learning about them.

Topics Covered

  • Review of Math Notation
  • Propositions and Quantifiers
  • Proofs
  • Induction
  • Stable Marriage
  • Graph Theory
  • Modular Arithmetic
  • Bijections and RSA
  • Polynomials
  • Error Correcting Codes
  • Infinity and Uncountability
  • Self-Reference and Incommutability
  • Counting
  • Introduction to Discrete Probability
  • Conditional Probability
  • Two Killer Applications
  • Random Variables
  • Variance
  • Chebyshev's Inequality
  • Some Important Distributions
  • Continuous Probability
  • Markov Chains
  • Review of Probability
  • Estimation

CS61C

Great Ideas in Computer Architecture (Machine Structures)

Computer Science

Description

CS61C is about the hardware-software interface and what the programmer needs to know to achieve the highest possible performance. The course uses C because languages like C are closer to the underlying hardware, unlike languages like Python. This allows us to talk about key hardware features in higher level terms and allows the programmer to explicitly harness underlying hardware parallelism for high performance: “programming for performance.”

Topics Covered

  • Design for Moore’s Law (Multicore, Parallelism, OpenMP)
  • Abstraction to Simplify Design (Everything is a Number, Machine/Assembler Language, C, Logic Gates, Datapaths)
  • Make the Common Case Fast (RISC Architecture)
  • Dependability via Redundancy (ECC, RAID)
  • Memory Hierarchy (Locality, Consistency, False Sharing)
  • Performance via Parallelism/Pipelining/Prediction
  • Request Level Parallelism (Warehouse Scale Computers)
  • Instruction Level Parallelism (Pipelining, CPI > 1)
  • (Fine Grain) Data Level Parallelism (AVX SIMD Instructions)
  • (Course Grain) Data/Task Level Parallelism (Big Data Analytics, MapReduce/Spark)
  • Thread Level Parallelism (Multicore Machines, OpenMP)

Languages Covered

  • C
  • MIPS
  • Logisim
  • Spark
  • Git

Projects

  • Project 1: Flight Map

    Imagine you're an airline, tasked with routing people between various cities, while maintaining an ever-changing map of cities and flights between cities. We're going to build a simple system to solve this problem. Our system will keep track of a set of named cities as well as a set of bi-directional links between them. It'll be able to answer queries about the number of cities and the links each city has to others, and also find routes between cities.
    You will be completing the implementation of flight_map.c, which is tied to the header file flight_map.h. The header file includes an abstract struct definition map_t, which you will need to fill in, as well as signatures for the functions you will need to implement. We will describe these components in a bit more detail below. There is also a file tests.c, where you can place your own tests (more on testing later).

    Full Project Specifications Request Access to Code
  • Project 2-1: MIPS Assembler

    In this part of the project, we will be writing an assembler that translates a subset of the MIPS instruction set to machine code. Our assembler is a two-pass assembler similar to the one described in lecture. However, we will only assemble the .text segment. At a high level, the functionality of our assembler can be divided as follows:
    Pass 1: Reads the input (.s) file. Comments are stripped, pseudoinstructions are expanded, and the address of each label is recorded into the symbol table. Input validation of the labels and pseudoinstructions is performed here. The output is written to an intermediate (.int) file.
    Pass 2: Reads the intermediate file and translates each instruction to machine code. Instruction syntax and arguments are validated at this step. The relocation table is generated, and the instructions, symbol table, and relocation table are written to an object (.out) file.

    Full Project Specifications Request Access to Code
  • Project 2-2: MIPS Linker

    In part 1 of this project, we wrote an assembler in C. Now, we will continue where we left off by implementing a linker in MIPS. The linker processes object files (which in our project are .out files) and generates an executable file. In the rest of this document, "input" will be used interchangeably with "object file", and "output" with "executable file".
    The linker has two main tasks, combining code and relocating symbols. Code from each input file's .text segment is merged together to create an executable. This also determines the absolute address of each symbol (recall that the assembler outputs a symbol table containing the relative address of each symbol). Since the absolute address is known, instructions that rely on absolute addressing can have the addresses filled in.

    Full Project Specifications Request Access to Code
  • Project 3-1: ALU and Regfile

    In this project you will be using Logisim to implement a simple 32-bit two-cycle processor. Throughout the implementation of this project, we'll be making design choices that make it compatible with machine code outputs from MARS and your Project 2! When you're done, you'll be able to run most, but not all, instances of MIPS code through your assembler and linker, and then on your very own CPU! We have left out some functionality to make the project easier.
    In part I, you will make the Regfile and ALU.

    Full Project Specifications Request Access to Code
  • Project 3-2: CPU

    Now that you've implemented the Regfile and ALU, you're ready to design your own 2-stage pipelined processor! When you're done, you'll be able to run MIPS code through your assembler and linker, and then on your very own CPU

    Full Project Specifications Request Access to Code
  • Project 4: Performance Optimization

    Cameras traditionally capture a two dimensional projection of a scene. However depth information is important for many real-world application. For example, robotic navigation, face recognition, gesture or pose recognition, 3D scanning and more. The human visual system can perceive depth by comparing the images captured by our two eyes. This is called stereo vision. In this project we will experiment with a simple computer vision/image processing technique, called "shape from stereo" that, much like humans do, computes the depth information from stereo images (images taken from two locations that are displaced by a certain amount).
    Optimize the naive depth map generator using any of the techniques you learned, including OpenMP. For full credit, the program needs to achieve an average speedup of 4.5x for the odd cases given in the benchmark, and 5.5x for the non-odd cases given in the benchmark.

    Full Project Specifications Request Access to Code
  • Project 5: Image Compression with Spark

    There have always been different methods of video compression in order to adapt videos to be rendered more easily on devices with less memory or computing capacity. We will be implementing a scheme using the Discrete Cosine Transform (DCT) to perform video compression. This form of lossy compression encoding is typically used alongside lossless compression to compress video files. For the purposes of this project, we will only focus on the lossy aspect.

    Full Project Specifications Request Access to Code

Math 54

Linear Algebra and Differential Equations

Math

Description

Basic linear algebra; matrix arithmetic and determinants. Vector spaces; inner product spaces. Eigenvalues and eigenvectors; linear transformations. Homogeneous ordinary differential equations; first-order differential equations with constant coefficients. Fourier series and partial differential equations

Topics Covered

  • Linear Equations in Linear Algebra
  • Matrix Algebra
  • Determinants
  • Vector Spaces
  • Eigenvalues and Eigenvectors
  • Orthogonality and Least Squares
  • Symmetry Matrices and Quadratic Forms
  • Linear Second-Order Equations
  • Theory of Higher-Order Linear Differential Equations
  • Matrix Methods for Linear Systems
  • Partial Differential Equations

CS61B

Data Structures and Advanced Programming

Computer Science

Description

The CS 61 series is an introduction to computer science, with particular emphasis on software and machines from a programmer's point of view. In CS 61B, we move to a somewhat more detailed (and to some extent, more basic) level of programming.

In CS61B, we're concerned also with engineering. An engineer, it is said, is someone who can do for a dime what any fool can do for a dollar. Much of 61B will be concerned with the tradeoffs in time and memory for a variety of methods for structuring data. We'll also be concerned with the engineering knowledge and skills needed to build and maintain moderately large programs.

Topics Covered

  • Object Oriented Programming: Interface/Implementation Inheritance
  • Dynamic vs. Static Typing
  • Generic Programming
  • The Model of Memory as Boxes Containing Bits
  • Bit Representation of Positive Integers
  • Objects as Function Containers
  • Default Method Specification in Interfaces
  • Iterators and Views
  • Mathematical Analysis of Data Structure/Algorithm Performance (Asymptotic Analysis, Worst Case vs. Average Case vs. Best Case, Determining the Runtime of Code through Empirical Analysis and Inspection,
  • Amortized Time
  • Array-based Data Structures (ArrayLists and ArrayDeque, HashSets, HashMaps, ArrayHeap (tree represented as an array))
  • Linked Data Structures (Linked Lists (LinkedList, IntList, LinkedListDeque), Trees (TreeSet, TreeMap, BSTMap, Tries), Graphs (generalization of a tree)
  • Tradeoffs of Arrays vs. Linked Data Structures
  • Prim’s Algorithm
  • Kruskal’s Algorithm
  • Dijkstra’s Algorithm
  • A* Search Algorithm
  • Sorting Algorithms
  • Huffman Coding
  • Java Syntax and Idioms
  • JUnit Testing
  • Test-driven Development
  • Debugging
  • Data Structure Selection (and API design)
  • Working with Complex APIs

Languages Covered

  • Java
  • Git

Projects

  • Project 0: NBody Simulation

    Ultimately, you will be creating a program NBody.java that draws an animation of bodies floating around in space tugging on each other with the power of gravity.

    Full Project Specifications Request Access to Code
  • Project 1a: Data Structures

    In project 1, we will build implementations of a "Double Ended Queue" using both lists and arrays. We will later learn how to write our own tests for those data structures, and finally we will use those data structures to solve a small real world problem.
    Project 1a is the implementation of the data structures. In this part of the project you will create exactly two Java files: LinkedListDeque.java and ArrayDeque.java, with public methods listed below.

    Full Project Specifications Request Access to Code
  • Project 1b: Data Structures

    In project 1b, you will build a rudimentary autograder for project 1a.

    Full Project Specifications Request Access to Code
  • Project 1c: Data Structures

    In project 1c, you will build a program that uses the Deque classes to find English words with interesting properties.

    Full Project Specifications Request Access to Code
  • Project 2: Editor

    In this project, you will build a text editor from scratch. You are probably familiar with a variety of different text editors, including relatively simple text editors that allow you to edit un-styled text (e.g., pico, Notepad, and TextEdit), and also more fully-featured text editors that allow you to do add formatting, run code, and more (e.g., Microsoft Word, Google Docs, Sublime, VI, Emacs, and IntelliJ). For this project, you'll implement a basic text editor that can be used to open, edit, and save plain text files.

    Full Project Specifications Request Access to Code
  • Project 3: Bear Maps

    Project 3 is a web mapping application, inspired by my time on the Google Maps team and the OpenStreetMap project, from which the tile images and map feature data was downloaded. You are working with real-world mapping data here that is freely available - after you've finished this project, you can even extend your code to support a wider range of features. You will be writing the back end - the web server that powers the API that the front end makes requests to.
    Your job is to implement a web API. You will write a web server that hosts some endpoints that take in parameters and provide output in JSON.

    Full Project Specifications Request Access to Code

CS61A

The Structure and Interpretation of Computer Programs

Computer Science

Description

The CS 61 series is an introduction to computer science, with particular emphasis on software and on machines from a programmer's point of view. This first course concentrates mostly on the idea of abstraction, allowing the programmer to think in terms appropriate to the problem rather than in low-level operations dictated by the computer hardware.

In CS 61A, we are interested in teaching you about programming, not about how to use one particular programming language. We consider a series of techniques for controlling program complexity, such as functional programming, data abstraction, and object-oriented programming. Mastery of a particular programming language is a very useful side effect of studying these general techniques. However, our hope is that once you have learned the essence of programming, you will find that picking up a new programming language is but a few days' work.

Topics Covered

  • Functions
  • Names
  • Control
  • Higher-Order Functions
  • Environments
  • Recursion
  • Tree Recursion
  • Data Abstraction
  • Sequences
  • Trees
  • Mutable Values
  • Mutable Functions
  • Objects
  • Inheritance
  • Representation
  • Composition
  • Hierarchy
  • Growth
  • Sets
  • Users
  • Scheme
  • Exceptions
  • Interpreters
  • Tail Calls
  • Iterators
  • Streams
  • Declarative Programming
  • Tables
  • Recursive Select
  • Aggregation
  • Distributed Computing
  • Distributed Data

Languages Covered

  • Python
  • SQL
  • Scheme
  • Spark
  • Git

Projects

  • Project 1: The Game of Hog

    In this project, you will develop a simulator and multiple strategies for the dice game Hog. You will need to use control statements and higher-order functions together.
    In Hog, two players alternate turns trying to be the first to end a turn with at least 100 total points. On each turn, the current player chooses some number of dice to roll, up to 10. That player's score for the turn is the sum of the dice outcomes. To spice up the game, we will play with some additional special rules (see full spec for more information).

    Full Project Specifications Request Access to Code
  • Project 2: Yelp Maps

    In this project, you will create a visualization of restaurant ratings using machine learning and the Yelp academic dataset. In this visualization, Berkeley is segmented into regions, where each region is shaded by the predicted rating of the closest restaurant (yellow is 5 stars, blue is 1 star). Specifically, the visualization you will be constructing is a Voronoi diagram.

    Full Project Specifications Request Access to Code
  • Project 3: Ants Vs. SomeBees

    In this project, you will create a tower defense game called Ants Vs. SomeBees. As the ant queen, you populate your colony with the bravest ants you can muster. Your ants must protect their queen from the evil bees that invade your territory. Irritate the bees enough by throwing leaves at them, and they will be vanquished. Fail to pester the airborne intruders adequately, and your queen will succumb to the bees' wrath. This game is inspired by PopCap Games' Plants Vs. Zombies.

    Full Project Specifications Request Access to Code
  • Project 4: A Scheme Interpreter

    In this project, you will develop an interpreter for a subset of the Scheme language. As you proceed, think about the issues that arise in the design of a programming language; many quirks of languages are byproducts of implementation decisions in interpreters and compilers. The subset of the language used in this project is described in the functional programming section of Composing Programs.
    The project concludes with an open-ended graphics contest that challenges you to produce recursive images in only a few lines of Scheme. As an example, the picture above abstractly depicts all the ways of making change for $0.50 using U.S. currency. All flowers appear at the end of a branch with length 50. Small angles in a branch indicate an additional coin, while large angles indicate a new currency denomination. In the contest, you too will have the chance to unleash your inner recursive artist.

    Full Project Specifications Request Access to Code

Math 1A/1B

Calculus

Math

Description

An introduction to differential and integral calculus of functions of one variable, with applications and an introduction to transcendental functions. Techniques of integration; applications of integration. Infinite sequences and series. First-order ordinary differential equations. Second-order linear ordinary differential equations.

Topics Covered

  • Functions and Models
  • Limits and Derivatives
  • Differentiation Rules
  • Applications of Differentiation
  • Integrals
  • Applications of Integration
  • Techniques of Integration
  • Further Applications of Integration,
  • Infinite Sequences and Series
  • Differential Equations
  • Second-Order Differential Equations

Languages

Basic

Intemediate

Proficient

Advanced

Expert