Introduction

1. Who I am
2. Review of course web pages, including first reading assignment (for quiz!), first CodeLab assignment, first program.
3. Modes of Learning: We remember:
   

   10% of what we read (e.g. our text book)
   20% of what we hear (eyes closed, listening in class)
   30% of what we see (overhead or chalkboard)
   50% of what we see and hear (lecture w/board
   70% of what we discuss with others (class discussion, lab groups)
   80% of what we experience personally (programming assignments)
   90% of what we teach to someone else (lab groups)
                     -William Glasser

   How much do you want to remember?

   
   

What's the Point of Learning CS, anyway?

Computer are increasingly being used to do things people used to do, freeing up people for other tasks. (e.g. measuring, counting, translating, communicating, conveying.)

Consider the following example (taken from Harvard's course cs50.) How can we efficiently count students in the room?

• Simple way: Have one person stand in front of the lecture hall and point to each student once,saying “1, 2, 3, …” until each student has been counted.
• This will take as many steps as there are students, say, 64
• We can do better by counting in twos in just 32 steps. But even if we count by threes or fours,the number of steps will always be proportional to the number of students
• Can we employ an algorithm that increases in speed as we increase the number of students?

We can count the number of students in the room by having each individual do the following:

1. Stand up
2. Assign yourself the number 1
3. Find someone that is standing up.
4. Add your number to that person’s number. The total is your new number.
5. One of you sit down.
6. If you are still standing, go back to step 3.
7. Algorithm finishes when there is one person standing. Her number is the number of students in the class.

Employing this algorithm, we might find that there are about 64 students in the room. How efficient is this?

1. If there were 2 people, it would take one iteration of the above algorithm to count
2. If there were 4 people, it would take two iterations
3. Similarly, for n people, it would take log2n iterations
4. For 64 people, it should take 6 iterations. Another way to think about it is that each “round” cuts the number of students still standing in half. So if there are about 64 students, it will require 6 rounds because we can halve 64 six times.
5. If we graph this, we see that it takes a relatively long time for small numbers of students, but as the number of students grows, the algorithm seems to speed up
6. For 4 billion students, it would take just 32 iterations!
7. Graphing this looks like: