Lecture 1

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 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 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:

      rgb

      We would get this shade of yellow:

      rgb-Color

  • 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:

      emojipixels

    • 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.

    efficiency

  • 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.