EBoard 12: Review 1

Approximate overview

• Administrative stuff [a long time]
• string->integer
• The tracing problem from the sample SoLA
• SoLA policies, reviewed
• Q&A

Administrative stuff

Introductory Notes

• Happy Wednesday!
• Please use the random seating cards and grab a pen.
• It’s Pop Quiz Day! (No worries; it only grants you tokens.)

Pop Quiz

A map of our classroom, more or less.

                   1  2  3  4
   +-+-----+-----+-----+-----+-+
 0 | |     |     |     |     |o|            40
   +-+-----+-----+-----+-----+-+            39
       5  6  7  8  9 10 11 12
   
      13 14 15 16 17 18 19 20
     +-----+-----+-----+-----+
S    |     |     |     |     |              38
C    +-----+-----+-----+-----+              37
R     21 22 23 24 25 26 27 28
E  
E   29 30 31 32       33 34 35 36          
N  +-----+-----+-----+-----+-----+-----+
   |     |     |     |     |     |     |

Upcoming activities

Events

• Convocation Thursday at 11am. Jarvis Givens on The Fugitive Life of Black Teaching: A History of Pedagogy and Power. Online and HSSC A1231. (I don’t know where you find the online link.)
• Writers at Grinnell Roundtable Thursday at 4:15 pm. HSSC S1325. https://www.grinnell.edu/news/writersgrinnell-welcomes-santiago-jose-sanchez-larissa-pham
• Homecoming parade Thursday at 5:30pm. Downtown Grinnell.
• Writers@Grinnell reading Thursday at 8:00 pm. HSSC S1325. See above.

Other good things

• Women’s soccer today at home. 4:30 p.m.
• Women’s volleyball Friday at home. 7:00 p.m.
• Women’s soccer Saturday at home. 11:00 a.m.
• Women’s volleyball Saturday at home. 1:00 p.m.
• Men’s soccer Saturday at home. 1:30 p.m.
• Have fun with family at family weekend.
  • Apologies to those whose families could not attend or who do not have good relationships with their families.

Upcoming work

• SoLA 1 starts today at 2:30 p.m., due Thursday at 10:30 p.m..
• No readings for Friday.
• Monday’s lab writeup is due next Monday.
• Mini-Project 3 is due next Thursday at 10:30 p.m.
  • I’ve add MPs to the class web menu.
  • We’ll walk through MP3

Doing readings

• Goal: <= 60min.
• General reading strategies.
  • Take notes. By hand. Separately. (Summarize.)
  • Don’t rely on highlighters as your primary mechanism of learning; highlighters exist to help you find things later.
  • Consider using colors to help you read/review your notes (e.g., procedures in blue).
• Applying general reading strategies to CS readings.
  • Write down procedures.
  • Take note of (or write down) the small procedures we write in the reading.
    • Understanding the code helps you understand goals.
    • Problem solving often involves “Have I solved (or seen) something similar before.”
• CS-specific reading strategies.
  • You can try to run the code. It should work most of the time. If not, post a question or check with evening tutors or both.
  • You can try variants of the code.
• Other notes on notes
  • Some folks find retyping their notes makes it easier to find things.
  • Take notes in class, too (even though Sam has the eboard) and consider rewriting afterwards.

Other notes on learning CS

• About negative feedback
  • Embrace the “it’s okay to try and it’s wrong”
  • It’s easier to know that you are wrong in CS.
• Testing your learning
  • Give yourself small problems and see how you do.
• Decomposition helps. Smaller pieces give you rewards.
  • “One brick at a time.”
• Work with other people (except on SoLAs)
  • I recommend you do your work in 3813 and 3815.
  • Shared suffering is easier to deal with.
  • There are people to ask for help, both formally.

Converting strings to integers

An exercise in decomposition, alternate thinking, and more.

I have to convert “4251” into the number 4251.

How do I do that by hand?

• Conceptually, 4251 (“four thousand two hundred fifty one”) is
  • Four one thosands
  • Two one hundreds
  • Five tens
  • One one
• What’s the pattern?
  • The rightmost digit gets multiplied by one (10^0)
  • The next digit gets multiplied by ten (10^1)
  • The next digit gets multiplied by one hundred (10^2)
  • The next digit gets multiplied by one thousand (10^3)
  • The next digit gets multiplied by ten thousand (10^4)
  • …

Things I may have to do

• Use the index of each digit, starting from the right
• We’ll say that the index of the rightmost digit is 0.
• So the index of the next-to-rightmost digit is 1.
• And so on and so forth.
• We multiply each digit by 10^index
• And then add them up.
• We can use length.

How do I break that apart?

• Compute 10^digit.
• Get the digits in the right order (reverse)
• Convert the string digits into actual digits "5" (or #\5) -> 5
• “Add things” (+)
• “Multiply” (*)

(define digit->integer
  (lambda (ch)
    (- (char->integer ch) (char->integer #\0))))

There are three ways I know of to get individual digits.

• I can use list-ref (gives me a character)
• I can use substring (gives me a string)
• I can use string->list

To use list-ref or substring, we’ll need a way to loop (in Scheme, the looping mechanism is called “recursion” and you’ll start learning it in two weeks).

So we’ll use string->list. Let’s check it out.

> (string->list "4251")
'(#\4 #\2 #\5 #\1)

For normal indexing, that’s backwards. Let’s reverse it.

> (reverse (string->list "4251"))
'(#\1 #\5 #\2 #\4)
> (list-ref (reverse (string->list "4251")) 0)
#\1
> (list-ref (reverse (string->list "4251")) 1)
#\5
> (list-ref (reverse (string->list "4251")) 2)
#\2
> (list-ref (reverse (string->list "4251")) 4)
. . list-ref: index too large for list
  index: 4
  in: '(#\1 #\5 #\2 #\4)
> (list-ref (reverse (string->list "4251")) 3)
#\4

I have to convert each of those to a digit. map

> (map digit->integer (reverse (string->list "4251")))
'(1 5 2 4)

Now I need powers of ten for the multiplication.

(define ten-to-the
  (lambda (n)
    (expt 10 n)))

Let’s check it

> (ten-to-the 0)
1
> (ten-to-the 1)
10
> (ten-to-the 2)
100
> (ten-to-the 3)
1000
> (ten-to-the 4)
10000

Yay!

But I need those in a list. For this case, I want the list '(1 10 100 1000).

I use map to make lists.

> (map ten-to-the '(0 1 2 3))
'(1 10 100 1000)

I have the digits. I have the multipliers. I still don’t know how to do a loop. But I do know how to work with lists. map.

> (map * '(1 5 2 4) '(1 10 100 1000))
'(1 50 200 4000)

How did I compute those?

> (map *
       (reverse (map digit->integer (string->list "4251")))
       (map ten-to-the '(0 1 2 3)))
'(1 50 200 4000)

Now I need to add them up. map?

> (map + '(1 50 200 4000))
'(1 50 200 4000)

I’m not trying to add two lists together. I’m trying to combine all of the elements of a list into a single value. Not map (list to a list). Is it filter? Also a list to a list. reduce or apply. [That’s an important thing to think about.]

> (reduce + '(1 50 200 4000))
4251

Yay! Get all of the code there.

> (reduce + (map *
                 (reverse (map digit->integer (string->list "4251")))
                 (map ten-to-the '(0 1 2 3))))
4251

Now we’re ready to generalize.

(define digits->integer
  (lambda (str)
    (reduce + (map *
                 (reverse (map digit->integer (string->list str)))
                 (map ten-to-the '(0 1 2 3))))))

Need to document

;;; (digits->integer str) -> integer?
;;;   str : string? (consisting only of digits)
;;; Convert a string to the corresponding integer.

Maybe I should try it on numbers that don’t have four digits.

> (digits->integer "123")
. . map: all lists must have same size
  first list length: 3
  other list length: 4
  procedure: #<procedure:*>

Whoops! I can’t use '(0 1 2 3). I can use the range function.

> (range 0 4)
'(0 1 2 3)

(define digits->integer
  (lambda (str)
    (reduce + (map *
                 (reverse (map digit->integer (string->list str)))
                 (map ten-to-the (range (string-length str)))))))

> (digits->integer "123")
123
> (digits->integer "21334623412343212")
21334623412343212

The mentors say it looks good.

The tracing problem

Some definitions

(define f 
  (lambda (x y)
    (string-append x "-" (string-reverse x))))

(define g
  (lambda (x y)
    (string-append (f x x) " " (f y x))))

(define h 
  (lambda (x y)
    (string-append (g x y) "&" (g y x))))

Tracing policies

And the trace

    h("foo" "bar")
-->

SoLA policies reminder and demo

• For each problem, you get an hour from the time you start.
• Unless something says “Document”, you do not have to document.
• You should check your answer in DrRacket.
• After the hour is over, you can no longer resubmit.
• There is a “late submit” feature enabled. That is only avaiable to those who make special arrangements (e.g., because of illness).
• There are seven SoLA problems.
• You can use DrRacket, the course Web site, your notes, and the DrRacket site.
• You cannot use other people, random Web pages, etc.
• If I find that you post your answers to social media or elsewhere, I will report you to CAS.
• Note: I trust you on these things. Please don’t betray my trust.

Questions and Answers

When will we get MP2 back?

Soon, I expect.