CSC 151.01, Class 13: Discussion of exam 1
Overview
- Preliminaries
- Notes and news
- Upcoming work
- Extra credit
- Questions
- Common issues
- Individual problems
Preliminaries
News / Etc.
- New partners!
- Exams to be returned later this week.
- I worked for about sixteen hours this weekend, but that was not enough time to make significant progress on grading.
- Happy presidents’ day!
- Congrats to our excellent swimmer
- We should do a study of how people follow the card directions in this classroom.
Upcoming work
- No lab writeup!
- Reading for Wednesday
- Homework 4 due Tuesday
- Flash Cards for Week 5 due Wednesday at 5pm.
Extra credit (Academic/Artistic)
- Visit the two exhibits at the Faulconer Gallery.
- Urban Education Forum Thursday.
- noon: “School segregation in the 21st century”, talk by Rachel Moskowitz ’06, JRC 101
- 4 PM: Teacher alumni Panel, Emily Kugisaki ’09, Anna McNulty Taylor ’06, and Erin Whalen ’12, JRC 101
- 7:30 PM: “Focusing on the role of inequality and segregation in public education”, talk by Nikole Hannah-Jones, Harris Center cinema
Extra credit (Peer)
Extra credit (Recurring peer)
- Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music. (Up to two units of extra credit.)
- Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.
Extra credit (Misc)
Other good things
Questions
- How will you return the exam?
- Via email, with marks on it.
Common issues
Some issues with formatting.
- General form is define on one line, lambda + params on next, and body after that
- Parameters should be arranged arranged so that it’s easy to figure out which procedure they belong to.
Not
(define fun (lambda (params)
...))
But rather
(define fun
(lambda (params)
...))
Remembers: In 6P’s, the Parameters and Produces sections should just be Name, Type
- Name allow us to talk about the parameters or result
- Type helps us understand restrictions
There were three really hard questions; there was a lot of reliance on sectioning.
Problem 2: Substring sorting
Write the documentation first.
;;; Procedure:
;;; sort-by-substring
;;; Parameters:
;;; los, a list of strings
;;; start, an exact non-negative integer
;;; finish, an exact non-negative integer
;;; Purpose:
;;; Sort los, using the substring of each string taken from positions
;;; start to finish, inclusive, as the mechanism for ordering.
;;; Produces:
;;; sorted, a list of strings
;;; Preconditions:
;;; * start <= finish
;;; * start and finish have to be valid indices into each string in
;;; the list of strings
;;; Postconditions:
;;; * sorted is sorted by substring. For all elements in the
;;; list, the substring of each element is less than or equal to the
;;; the substring of the subsequent element. For all "reasonable" i
;;; (string<=? (substring (list-ref sorted i) start (+ 1 finish))
;;; (substring (list-ref sorted (+ i 1)) start (+ 1 finish)))
;;; * sorted must have the same elements as los, just (potentially) in a
;;; a different order; strings are neither added, nor removed, nor changed.
;;; "sorted is a permutation of los".
Question: Can a lazy programmer meet the “sorted is sorted by substring” postcondition without achieving the real goals of the procedure?
- Worried about the lazy programmer adding or dropping things so that the result has things not in the original list.
- Worried that the strings change. For example, the original might be
‘(“alpha” “beta” “gamma” “delta”)
and we sort by characters 2 to 2, the result is’(“xxlxx” “xxmxx “xxpxx” “xxtx”)`.
(define sort-by-substring
(lambda (los start finish)
null))
(define sort-by-substring
(lambda (los start finish)
(list "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
"ccccccccccccccccccccccccccccccccccccccccccccccccc")))
- Note: We’ve chosen to support sorting the empty list.
Alternative preconditions
;;; (< finish (reduce min (map string-length los)))
An initial solution
(define sort-by-substring
(lambda (los start finish)
(sort los
(lambda (a b)
(string<=? (substring a start (+ 1 finish))
(substring b start (+ 1 finish)))))))
What? You can write a lambda within a lambda?
Yes, you can use a lambda wherever a procedure is required.
;;; Procedure:
;;; compare-by-substring<=?
;;; Parameters:
;;; a, a string
;;; b, a string
;;; start, a non-negative exact integer
;;; finish, a non-negative exact integer
;;; Purpose:
;;; Compare a and b using the substrings between start and finish,
;;; inclusive.
;;; Produces:
;;; comes-before?, a Boolean
(define compare-by-substring<=?
(lambda (a b start finish)
(string<=? (substring a start (+ 1 finish))
(substring b start (+ 1 finish)))))
(define sort-by-substring
(lambda (los start finish)
(sort los (section compare-by-substring<=? <> <> start finish))))
Observation: sort requires that its last parameter be a procedure of
two parameters that is used to tell whether the first can come before
the second.
How does sort work?
- We’ll make up an algorithm.
- Step through the list, comparing neighboring elements.
- If two elements are out of order, swap them, then go back to the beginning
- Stop when you hit the end of the list.
- This approach is independent of the comparator. Hence, we have to provide it with one.
Detour: Section
We will often be in a situation in which we have a procedure we want to
use, and we also need a procedure (e.g., map, reduce, sort, filter),
but the procedure we have has too many parameters.
E.g., we want to add 2 to each element of a list.
(map ? (list 1 2 3 4))
+ adds, but it usually takes two parameters. I can write (section + <> 2)
(map (section + <> 2) (list 1 2 3 4))
I could also create a second list.
(map + (list 1 2 3 4) (make-list 4 2))
We try to avoid calls to make-list
Back to our example above. We want to sort. We need a comparator that
takes two parameters (a and b). We had a comparator that takes four
parameters (a, b, start, and finish). So we use section to fill in
two of them.
(section big-comparator <> <> start finish)
Back to the main sorting problem
We had an approach from HW3.
- Shove the substring on the front of the string.
- Sort
- Remove the substrings you added
;;; Procedure:
;;; prepend-substring
;;; Parameters:
;;; str, a string
;;; start, a non-negative exact integer
;;; finish, a non-negative exact integer
;;; Purpose:
;;; Shove the substring on the front of str.
;;; Produces:
;;; newstr, a string
;;; Preconditions:
;;; start <= finish < (length str)
;;; Postconditions:
;;; * (substring newstr 0 (+ 1 (- finish start))) =
;;; (substring str start (+ 1 finish))
;;; * (substring newstr (+ 1 (- finish start))) = str
(define prepend-substring
(lambda (str start finish)
(string-append (substring str start (+ 1 finish))
str)))
(define sort-by-substring
(lambda (los start finish)
(map (section substring <> (+ 1 (- finish start)))
(sort (map (section prepend-substring <> start finish)
los)
string<=?))))
Problem 6: Filtering
Problem: Given the list of classes, and a range of sizes, find all the classes between those sizes.
- Put the size at the front of each entry so that we can sort.
- Add an entry with the smallest size. [skip for now]
- Add an entry with the largest size. [skip for now]
- Sort in increasing order.
- Find the index of the smallest size.
- Drop to that index.
- Sort in decreasing order.
- Find the index of the smallest size.
- Drop to that index.
- Reorder by capacity.
What happens if the class size does not exist?
- We have a strategy for “remove negative” that is similar and that handled that problem.
- Add 0 to the list
- Sort by number
- Find the index of 0
- Remove up to that index.
Step 1: Add the size to the front
(define extract-courses-by-size
(lambda (list-of-courses smallest largest)
(map add-size-to-front list-of-courses)))
Step 2: Sort
(define extract-courses-by-size
(lambda (list-of-courses smallest largest)
(sort (map add-size-to-front list-of-courses)
string<=?)))
Step 3: Remove up to
…