Welcome to CS61B!
Please see the rather extensive information on sections, Covid-19 policy, sections, labs, initial assignments, and the presemester sur- vey on the Spring 2022 CS61B Piazza site.
Labs start today. In (or preferably before) lab this week, get a CS61B Unix account from https://inst.eecs.berkeley.edu/webacct.
Try logging in remotely to one of the instructional servers
Copyright By PowCoder代写 加微信 powcoder
(. . . @X .berkeley.edu, where X is ashby.cs, derby.cs, cedar.cs, cory.eecs, and others).
The course homepage (https://inst.eecs.berkeley.edu/ cs61b/sp22) is our central distribution site for assignments, lecture slides, course policy, and much else.
Lectures will be recorded and screencast. The recordings should become available in the bCourses Media Gallery sometime after the lecture.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 1
Crowding, etc.
If you choose not to take this course please drop it as soon as possi- ble for the benefit of others (the add/drop deadline is 9 February— 28 January if you wish to avoid a fee).
As you know, Dwinelle will not hold us all, which is why there are both offline and online lectures. Lecture seating is on a first-come- first-seated basis. Definitely not ideal, but we hope that after the first few weeks, those of you who prefer in-person lectures will be able to have it.
Lectures, etc., will be entirely online for at least the first two weeks, due to the current outbreak.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 2
There are two readers currently on-line (see the website). Textbook (for first part of the course only) is Head First Java. It’s
kind of silly, but has the necessary material.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 3
Course Organization I
You read; we illustrate.
Labs are important: exercise of programming principles as well as practical dirty details go there. Generally we will give you homework points for doing them.
Homework is important, but it’s reasonably easy to get full credit: use it as you see fit and turn it in! You should get points for just putting some reasonable effort into it.
Individual projects are really important! Expect to learn a lot. Projects are not team efforts (that’s for later courses).
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 4
Course Organization II
Use of tools is part of the course. Programming takes place in a programming environment:
– Handles editing, debugging, compilation, archiving versions.
– Personally, I keep it simple: Emacs + gjdb + make + git, (doc- umented in one of the readers and on-line). But we’ll look at IntelliJ in lab.
Tests are challenging: better to stay on top than to cram. Tests, 40%; Projects, 50%; HW, 10%
Stressed? Tell us!
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 5
Pandemic Considerations
It’s everyone’s responsibility to look out for each other.
This semester, in particular, this means adhering to certain incon- venient practices mandated by the University.
These include wearing masks indoors, as well as staying home when sick.
Please observe the mask mandate; if anyone refuses, I can and will be forced to simply end the day’s lecture, and you’ll all have to rely on the on-line slides for the material.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 6
Academic Dishonesty
Sadly, the incidence of academic dishonesty seems to have increased over the years.
To an extent, this is our fault: the minimum GPA threshold policy for L&S majors puts people under a lot of stress,
Nevertheless, we can’t afford to tolerate cheating. The Course Info tab on the course homepage contains our policy on cheating and the penalties we impose; please read them.
By keeping up with the course and starting assignments early, you can reduce any perceived need to cheat.
Also, this course is not curved, so you are not disadvantaged by other people’s dishonesty.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 7
Programming, not Java
Here, we learn programming, not Java (or Unix, or Windows, or. . . ) Programming principles span many languages
– Look for connections.
– Syntax (x+y vs. (+ x y)) is superficial.
– Java, Python, and Scheme have a lot in common.
Whether you use GUIs, text interfaces, or embedded systems, im- portant ideas are the same.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 8
For next time
PleasereadChapter1ofHeadFirstJava,plus 1.1–1.9oftheon-line book A Java Reference, available on the class website.
This is an overview of most of Java’s features. We’ll start looking at examples on Friday.
Always remember the questions that come up when you read some- thing we assign:
– Who knows? We might have made a mistake.
– Feel free to ask at the start of lectures, by email, or by Piazza.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 9
Last modified: Wed Jan 19 22:04:19 2022
CS61B: Lecture #1 10
Acronyms of Wisdom
A Quick Tour through the First Program
In Python, we would write
# Traditional first program print(“Hello, world”)
But in Java,
/** Traditional first program. * @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */ public static void main(String[] args) {
System.out.println(“Hello, world!”);
Last modified: Wed Jan 19 22:04:19 2022
CS61B: Lecture #1 11
Commentary
/** Traditional first program.
* @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */
public static void main(String[] args) { System.out.println(“Hello, world!”);
Java comments can either start with ‘//’ and go to the end of the line (like ‘#‘ in Python), or they can extend over any number of lines, bracketed by ‘/*’ and ‘*/’.
I don’t use the ‘//’ comments, except for things that are supposed to be replaced, and our style checks will flag them.
The second, multiline kind of comment includes those that start with ‘/**’, which are called documentation comments or doc comments.
Documentation comments are just comments, having no effect, but various tools interpret them as providing documentation for the things that follow them. They’re generally a good idea and our style checks require them.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 12
/** Traditional first program.
* @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */ public static void main(String[] args) {
System.out.println(“Hello, world!”);
Every function and variable in Java is contained in some class. These are like Python’s classes, but with (of course) numerous dif-
ferences in detail.
All classes, in turn, belong to some package. The Hello class belongs
to the anonymous package. We’ll see named packages later,
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 13
Methods (Functions)
/** Traditional first program.
* @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */ public static void main(String[] args) {
System.out.println(“Hello, world!”);
Function headers in Java contain more information than those in Python. They specify the types of values returned by the function and taken as parameters to the functions.
The “type” void has no possible values; the main function here re- turns nothing. The type String is like Python’s str. The trailing ‘[]’ means array of. Arrays are like Python lists, except that their size is fixed once created.
Hence, main takes a list of strings and returns nothing.
Functions named “main” and defined like the example above are spe- cial: they are what get called when one runs a Java program (in Python, the main function is essentially anonymous).
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 14
/** Traditional first program.
* @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */ public static void main(String[] args) {
System.out.println(“Hello, world!”);
As in Python, E.N means “the thing named N that is in or that applies to the thing identified (or computed) by E.”
Thus “System.out” means “the variable named ‘out’ that is found in the class named ‘System’.”
Likewise, “System.out.println” means “the method named ‘println’
that applies to the object referenced by the value of variable ‘System.out’.”
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 15
/** Traditional first program.
* @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */ public static void main(String[] args) {
System.out.println(“Hello, world!”);
Every declared entity in Java has access permissions indicating what pieces of code may mention it.
In particular, public classes, methods, and variables may be referred to anywhere else in the program.
We sometimes refer to them as exported from their class (for methods or variables) or package (for classes).
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 16
/** Traditional first program.
* @author P. N. Hilfinger */
public class Hello {
/** Print greeting. ARGS is ignored. */ public static void main(String[] args) {
System.out.println(“Hello, world!”);
Static methods and variables are “one-of” things.
A static method is just like an ordinary Python function (outside of
any class) or a function in a Python class that is annotated @staticmethod.
A static variable is like a Python variable defined outside of any class or a variable selected from a class, as opposed to from a class instance.
Other variables are local variables (in functions) or instance vari- ables (in classes), and these are as in Python.
Last modified: Wed Jan 19 22:04:19 2022 CS61B: Lecture #1 17
Administrivia
Please make sure you have obtained a Unix account.
If you decide not to take this course after all, please tell CalCentral ASAP, so that we can adjust the waiting list accordingly.
HW #0 will be due next Friday at midnight. While you get credit for any submission, we strongly suggest that you give the problems a serious try.
We strongly discourage taking this course P/NP (or S/U).
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 1
Lecture #2: Let’s Write a Program: Prime Numbers
Problem: want java Primes U to print prime numbers through U. You type: java Primes 101
Ittypes: 2357111317192329
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101
Definition: A prime number is an integer greater than 1 that has no divisors smaller than itself other than 1.
(Alternatively: p > 1 is prime iff gcd(p,x) = 1 for all 0 < x < p.)
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 2
public class Primes {
/** Print all primes up to ARGS[0] (interpreted as an
* integer), 10 to a line. */
public static void main(String[] args) { printPrimes(Integer.parseInt(args[0]));
/** Print all primes up to and including LIMIT, 10 to * aline.*/
private static void printPrimes(int limit) {
/*{ For every integer, x, between 2 and LIMIT, print it if
isPrime(x), 10 to a line. }*/ }
/** True iff X is prime. */
private static boolean isPrime(int x) { return /*( X is prime )*/;
Last modified: Sat Jan 22 20:02:28 2022
CS61B: Lecture #2 3
private static boolean isPrime(int x) { return /*( X is prime )*/;
Testing for Primes
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 4
Testing for Primes
private static boolean isPrime(int x) { if (x <= 1)
return false;
return !isDivisible(x, 2, x); // "!" means "not" }
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 5
Testing for Primes
private static boolean isPrime(int x) { if (x <= 1)
return false;
return !isDivisible(x, 2, x); // "!" means "not" }
/** True iff X is divisible by any positive number >= LOW >= 1 * and
return false;
else if (x % low == 0) // “%” means “remainder”
return true;
else // if (low < high && x % low != 0)
return isDivisible(x, low, high); }
Last modified: Sat Jan 22 20:02:28 2022
CS61B: Lecture #2 7
Thinking Recursively
Understand and check isDivisible(13,2) by tracing one level.
Call assigns x=13, low=2, high=13
/** True iff X is divisible by some number * >=LOW>=1and
return false;
else if (x % low == 0)
return true;
return isDivisible(x, low + 1, high); }
Body has form
if (low >= high) S1 else S2.
Since 2 < 13, we evaluate the (first) else.
Check if 13 mod 2 = 0; it’s not.
Left with isDivisible(13, 3, 13).
Rather than tracing it, instead use the comment:
Lesson: Comments aid understanding. Since 13 is not divisible by
Make them count!
any integer in the range 3..12, isDivisible(13, 3, 13) must be false, and we’re done!
Sounds like that last step begs the question. Why doesn’t it?
Last modified: Sat Jan 22 20:02:28 2022
CS61B: Lecture #2 8
if ( ) return false;
else if (x % low == 0)
return true;
while ( ) { // if (x % low == 0)
return true;
low = ;
// or low += 1, or (yuch) low++
low >= high
returnisDivisible(x, ,high); }returnfalse;
isDivisible is tail recursive, and so creates an iterative process.
Traditional “Algol family” production languages have special syntax for iteration. Four equivalent versions of isDivisible:
low < high
while ( ) { if (x % k == 0)
return true;
r}eturn false;
Last modified: Sat Jan 22 20:02:28 2022
for( ; ; ){ if (x % k == 0)
return true; }
return false;
CS61B: Lecture #2 9
!(low >= high)
int k = low;
int k = low
Using Facts about Primes
A couple of obvious facts:
– k ≤ √N iff N/k ≥ √N, for N, k > 0.
– If k divides N then N/k divides N.
So how far do we really have to go to find a possible divisor for x?
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 10
Using Facts about Primes
A couple of obvious facts:
– k ≤ √N iff N/k ≥ √N, for N, k > 0.
– If k divides N then N/k divides N.
So how far do we really have to go to find a possible divisor for x?
Only up to and including √x.
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 11
Using Facts about Primes
A couple of obvious facts:
– k ≤ √N iff N/k ≥ √N, for N, k > 0.
– If k divides N then N/k divides N.
So how far do we really have to go to find a possible divisor for x?
Only up to and including √x. So, reimplement isPrime:
private static boolean isPrime(int x) { if (x <= 1)
return false;
return !isDivisible(x, 2, (int) Math.round(Math.sqrt(x))); // (int) ... here converts to an integer in the range
// −231..231 − 1 (type ‘int’) from one in the
// range −263..263 − 1 (type ‘long’).
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 12
Cautionary Aside: Floating Point
In the last slide, we used
(int) Math.round(Math.sqrt(x));
intending that this would check all values of k up to and including the
square root of x.
Since floating-point operations yield approximations to the corresponding mathematical operations, you might ask the following about Math.round(Math.sqrt(x)):
– Is it always at least ⌊√
x⌋? (⌊z⌋ means “the largest integer ≤ z.”)
x when x is a perfect square. If not, we might miss testing √
As it happens, the answer is “yes” for IEEE floating-point square roots.
Just an example of the sort of detail that must be checked in edge cases.
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 13
Final Task: printPrimes (Simplified)
/** Print all primes up to and including LIMIT. */
private static void printPrimes(int limit) {
Last modified: Sat Jan 22 20:02:28 2022 CS61B: Lecture #2 14
Simplified printPrimes Solution
/** Print all primes up to and including LIMIT. */
private static void printPrimes(int limit) { for (int p = 2; p <= limit; p += 1) {
if (isPrime(p)) { System.out.print(p + " ");
System.out.println();
Last modified: Sat Jan 22 20:02:28 2022
CS61B: Lecture #2 15
printPrimes (full version)
/** Print all primes up to and including LIMIT, 10 to * aline.*/
private static void printPrimes(int limit) { int np;
for (int p = 2; p <= limit; p += 1) {
if (isPrime(p)) { System.out.print(p + " "); np += 1;
if (np % 10 == 0)
System.out.println();
if (np % 10 != 0)
System.out.println();
Last modified: Sat Jan 22 20:02:28 2022
CS61B: Lecture #2 16
√Recreation
Prove that ⌊(2 + 3)n⌋ is odd for all integer n ≥ 0.
[Source: D. O. Shklarsky, N. N. Chentzov, I. M. Yaglom, The USSR Olympiad Problem Book, Dover ed. (1993), from the W. H. Freeman edition, 1962.]
Last modified: Mon Jan 24 00:22:33 2022 CS61B: Lecture #3 1
CS61B Lecture #3: Values and Containers
Labs are normally due at midnight Friday. Last week’s lab, however, is due this coming Friday at midnight.
Today. Simple classes. Scheme-like lists. Destructive vs. non-destructive operations. Models of memory.
Last modified: Mon Jan 24 00:22:33 2022 CS61B: Lecture #3 2
Values and Containers
Values are numbers, booleans, and pointers. Values never change. (So, for example, the assignment 3 = 2 would be invalid.)
3 ’a’ true
Simple containers contain values:
Examples: variables, fields, individual array elements, parameters. The contents of containers can change.
Last modified: Mon Jan 24 00:22:33 2022 CS61B: Lecture #3 3
Alternative Notation
Class Object
Array Object
012 42 17 9
Empty Object
Last modified: Mon Jan 24 00:22:33 2022
CS61B: Lecture #3 4
Structured Containers
Structured containers contain (0 or more) other containers:
Pointers (or references ) are values that reference (point to) containers. One particular pointer, called null, points to nothing.
In Java, structured containers contain only simple containers, but pointers allow us to build arbitrarily big or complex structures anyway.
Last modified: Mon Jan 24 00:22:33 2022
CS61B: Lecture #3 5
Containers in Java
Containers may be named or anonymous.
In Java, all simple containers are named, all structured containers are anonymous, and pointers point only to structured containers. (Therefore, structured containers contain only simple containers).
named simple containers (fields) within structured containers
ht ht p: 3 7
simple container structured containers (local variable) (anonymous)
In Java, assignment copies values into simple containers. Exactly like Scheme and Python!
(Python also has slice assignment, as in x[3:7]=..., which is shorthand for something else entirely.)
Last modified: Mon Jan 24 00:22:33 2022 CS61B: Lecture #3 6
Defining New Types of Object
Class declarations introduce new types of objects. Example: list of integers:
public class IntList {
// Constructor function (used to initialize new object) /** List cell containing (HEAD, TAIL). */
public IntList(int head, IntList tail) {
this.head = head; this.tail = tail; }
// Names of simple containers (fields)
// WARNING: public instance variables usually bad style! public int head;
public IntList tail;
Last modified: Mon Jan 24 00:22:33 2022 CS61B: Lecture #3 7
IntList Q, L;
L: 3 42 Q:
L: 3 43 Q:
Primitive Operations
L = new IntList(3, null); Q = L;
Q = new IntList(42, null); L.tail = Q;
L.tail.head += 1;
// Now Q.head == 43
// and L.tail.head == 43
Last modified: Mon Jan 24 00:22:33 2022
CS61B: Lecture #3 8
Side Excursion: Another Way to View Pointers
Some folks fi
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com