Efficient Algorithms and Intractable Problems
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.
Introduction to computer security.
Designing Information Devices and Systems I
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.
Discrete Mathematics and Probability Theory
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.
Great Ideas in Computer Architecture (Machine Structures)
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.”
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).
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.
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.
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.
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 CPUFull Project Specifications Request Access to Code
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.
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
Linear Algebra and Differential Equations
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
Data Structures and Advanced Programming
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.
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
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.
In project 1b, you will build a rudimentary autograder for project 1a.Full Project Specifications Request Access to Code
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
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 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.
The Structure and Interpretation of Computer Programs
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.
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).
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
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
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.
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.