My Web Markups - Kev Peng
Your procedure should work correctly if one or both of the words has fewer than three characters
CSC 151-02 (2021S2) - Mini-Project 5
This second kind of recursion is comparatively powerful. In essence, by choosing one subtree or another, we get to “throw away” half of the tree. That makes tree procedures that use this model relatively fast.
;;; When we say that bst is a binary search tree, we mean it is a binary ;;; tree with the property that the left subtree contains smaller values ;;; the right subtree contains larger values, and the subtrees are both ;;; binary search trees.
As its name suggests, a decision tree represents a series of decisions, such as yes/no questions. We might have the left branch correspond to a “yes” answer and the right branch correspond to a “no” answer.
(define binary-tree-contains? (lambda (tree val) (and (not (empty-tree? tree)) (or (equal? (contents tree) val) (binary-tree-contains? (left tree) val) (binary-tree-contains? (right tree) val)))))
a base case when the tree is empty
A binary tree, in comparison, is either the (a) empty tree or (b) a combination of a value and two subtrees. If it’s Hence, we will need to recurse on both halves, as well as look at the value in the node.
Since the cdr of a list is itself a list, in makes sense to recurse on the cdr.
CSC 151-02 (2021S2) - Tree recursion
In this reading, we’ve introduced the recursive definition of a binary tree as well as associated functions for creating, manipulating, and displaying binary trees. You should study these implementations because they are excellent examples of advanced applications of lists and pairs!
it is much more easier and readable, for example, to call binary-tree-right than caddr.
However, even though a tree is really a list behind the scenes, we want to avoid thinking about these implementation details when writing tree code. Therefore, we’ll define empty-tree and empty-tree? to be aliases for null and null? which hides the fact that we implement trees as lists.
We always have three elements, even though there are sometimes one or zero subtrees. This keeps the structure of the tree uniform so we can operate it in the say way irrespective of the number of subtrees at each node.
Putting all of this together, we can represent a tree as follows: The empty tree is null. The non-empty tree (a node) is a list of three values, (v l r): v, the value at the node, l, the left subtree, and r, the right subtree.
the “tail” of a tree will be a pair of subtrees instead of a single subtree!
Note that the only difference between a list and a tree is that a list can only have one sublist whereas a binary tree can have up to two subtrees.
Non-empty where it contains a datum and one or more children that are, themselves, trees.
we represent hierarchies using a data structure called a tree
the motivation behind the study of data structures which allow us to organize our data in various ways
take advantage of the structure of a data type, here a list, to make defining operations easier as well as more efficient
aliases or alternative names for car and last
In Scheme and Racket, you build lists with null (empty list) and cons (join a head and tail). You deconstruct lists with null? (check for empty list), car (grab the head), and cdr. Every other list operation we use can be built from those basics.
CSC 151-02 (2021S2) - Trees
change someone’s phone number
you could make a directory a vector of four hash tables
if you ask it nicely
(hash-has-key? table key)
(hash-set! table key value)
(hash-ref table key)
we look up values by keys
we add key/value pairs
we create them
its purpose is to store key/value pairs
The type is named “hash table”
What is its name? What is its purpose? How do I express values in the type? How does DrRacket display values in the type? What procedures are available for working with the type?
But you should remember that hash tables are just one way to implement dictionaries.
In referring to these kinds of structures, computer scientists often call the thing used to look up information the key and the associated information the value.
CSC 151-02 (2021S2) - Dictionaries, maps, and hash tables
relative velocity between the surfaces provides insufficient time for additional cold welding to occur
some abrasion continues to occur, but at a much lower level than during static friction
both adhesion and abrasion of the contacting surfaces.
must be broken or plastically deformed before the surfaces can move.
the surfaces will interlock
Before the surfaces can move relative to each other, the bonds that cause this adhesion must be broken.
This extreme pressure allows adhesion to occur between the surfaces, via a process known as cold welding,
the two most widely-accepted theories behind static friction have to do with the microscopic roughness of surfaces.
Why is static friction greater than kinetic friction?
We also typically precompute a stopping point so that we don’t have to recompute it for each pass through the helper.
As the previous examples suggested, recursion over vectors is relatively straightforward, but usually requires that we have a helper procedure that includes additional parameters - the current position in the vector.
The vector-fill! procedure takes two arguments, the first of which must be a vector. It changes the state of that vector, replacing each of the elements it formerly contained with the second argument.
The mutator vector-set! takes three arguments – a vector vec, a natural number k (which must be less than the length of vec), and a Scheme value obj – and replaces the element of vec that is currently in the position indicated by k with obj. This changes the state of the vector irreversibly; there is no way to find out what used to be in that position after it has been replaced.
All of the previous procedures look a lot like list procedures, except that many are more efficient (e.g., vector? and vector-length take a constant number of steps; list? takes a number of steps proportional to the the length of the list and list-ref takes a number of steps proportional to the index).
The second argument is optional; if you omit it, the value that initially occupies each of the positions in the array is left unspecified. Various implementations of Scheme have different ways of filling them up, so you should omit the second argument of make-vector only when you intend to replace the contents of the vector right away.
but with a preceding pound sign, #
The particular values that a vector contains at some particular moment constitute its state.
Unfortunately, list-ref works by cdr’ing down the list.
vectors are indexed and vectors are mutable.
CSC 151-02 (2021S2) - Vectors
Every pair has exactly two components, and it is always valid to take the car and the cdr of a pair. So the base case for a pair recursion is just any value that is not itself a pair.
There is no such thing as an empty pair analogous to an empty list.
If we have a pair structure that is constructed by repeated invocations of cons, starting from constituents of some simple type such as numbers or strings, we call such a structure a tree
not all pairs are lists
all lists are pairs
The distinction is that lists always end in null
The car and cdr procedures can be used to recover the halves of one of these improper lists:
a cons cell or a pair
Symbol are atomic. Unlike strings (which symbols seem to resemble), symbols do not support procedures, like string-ref or substring, that extract some part of the symbol.
CSC 151-02 (2021S2) - Pairs and pair structures
gives the Dale-Chall score for the word
computes the various aspects of the string (number of words, number of difficult words, number of sentences)
if the percentage of difficult words is above 5%, then add 3.6365 to the score.
Consider using RackUnit to test your code
Use local bindings (let and let*)
Every procedure should have documentation
CSC 151-02 (2021S2) - Mini-Project 3
In both cases, the empty list should return #t.
Every procedure (not necessairly helpers in this case) should inlcude testing
list recursion, numeric recursion, tail recursion, and letrec
CSC 151-02 (2021S2) - Mini-Project 4: Recursion Practice
A function f of two arguments (a binary function)
filter can only decide whether to keep an element based on the current element and no other information.
We require that f is a function that takes an element of l and then produces a boolean. filter uses that boolean to determine whether to keep that element (#t) or drop that element (#f) from the list.
We say that map is non-contextual: it only “knows” one element at a time and is not “aware” of its prior processing or what is coming up next.
CSC 151-02 (2021S2) - Higher-order Recursive Design
n the specific case of tail-call optimization, we should only aggressively pursue tail-call optimization when we know that the inputs to our recursive functions will be large.
That is, we should not necessarily pursue the most optimized code upfront This is because optimizations frequently come with a cost: decreased code readability and more time and effort spent, sometimes with lesser gains that expected!
Premature optimization is the root of all evil.
Our implementation became decidedly more complicated. Rather than being a simple recursive function, append requires a helper function as well as a call to reverse. This complication also leads to potentially decreased performance in some situations. reverse must walk the entire input list to reverse it. So in effect, this tail-recursive version of append walks l1 twice: once to perform the reversal and once to cons its elements onto the front of l2. If the size of the inputs to append are small (thus not requiring us to use tail-recursion), then the tail-recursive version will be slower than its non-tail-recursive variant!
The left-hand expression arises in the tail-recursive variant of append. The right-hand expression arises with the naive version.
By cons-ing the elements in a top-down fashion rather than bottom-up fashion, we’ve reversed the order of l1 in the appended list!
Because they are local, you can also choose a pithier name for the helper so you less to type! Some folks use go, others use kernel:
letrec which acts like let* but also allows for recursive identifiers:
It is highly unlikely that replicate-helper would ever be used any other function other than replicate. So we would like to make replicatee-helper local to replicate reduce to avoid polluting the global namespace.
Updating the helper function to use the accumulator parameter. In the base case, this usually means returning the parameter as the overall result of the computation. In the recursive case, this usually means updating the parameter in some way when making the recursive call.
Creating a helper function that acts like the original function but includes an extra argument, an accumulator parameter, that captures the result of the function “so far” in the computation.
In the base case, we return the result argument since it is assumed to contain the result of traversing the list up until this point. Since we are in the base case of the recursion, we must have processed every element of the list, so the result argument contains our final result.
First, we’ll define a helper function that takes an extra argument that represents the result computed by replicate so far in its execution.
We call such functions that do all their work before they make their recursive calls tail-recursive functions. Tail-call optimization refers to both the process of making a function tail-recursive by the programmer as well as specific optimizations done by Racket behind the scenes to make tail-recursive functions efficient.
To do this, we’ll add an additional parameter to my-length that is the intended result of the computation so far.
What if we could reverse the steps? Rather than acting on the return value of the recursive call, can we figure out a way to add one to the result and pass that result to the recursive call? If we figured out some way of doing that, then we wouldn’t have any work to do after the recursive call and the resulting expression would not grow in size like it currently does.
However, Racket must still remember to perform all of these additions while it is carrying out the recursive my-length calls! This is where the inefficiency of the function lies: Racket needs to remember 1000000 (+ 1 ...) expressions, one for each my-length call made, so that they can be resolved after the last my-length call that returns 0 resolves.
CSC 151-02 (2021S2) - Tail Recursion
Finally, note that sometimes we don’t use all of the bindings introduced by a pattern.
The non-empty list case is more interesting. Recall that a non-empty list is formed by the cons function. The pattern (cons head tail) checks to see if l is such a list. However, on top of this check, if successful, the match also binds the two arguments of the cons to the variables head and tail respectively.
Following the match is an expression that evaluates to the value that is the scrutinee of the pattern match, i.e., it is the value that we are analyzing.
The base case: compute the length of a list that is empty. The recursive case: compute the length of a list that is non-empty.
We solve the problem in the case where the list is empty, the base case. We solve the problem in the case where the list is non-empty, the recursive case.
we’re going to assume that a recursive function call to the tail of the list produces the intended result.
In the case where the list is non-empty, the sum of the numbers can be expressed as the result of adding (a) the head element and (b) the sum of the rest of the list.
Empty (or null), or Non-empty, consisting of a head element (retrieved with car) and its tail, the rest of the list (retrieved with cdr).
(a) solve a problem in a recursive manner and (b) translate that solution into a recursive function.
CSC 151-02 (2021S2) - Recursive Skeletons and Pattern Matching
attempt the conceptual questions posted in the weekly folder. Submit your answers by midnight to receive your attendance score. Being correct is not important but please do provide your reasoning.
Mail - Peng, Kevin - Outlook
Fortunately, if does not behave like most procedures and only evaluates its final parameter (the false part) when the guard is false. In this case, the guard was true, and so we never got to the invalid expressions
recursive function call.
(cons x xs) creates a new list by appending the element x to the front of the list xs.
o ensure that we don’t call car and cdr on an empty list, we can use the null? function which takes a list as input and returns #t if and only if the list is empty, i.e., null. As an example, here is a use of car, cdr, and null? in combination to define a function singleton? that returns #t if the input list contains exactly one element.
This idea that we can decompose a problem into a smaller version of itself is called recursion.
CSC 151-02 (2021S2) - Recursion basics
For some programmers, writing the formal postconditions can give them an idea of how to solve the problem.
So, whenever you make a test suite, you’ll probably have to name it with define
Note that, unlike test-case, test-suite does not run the tests. Instead, it builds a suite that we can later run with run-tests.
Create a new test case by running a series of checks.
compare them for numeric equality (within *epsilon)
CSC 151-02 (2021S2) - Testing your procedures with RackUnit
can be more complicated to learn
nvasive to code
Unit testing frameworks
When debugging, we don’t run risk of violating ethical standards if we observe-and-then-predict. However, we do run the risk of wasting our time if we aren’t entering the observation phase of debugging without a clear prediction to verify or refute.
When run is pressed: DrRacket first checks the syntax of our program to ensure that it is well-formed. It also checks to ensure that all of our usage of identifiers are well-scoped. DrRacket then runs the program in the current definitions pane.
Static errors: these are errors that happen before the program executes. Dynamic errors: these are errors that happen during program execution.
Our knowledge of what parts of the code were last edited since the appear began appearing.
the call stack of an error which describes the sequence of function calls that generated the error in question.
Gather data State assumptions Predict what is wrong Use tools to verify/refute your prediction Analyze your results
CSC 151-02 (2021S2) - Hypothesis-driven debugging (Notes)
爸爸带娃 还是娃带爸爸？ | 单读
Doc comments are meant for our collaborators and other potential users of this code to quickly learn about the program’s available functionality without having to dive through the details of the code. This audience also includes our future selves who may have forgotten these details!
A description of the computation that the function performs and the result value that it outputs. Any important details about the function’s behavior that a user of the function ought to know.
if a constraint only involves one parameter and it is short to express (either with a Racket expression, mathematical formula, or phrase), place it with the parameter list. If the constraint involves the interaction of multiple parameters or is complicated, place it in the description where there is more prose.
This section describes the types of each parameter again by way of predicates that usually test type identity. In addition to the predicates, we might also specify other essential properties of the parameters that aren’t necessarily captured in the predicate.
by a predicate,
the arrow (->)
The signature of a function describes what it takes as input and produces as output.
Note that throughout, we use triple semicolons (;;;) to encase our doc comments to make them stand out from other comments we might write.
Having to execute our function to figure out what it does is not ideal. What if the function we’re considering takes a long time to execute? What if the function is deeply nested inside of our system and, thus, difficult to execute on its own? What if the function’s behavior is so convoluted we don’t even know what we could pass to the function to experiment?
Is our translation of our solution to a program correct?
Is our solution (our algorithm) correct?
CSC 151-02 (2021S2) - Documenting Your Code
he large unc
175 ± 5 grams
Student Response | Pivot Interactives
If the helper procedure you’re defining uses any of the parameters of the main procedure, it needs to come after the lambda. Otherwise, it is generally a better idea to do it before the lambda.
In the second case, it is done every time the procedure is executed.
Regardless of whether square is also defined outside this definition (e.g., as a procedure that draws squares), the local binding gives it the appropriate meaning within the lambda-expression that describes what hypotenuse-of-right-triangle does.
Yes, one can use a let- or let*-expression to create a local name for a procedure.
But that definition requires DrRacket to build the list every time we call the vowel? procedure.
One moral of this story is whenever possible, move your bindings outside the lambda.
What we’d like to do is to declare the values once, but keep them local to years-to-seconds. The strategy is to move the let outside the lambda.
About a decade ago, SamR said, “When you have sons between the ages of 5 and 12, you’ll understand.”
each binding specification in the binding list is completely processed before the next one is taken up
You have to think of the local bindings coming into existence simultaneously rather than one at a time.
Within one binding list, all of the expressions are evaluated before any of the names are bound.
; Combining the binding lists doesn't work!
this is the second argument to + and is outside the body of the let, so we do not substitute for it. Presumably, this x is bound by a different construct, e.g., a define.
In contrast, if you use let to define your local names, these names are completely inaccessible to other pieces of code.
When we do a new top-level define (Racket only allows that in the interactions pane), we permanently replace the old value associated with the name. That value is no longer accessible. In contrast, when we use let to override the value associated with a name, as soon as the let binding is finished, the previous association is restored.
Values named by define are available essentially everywhere in your program. In contrast, values named by let are available only within the let expression.
The programmer can compute the value of the subexpression just once, bind a name to it, and then use that name whenever the value is needed again.
There is. Raacket provides let expressions as a way to bind values to names. A let-expression contains a binding list and a body. The body can be any expression, or any sequence of expressions, to be evaluated with the help of the local name bindings. The binding list takes the form of a parentheses enclosing zero or more binding expressions of the form (name value).
Rewrite procedures that do a sequence of steps by using one procedure for each step
once when counting the vowels and once when counting the consonants.
we ask if many letters are a vowel twice
Second, we call (string->list str) twice.
First, we call (char-downcase ch) as many as five times.
parameter bindings are local – they apply only within the body of the procedure.
by means of a definition
CSC 151-02 (2021S2) - Naming values with local bindings
It is not a single integer—note that because one of the characters of the ISBN could be ‘X’
when the test suceeds, we get no output. When the test fails, we get a large failure notice.
For now, we’ll look at two basic RackUnit procedures: (test-true DESCRIPTION EXP) and (test-false DESCRIPTION EXP). These procedures evaluate the expression EXP and prints out the description when the expression does not evaluate as expected.
codify your tests in your code so that you can rerun the tests at will.
A brief sentence or two which describes the behavior and output of the function.
that it procedures a real number (as tested by the real?` function)
names its arguments and describes the output type of the function
The types of each of the parameters mentioned in the signature.
For each function that you write in this mini project, include a function comment that captures the types of the function as well as describes its output in a sentence or two
large strings of digits
CSC 151-02 (2021S2) - Mini-Project 2
matches any one character that does not appear in str.
matches any one character in str
we can repeat them and we can concatenate them.
So, (rex-concat (rex-string "hello") (rex-repeat-0 (rex-string "o"))) matches "hello" with an arbitray number of additional o’s.
For example, the following regular expression captures the pattern of one or more repetitions of "hello".
For example, the following string captures the pattern of zero or more repetitions of "hello".
The simplest way to use them is to check whether a string matches a regular expression using (rex-matches? rex str)
CSC 151-02 (2021S2) - Regular expressions
Warning! The string->file procedure will overwrite an existing file, completely eliminating any previous content.
CSC 151-02 (2021S2) - Text and text files
You can read this as “map (a function that takes one parameter, x, squares x and then adds 1) to the list …”. What’s the name of that function? It doesn’t have one. it’s anonymous.
composition works only for one-parameter procedures and partial-functions only work when you’re filling in some parameters of a multi-parameter procedure.
instead of writing (/ ? 2), we write (section / <> 2)
we can’t write that expression because as soon as DrRacket sees (/ ...), it says to itself “I’m supposed to do division right now
For now, we’ll stick with the right-to-left behavior. Later in the semester, we may explore some variants of the composition operation.
It may not be a surprise that these operations can create new procedures; after all, procedures like map and apply take procedures as parameters.
composition and partial expressions
CSC 151-02 (2021S2) - Anonymous procedures
map can also build a new list by applying the procedure to the corresponding elements of all the lists.
filter takes two parameters, a unary (one-parameter) predicate and a list of values, and selects all the values for which the predicate holds.
(filter pred? lst)
they cannot be easily parallelized because we have chosen a particular sequence of operations.
we also provide reduce-left and reduce-right
Ooh, that’s not very good, is it. We’d almost certainly prefer consistent results.
you simply think of what to do with neighboring pairs and then rely on reduce to do the heavy lifting.
reduce repeatedly applies the function to neighboring pairs of values.
Now, we can use the reduce procedure with combine-with-space. (reduce FUN LST), converts LST to a single value by repeatedly applying FUN to neighboring pairs of values, replacing the pair with the result of the function.
As we start to reach the limits on the speed of one processing unit, the way we make large computations faster is to parallelize them, to make them run on multiple processing units.
Since map does not specify the order in which the elements are processed, one can implement map so that all (or at least many) of the applications can be done at the same time.
CSC 151-02 (2021S2) - The "big three" list operations
reduce expects a procedure as its first parameter and and is a keyword rather than a procedure.
CSC 151-02 (2021S2) - More list operations
while (+ 2 3) is an expression that indicates that the computer should add the numbers 2 and 3, '(+ 2 3) is a list with three values, the symbol + and the numbers 2 and 3.
Racket distinguishes lists from expressions with a tick mark (a single-quotation mark)
The name of the type is “list” and its primary purpose is to group or collect values.
its name, its purpose, how one expresses values in the type, how the computer displays values in the type, and what operations are available to you
CSC 151-02 (2021S2) - List basics
This strategy also gives the programmer a way to avoid meaningless tests. For example, we should not make the comparison (< ...) unless we are sure that both a and b are numbers.
the expressions that follow the keyword and are evaluated in succession until one is found to have the value #f (in which case the rest of the expressions are skipped and the #f becomes the value of the entire and-expression
Suppose new-even? is called with 2.3 as a parameter. In the keyword implementation of and, the first test, (integer? ...), fails, and new-even? returns false. If and were a procedure, we would still evaluate the (even? ...), and that test would generate an error, since even? can only be called on integers.
number? tests whether its argument is a number. integer? tests whether its argument is an integer. real? tests whether its argument is a real number. string? tests whether its argument is a string. procedure? tests whether its argument is a procedure. boolean? tests whether its argument is a Boolean value. list? tests whether its argument is a list.
A predicate is a procedure that always returns a Boolean value
CSC 151-02 (2021S2) - Boolean values and predicate procedures
<expr1> is an expression that evaluates to a boolean value, i.e., to either #t or #f.
CSC 151-02 (2021S2) - Conditional evaluation in Scheme
CSC 151-02 (2021S2) - Characters and strings
A symbol is simply a word (usually) that we use to denote only itself.
CSC 151-02 (2021S2) - Symbolic values in Racket
What does a datum of this type represent? How do we make values of this type? What library functions are available for manipulating values of these types?
the types of the inputs and outputs don’t have to be the same
we must provide values of the appropriate type.
The type of an expression is the type of the value that the expression evaluate to.
Primitive data: “indivisible” data, i.e., data that cannot be broken up into smaller pieces.
Compound data: data that is made up of other, smaller pieces of data.
In this sense, numbers are examples of primitive data
CSC 151-02 (2021S2) - Expressions and types
we should try to describe how the type of the result depends on the type of the input.
For example, the addition operator, +, provides an exact result only when all of its inputs are exact.
When we want to be precise, such as when dealing with financial matters, we will use exact numbers (most likely, exact integers). When the computation does not permit exact representation, such as when we start to deal with certain square roots, we will use inexact values. What about complex numbers? We’ll generally leave those to the physicists.
That is, when you want an exact number, you do not include a decimal point or the exponent.
And, because it’s approximated, our calculations using that result will also be approximate.
In traditional mathematics, each category is a subset of the next category. That is, every integer is a rational number because it can be expressed with a denominator of one, every rational number is a real number because it can be plotted on the number line, and every real number is complex because it can be expressed with a an imaginary component of zero.
CSC 151-02 (2021S2) - Numeric values
it may be that you discover a more efficient way to do a computation. If you’ve written the same code for the computation throughout your program, you’ll have a lot of code to update.
The other programmer may also find it easier to write programs using simple-house than the much longer series of expressions.
One of the most important is clarity or readability.
The first definition, for house-grid defines a value. (It’s a value which is an image, but it’s still a value.) In contrast, the definition for house-seq defines a procedure. We refer to values and procedures differently.
my-square names a procedure that takes one input, x, and computes its result by multiplying x by itself.
the instructions the procedure executes
the names of the parameters (inputs) to the procedure
The name we use to refer to the procedure
CSC 151-02 (2021S2) - Writing your own procedures
We determine the sub-expression to evaluate next based off of our rules. We evaluate that sub-expression to a value. We substitute the resulting value for that sub-expression to create a new, slightly simplified expression.
Does this difference matter?
CSC 151-02 (2021S2) - Mental models of computation
Create a list of five images
Write five (5) procedures that you think will be useful in building more complex images.
programming is not a spectator sport (really, few things are in this world)
In particular, you will find that in three months (or perhaps sooner), you will feel like “another person”, forgetting what you were thinking when you were designing the program.
Is it readable? Does it follow the design guidelines outlined in the exercise write-up and otherwise adhere to good coding conventions?
we can run a program and determine that its behavior is correct
External correctness: Does the program behave correctly according to its specification? Internal correctness: Is the program designed well?
CSC 151-02 (2021S2) - Mini-Project 1
The short answer is that it depends on the kind of problem you are tackling and your own personal preference.
The process by which we take a complicated problem like ranking all webpages and distill it into a collection of smaller, easier-to-solve problems is called algorithmic decomposition.
CSC 151-02 (2021S2) - Decomposition
we will also consider issues of style and elegance
computer science is the study of algorithms and data structures.
CSC 151-02 (2021S2) - An Introduction to the course
procedures or functions
parameters or arguments
Rather than repeating the instructions, we will find it helpful to make a separate algorithm that we can refer to in our main algorithm.
In other cases, the ordering will be less explicit, as in the computation of 3+4*5.
the order in which we perform steps can have a significant impact on the outcome of our algorithm
Behind the scenes, computers “know” very little. But most programming languages and environments provide a rich infrastructure of values and operations on those values. We call these the “built in” values and operations.
As you learn a new programming language, make sure to pay attention to how you express these blocks.
the way we express an algorithm depends, in large part, on the audience for the algorithm
CSC 151-02 (2021S2) - Algorithm building blocks
Here’s a quick example of naming in Racket, which we do with the define keyword.
Parentheses play an important role in DrRacket.
the bottom pane is called the Interactions Pane
The top pane is called the Definitions Pane
While it is possible to create programs in almost any text editor, more programmers develop their program in what is normally called a program-development environment or integrated development environment (IDE)
CSC 151-02 (2021S2) - The DrRacket programming environment
Sequence computations by nesting.
Write expressions in prefix order.
Parentheses tell Racket that you want to apply a procedure to some values
we have to explicitly state the order, writing either (+ 2 (* 3 5)) or (* (+ 2 3) 5), using * as the multiplication symbol
To tell the computer to apply a procedure (subroutine, function) to some arguments, you write an open parenthesis, the name of the procedure, the arguments separated by spaces, and a close parenthesis.
CSC 151-02 (2021S2) - An abbreviated introduction to Racket
(For those who learned binary in high school or elsewhere, if you have exactly eight binary digits, and you only care to represent positive numbers, you can represent exactly the integers from 0 to 255. This is akin to being able to count up to 999 with three decimal digits.)
What is the name of the type? It’s “image”. What is the purpose of the type? To allow people to make interesting images. How do you express values in this type? We’ve seen a few ways, including circle the and rectangle procedures. There are more. How does DrRacket display values? As the “expected” images. What procedures are available? We’ve seen that we can use above and beside. Once again, there are more.
CSC 151-02 (2021S2) - Simple images in Racket
To earn an A, one must pass learning assessments for 26 of the 28 learning objectives.
To earn an A, one must do an excellent job on most mini-projects.
To earn an A, one should show appropriate work on most of the reading problems for the semesters.
To earn an A, one should turn in most of the lab exerises
Need to Talk Line: 641-269-4404 (available 24/7 for counseling needs)
24 hours per week
you should develop a habit of saving your work frequently
CSC 151-02 (2021S2) - Syllabus
on Tuesdays from 9-11:50am via Pivot Interactives
so you will be expected to have watched the recorded lectures before meetings
this Thursday (4/1) at 10-11:30am
10-11:30am, CST, M/W/F
Mail - Peng, Kevin - Outlook
They can also, it seems, make us sexy.
Opinion | Microbes, a Love Story - The New York Times
the email says that this summer the school "will work individually
Mail - Peng, Kevin - Outlook
It is expected that participation in this study will provide you with no more than minimal risk or discomfort, which means that you should not experience it as any more troubling than your normal daily life.
Online Survey Software | Qualtrics Survey Solutions
Twenty-four semester hours of humanities and social studies
A year of chemistry
Modern Physics and Mechanics
a knowledge of C, C++, Java, Python, or MATLAB
chemistry (Chemistry 129 or 210
physics (Physics 131-132)
Differential Equations (Math 220)
Linear Algebra (Math 215)
Columbia University California Institute of Technology
3-2 Engineering Program | Grinnell College
made available by specific programs and individual faculty members at their discretion
work closely with a faculty member on a research or creative project
Mentored Advanced Projects (MAP) | Grinnell College
FMT showed significant improvement of depression, anxiety and sleep subscale scores in patients with Functional Gastrointestinal Disease (FGID).
The effect of fecal microbiota transplantation on psychiatric symptoms among patients with irritable bowel syndrome, functional diarrhea and functional constipation: An open-label observational study - ScienceDirect
Forced swimming test (FST)
We found that the weight of ‘depression microbiota’ recipient mice was not significantly different than 'healthy control' recipient mice during FMT experimentation (Supplementary Figures S7a–c).
These findings show that colonization of GF mice with ‘depression microbiota’ resulted in increased depression-like behaviors as compared with colonization with ‘healthy microbiota’.
Fecal microbiota transplantation of GF mice with ‘depression microbiota’ derived from MDD patients resulted in depression-like behaviors compared with colonization with ‘healthy microbiota’ derived from healthy control individuals.
Gut microbiome remodeling induces depressive-like behaviors through a pathway mediated by the host’s metabolism | Molecular Psychiatry
a lower bacterial load and a relatively low abundance of the bacterial genus Faecalibacterium.
immune system,13,17 synthesis and metabolism of metabolites and neurotransmitters,18 and activation of the vagus nerve.
Interestingly, it is over 100 years ago since George Porter Philips put forward the concept of treating melancholia with lactobacillus;164 with more clinical research, we may be able to validate how much he was ahead of his time.
The reverse is likely also true. Looking toward the future, the microbiome might be the place to probe when developing new treatments for MDD
As discussed earlier in the review, microbiome features such as an altered microbial composition, or alpha diversity, are often associated with MDD symptoms. FMT has been shown to transfer these features to the recipient.160 While dedicated studies are not yet available, a recent study on the effect of FMT on inflammatory bowel disease has reported improved mood in recipients of a healthy microbiome
Microbiome interventions specifically designed to improve mental health are termed psychobiotics.
prebiotics and probiotics.
it has been speculated upon that the microbiome-targeted effects of psychotropic drugs might play a role in the mechanism of action or in the side effects of these medications.
A general trend among the microbiomes of depressed patients and animals with increased depressive-like behavior is a drop in alpha diversity, an increase in relative abundance of microbes associated with a proinflammatory state, and a heightened state of inflammation in the host
While only shown in rodents, the behavioral outputs of these studies and their respective translational implications support the notion that certain compositions of the microbiome can affect behavior and mood.
both mice and rats that received a fecal microbiome transplantation (FMT) from depressed humans displayed a heightened state of inflammation and increased anhedonia-like (as measured by the sucrose preference test) and anxiety-like behavior (as measured by the open field test and elevated plus maze test) compared to those who received FMT from healthy volunteers.
depressed individuals were more likely than their healthy counterparts to fall into a certain enterotype
a classification of living organisms based on their bacteriological ecosystems in the gut microbiome
diversity of MDD patients tends to be lower overall, with a higher abundance of bacterial phyla generally associated with inflammation, like Bacteroidetes, and a reduction in phyla associated with a decrease in inflammation, like Firmicutes
MDD patients have an altered gut microbiome composition when compared to healthy controls
some studies have also shown that transferring the microbiome of a depressed individual into a healthy rodent can induce depressive-like behavior in the recipient.
A wealth of studies, from different perspectives and experimental approaches, link the gut microbiome to MDD
an increase in the relative abundance of the genera Bifidobacterium and Lactobacillus and the species Blautia coccoides and Eubacterium rectale, as well as with an increase in microbiota diversity,
potential positive effects on brain and behavior
a dampening or abolishment of microbiota compositional oscillations
circadian disruptions can affect the intestinal microbiota
reduced levels of Lactobacillus, a health-promoting genus that is abundant in early life, and reduced SCFA production
high-stress microbiomes featuring an increased diversity of Clostridium genera, which is generally associated with inflammation and disease
Many studies exist in animal models showing the impact of stress on the microbiome—including rodents,29,36,37,46,75,76 pigs,77 and primates.
that stress influences the microbiome
also to shorten episodes of depression
associated with an increased abundance of bacteria with anti-inflammatory properties.
diet can be effective in alleviating MDD symptoms.
quality of diet is known to influence the severity of MDD
diet is known to markedly shape the composition of the gut microbiome.
In the context of MDD and the microbiome, two such factors stand out especially—namely, diet and stress.
we will examine evidence suggesting that the microbiome is altered in MDD, and discuss why the microbiome should be considered during MDD treatment
Neurodevelopmental differences—including neurogenesis, a process that is dysregulated in depression—have been observed in mice with a humanized microbiome, where specific microbes seemed to be necessary for normal neurodevelopment.
The gut microbiome is also known to modulate the physiology and behavior of the animal.
stress can change the microbiome in mice, specifically decreasing Lactobacillus
interpreting changes in mood and behavior in animals is challenging
Factors that influence the microbiome and, in turn, the onset/development of depression include lifestyle, medications, stress, and dietary habits
HPA axis becomes hyperactivated
In major depressive disorder, alterations in the gut microbiota negatively affect the gut–brain axis
depression has been associated with impairment of the microbiome’s ability to produce neuroactive metabolites and with disrupted intestinal barrier function
Alterations in the microbiome can also lead to hyperactivation of the immune system, with production of inflammatory cytokines typically observed in depression.
microbiota could influence central nervous system function directly by means of neuronal activation of stress circuits
gut microbiota plays a role in the programming and reactivity of the HPA axis
episodes of depression are associated with a dysregulated hypothalamic–pituitary–adrenal (HPA) axis,25 and conversely, improved depressive symptoms are associated with stabilization of the HPA axis.
the gut microbiome has been linked to several physiological functions relevant to depression
major depressive disorder (MDD).
the microbiome–gut–brain axis (MGBA)
Fecal Microbiome Transplantation as a Therapy for MDD
the bacteria on the teeth of his patients were the source of their psychiatric conditions
Élie Metchnikoff, adhered to the idea that bacteria in fermented milk were beneficial against autointoxication
the syphilis-causing microbe Treponema pallidum was responsible for filling large parts of Victorian mental asylums
how the microbiota might become a therapeutic target for MDD
the interplay between the microbiota and MDD
factors that affect the onset/development of MDD that also greatly impinge on the composition of the gut microbiota—especially diet and stressful life events
the gut contains the largest number of neurons in the body, after the brain
the gut microbiome is in communication with the brain, through the gut–brain axis.
Gutted! Unraveling the Role of the Microbiome in Major Depre... : Harvard Review of Psychiatry
There appears to be strong evidence for the treatment and transmission of psychiatric illnesses through FMT
All studies found a decrease in depressive and anxiety-like symptoms and behaviours resulting from the transplantation of healthy microbiota
Effect of fecal microbiota transplant on symptoms of psychiatric disorders: a systematic review | BMC Psychiatry | Full Text
However, after completing FMT treatment there was an objective improvement in mood, medication and/or symptoms reported by the patient and/or attending physician.
Faecal microbiota transplantation may be a potential adjunct therapy for treating depression and irritable bowel syndrome through the gut-brain axis.
Despite varying symptom onsets, types and levels of neurological and gastrointestinal symptoms there was an objective improvement in mood, medication and/or symptoms reported by the patient and/or attending physician.
Depression is a common mental health disorder that affects more than 260 million individuals worldwide.
Faecal microbiota transplantation alleviates symptoms of depression in individuals with irritable bowel syndrome: A case series - ScienceDirect
The goal of FMT is to introduce or restore a stable microbial community in the gut by transplanting intestinal microbiota from a healthy donor to the patient.
Fecal Microbiota Transplantation in Depression - Full Text View - ClinicalTrials.gov
Feeling Depressed? Bacteria in Your Gut May Be to Blame
These behavior changes in mice affect such things as appetite, weight gain and activities like swimming.
several recent studies show.
research was published
a 2019 review in the Journal of Experimental Medicine
Human Microbiome Project.
These behavior changes in mice affect such things as appetite, weight gain and activities like swimming.
Until now, though, no one has been able to single out specific species of microbes linked to a mental illness. This month, an international research team for the first time identified dozens of species of gut microbes involved in depression by comparing patients diagnosed with the disorder to healthy people. These 47 species are a tiny fraction of the gut’s microbial diversity, which includes other single-celled organisms, thousands of virus species and fungi.
Bacteroides, here seen in a colored scanning electron micrograph, are the most common bacteria found in the human intestinal tract.
“When you give these mice the microbes from depression, they begin to behave in a depressive-like way,” said psychiatrist Julio Licinio at State University of New York Upstate Medical University in Syracuse. These behavior changes in mice affect such things as appetite, weight gain and activities like swimming.
chemically altering nerve signals going into the brain, which alter brain chemistry and therefore behavior, mood and, we believe, depression and anxiety.
Some common gut bacteria, for example, help generate neurotransmitters such as serotonin, which affects neural activity related to mood and memory. It’s commonly used to treat depression. Others make an amino acid called gamma-aminobutyric acid that naturally blocks some brain signals. It’s used in medication to relieve anxiety and improve mood.
While no one yet knows exactly why, patients with various psychiatric disorders including depression, bipolar disorder, schizophrenia and autism-spectrum disorder have significant disruptions in the composition of their gut microbiome.
indiscriminate use of antibiotics and other sanitation measures eliminated the harm that bacteria cause at the expense of the protection they can provide.
a potential mechanism for a mental illness that affects an estimated 350 million people world-wide
infect mice and rats with mental disorders, including depression and anxiety, by transplanting stool samples, which contain gut microbes, from human patients into laboratory animals, several recent studies show.
often associated with gastrointestinal disorder
the microbial menagerie living in our digestive tract may help regulate brain function, including mental health
we can have behavioral effects that are going to have impact on overall well-being.”
directly by affecting nerve signals and indirectly through chemicals absorbed into the bloodstream
Conversely, other bacteria in the gut appear to produce some of the same substances used by doctors to treat depression and may naturally play a role in maintaining our emotional balance.
Feeling Depressed? Bacteria in Your Gut May Be to Blame - WSJ
fuse cells into a wall — the placenta
Once a viral protein, the virus essentially morphed or evolved into what we now know as syncytin.
we get this viral DNA that lets us make a protein that fuses things.
When evolutionary biologists like Chuong mapped the genomes of these cells, they found that the protein that allowed these cells to fuse into a wall, called syncytin, didn’t look like it came from human DNA. It looked more like HIV. According to Chuong, this protein actually came from an ancient retrovirus,
evolved about 150 million to 200 million years ago. Before that, if you wanted to reproduce, you had to lay eggs.
Because half of the fetus is maternal, but the other half is paternal, and yet the pregnancy can go on for nine months without the mom’s body destroying it,” Barroeta said. “And that, from an immune standpoint, is fascinating, because if you were to receive a piece of someone else and insert that under your skin, that would not last there for three days, your body will actively reject it.”
it’s the baby’s lung, it’s a waste-disposal system, and it’s a nutrition source.”
How the placenta evolved from an ancient virus — WHYY
noncoding regulatory elements
mediating cell–cell fusion to form a multinucleate barrier, suppressing maternal immunity, and protecting the fetus from exogenous viruses
These findings have led to speculation that the co-option of unrelated ERVs in different species was a driving force underlying the evolutionary diversification of the placenta
Most ERVs are considered fossilized relics that can no longer replicate or encode functional viruses, but the occasional insertion may prove beneficial for the host and become co-opted for a cellular role.
Genome-sequencing projects of many species have revealed that ERVs have a ubiquitous presence in vertebrate genomes, constituting over 8% of the human genome
A key step in the retrovirus lifecycle is retrotransposition, in which the RNA-based virus genome is reverse transcribed and integrated into the DNA of the host cell.
The placenta goes viral: Retroviruses control gene expression in pregnancy
Unexpectedly, syncytin-B null embryos are viable, with only limited late-onset growth retardation and reduced neonate number.
A pair of co-opted retroviral envelope syncytin genes is required for formation of the two-layered murine placental syncytiotrophoblast - ProQuest
from egg-laying to placental mammals.
tolerance of the fetus by the maternal immune system
Knocking out one or both mouse syncytin-A and -B genes provided evidence that they indeed play a critical role in placentation.
such events must have occurred repeatedly during the course of millions of years of evolution.
From ancestral infectious retroviruses to bona fide cellular genes: Role of the captured syncytins in placentation - ScienceDirect
The most striking example, though, relates to the evolution of the mammalian placenta and the timing of gene expression in human pregnancy. Evidence indicates that we owe our ability to have live births to a bit of genetic code that was co-opted from ancient retroviruses that infected our ancestors more than 130 million years ago.
In 2018, for example, two research teams independently made a fascinating discovery. A gene of viral origin encodes for a protein that plays a key role in long-term memory formation by moving information between cells in the nervous system.
Ultimately, though, the more we learn about all viruses, not just the pathogens, the better equipped we will be to harness certain viruses for good and to develop defenses against others that could lead to the next pandemic.
Why the world needs viruses to function - BBC Future
Syncytin originated from a retroviral gene encoding a protein that is embedded in the outer surface of a virus. This protein mediates the fusion of the virions with the host cell membrane, thereby facilitating viral infection. In a remarkable turn of events, the human body has repurposed the viral protein's cell-fusing activities to promote the formation of the layer of cells that merge the placenta and the uterus.
When viruses infect us, they can embed small chunks of their genetic material in our DNA. Although infrequent, the incorporation of this material into the human genome has been occurring for millions of years. As a result of this ongoing process, viral genetic material comprises nearly 10 percent of the modern human genome.
Our complicated relationship with viruses -- ScienceDaily
At first, endogenous retroviruses coax cells to make more retroviruses that can infect other cells. But over the generations, the viral DNA mutates, and endogenous retroviruses eventually lose the ability to infect new cells.
If a retrovirus happens to infect an egg or sperm, its DNA can potentially be passed to the next generation and the generation after that.
Placentas make viral proteins, and scientists have found that some types, known as syncytins, fuse together placental cells, a crucial step in fetal development.“My speculation is that without syncytins, mammal evolution would have looked very different,” Dr. Coffin said.
But in certain cases, Dr. Coffin said, we have domesticated our viruses. We make proteins from endogenous retroviruses to carry out functions we depend on.
Ancient Viruses Are Buried in Your DNA - The New York Times
Phylogenetic analyses showed that mammalian Arc is derived from an ancient retrotransposon of the Ty3/ gypsy family and contains homology to the retroviral Gag polyproteins
Recent studies made the surprising observation that the neuronal gene Arc forms virus-like protein capsids that can transfer RNA between neurons to mediate a novel intercellular communication pathway.
Viruses and transposable elements are major drivers of evolution and make up over half the sequences in the human genome
Intercellular Communication in the Nervous System Goes Viral: Trends in Neurosciences
Evolutionary analysis indicates that Arc is derived from a vertebrate lineage of Ty3/gypsy retrotransposons, which are also ancestors to retroviruses.
Ty3/gypsy retrotransposons are ancient mobile elements that are widely distributed and often abundant in eukaryotic genomes and are considered ancestral to modern retroviruses (Malik et al., 2000). There is evidence that coding sequences derived from Ty3/gypsy and other retroviral-like elements have been repurposed for cellular functions repeatedly during evolution (Feschotte and Gilbert, 2012).
The Neuronal Gene Arc Encodes a Repurposed Retrotransposon Gag Protein that Mediates Intercellular RNA Transfer - ScienceDirect
In the BAM model, phage adhere to mucus protecting the metazoan host against invading, potentially pathogenic bacteria.
Viruses and the origin of microbiome selection and immunity - ProQuest
Then there’s the fact that Arc has been implicated in a variety of neurological diseases and conditions, ranging from Fragile X syndrome to Alzheimer’s disease. The Arc study will be an invaluable corner piece for those puzzles.
rather than simply asking the other side of the synapse to turn up the gain, Arc packages the raw genetic material to do so, and then visits the other side of the synapse in person. Effectively, Arc ‘infects’ other neurons with the raw materials of memory.
Arc still seems to act like a virus.
which contains stretches that look eerily similar to those found in ancient viruses.
One of these genes, known as Arc, is so critical to these processes that it has often been called a ‘master-regulator’ of synaptic plasticity.
This ‘synaptic plasticity’, is fundamental to the ability of animals to learn, and without it we would no more be able to tie our shoes than to remember our own names.
Prehistoric Viruses and the Function of the Brain - Scientific American
BEST source. Search these 3 databases at the same time; a good way to start searching for primary literature about almost any topic in Biology.
Identify - Biology - LibGuides at Grinnell College Libraries
AirTags: Everything We Know So Far - MacRumors
your last name, followed by a space with a page number
In the upper left-hand corner of the first page, list your name, your instructor's name, the course, and the date.
Do not make a title page
1 inch on all sides
Create a header that numbers all pages consecutively
Indent the first line of each paragraph
a legible font (e.g. Times New Roman).
white 8.5 x 11-inch paper.
General Format // Purdue Writing Lab
When placed in a darkened box, normal mice will stay away from a dish of bobcat urine, but will happily wander near a dish of rabbit urine. But when infected by Toxo—any strain of Toxo—they’ll blithely wander near the bobcat pee too.
turned it into a Trojan rodent
Mind-Bending Parasite Permanently Quells Cat Fear in Mice