CS50’s Computer Science for Lawyers

OpenCourseWare

Donate (https://cs50.harvard.edu/donate)

Doug Lloyd (http://douglloyd.com/), J.D.

lloyd@cs50.harvard.edu

David J. Malan (https://cs.harvard.edu/malan/)

malan@harvard.edu
Facebook (https://www.facebook.com/dmalan) GitHub (https://github.com/dmalan) Instagram
(https://www.instagram.com/davidjmalan/) LinkedIn (https://www.linkedin.com/in/malan/)
Reddit (https://www.reddit.com/user/davidjmalan) Threads
(https://www.threads.net/@davidjmalan) Twitter (https://twitter.com/davidjmalan)

Lecture 1
Overview
Representing Inputs and Outputs
Numbers
Letters
Media
Algorithms
Phone Book Searching
Efficiency
Pseudocode
Abstraction

Overview
Computational thinking is thinking algorithmically, taking inputs to a problem and carefully going step
by step to produce an output.

What is computer science? Fundamentally, computer science is problem-solving. We have some input
and, via some process, generate some sort of output.

Representing Inputs and Outputs

Numbers
We might use our fingers and toes to count, holding up 1 finger for 1 item, 2 fingers for 2 items, etc.
This is a representation in the unary system.
 We might use a system that we’ve grown up with, the decimal system, where we use digits from 0
through 9.
For 123 , we know that that the 3 is in the ones place, the 2 is in the tens place, and the 1 is in
the hundreds place.

100s 10s 1s

1 2 3

This gives us (3 × 1) + (2 × 10) + (1 × 100) = 123.

Note that in the decimal system, we use powers of 10.
Computers use a binary representation.
In binary, we only use 0 or 1, or if thinking of a switch, off and on.
In the binary system, we use powers of 2.
For 110 , we know that 0 is in the ones place, 1 is in the twos place, and 1 is in the fours place.

4s 2s 1s

1 1 0

This gives us (0 × 1) + (1 × 2) + (1 × 4) = 6.

If we wanted to represent 8 in binary, we would need another digit, or another switch.

8s 4s 2s 1s

1 0 0 0

These digits are also called bits, and 8 bits make up 1 byte.
This gives us (0 × 1) + (0 × 2) + (0 × 4) + (1 × 8) = 8.
Computers today have millions of these switches (also called transistors), but to represent larger
and larger values and do more and more computationally, it will require more physical storage.

Letters
ASCII (https://en.wikipedia.org/wiki/ASCII) is a standardized system created by humans mapping from
numbers to letters.
The decimal number 65 maps to the letter A, 66 maps to B, and so on.
The decimal number 97 maps to lowercase a, 98 maps to b, and so on.
ASCII tends to use 7 or 8 bits total, so there are only 128 or 256 possible representations.
How these bits are interpreted (as letters, as numbers, or more) depends on the context.
Unicode (https://en.wikipedia.org/wiki/Unicode) is another system that additionally includes other
texts we might see, such as letters with accents, certain foreign punctuation, or even emojis.
has a decimal representation of 128514.

For example, we might receive a message that says 72 73 33 . Accounting for ASCII mappings, we get
 72 73 33

H I !

In this example, note that the abstraction greatly benefits us, as viewing HI! is much easier than
viewing a series of 0’s and 1’s.
Abstraction allows us to think about a problem at a higher level rather than at the lowest level that it
is implemented in.

Media
RGB allows us to represent color.
We use 8 bits to represent red, 8 bits to represent green, and 8 bits to represent blue.
To select a color we would like, we just pick how much red we want, how much green we want,
and how much blue we want.

For example, if we have this set of bits:

We would get this shade of yellow:

Any image or photo on a screen is just a pattern of pixels, and every pixel has 24 bits representing its
particular color.

We can see the individual pixels if we zoom in on this emoji:

We might notice that images we download have sizes of kilobytes (thousands of bytes) or
megabytes (millions of bytes).
A video is a series of images that is being presented so quickly, perhaps 24 to 30 frames per second,
that it presents an illusion of movement.
In this case, we have many levels of abstraction.
A video is a collection of images.
An image is a collection of pixels.
A pixel is some number of bits representing some amount of red, green, and blue.
A bit is a digital representation of something being present, like electricity or not, or an on switch
or off.
Algorithms
We can now represent inputs and outputs. Now, we’ll need a process by which we can generate this
output.
Algorithms are step by step instructions for solving a problem.

Phone Book Searching

Suppose we wanted to find Mike Smith in a phone book. How might we find his number?

We might search through the phone book person by person, flipping page by page, until we either find
Mike Smith or reach the end of the phone book, meaning Mike Smith isn’t in the book. For a phone
book with 1000 pages, if Mike isn’t in the book (worst case), we would have to search 1000 pages.

We might search through the phone book flipping two pages at once. If we go too far, then we’ll have
to flip back one page to check that page. For a phone book with 1000 pages, if Mike isn’t in the book,
we would have to search 500 pages.

We might also flip to the middle of the phone book and note that we’re in the M section. We know that
Mike Smith must come afterwards, so we can now ignore the first half of the phone book. Repeating
this strategy, for a phone book with 1000 pages, if Mike isn’t in the book, we would only need to search
approximately 10 pages.

Efficiency
We can visualize effiencies of algorithms on a plot.

Let n be the number of pages in the phone book.

For our first algorithm, our searching time increases linearly with the size of the phone book.
For our second algorithm, we search half as many pages, so our searching time is still linear, but less
steep.
 For our final algorithm, our search time is logarithmic with respect to the number of pages. As the size
of the phone book increases, our search time increases at a slower rate.
Concretely, if our phone book went from 1000 pages to 2000 pages, we would only need to search
1 additional page.

Pseudocode
Pseudocode generally involves using concise phrases in English to describe an algorithm step by step
so everyone can understand the algorithm.

For our phone book searching, we might have the following pseudocode:

1 pick up phone book

2 open to middle of phone book
3 look at page
4 if Smith is on page
5 call Mike
6 else if Smith is earlier in book
7 open to middle of left half of book
8 go back to line 3
9 else if Smith is later in book
10 open to middle of right half of book
11 go back to line 3
12 else
13 quit

Some of these lines start with verbs, or actions. We’ll start calling these functions. These statements
tell the human or computer what to do.

1 pick up phone book

2 open to middle of phone book
3 look at page
4 if Smith is on page
5 call Mike
6 else if Smith is earlier in book
7 open to middle of left half of book
8 go back to line 3
9 else if Smith is later in book
10 open to middle of right half of book
11 go back to line 3
12 else
13 quit

Some of these lines begin with conditions, or forks in the road. We make a decision on which way to
go.

1 pick up phone book

2 open to middle of phone book
3 look at page
4 if Smith is on page
5 call Mike
6 else if Smith is earlier in book
7 open to middle of left half of book
8 go back to line 3
 9 else if Smith is later in book
10 open to middle of right half of book
11 go back to line 3
12 else
13 quit

To decide which way to go, we need Boolean expressions. These expressions have yes/no or true/false
answers.

1 pick up phone book

2 open to middle of phone book
3 look at page
4 if Smith is on page
5 call Mike
6 else if Smith is earlier in book
7 open to middle of left half of book
8 go back to line 3
9 else if Smith is later in book
10 open to middle of right half of book
11 go back to line 3
12 else
13 quit

We might also have loops, or cycles that get us to do something again and again until some condition
is no longer true.

1 pick up phone book

2 open to middle of phone book
3 look at page
4 if Smith is on page
5 call Mike
6 else if Smith is earlier in book
7 open to middle of left half of book
8 go back to line 3
9 else if Smith is later in book
10 open to middle of right half of book
11 go back to line 3
12 else
13 quit

Abstraction
Abstraction is a technique where we can think about a problem more usefully at a higher level as
opposed to the lowest level that it is implemented in.
Choosing an appropriate level of abstraction is important – too much can lead to ambiguity and too
little can become difficult to understand or tedious.
In an ideal world, only one human would need to write code at a low level (like drawing a square or
circle), and the rest of us can build on top of that (using these pre-made squares and circles), coding at
a higher level.