Skip to content

0. Introduction

Welcome to CS61A! My name is Matthew Dharmawan, and I want to create these notes/videos/etc. as a means to help you all succeed in this class. I took CS61A in Fall 2021, and I thoroughly enjoyed this class. It actually was my second experiece in programming (if you count AP Computer Science Principles).

About this Course

You'll primarily learn two skills from this course.

  1. How to read code and write it yourself. Now this class uses Python and Scheme as two programming languages to learn, but unlike learning languages like Spanish, French, etc., once you learn one and are comfortable with handling code in one language, learning another will only require a few days work.

  2. How to approach difficult problems. Now when I took this course, I was surprised to find how difficult some of the problems were throughout the semester; the midterm and final problems were especially super challenging. One thing that I really like how this course runs is that you'll see how to approach these complicated problems. Along the way, you will gain essential problem-solving skills that you will carry in your toolbox.

The Purpose of These Notes

Now my main priority here is to focus on being able to gain problem-solving skills necessary for not only this class, but future EE/CS classes you'll take in later semesters. What that means is I will approach looking at problems from your perspective, a student who may be looking at these problems for the first or second time.

I do know that I am not alone in achieving this goal, and I know that other students have done something similar to these notes. These notes are just another resource for you to use. With that said, I hope that you will takeaway some important skills by going throught any resource from Instructors, TAs, Tutors, Academic Interns. I'll be sure to share the resources I found helpful when I took this class when we get to those topics.

Overview

I think that giving you all a high-level overview of what is to come in this course will allow you to understand the bigger picture of this course. You can read through what I have to say below (or not), but I hope that reading through this will give you excitement and motivation to learn and see how each of these different topics fit together. Once you come to understand the topics more, you'll appreciate reading this overview again to see how far you have come in your Computer Science journey. The overview is how I plan to continue these notes.

  1. We will start with the tools you will be using: Python and your Terminal. Getting to know how to use it and getting a general workflow in running your programs will basically be what you will be doing in this class all the time, so getting used to basic Python syntax and basic terminal commands is a good start.

  2. Variables, Expressions, and Functions: I like to think of programming as like math -- there are certain rules you must follow and also a strict way of evaluating the rules. In addition, there are ways to generalize concepts and abstract the nitty-gritty of things. For example, variables can be used and referenced again and again; functions can be called again and again without repeating yourself too much. Functions are just like those in math -- they take in parameters, operate on them, and then (possibly) spit out an answer. Unlike in math, functions in code can be any series of steps that can repeat itself, call other functions, and they don't have to evaluate to just numbers (or anything at all)!

  3. Control: Of course, your code won't always be read line by line. What happens if you want to do the same operation 500 times? Are you going to just copy-paste it 500 times? No! How about if your program depends on if a condition is met? Well, control will help you break away from sequential reading of your code and add in the ideas of iteration and selection.

  4. Higher-Order Functions: At this point, you'll be used to implementing some functions using control and what you already know. However, we can take it one step further... remember when I said functions take in parameters? What if those paramaters are functions? What if the function returns a different function? And why is doing this useful at all?

  5. Environment Diagrams: Now the implementation of code that you are writing is getting more and more complex. What an environment diagram does is that it helps you visualize what is going on in your program and allows you to see what variables functions can and cannot see. We will be revisiting this topic a couple of times throughout this course.

  6. Recursion: When I first learned recursion it didn't make sense. It never really started clicking until after midterm 2... when most of the exam was... recursion... I didn't do too well on that midterm. But now I understand it pretty well. So what is recursion? It is basically this idea that you might not know the answer immediately, so what if you ask that same question again to someone else but for a simpler case? Well they still might not know it, so ask it again to another person. At some point someone will know the answer because the input is so simple. Now that person will tell the person their answer, so that the answer can be combined to form the answer for that person, who tells it to the person who asked them... until it reaches you, and then you can create the answer. Why this topic is always a hard topic is that you basically call the function inside itself, and you have to trust that it will give you the right answer. Recursion will be a topic that will appear a lot on this course, so you will be hopefully good at it by the end of this course.

  7. Containers: You know some basic types in Python, such as strings, int, booleans, but now we want to store these values into more complicated structures. Here, we will discuss some important containers -- lists, tuples, dictionaries, as well as some operations we can perform on containers that will help us solve more problems.

  8. Mutability: Containers are definitely more complicated than a single entity, and there might be cases when we need to add new values to our containers, remove some. Mutability is the concept of mutating these containers. However, there are some containers that are immutable.

  9. Object-Oriented Programming: One can think of the container as an object. What is an object in Computer Science? It is something that holds data. Object-Oriented Programming (OOP) is organizes code to be all about the data, and the methods that operate on them. This is opposed to the organization of code to be functions and logic that you have been doing from the beginning.

  10. Trees and Linked Lists: OOP is great because it allows us to solve really complex problems. A specific data structure that you will learn here are the Trees and the Linked Lists. These are two specific types of objects that allow you to solve a ton of problems. There is a lot of recursion happening here, and it is a huge topic in this class and for future classes too (like CS 61B)

  11. Iterators and Generators: Maybe you have written so many functions using a for loop. Let's analyze the syntax of a for loop and understand that it iterates over somethng that is iterable. An iterator is an iterable, and a generator is an iterator. The best part about the generator is that you can define the generator to be anything you want, and we can iterate over that generator. Iterators and Generators are not too terrible to understand, but they do have their trickiness associated with it.

  12. Efficiency: How fast are the programs that you create? Is there a way to quantify the speed of your program? Efficiency is a topic that comes up a lot in CS, and you'll see it in almost every CS class you'll take. I will introduce the concept of Efficiency here.

  13. Scheme: Now it's time to move on to the second half of the course, also conveniently the second half of the course name: The Interpretation. In order to do this, you'll first have to learn the Scheme language. The Scheme language is not really a used language in today's world, but you will learn how to use it for the purpose of the end of this class.

  14. Interpreters: Did you know that Python is an interpreted language? That means the text of Python is read by the C language, and then the C language creates the necessary components to run your program (then C is compiled into an assembly language, then machine code). Now what you will learn is how to create an interpreter of the Scheme language using Python. How do you know what to read in Scheme and how do you break down the syntax of Scheme and create the necessary Python components to run the code?

  15. Regex: We are now moving on to a different type of programming called declarative programming. We've discussed functional programming and object-oriented programming. Declarative programming is all about just stating what you want, without really any regards to how the internals really work. In this case, we will be trying to create a grammar that can read strings and code. Regex is a tool that is used to match text; when you use CTRL+F, the words you type in are kind of like regex!

  16. SQL: Here is another programming language that you will be introduced to that is also declarative. When you store information in a database, how can you retrieve that information. What if you want to retrieve data that has a specific attribute to it? SQL is the language to do that.