Warning! You are being recorded and transcribed, provided the technology is working correctly.
Approximate optimistic overview
Scholarly
Artistic
Multicultural
Peer
Musical, theatric, sporting, and academic events involving this section’s students are welcome.
Wellness
Misc
These do not earn tokens, but are worth your consideration.
When will the MP redos be graded?
Most are graded, but we’re waiting on one grader.
MP7 should be graded by Wednesday night.
I’ve missed way too many reading responses, labs, and/or metacognitive reflections. Can you just waive the penalty for missing those things?
Each of these is important to your learning in its own way.
Reading responses ensure that you’re ready for the lab. At least they are supposed to.
Metacognitive reflections help you develop as a learner.
Labs help you learn the material. They may even be the primary way in which you learn the material.
I will, however, cap the grade decrease at one letter grade provided (a) you turn in the post-reflection for MP9, (b) you turn in the post-reflection for SoLA 4, (c) set up an appointment with academic advising to discuss strategies for getting regular work done on time, and (d) send me a message describing one or two strategies you’ve decided upon.
Also: I will not be charging tokens for late reading responses, lab writeups, or metacognitive reflections.
I won’t be in class on Friday. What should I do?
If you may be unable to make it to class on Friday (e.g., because your team is traveling), please plan to come early on Wednesday (Section 1) or stay late on Wednesday (Sections 2 and 3).
Does only one team member submit the MP9?
Yes, only one member should submit MP9.
TPS
The study of algorithms and (using math) (computers) data structures
Algorithms are: Instructions for processing data in order to generate a result. (Sets of instructions for solving problems.)
Data structures: A way to organize information. Maybe images. Dictionaries/hashes let us organize information by keys. Trees let us organize hierarchical information. BSTs organize information for searching. Lists and vectors are two of the central mechanisms for organizing info.
What problems do computer scientists solve? It depends. Many occur as part of “everyday work”.
We also look for generalizable/generalized problems.
Searching! (BSTs and binary search both provide fastish searching.)
To do binary search, you need the data organized in a particular way. You need them in order from smallest to largest.
We use the term “sort” to mean “put in order from smallest to largest or from largest to smallest”.
TPS: Design a sorting algorithm
Inputs: A list or vector of values + a way to compare any two values
Output: The same group of values, now in order. (for lists, we’ll output a new list; for vectors, we’ll change them in place)
Describe how to sort a list or vector. (In English; assume good will on the part of the enactor.)
(my-sort lst less-equal?) or (my-sort! vec less-equal?).
TPS: What’s the running time? Is it constant? Linear? Quadratic? (Assume the worst case.)
n*n (also known as n-squared) time doing this.TPS: Write this in Scheme
(define insertion-sort
(lambda (lst less-equal?)
(insertion-sort/helper lst null less-equal?)))
(define insertion-sort/helper
(lambda (remaining so-far less-equal?)
(if (null? remaining)
so-far
(insertion-sort/helper (cdr remaining)
(insert (car remaining) so-far less-equal?)
less-equal?))))
;;; (insert val lst less-equal?) -> list?
;;; val : any?
;;; lst : list? (sorted?)
;;; less-equal? : binary predicate (applicable to val and elements of lst)
;;; Put val at the appropriate place in lst.
(define insert
(lambda (val lst less-equal?)
(cond
[(null? lst)
(list val)]
[(less-equal? val (car lst))
(cons val lst)]
[else
(cons (car lst)
(insert val (cdr lst) less-equal?))])))
Or
(define insert
(lambda (val lst less-equal?)
(if (or (null? lst)
(less-equal? val (car lst)))
(cons val lst)
(cons (car lst)
(insert val (cdr lst) less-equal?)))))
First we insert one value into an empty list, then one value into a list of one element, then one value into a list of two elements, …
To sort ten elements, that’s about 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 total steps. 55.
To sort twenty elements, that’s 1 + 2 + 3 … + 20, which is 210. We’ve doubled the number of elements, and almost quadrupled the number of steps.
The magic formula for 1 + 2 + 3 + … + n. \(n*(n+1)/2\)
TPS: Document
;;; (sort ???) -> ???