Learn to Program from Scratch

Don't post your solutions to the assignments anywhere, such as keeping a public github with every assignment completed. Schools will hide them behind logins if too many solutions are posted. Some of the AI courses we'll see later the assignments have been restricted to the public. We'll work around this but it's annoying. In the beginning I'll post some partial solutions breaking this rule, but it's better you figure it out yourself anyway since that's how you learn. There is no right and wrong answers to the exercises, this isn't typical school, it's self-directed research where you kind of experiment your way through it at the beginning and then over time get better and better.

Do 1% effort for 100 consecutive days as per CMU prof Ryan O'Donnell and see where you end up. It would be better to take your time and redo a chapter numerous times (or go back and redo a few chapters) really fleshing out the exercises than it would to speed ahead and end up confused.

As stated in the intro it's possible to complete this course with just a phone or a tablet, the interpreter you use is online and even has a static type checker

• the book Programming and Programming Languages (use the most latest version, which is 2020)
• a web browser to view the lectures
  • the lectures cover extra material not in the book
• a web browser to use the Pyret online interpreter
• a google account to save your work if you wish
• the 2018 copy of the assignments since we are watching the 2018 lectures
• the labs at the bottom of this page (Big-O, Higher-Order Functions, Streams etc).

If you have wget installed:

wget --mirror --convert-links --adjust-extension --page-requisites --no-parent https://cs.brown.edu/courses/cs019/2018/assignments.html

You may also want to archive the pyret documentation or even the entire book using the same method. To archive the lectures try a browser plugin that can download video content and save them as you watch.

Let's work through the book starting at the beginning, I'm using whatever the latest version is (as of this writing, 2020). This book is a work in progress so you'll see some minor errors like "REF" which is supposed to later be a link to whatever reference in the text that's not finished yet. The lectures we do will fill in these blanks. You can get a crash course to do the assignments with this single chapter from 2015 though some syntax may have changed, compare it to the Pyret documentation.

Chapter 2 Basic Data and Expressions read while you have the pyret interpreter at code.pyret.org open. The examples with ">" in front of them indicates enter this into the REPL, on the right hand side of the pyret code editor like he did in the lecture pressing enter to eval. It's running a read-eval-print-loop (repl) which means exactly what you think it means. It reads input, evaluates it, prints it to the console and then loops back to waiting to read input again. You can increase the font size if you click the lambda skull logo on the top left side.

Already we are introduced to built-in functions, such as num-expt. To understand these, let's read the documentation. If you have a small screen, you will need to turn your device to landscape or increase the browser window size in order to see the table of contents in the pyret docs which automatically hide depending on screen size and is annoying UI.

Find the number functions documentation by hitting Ctrl-F in your browser or otherwise searching the page for 'num-expt'. Here is how you read it. The "::" syntax refers to type expected, so num-expt(base :: Number, exponent :: Number) -> Number is annotation telling you this built-in requires two inputs: a base and an exponent of type number, and it outputs a number. This will be explained in chapter 3. Repeat looking in the documentation to understand what string-subtring() does. Try changing the examples yourself in the REPL as you go.

The last section on roughnums, where irrational numbers like the square root of two return different values is due to floating point approximation that by default use a 'round to even' rounding strategy which if you wanted you could learn from this lecture but it assumes a technical background we don't have yet, namely that you've completed all the other lectures in that playlist and an introductory programming course, which we are doing right now. The final exercise Do roughnums obey the axioms of arithmetic operators like distributivity, associativity and commutativity? you can tell immediately from the examples in the book that roughnums are always returning different values, so a + b does not equal b + a if the numbers are roughnums. Think to yourself what would happen if you used floating point to encode money in financial software, with unpredictable results if some trade combination resulted in a roughnum.

You spent all of chapter 2 entering commands into the REPL on the right hand side of the pyret online editor, now you'll use the left hand side to write functions and run them by either pressing Ctrl-Enter or the Run button. If you make a mistake like accidentally deleting all your code Ctrl-z will undo.

In 3.5 Defining Functions in Steps notice he changes the tests to not just return the expected value, but to return the expected computation, writing out in full what should be happening. The idea of doing this is to help you write the function. These aren't tests to prove it is correct, they are tests to help understand the full domain of the problem so we can write a model for it with software.

I'm assuming you're doing all the exercises. Let's walk through the 'has-overtime' raises exercise.

fun has-overtime(hours :: Number) -> Boolean:
  doc: "Returns true if hours > 40 or returns false. Hours must be a positive number or error is raised"
  if hours < 0:
    raise("hours must be greater than zero")
  else if hours > 40:
      true
  else:
    false
  end
where:
  has-overtime(40) is false
  has-overtime(40.0001) is true
  has-overtime(-1) raises "hours must be greater than zero"
end

Notice raise() is a built-in function. Where did I find how to use it? In the pyret language documentation.

Let's write some tests for the last exercise hours-to-wages-ot as an example of how writing tests helps to define the problem better, and helps write the program for you. We have to write a function that consumes hours, an hourly rate, a threshold for OT, and returns anything over that threshold at 1.5 times the rate, adding it to the total pay.

First, let's write the parameters:

fun hours-to-wage-ot(hours :: Number, rate :: Number, threshold :: Number) -> Number:
  doc: "Calculates total pay with all hours over threshold at 1.5 the rate"
where:
end

now let's write the tests:

where:
 hours-to-wage-ot(10, 1, 40) is 10 * 1
 hours-to-wage-ot(41, 1, 40) is (40 * 1) + (1 * (1 * 1.5))
 hours-to-wage-ot(50, 20, 48) is (48 * 20) + ((50 - 48) * (20 * 1.5))
end

Keep writing test cases where you don't write the final expected result, but how you would arrive at that result. Notice all I did here was copy the last test case, and the first test case to the function body:

fun hours-to-wages-ot(hours :: Number, rate :: Number, threshold :: Number) -> Number:
  doc: "Calculates pay with all hours over threshold at 1.5 the rate"
  if hours > threshold:
    (threshold * rate) + ((hours - threshold) * (rate * 1.5))
  else:
    hours * rate
  end
where:
  hours-to-wages-ot(10, 1, 40) is 10 * 1
  hours-to-wages-ot(41, 1, 40) is (40 * 1) + (1 * (1 * 1.5))
  hours-to-wages-ot(50, 20, 48) is (48 * 20) + ((50 - 48) * (20 * 1.5))
end

This is an interesting and short chapter how you would go about converting data to rows. There's nothing in here you can't already figure out now that you know how to read the documentation for pyret. The text also expects you to start reading documentation, not telling you how to assign a table to a variable so you can run all those sieve expressions on it. Change the examples in the text as you go to see what they do:

my-table = table: name, age
  row: "Alice", 30
  row: "Bob", 40
  row: "Carol", 25
end

sieve my-table using name:
  name == 'Carol'
end

order my-table:
  name ascending
end

This is similar to SQL syntax, where you just declare what you want to do to rows and columns instead of how to do it. Congrats you know some SQL now. In 4.2.7 the principle of orthogonality comment note why they composed these table row operations to be independent of each other so combining them in complex expressions is possible.

In 5.3.1 the description of the properties of an 'anonymous value' abstraction by using numbers and asking what they mean is similar to Terence Tao's Linear Algebra text where he points out that a property of numbers that makes them useful is their ability to be interpreted differently depending on context.

A Do Now appears. This means we should actually do it. Try to sieve our playlist to show the most played song using built-in language functions from the math or statistics library:

include math

my-playlist = 
  table: artist, song, playcount
    row: "Lustre", "The First Snow", 10
    row: "Lustre", "The First Beauty", 8
    row: "Lustre", "Welcome Winter", 2
  end

play-count = extract playcount from my-playlist end
most-played-count = max(play-count)

sieve my-playlist using playcount:
  playcount == most-played-count
end

Lists are introduced, which is the datastructure we will be using for a lot of the exercises because they frequently present themselves in nature.

Exercise in 5.4.2 Implement all the other statistical questions posed in Basic Statistical Questions. Let's look at them:

'keep-if' likely is supposed to be sieve as per 4.2.1 Keeping or another command you write to filter a table and keep results. Remember the warning from 1.3 The Structure of This Book: "We will include mistakes, not because we don’t know better, but because this is the best way for you to learn. Including mistakes makes it impossible for you to read passively: you must instead engage with the material, because you can never be sure of the veracity of what you’re reading" unless that is just a clever disclaimer to blanket cover all unintentional errors.

Let's go through 5.1 Basic Statistical Questions but using another my-playlist as an example. These will all be functions on lists, because we use the extract built-in function to remove this information from a table and returns a list.

# notice these import statements so we can use these built-in function
include math
include statistics
import lists as L

my-playlist = 
  table: artist, song, playcount
    row: "Lustre", "The First Snow", 10
    row: "Lustre", "Green Worlds", 1
    row: "Lustre", "Welcome Winter", 2
  end

# From 5.1 Basic Stat Questions:
# Question 1, 2, and 3 are the same: the maximum or largest value
# To see what these datastructures look like, type 'play-count' into REPL
play-count = extract playcount from my-playlist end
most-played-count = max(play-count)

sieve my-playlist using playcount:
  playcount == most-played-count
end

# Smallest value in a column 
least-played-count = min(play-count)

# Number of songs in a playlist
# Since we have extracted a list, count the length of the list using a built-in function
# using: play-count = extract playcount from my-playlist end
play-count.length()

# All the distinct entries in playcount column
# Another built-in from lists documentation
# Notice import lists as L, you can call this something else 'import lists as whatever' 
L.distinct(play-count)

# The number of distinct entries in a playcount column
# Asking us: count how many entries are distinct
# Note we are chaining built-ins together here:
L.distinct(play-count).length()

# The average, this is another built-in, from this exact chapter
avg-play-count = mean(play-count)

# Other statistics
# Replace x(play-count) with that built-in from the statistics library 
modes-play-count = modes(play-count)
median-play-count = median(play-count)
stdev-play-count = stdev(play-count)

If during an assignment you get stuck come back to this chapter and you will certainly find what you're looking for. I highly recommend doing all the exercises here and understanding everything in fact I would re-read this chapter until you can effortlessly do all the examples and understand exactly how they work, then you're at a point where the rest of the lectures will make sense without having to stop and figure out all steps. There's a silly story about Gordon Ramsay as a junior chef practicing how to make lobster ravioli with a small frozen potato and pasta over 90x after his shift until the restaurant he was at would let him try it on real lobster. He also had to practice slicing a mackerel a few hundred times until they would let him near the more expensive fish.

Let's try the first assignment. One way to slog through a long chapter on list functions is to actually implement something using lists, then we can refer to it as reference. In other words it becomes a research project to read that we are more motivated to do since we're trying to complete a task. You could also try watching Lecture 3 first before doing this assignment.

This assignment looks difficult on purpose. The dot product algebraic definition, look at the example for [1,3,-5] x [4,-2,-1]. Each index in the first list is multiplied by it's corresponding index in the second list, then those results are added together. To read the sigma notation, a*b = the sum of \(a_ib_i\) starting at index 1 (first element of the list) up to the length of the list (n):

Some more requirements are listed, such as ignoring the case (upper/lower) of a word when counting it's number of occurrences, this translates to converting list string inputs to string-to-lower/string-to-upper. The exact equation for overlap is given: dot-product(doc-vec1, doc-vec2) / num-max(num-sqr(magnitude(doc1)), num-sqr(magnitude(doc2))). The magnitude is defined as: num-sqrt(x * x) so the square root of a vector multiplied (dot product multiplication) by itself.

Example vectors:

Before we begin see the Pyret style guide.

Let's do the lab on functions as data, and write our own map, filter and fold.

fun fun-plus-one(num :: Number, func :: (Number -> Number)) -> Number:
  func(num) + 1
end

>>fun-plus-one(16, num-sqr)
>>5

Try entering various built-ins, or one you wrote yourself, as the second parameter to fun-plus-one.

Map

We're given test cases and asked to implement f-to-c and goldilocks, and given the formula for f to c temperature unit conversion.

fun f-to-c(f-lst :: List<Number>) -> List<Number>:
  cases (List) f-lst:
    | empty => empty
    | link(f, r) => 
      link((f - 32) * (5/9), f-to-c(r))
  end
end

fun goldilocks(f-lst :: List<Number>) -> List<String>:
  cases (List) f-lst:
    | empty => empty
    | link(f, r) =>
      if f > 90:
        link("too hot", goldilocks(r))
      else if f < 70:
        link("too cold", goldilocks(r))
      else:
        link("just right", goldilocks(r))
      end
  end
end
check:
  f-to-c([list: 131, 77, 68]) is [list: 55, 25, 20]
  goldilocks([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

We're asked to rewrite goldilocks using map. The data dumped into a map function is whatever the value is at that list index. In this case we know it's a number since f-lst parameter is :: List<Number>.

fun goldilocks2(f-lst :: List< Number>) -> List<String>:
  f-lst.map({(x): if x > 90: "too hot" else if x < 70: "too cold" else: "just right" end})
end
check:
  goldilocks2([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

.map() is a built-in method on a list, where f-lst.map() means we are mapping over f-lst. I used the shorthand syntax for lambdas.

We could have also rewritten it like the following example, where a seperate function is used for map instead of writing our own lambda:

fun goldilocks(x :: Number) -> String:
  if x > 90:
    "too hot"
  else if x < 70:
    "too cold"
  else:
    "just right"
  end
end

fun goldilocks2(f-lst :: List< Number>) -> List<String>:
  map(goldilocks, f-lst)
end
check:
  goldilocks2([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

Now our task is write our own version of map(). I used the documentation examples for map as check tests. Remember map consumes a function and a list, applies the function to each entry in the list returning a new list, try to do this yourself before looking at a solution (your solution may be better). For annotations, I used the built-in name annotations but if you read through the documentation you can also import annotations, or create your own datatype. The 'T' annotation is described at the end of chapter on processing lists, the notation <T> says that T is a type variable parameter meaning it can be any type, so if you give map a list of numbers it will be that type, or a of strings, it will be List<String> etc.

fun my-map<T>(func :: (T -> T), l :: List<T>) -> List<T>:
  cases (List) l:
    | empty => empty
    | link(f, r) =>
      link(func(f), my-map(func, r))
  end
end
check:
  my-map(num-tostring, [list: 1, 2]) is [list: "1", "2"]
  my-map(lam(x): x + 1 end, [list: 1, 2]) is [list: 2, 3]
end

Filter

First two assignments are straight forward to get you to used to using filter, except you have to use string-to-code-points() instead of any built-in string functions.

fun tl-dr(lol :: List<String>, length-thresh :: Number) -> List<String>:
  filter(lam(element): string-to-code-points(element).length() <= length-thresh end, lol)
end
check:
  tl-dr([list: "dkfjdkj", "hi", "dkfjk"], 2) is [list: "hi"]
  tl-dr([list: "corner", "case", ""], 2) is [list: ""]
  tl-dr([list: "a", "b", "c"], 0) is [list: ]
end

# I got '101' from entering string-code-points("e") in the REPL
# See comments below, you would not want to write code this way
fun eliminate-e(words :: List<String>) -> List<String>:
  filter(lam(element): if string-to-code-points(element).member(101) or
    string-to-code-points(element).member(69): false else: true end end, words)
end
check:
  eliminate-e([list: "e"]) is [list: ]
  eliminate-e([list: "there's", "no", "letter", "e", "here"]) is [list: "no"]
  eliminate-e([list: "hello", "everybody"]) is [list: ]
  eliminate-e([list: "E", "101", "!!!"]) is [list: "101", "!!!"]
end

Lambda parameters can be a single letter: filter(lam(x): x > 1 end) as it's immediately evident what that parameter is, as the 'scope' of that function is only the filter.

Task: implement our own version of filter, which is similar to what we did for map:

fun my-filter<T>(func :: ( T -> Boolean), l :: List<T>)-> List<T>:
  cases (List) l:
    | empty => empty
    | link(f, r) =>
      if func(f):
        link(f, my-filter(func, r))
      else:
        my-filter(func, r)
      end
  end
end
check:
  fun length-is-one(s :: String) -> Boolean:
    string-length(s) == 1
  end
  my-filter(length-is-one, [list: "ab", "a", "", "c"]) is [list: "a", "c"]
  my-filter(is-link, [list: empty, link(1, empty), empty]) is [list: link(1, empty)]
end

Fold

Try the two tasks: list-product and list-max:

fun list-product(lon :: List<Number>) -> Number:
  fold(lam(acc, n): acc * n end, 1, lon)
end
check:
  list-product([list: 2, 2, 2]) is 8
  list-product([list: 0, 1, 2]) is 0
  list-product([list: -1, -1]) is 1
end

fun list-max(lon :: List<Number>) -> Number:
  fold(lam(acc, n): if n > acc: n else: acc end end, 0, lon)
end
check:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
end

Try implementing fold yourself before you look at my solution, use the check tests for fold in the pyret documentation to test your solution. I used function/arrow annotation syntax so: (Ann1, Ann2, …, AnnN -> AnnR) where Ann1 through AnnN are annotations representing arguments to a function, and AnnR is an annotation representing the return type of a function. Since fold takes two inputs, I used two annotations:

fun my-fold<T>(func :: (T, T-> T), acc :: T, l :: List<T>) -> T:
  cases (List) l:
    | empty => acc
    | link(f, r) =>
      my-fold(func, func(acc, f), r)
  end
end
check:
  my-fold((lam(acc, elt): acc + elt end), 0, [list: 3, 2, 1]) is 6
  my-fold((lam(acc, elt): acc + elt end), 10, [list: 3, 2, 1]) is 16
  fun combine(acc, elt) -> String:
    tostring(elt) + " - " + acc
  end
  my-fold(combine, "END", [list: 3, 2, 1]) is "1 - 2 - 3 - END"
  my-fold(combine, "END", empty) is "END"
end

Map2

Try the task for implementing who-passed, the second task we're asked to write map2 ourselves.

# link(ff, rr) and link(f, r) can be called anything:
# ie: link(head-first, tail-first) or link(head-second, tail-second)

fun my-map2<T>(func :: (T, T -> T), list1 :: List<T>, list2 :: List<T>) -> List<T>:
  cases (List) list1:
    | empty => empty
    | link(f, r) =>
      cases (List) list2:
        | empty => empty
        | link(ff, rr) =>
          link(func(f, ff), my-map2(func, r, rr))
      end
  end
end
check:
  my-map2(string-append, [list: "mis", "mal"], [list: "fortune", "practice"])
    is [list: "misfortune", "malpractice"]
  my-map2(_ + _, [list: "mis", "mal"], [list: "fortune", "practice"])
    is [list: "misfortune", "malpractice"]
  my-map2(string-append, [list: "mis", "mal"], [list: "fortune"])
    is [list: "misfortune"]
  my-map2(string-append, [list: "mis", "mal"], empty)
    is empty
end

The last task, best-price, look on youtube what a basic demand function is. Here's an example:

fun demand(price-increase :: Number) -> Number:
 doc: "1000 is approx demand of product at a fixed price"
  1000 - (60 * price-increase)
end

This means as the price increases, the quantity demanded will decrease by 60 units times the price increase, so if the price increase is 1, the demand is 1000 - 60. Your best-price function can take a list of price increases, the demand function, then map over the price list w/the demand function, to get a new list of adjusted demand vs price increase. Map over the adjusted demand with the price list to produce the forecast revenue, which is price * qty demanded. Then figure out how to use a combo of filter/fold in order to return the optimal price increase or write a helper function, inside the best-price function for the higher-order functions to use. The reasons for using a helper function is so you get access to the scope of the parent function, so any locally lived variables in that parent function you can pass into the helper function.

Map vs Filter vs Foldl vs Foldr

map and filter only consider one item at a time whereas fold can consider the entire list. You can implement both map and filter with fold (try it). If you've noticed in the Pyret documentation there is two folds: foldl and foldr.

• foldl(lam(x): 0 + x end, [list: a, b, c])
• ((0 + a)+ b)+ c)
  • eval nested brackets first, work left to right
• foldr(lam(x): 0 + x end, [list: a, b, c])
• a +(b +(c + 0))
  • eval nested brackets first, work right to left

Try subtracting [list: -1, 1, 2] with foldl and foldr to see the difference. With fold you have to go through every element whereas in our cases on list functions, you can break looping through a list if something is false/true and return immediately 'if f == 8: acc else: (loop again)'.

To really understand these functions try scaffolding them together in the REPL for the assignments, map over a list, feed it into a fold, feed that into a filter all chained together.

We're now on module 1 Preconditions - When Do Errors Show up? which is the bulk of 15-122, analyzing imperative code and reasoning about it's correctness. You use code commenting to describe the behavior or a function, and these comments are called contracts. The compiler can statically check these contracts meaning the code is not running. If you watched the talk ex CMU prof Simmons gave about contracts I posted earlier in these notes, you'll see that extensive testing covers less than 1% of the field of potential inputs. That same talk he also points out contracts have benefits even for functional languages with strong typing and briefly gives an idea about dependent types as a replacement for contracts, something we'll also briefly cover later.

In When Do Errors Show Up? the example string attach(int n, char c, string str) int, char, and string are similar to Pyret type notations describing what inputs they should accept. Some of the exercises assume syntax knowledge like a char must be in single quotes ie: 'c' (char) vs "c" (string) but otherwise the syntax is easy enough to figure out just by looking at it, and if you make a simple syntax error the system still gives you the correct answer anyway. Module What 'Safety' Means in C0 the first learn by doing you're entering statements like n >=0 && n <=12. The equality boolean is n == 0 (double equal, single is assignment like Pyret).

Moving on to Module 2 Assertions. These are similar to Pyret check tests. If you're following the math workshop with this programming workshop, you will have no problem understanding their examples of 'point-to reasoning'. It's similar to the proofs we've done in Tao's Analysis, you are listing reasons why something is true by pointing out which axiom or lemma gives it to you. The first learn by doing question has a bug, look at the actual assertion statement and not the 'The assertion x!= 8 is valid' title as sometimes the assertion is x!=20 if you reset the question.

Module 2 Conditionals the syntax of [0, 14) which is standard interval notation for inclusive/exclusive. In the example of @assert x==y, note we are using int's and not floats or roughnums so this assertion is true. If you get stuck on the nested conditionals question notice the @requries x < 10, and if 4 < x makes the nested x <= 16 statement a waste of code. Let's continue on to the Assignments module, the example of if (e > 0) { e = e - 1;.. note again these are integers, so the input can't be 0.5 or a 'half number' that makes e negative after 1 is subtracted. This is a little confusing because they are mixing assignment statements '=' with equality statements in working out their point-to reasoning. The very last assignment took some word smithing, x' + y' > 2 * n. The last question to rewrite the assertion without using primed variables substitute exactly what x and y are into x + y > 2 * n, which is (x * 2) + x > 2 * n.

Module 2: Introduction to Loops when you mutate data many things can go wrong, so learning how to reason about correct loops will be important to us should we go on to use a Python or some other AI library later. The first example the while loop you can hand step this loop, adjust the varibles with each iteration, then compare them to the assert such as @assert i >=n once the loop exits, since if n = 3, then i should equal 3. Invariants are talked about but not introduced yet, these will be critical to know. An invariant is something that remains constant and doesn't change.

Module 3: Postconditions or what can be shown to be true after a function returns. The first learn by doing example note the brackets that C0 uses to declare scope, you want your first assignment within the first bracket:

int endless_subtraction(int x, int y)
//@requires x > 0;
//@ensures \result < y;
{
  int temp = y;
  while (temp > 0) {
    temp = temp - x;
  }
  return temp;
}

For the next assignment, an example of the @ensures syntax:

//@ensures \result > 0 && \result % 2 == 0
//@ensures \result == x || \result == -x

In Contract Exploits, I couldn't get the gcd() function exercise to accept my answer:

//@ensures \result % x == 0 && \result % y == 0;

However it does accept as correct answer:
//@ensures x % \result == 0 && y % \result == 0;

Module 3 Introduction to Testing I had no problems answering all the assignments correctly the first time, a testament to the greatness of CS019/PAPL. For the edge cases I used gcd(1, 10) and gcd(10, 1), for the factorial function I used fact(0) is 1. There's numerous pow(base, exp) function edge cases you can come up with like pow(0,2) is 0.

Specification Functions module is interesting, writing an inefficient secondary correct function to test a much faster implementation, or a secondary function to quickly test the result. I used 100,10 as inputs to the incorrect gcd. It uses a for loop, something the text didn't discuss at all before using it but you can probably figure it out anyway (for loops are covered in Module 10). First i is declared and assigned to 1, this is the index. A condition: i must be less or equal to x and i must be less or equal to y for the loop to continue. On each iteration increment i with i++ until i's value doesn't pass the loop condition. This is a completely incorrect implementation for example purposes.

Module 4 Proving Correctness let's learn about invariants and correctness proofs. The exercise in Reasoning about Loop Invariants for int test(int lo, int hi) my answers if you're stuck were lo <= i', lo <= i + 1, and i + 1 <= hi. I couldn't get the system to accept i' <= hi which it should be, if the condition on line 10 is i + 1 <= hi. It does however accept i <= hi (without the prime). We found another exercise bug.

Aside: It's sometimes beneficial to have a few bugs in these kinds of courses, because you then challenge your own answer and go through the material again to prove your answer is correct. You'll experience this if you ever use an international version of a popular university textbook which typically sell for only 10% the regular cost. Almost always the end of chapter exercises will have been rewritten by some contractor to force students to buy the full priced version, as often the exercises will be assigned homework. Since the publisher doesn't care at all about the international version it will likely be filled with errata/mistakes in these exercises. You will have to dig deep into the material in order to assure yourself that you have the correct answer and the text is wrong. It also keeps you awake while going through the material.

There's another mistake in the very last point-to reasoning question in Proving Correctness, the second loop invariant should be i <= hi instead of lo <= i. In Termination the answers are a little tricky, i + 5 doesn't really make any sense but is still valid since i is decreasing. Proving Functions Correct the last module is very short but enough to put all this material together. Congrats you now know how to reason about a program that mutates it's variables.

Since we're on a roll let's finish this entire course, starting with Module 8 C0 Memory Model for Simple Types. In Function Calls in a C program main() is called first, which is usually at the bottom. The first learn by doing exercise you are only determining what fast pow is being called with (parameters), so x and y. The second is hand stepping the function one iteration. You can see how difficult this can become, trying to keep the entire state of a program's variables in your head. In Pyret and other functional languages you don't have to do this, since variables are immutable. The recursion module should be easy to figure out since we've already done a lot of recursion with Pyret.

The first array exercise actually runs your code, this was mine, note we are using booleans, so &&, || or !.

bool[] B = alloc_array(bool, 4);
B[0] = b;
B[1] = !B[0];
B[2] = B[0] && B[1];
B[3] = B[1] || B[0];

The second array exercise also runs your code, I copied the examples for int[]:

char[][] C = alloc_array(char[], 3);
for (int i = 0; i < 3; i++) {
    C[i] = alloc_array(char, 2);
}
C[0][0] = 'a';
C[0][1] = 'b';
C[1][0] = 'c';
C[1][1] = 'd';
C[2][0] = 'e';
C[2][1] = 'f';

In Module 9 The C0 Memory Model the first assignment asks you to open the c0 interpreter and find out what the default initialized value is for an array of type boolean. I guessed it was false instead of using the interpreter since false would be the obvious design choice. You can try the online interpreter for c0 here. At the end of this module they example a contract calling a helper function with \length(A) being used as an input in order to find the length of the array, with a warning that this is a hacky method that won't work if contracts aren't enabled in production since that assert statement won't be run.

Scope and aliasing can be difficult topics to learn, as per this paper on Prof Shriram's Brown Univeristy page where upper-level students even failed to understand aliasing. That paper is worth looking at, to see how confusing this can become in some languages like Java where one change affects two different locations, as they both point to the same thing. The exercises on this page can get tricky, remember that A = B if true means array A and B share the same memory location and are thus the same array. A[1] = B[1] if true means the values stored at those indexes are the same.

Moving on to module 10 Coding with Arrays we run into more aliasing. Here they decide to introduce for loops even though they were already used previously. The main difference between a while loop and a for loop, is you want to use a for loop when the range is known, and a while loop for unknown amounts of loops, such as waiting for a user to enter a key, or summing an arbitrary amount of inputs. Since an array is a fixed range you'd use a for loop for our array copy program. The learn by doing for summing an array, all you need to do here is declare int sum = 0 then in the body of the for loop keep a running sum, returning it outside the loop. Better code you'd have an if test to see if n == 0 then return 0 (sum of an empty array) but I didn't bother and it accepted my answer anyway.

int sum = 0; 
for(int i = 0; i < n; i++) {
   sum += A[i];
}
return sum;
// grader doesn't like sum = sum + A[i], preferring the += syntax instead


//the 'did I get this' exercise
int sum = 0;
for(int i = 0; i < n; i++) {
   sum += i;
}
return sum;
//note the 'between 0 and n' meaning exclusive of n

In Safety of Array Code you can see how difficult this can become to prove safety such as needing to guarantee the loop never reaches INT MAX. The very last did I get this question asks you to prove access to B[i] is safe, which there is only one answer and what we just covered in this module (the loop invariant). The rest of the exercises get harder and harder, but you will eventually figure them out and get better at 'point to reasoning'. For example the reasoning in array copy after the postcondition is added, how can we prove the postcondition is correct: if array B is created with length of n, and returned, then the postcondition must be correct. In Correctness of Array Code I couldn't get the system to accept my answer, which was originally A[i] == B[i] and return true, false otherwise. The accepted answer is to check if they don't equal, return true otherwise:

bool is_same_array(int[] A, int[] B, int n)
 //@requires n == \length(A) && n == \length(B)
{ 
 for (int i = 0; i < n; i++) 
 //@loop_invariant 0 <= i
 {
   if (A[i] != B[i]) 
   return false; 
  } 
  
  return true;
}

For Module 10 Contract Exploits w/Array Code the learn by doing assignment wants you to write assert statements such as assert(A[0] == 0);, checking A's elements are not modified by array copy.

The loop invariant in the first search function is suspect, as that invariant will be broken the first iteration. From the assignment questions this appears to be a typo, that it should read 0 <= i instead. In Module 11 this is a confirmed typo, as the same function is repeated but with the fixed invariant. The first search learn by doing there's a few typos you'll catch, like search(100, x, A, 0, 10) when our search function only takes 4 parameters not 5. The last exercise in Searching in a sorted Array is easy once you've done the other exercises, only the 3rd line was a problem which was assert that A[i] < x, a kind of pointless assertion since if A[i] is not x, and A[i] is not bigger than x (remember it's a sorted array), then our present iteration of A[i] must be less than x. In Reasoning about the search function the first exercise any function calls in the requires/ensures/assert contracts need to be checked for safety violations, and any statement accessing arrays in the @ensures postconditions, assert contracts or body of the code. The feedback for the correct answer on the last exercise is wrong but by now you should be pretty good at point to reasoning. The postcondition in the last exercise is correct because the array has a precondition that it's already sorted, there's a loop invariant that the desired value is not in the array so far making a call to a boolean function with the current value of i, there's 2 assert statements and an if block that if A[current loop index] is bigger than x, then clearly x isn't in the array since it's a sorted array.

At this point, believe it or not, you know all there is to know about basic imperative programming and can go through the docs of any mainstream language like Python3.x for a future AI course. What we didn't cover was manual C pointers which if you wanted could go through the slides of the full 15-122 course or try a systems course that shows how these pointers work at the assembly level. Since we care about AI and will likely be using Python soon this course was a great intro to reasoning about code that mutates memory.

We made it to the last unit on complexity.

The first example: 3n + 4 \(\in\) O(2n - 1)

• try n = 1
• 7 \(\le\) c(1) so c = 7 and technically that answer is fine, f(3n + 4) is still in O(n)

Their assignment: 3n + 4 \(\in\) O(2\(n^2\) + 3n + 1)

• Try n = 1:
• 7 \(\le\) c(2(\(1^2\)) + 3(1) + 1)
• 7 \(\le\) c(6)
• You could claim c = 2 or find a better approximation of n:
• Try n = 2:
• 3(2) + 4 \(\le\) c(2(\(2^2\))+ 3(2) + 1
• 10 \(\le\) c(15)
• True, so \(n_0\) = 2 and c = 1 though c = 2 is still a valid upper bound since f(n) is in O(\(n^2\))
• c = anything would be fine since n is always going to be bounded by \(n^2\)

There's an optional assignment, to show 2\(n^2\) + 3n + 1 is not in O(3n + 4)

• Try n = 1
• 2(1) + 3(1) + 1 \(\le\) c7
• Try n = 2
• 2(4) + 3(2) + 1 \(\le\) c10
• Try n = 3
• 2(9) + 3(3) + 1 \(\le\) c13 or 28 < c13
• We can see at this point that no matter what constant we pick for c, the \(n^2\) variable on the left will always be greater eventually than whatever we choose the constant c to be.

The did I get this assignment will be easy, whatever polynomial has the highest degree it will bound the lower degree polynomial since n can't outgrow \(n^k\). In Simplest and Tightest Bound what they are saying here is if your steps are 3n + 1, you don't want to pick any giant bound such as 3n + 1 is \(\in\) \(n^4\). You want the tightest bound, which is n, or whatever the maximum power is of f(n). If there is no variable n then the tightest bound is O(1) or constant time.

The Complexity Classes module assumes you remember logarithms the inverse of exponentiation. Let's try the example using the logarithmic properties from that AoPS page:

• 3n(2+ log 2\(n^3\))
• 6n + 3n log 2\(n^3\)
  • From AoPS: log bc = log b + log c
• 6n + 3n(log 2 + log \(n^3\))
  • From AoPs: log \(b^n\) = n log b
• 6n + 3n(log2 + 3 log n)
• 6n + 3n log2 + 9n log n
  • 6n is in O(n) complexity class obviously
  • 3n log 2 is in O(n) because the constant 2
  • 9n log n is in O(n log n) since n is not constant
  • We pick the biggest class: O(n log n)

Try the exercises for determining complexity class:

• log (3\(n^2\)) - 2
• log 3 + log \(n^2\) - 2
• log 3 + 2 log n - 2
  • complexity class: log n

In this module don't worry about their fancy square matrix functions only what the code overall structure is (nested loops where functions are called, constant time returns, etc). In Beyond n I couldn't get the last exercise about n collection of images but correctly guessed 'wh' since we're still making a copy. It doesn't matter if you don't get these immediately you will gain through experience how to estimate complexity.

The last module Experimentally Testing Complexity the cost form an+b is what we've seen before such as 3n + 7, and this chapter is about analyzing a running program to discover what the multiplying constant is (the a in an). To figure out if it's n, \(n^2\), \(n^3\) read the introduction where doubling the size of the input should get double the cost if it's O(n), four times the cost if it's O(\(n^2\)), eight times the cost if it's O(\(n^3\)). The first activity that is f(n) = an², notice the time goes from 0.02 -> 0.08 -> 0.28 -> 1.05 etc. That's roughly 4x the cost or \(n^2\). The matrix mult activity has roughly 8x the cost after n > 400. There's an error in the assignments, I couldn't get my answers accepted unless I multiplied 'a' by 100,000,000 not 10,000,000. In fact if you check their example chart for vector-above-avg-better, they have clearly multiplied 'a' by 100 million not 10 million.

The last learn by doing assignment 0.38sec multiplied by 4 is 1.52 or close enough to the next doubled input, so this function must be \(n^2\). Multiplying f(n)/n² you end up with roughly a = 0.6 and there's an interesting follow up on how you can screw up your tests since the initialization of the test is \(n^2\) but the function cost is only n.

We're reading Predicting Growth following the last cs019 lecture on complexity.

14.5 structural recursion can be described as you have built up a structure like say a list, adding n + 1 elements and structural recursion is taking that structure apart in the same way you built it up, recurring on (n - 1) like counting it's length, whereas generative recursion rearranges a problem into a set of new generated problems, basically recursion that ignores structure. Quick sort is an example of generative recursion you break on a pivot and now have 2 lists plus the pivot, that's not how you assembled that list structurally.

The Tabular Method, is not necessary as you will read in 14.8 since we can hand count these functions like we learned in the lecture. The 'question' refers to the conditionals in the cases statement like empty? and the answer is what that datatype variant evaluates to, like empty, or 0 or the recursive call in link(f, r).

"Let's consider the first row. The question costs three units (one each to evaluate the implicit empty-ness predicate, l, and to apply the former to the latter)" which is a very difficult way of saying: calling the function is +1 cost, opening up l for cases is +1, considering empty variant is +1, so 3 in total and once more if the list is actually empty which you should remember from lecture 4 Fri/9/14/18. Second row cost calculation is different from the lecture (none of these tiny costs matter of course), We get to link(f, r) and count: link +1, f + 1, rest + 1, 2 more for the addition operation, and one more to call len() again, so total 6 for the 'answer' though the lecture we saw is +1 for link, +1 for addition, and plus (k - 1), so in the lecture len() is total 5k + 4, here it's 12k + 4. You can do either this tabular method or you can do the adhoc assign + 1 cost to anything that looks like an operations that we did in the lecture and you will end up with O([k -> k]) anyway since we don't care about constants.

14.7 We've seen this notation in lectures, they are lambda functions to remove ambiguities of math notation. 14.8 recall from lectures that in english reads: 'there exists some constant C, for all inputs n in the set of Natural Numbers to the function f(n) such that f(n) is less or equal to this same constant C multiplied by some other function g(n) implying that f() is bounded by g().

14.8 Let's find the smallest constant for 13k + 4 \(\le\) ck². If k = 1 then c needs to be 17 or larger. If k = 2 then we have 30 \(\le\) 17(2²) which is true, and also true for k = 3, k = 4, if k = a trillion then 13(1 trillion) + 4 is still less than 17(1 trilllion * 1 trillion) in fact for inputs bigger than 13 the constant c becomes irrelevant. Big theta is then discussed briefly as the family of functions that grow at the same speed up to a constant. Reading PAPL, if you want to understand the math notation right click it, or if on a phone press the notation, in most browsers you should get a menu popping up from MathJax to show the TeX code to see exactly what it is.

14.9 Combining Big-oh Without Woe as we saw in 15-122 two functions in O(n) run consecutively (one after the other) are O(n + n) or O(2n) which is O(n) since constants don't matter, like f(5k + 4) is really f(k). A function f(n) that invokes z(n) in each of it's steps is O(n x n) or O(n²).

Before we look at the big-O lab let's learn some more about recurrences so we 'can feel them in our bones' as suggested by Prof K in the last lecture. I'm going to use Part V Recurrences from MIT's Mathematics for Computer Science(mcs) free book, starting on page 993 and read only up to page 1001 as cs019 will cover the analysis later (Akra-Bazzi formula/asymptotic solution) in future lectures. For now we're going to read the intro of the Tower of Hanoi, and the steps they do to solve the recurrence for merge sort.

There are lectures for the recurrence chapter of mcs, the inductive proof in the recorded lecture for the Tower of Hanoi recurrence is slightly different than the pdf:

• Our original recurrence: \(T_n\) = 2\(T_{n-1}\) + 1
• Inductive Hypothesis(IH)/closed form solution: \(T_n\) = \(2^n\) - 1
• Base Case: \(T_1\) = \(2^1\) - 1
• Inductive step: \(T_{n+1}\) = 2\(T_{(n-1) + (n+1)}\) + 1 or 2\(T_n\) + 1
• "Suppose \(T_n\) = \(2^n\) - 1. Then the successor of \(T_n\) is \(T_{n+1}\) = \(2^{n+1}\) - 1"
• Now via substitution plug in our inductive hypothesis, since we declared \(T_n\) = \(2^n\) - 1 wherever you see \(T_n\) insert that hypothesis:
  • \(T_{n+1}\) = 2\(T_n\) + 1
  • \(T_{n+1}\) = 2(\(2^n\) - 1) + 1 (substitution)
  • \(T_{n+1}\) = \(2^{n+1}\) - 2 + 1 (distributive law)
  • \(T_{n+1}\) = \(2^{n+1}\) - 1

In mcs (the pdf text), for their IH they assumed that \(T_{n-1}\) = \(2^{n-1}\) - 1, so instead of substituting for \(T_n\) they substituted \(T_{n-1}\):

• Original recurrence: \(T_n\) = 2\(T_{n-1}\) + 1
• Assume/IH: \(T_{n-1}\) = \(2^{n-1}\) - 1
• Inductive step (looking at the left side) from \(T_{n-1}\) to \(T_{n++}\) becomes \(T_n\), and we already know the value: \(T_n\) = 2\(T_{n-1}\) + 1
• By substitution replace all occurrences of \(T_{n-1}\) with IH:
  • \(T_n\) = 2(\(2^{n-1}\) - 1) + 1
  • \(T_n\) = \(2^n\) - 2 + 1
  • \(T_n\) = \(2^n\) - 1

In Merge Sort, \(T_n\) describes two recursive calls, with the total input divided in half between them, plus another recursive call to compare each list and produce the smaller value (merging). The plug and chug method they use is self explanatory until Step 3 where they introduce k = log n in order to get their base case of \(T_1\) = 0. When you see \(2^k\) anywhere in the recurrence replace it with \(2^{\log n}\) which is n because \(a^{\log b}\) = \(b\). What you should take away from step 3 is how they manipulate the recurrence in order to produce a known value of \(T_n\) such as \(T_0\) or \(T_1\) in this case.

Step 3, after k = log n has been substituted for all k:

• \(2^{\log n}T_{n/2^{\log n}}\) + log n * n - \(2^{\log n}\) + 1
  • Remember \(2^{\log n}\) = n
• n\(T_{n/n}\) + n * log n - n + 1
  • n\(T_{n/n}\) is n\(T_1\) and in step 3 \(T_1\) was already declared to be 0
• n(0) + n * log n - n + 1
• n log n - n + 1 or \(T_n \in O(n \log n)\)

Let's go back and read 14.10 Solving Recurrences again now that we know how logarithms are used to produce a known base case value, like \(T_1\). The first is T(k) = T(k/2) + c or [k -> log k] recurrence, we are looking at binary search. For this binary search example, note the trick to make this recurrence \(T_1\) and look up how the logarithms are defined for \(log_2\) k.

The next example T(k) = T(k/2) + k or [k -> k], again they have used the \(2^{\log k}\) trick to produce k/k, and they have also used the distributive property to factor out k producing k(1/k + …+ 1/4 + 1/2 + 1) which ends up simplifying to base case 1 constant + 2k. The [k -> k log k] example they get rid of \(2^k\) by replacing it with \(2^{\log k}\) which is k and this is multiplied by T(1) which is \(c_1\). The rest of the recurrence is k \(\log_2\) k which is exampled and explained in this article on power rule. \(\log_2 k^k\) is k \(\cdot\) \(log_2\) k or k.

Let's go through the lab here.

First task, why can we disregard constants, we already know why, because g(x) = 5x² + x is T(k) = T(k-1) + n which is O[k -> k²]), since we only care (in this class anyway) about finding an upper bound for the worse case, we don't care about the constant 5 or x as they are both bound by x². We've seen how when inputs grow large, x² grows so much that x and any constants are insignificant numbers (solely for worse case analysis of course).

Second task in the chapter Notation notice the brackets are needed if using the [k -> k] notation and is why the first example of O(w -> w³) is wrong, it should be f \(\in\) O([w -> w³]). There also shouldn't be any constants in the notation like [m -> 3m]. The example of f \(\in\) O(h²) should likely be f \(\in\) O([h -> h²]) or f(h) \(\in\) O(h²).

In 3 The Tabular Method we finally get an explanation what the terms 'question' and 'answer' mean, this should probably be in the book. The second row of the cases statement we already read in the book for len function, and saw it in lectures. It really doesn't matter how you count the constant units either for worse case analysis, in lectures we chose link(f, r) as +1 cost, the addition as +1 cost, and added it to 3k + 4 so total 5k + 4. If you carefully counted each operation in link and came up with 100k + 4 it'd still be the same worst case analysis of len() is in O([k -> k]). Looking back at chapter 14 T(k) = T(k - 1) + c recurrence is the same as len().

4 Big-O with less math explains how to estimate complexity a little more clearly than the book does. Task:

• 1: This could be [k -> k * log k] because for each element we make a call to another function so O(F X G). This also fits the explanation of f(x) = x log x where the recursive call is logarithmic but input stays the same.
• 2: This could be [n -> n + m] which is [n -> n]
• 3: This could be [k -> k * m²] which is [k -> k³]
• 4: This is 'a function makes calls to another function at every one of it's steps' so O(F X G) as we are linearly going through to-delete, and at each element f, we call remove(f) on another list (remove(f) then needs to linearly go through all of l to remove f).

Let's figure out 5, a function that takes input 2 lists and counts their length. This translates to two nested cases:

fun dbl-count(list1, list2):
 cases (List) list1:
  | empty => 0
  | link(f, r) =>
 cases (List) list2:
  | empty => 0
  | link(ff, rr) => 1 + dbl-count(r) + 1 + dbl-count(rr)
  end
 end
end   

Looking at chapter 14 in the book, this is T(k) = 2T(k - 1) + c. Two recursive calls each doing a constant amount of work. Let's confirm by watching T(n)=2T(n-1)+1. Indeed this is O([k -> k^k]).

• 6: My guess is that this is O(F(k) X G(k) X H(k²)) or O([k -> k⁴])
• 7: Recall from lectures that you figure out complexity cost of dependent functions from the function dependencies up, so we want to find the cost for rem-helper() first. It takes a size k input, and an element from rem-dups. We have an if-branch so we take the worst branch, and both branches involve going linearly through the entire list and looking at every element. We'll just naively calculate some costs: We go into the function, +1, we open the list, +1, we look at empty case, +1, it is empty and we return empty so 3k + 1. If it's not empty +1 for link operation, +1 to compare f to c, and worst case I guess is +1 to link f then + all the previous operations all over again until empty. So this is k + constant or O([k -> k]). Let's look at rem-dups. It's doing linear work up until it calls rem-helper() on every single element. The definition of Quadratic: 'appears when comparing each element of a data structure to all other elements in that structure' seems to fit this situation, so O([k -> k²]). Looking in the book, we see T(k) = T(k - 1) + k describes this program as well.

5.1 Recall \(c_0\) represents the base case T(0) which is some constant amount of work.

Another task, find the closed form of T(k-2) + 1 if k > 1. I will show the improper guess method where you input values for T(n) and hope an obvious pattern reveals itself, then link the correct method:

• T(0) = constant
• T(1) = constant
• T(2) = T(0) + 1 or 1 + constant
• T(3) = T(1) + 1 or 1 + constant
• T(4) = T(2) + 1 or 1 + 1 + constant
• T(5) = T(3) + 1 or 1 + 1 + constant
• T(6) = T(4) + 1 or 1 + 1 + 1 + constant
• T(7) = T(5) + 1 or 1 + 1 + 1 + constant
• T(8) = T(6) + 1 or 1 + 1 + 1 + 1 + constant
• Pattern: 1,1,2,2,3,3,4,4 etc.
  • Hint: Enter the pattern into OEIS and you find this
  • floor(n/2) (integer division, no remainder)
• T(n) = floor(n/2) + constant for n > 1
• This is [n -> log n] since at each level we only do constant work and throw away half the input.
• For a better explanation, watch this.

Second recurrence relation: 2T(k-1) + 1 for k > 0 we already did, it's O([k -> k^k]). The extra challenge relations are all in the book and lectures to solve these exist in this guy's playlist under 2.1.1 - 2.3.3.

Now we can do the second lab. The first task is a mental exercise, which you can figure out after reading the Wikipedia article on Quicksort implementation issues. Several optimizations are listed in the article, one is switching to insertion sort when the number of elements remaining to be sorted are under some threshold. Since insertion sort efficiency for small lists in the best/average case scenario was repeatedly talked about in lectures I'm going to guess this is the solution they expect you to come up with since as we will see soon every single comparison sort style algorithm has the same worst case complexity, unless this whole task is just a trick to get you to see how hopeless it is to try and improve the worst case complexity of quicksort.

The next task is to read some slides up to and including the lower bound slides, coincidentally from the same school I once went to though I wish our classes were as good as CS019. The decision tree is somewhat confusing at first, a<b means abc, acb, cab, as in 'a' appears before 'b' does in that permutation. Lower bound slide, n! leaves, there are 6 leaves (meaning branches with no children) and since this tree is n = 3, n! is 1x2x3 or 6. The lower bound proof look at the first example of logarithms here if \(2^{h+1}\) \(\ge\) \(n!\) then \(h + 1\) \(\ge\) \(\log_2 n!\) because \(b^y = x\) is \(log_b x = y\). The task is to explain how this relates to our previous problem of attempting to optimize quicksort, and these slides prove that every comparison sort algorithm has the same worst case \(\Omega\)([n -> n log n]) comparisons. However I recall him telling us in lecture that insertion sort for a small list can help with the average/best case (note worse case obviously stays the same).

1.1 Tasks, sum all integers in a list requires linear work to go through the list and get the elements so this must be minimum O([k -> k]) unless they were in some kind of sequential order where you could use a closed form solution, like n(n -1)/2. Looking at the recurrence relations chapter in PAPL, this is doing constant work at every step, so T(k) = T(k - 1) + c where the c is addition of elements. The rest of the tasks look at the chapter on Predicting Growth in PAPL and see if there is a corresponding recurrence. They did however, make sure to point out we're using integers, so this opens the door to tricks we can do on only even or odd integers such as fast exponentiation but even with those tricks the minimum runtime for going through an n sized list, and at each element doing constant work on an entire other list of size n won't change it's recurrence of T(k) = (k - 1) + k.

Formal analysis writeup, use it as a template to look at the other function.

The last optional task asks how you would implement silly flipper in linear time. The original function calls reverse at every single element. Really all it's doing is linking first, last-rest, first-rest, last-rest - 1 .. so two lists input, the orig and reversed version, link(f, ff) and then on empty case use .take() to truncate. Linear reverse is described in the above pdf on fast exponentiation.

Using the 2019 Nile assignment spec, notice the new datatype for popular-pairs(), this will be inside a recommendation instead of a list of titles: recommendation(2, [list: pair(book1, book2), pair(book2, book3)] and the return annotation is popular-pairs() -> Recommendation<BookPair>:

data BookPair:
    | pair(book1 :: String, book2 :: String)
end

From the examples you write, notice the pattern is f paired w/r, fr paired w/rr, etc.

input = [list: file("alist.txt", "1984\nAnimal Farm\nHigurashi\nLife of Pi"),
               file("blist.txt", "Animal Farm\nHigurashi\nLife of Pi"),
               file("clist.txt", "1984\nHeart of Darkness")]

recommendation(2, [list: pair("Animal Farm","Higurashi"), pair("Animal Farm", "Life of Pi"), pair("Higurashi", "Life of Pi")])

Straight forward to figure out using map/map2/fold. When you map over nested lists the x in lam(x) is the entire nested list.

Notice two consecutive 0's in the test case which will screw up your list/empty cases if you're linking on occurrences of 0 unless you filter the returned acculumator.

Template is:

data PHR:
  | phr(name :: String,
      height :: Number,
      weight :: Number,
      heart-rate :: Number)
end

data Report:
  | bmi-summary(under :: List<String>,
      healthy :: List<String>,
      over :: List<String>,
      obese :: List<String>)
end

fun bmi-report(phrs :: List<PHR>) -> Report:
  ...
where:
  bmi-report([list: phr("eugene", 2, 60, 77),
      phr("matty", 1.55, 58.17, 56 ),
      phr("ray", 1.8, 55, 84),
      phr("mike", 1.5, 100, 64)]) is 
  bmi-summary([list: "eugene", "ray"], # under
    [list: "matty"],         # healthy
    [list: ],                # over
    [list: "mike"]           # obese
    )
end

My solution was to write a helper function bmi(p :: PHR) -> Number and then filter each list for under, healthy, over, obese. Return bmi-summary by mapping over those filtered lists for lam(x): x.name, try adding more test cases like the empty case, or multiple same names. Assignment claims we can assume no entry will be zero so we don't need a test case for division by zero.

You could want tests for empty, one element, two elements, and the given assignment example:

fun data-smooth(phrs :: List<PHR>) -> List<Number>:
  doc: "Smooth heart rate data"
...
where:
  # given example from assignment writeup
  data-smooth([list: phr("eugene", 2, 60, 95),
      phr("matty", 1.55, 58.17, 102),
      phr("ray", 1.8, 55, 98),
      phr("mike", 1.5, 100, 88), phr("a", 2, 2, 105)]) is [list: 95, 295/3, 96, 97, 105]

  # empty test
  data-smooth(empty) is empty

  # one element test
  data-smooth([list: phr("spock", 3, 2, 1)]) is [list: 1]

  # two element test
  data-smooth([list: phr("spock2", 1, 2, 90), phr("spock3", 3, 4, 91)]) is [list: 90, 91]
end

One way to try this assignment is recurse on length with (prior + l.first + l.rest.first) / 3 then before your helper function returns, append the last element which we want unchanged. Before your data-smooth function returns append the first element to .rest of what helper returned, since we want the first element unchanged too.

I wrote this template:

# optional
data Freq:
  | frequency(word :: String, count :: Number)
end

fun frequent-words(words :: List<String>) -> List<String>:
 ...
where:
  frequent-words([list: "silver", "james", "james", "silver",
      "howlett", "silver", "loganne", "james", "loganne"])
    is  [list: "james", "silver", "loganne"]
  frequent-words([list: "a", "a", "a", "a", "b", "b", "c"]) is [list: "a", "b"]
  # corner case, all words are only 1 frequency so return sorted
  frequent-words([list: "james", "so"]) is [list: "so", "james"  ]
  frequent-words(empty) is empty
end

The assignment wants a list returned of words, in descending order of freq count, sorted by smallest string length if there's a tie. If the highest frequency count is greater than 1, then you return those words otherwise return the list sorted if there are no freq greater than 1 is how I interpret the assignment. I made a distinct list, mapped over it and at each distinct list entry filtered the total input list 'words' to get a list of same words, storing x.word and the length of whatever list that filter returned to get frequency("word", 3). I then obtained the highest frequency count, and used it to recurse on, creating a new list if x.count == count breaking on if count < 2. Before appending to a helper function accumulator I used sort-by() from the documentation. If the highest freq count however was only 1 then I sorted and returned the list. Maybe you can engineer a simpler way.

We're asked to take [list: 20151004, 150, 200, 175, 20151005, 0.002, 0.03, 20151007, 130, 0.54, 20151101, 78] and turn it into a daily maximum [list: max-hz(20151004, 200), max-hz(20151005, 0.03), max-hz(20151007, 130)] if the searched for month is October. Our template:

data Report:
  | max-hz(date :: Number, max-reading :: Number)
end

fun daily-max-for-month(sensor-data :: List<Number>, month :: Number) -> List<Report>:
  ...
where:
  input = [list: 20151004, 150, 200, 175, 20151005, 0.002, 0.03, 20151007, 130, 0.54, 20151101, 78]
  daily-max-for-month(input, 10) is [list: max-hz(20151004, 200), max-hz(20151005, 0.03), max-hz(20151007, 130)]
end

I completed this with 2 functions maxx(), and a helper(). I filtered sensor-data for the month desired to get a distinctlist of all dates of that month [list: 20151004, 20151005, 20151007] since if you multiply month by 100, and add 20150000 you get the desired month. Then I called helper(distinct-list, sensor-data) which tested if f was a member of my distinct month list. If so I called maxx to find the highest count that day: link(max-hz(f, maxx(r), helper(distinct-list, r))).

This chapter talks about representations, which will come up in lecture 8 again. Cases are introduced here after we have used them multiple times, but now you know the meaning of the term data variant.

Notice the typo in oldest-song() examples, using lvar instead of lver (always run the examples so they pass). In fact this chapter has a few errors, but of course they could be intentional due to that awesome disclaimer in the beginning of the book. You can rewrite oldest-song() using just a single fold statement: if (current-year - x.year) > acc.year: x else: acc. Fold does all the magic for you taking anything you return such as x (the song) and puts it in the accumulator as it iterates over the list.

The recursive data definitions that we saw in Lecture 7, and they hand step through a recursive function. Seems like this should be in chapter 1. The design recipe template from HtDP book for recursive data definitions is also shown. For the 3 exercises, cut and paste the recursive template and try filling it in to complete the exercises, notice how easy it is, that's why they shill the design recipe.

data NumList:
  | nl-empty
  | nl-link(first :: Number, rest :: NumList)
end

#|
fun num-list-fun(nl :: NumList) -> ???:
  cases (NumList) nl:
    | nl-empty => ...
    | nl-link(first, rest) =>
      ... first ...
      ... num-list-fun(rest) ...
  end
end
|#

The HtDP method is first uncomment the template, change the function name and the recursive call name to w/e name your function is. Change the annotation for the return such as -> Boolean. If you add a parameter, add one to the recursive call too. Now the function pretty much fills out itself. Try the exercises, the very last one I interpreted as:

data NumListList:
  | nll-empty
  | nll-link(first :: NumList, rest :: NumListList)
end

fun sum-of-lists(nl :: NumListList) -> NumList:
  doc: "We already wrote num-list-sum() as an exercise"
  cases (NumListList) nl:
    | nll-empty => nl-empty
    | nll-link(first, rest) =>
      nl-link(num-list-sum(first), sum-of-lists(rest))
  end
end
test = nll-link(nl-link(1, nl-link(3, nl-empty)), nll-link(nl-link(3, nl-link(4, nl-empty)), nll-empty))
sum-of-lists(test)

>>nl-link(4, nl-link(7, nl-empty))

We haven't covered 15.2 yet so just reading 15.1, covers what we just saw in the lecture representing sets using lists. Again this is a good course because you have to manually implement everything yourself including built-ins such as all the set built-ins.

There's a link to the glossary, interesting definitions in there such as links to a paper on coalgebras/coinduction. In the size() recurrence, remember the chapter Predicting Growth where common recurrences are listed such as T(k) = T(k - 1) + k is \([k \rightarrow k^2]\) because it's closed form solution is: \(\frac{k^2 + k}{2}\) hence T(d) = d + (d - 1) is also \([d \rightarrow d^2]\).

End of 15.1.3 notes your program could keep running stats about which representation of insert() to use and make a decision. The exercises here you can do in your head, thinking of types to give these operations like subset() or how remove is going to work, obviously it must remove all the duplicates if the representation allows for duplicates which is easy to implement if f == removed-thing, skip over it and link the rest. I'm not exactly sure about the last exercise, I'm assuming they want us to consider that type LSet = List is not good enough, and to create an entire new datatype of nl-set since Set datatype is already built-in, like we did for nl-link.

This is short unfinished chapter on testing. In testing blocks we have some new binary and unary test operators we can use like expr1 is%(function) expr2 or expr1 satisfies (function). See examples in the documentation.

All of this was covered in the lecture, including most of the exercises. There's an interesting writeup about how hashing functions work.

Let's try the CS019 lab for trees. The first part is just thought exercises then the lab offers us stencil code for the BT tree lab sections:

#  _____                _                                      _ 
# |_   _| __ ___  ___  | |_ _ __ __ ___   _____ _ __ ___  __ _| |
#   | || '__/ _ \/ _ \ | __| '__/ _` \ \ / / _ \ '__/ __|/ _` | |
#   | || | |  __/  __/ | |_| | | (_| |\ V /  __/ |  \__ \ (_| | |
#   |_||_|  \___|\___|  \__|_|  \__,_| \_/ \___|_|  |___/\__,_|_|

data BTree<T>:
  | mt
  | node(value :: T, left :: BTree<T>, right :: BTree<T>)
end

fun btree-in-order<A>(tree :: BTree<A>) -> List<A>:
  doc: "Returns the elements of tree in a list via an in-order traversal"
  ...
where:
  nothing
end

fun btree-pre-order<A>(tree :: BTree<A>) -> List<A>:
  doc: "Returns the elements of tree in a list via a pre-order traversal"
  ...
where:
  nothing
end

fun btree-post-order<A>(tree :: BTree<A>) -> List<A>:
  doc: "Returns the elements of tree in a list via a post-order traversal"
  ...
where:
  nothing
end

First make a tree, run it, and type 'a-tree' into pyret interpreter and click the output to see the right and left branches, or a-tree.left or a-tree.right

a-tree =
  node(5,
    node(4, 
      node(3, mt, mt), mt),
    node(6, node(7, mt, mt), node(8, mt, mt)))

>> a-tree.left
node(4, node(3, mt, mt), mt)

>> a-tree.right
node(6, node(7, mt, mt), node(8, mt, mt))

>> a-tree.value
5

The lab wants us to write various traversals, here's what I wrote for btree-in-order which is basically the other two orders as well, just rearrange helper(l) + root + helper(r):

data BTree<T>:
  | mt
  | node(value :: T, left :: BTree<T>, right :: BTree<T>)
end

a-tree =
  node(5,
    node(4, 
      node(3, mt, mt), mt),
    node(6, node(7, mt, mt), node(8, mt, mt)))

# degenerate tree from PAPL chapter 17.2.2
b-tree = node(1, mt,
  node(2, mt,
    node(3, mt,
      node(4, mt, mt))))

fun btree-in-order<A>(tree :: BTree<A>) -> List<A>:
  doc: "Returns the elements of tree in a list via an in-order traversal"

  fun helper(n :: BTree<A>) -> List<A>:
    cases (BTree) n:
      | mt => empty
      | node(v, l, r) =>
        link(v, helper(l) + helper(r)) 
    end
  end

  cases (BTree) tree:
    | mt => empty
    | node(v, l, r) =>
      helper(l) + link(v, empty) + helper(r)
  end
where:
  btree-in-order(a-tree) is [list: 4, 3, 5, 6, 7, 8]
  btree-in-order(b-tree) is [list: 1, 2, 3, 4]
end

Another lab where we rewrite map/filter/fold. Below when you see Prof K's lecture on knowledge transfer you'll understand why he makes us do this over and over. This is my first attempt at map, I wrote it like he writes software on the board in class thinking through the data definition:

data BTree<T>:
  | mt
  | node(value :: T, left :: BTree<T>, right :: BTree<T>)
end

a-tree =
  node(5,
    node(4, 
      node(3, mt, mt), mt),
    node(6, node(7, mt, mt), node(8, mt, mt)))

# degenerate tree from PAPL chapter 17.2.2
b-tree = node(1, mt,
  node(2, mt,
    node(3, mt,
      node(4, mt, mt))))

fun btree-map<A, B>(f :: (A -> B), tree :: BTree<A>) -> BTree<B>:
  doc: "Recursively applies f to the value of every node contained in tree"

  cases (BTree) tree:
    | mt => mt
    | node(v, l, r) =>
      node(f(v), btree-map(f, l), btree-map(f, r))
  end
where:
  btree-map(lam(x): x + 1 end, a-tree) is node(6, node(5, node(4, mt, mt), mt), 
    node(7, node(8, mt, mt), node(9, mt, mt)))
  btree-map(lam(x): x + 1 end, b-tree) is node(2, mt, node(3, mt, node(4, mt, node(5, mt, mt))))
end

>>btree-map(lam(x): x * x end, a-tree)
node(25, node(16, node(9, mt, mt), mt), node(36, node(49, mt, mt), node(64, mt, mt)))

I was actually surprised when it worked the first time, the magic of recursion. You can figure out filter and fold, note that btree-fold the lab wants you to convert the tree to a list, apply f to every element and produce a value just like regular fold does with a warning about complete testing, meaning every function of regular fold should be replicated here.

I do these exercises on a phone whenever I have spare time (commuting, lunch break, randomly get an idea somewhere) and often repeated the same annoying mistakes you may also run into:

• Using [list: ] instead of 'empty' which breaks everything in Pyret
• Not reading requirements carefully enough, we should probably do some materials on requirements later
• Not writing type annotations for parameters. Try the code.pyret.org type check + run feature.

The chapter on streams will explain some calculus notation converting it to a pyret function. The symbol \(\varepsilon\) is epsilon which is a small positive qty, and "functions of arity one" means one parameter or input. There's a for loop used in the check block which is an iterator. We learn more about the ( ->) notation, meaning no arguments.

The fibonacci example, change the starting values around so you can see what's going on. You first lz-link 0 and 1 then those values are mapped over, producing a new value, which gets mapped over again etc.

The streams lab is here, mostly adapted from the chapter we just read in PAPL. Everything here we've already seen. We already wrote map and map2, try to write your own filter/fold for streams:

fun lz-fold<A, B>(f :: (A, B -> A), base :: A, s :: Stream<B>) -> Stream<A>:
  lz-link(f(base, lz-first(s)), lam(): lz-fold(f, f(base, lz-first(s)), lz-rest(s)) end) 
end

fun lz-filter<A, B>(f :: (A -> Boolean), s :: Stream<B>) -> Stream<A>:
  if f(lz-first(s)) == true:
    lz-link(lz-first(s), lam(): lz-filter(f, lz-rest(s)) end)
  else:
    lz-filter(f, lz-rest(s))
  end
end

>> take(10, lz-filter(lam(x): if x > 10: true else: false end end, nats))
[list: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

>> take(10, lz-fold(lam(x, y): x + y end, 0, nats))
[list: 0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

Chapter on sharing and equality, covers what we just did in lecture.

Try Numerical methods w/Functional programming in Python, it shows how to create the same kind of streams to refine a result to better and better accuracy. To understand the weird init syntax see this, note the video button for a short YouTube tutorial.

This method of writing a draft and throwing it out as you learn more about a program you want to write is explained in The Art of Computer Programming vol 1. Go on libgen and get any draft of the MMIX fascicle or Vol 1 copy, look at 1.4.1 (page 63 in the MMIX fascicle). Knuth talks about how you would go about writing 'a complex and lengthy program'. This is the Dijkstra method from Structured Programming in 1972. Nobody writes programs this way anymore, but it's still an interesting read. Note he sketches everything on paper, figuring out all the program logic and splitting it up into smaller and smaller pieces or helper functions. After the strategic part is done he starts writing the easiest subroutine first, up the chain, until he reaches a point where enough is known about the problem that everything can be scrapped and redesigned.

This is how I do these assignments, pick the easiest functionality of updater or nile or joinlists, write out examples (tests) and from the examples sketch the logic, and work up from there. For me anyway it's easier to use paper first planning out the program as it makes these assignments much faster to write. If you find yourself sitting in the pyret interpreter for hours confused debugging a huge amount of code then consider writing a draft first and spending all your time there and the least amount of time entering and running the code.

Lecture Wed 10/17/18 the graph node code is slightly cut off but this is all in the book, plus it's only for demonstrating the point that you need a 'level of indirection' key as the content can be a duplicate. He goes on a tangent about impersonation attacks on social media.

For some reason many students confused about found() in the lecture probably because it looks like it's a parameter to reach() on the board. They are two different functions: reach(g :: Graph, nl :: Node) -> Boolean and found(nl :: Node) -> Boolean is a seperate/helper function that is called as reach traverses the graph and feeds a node to found, you'd write found() within the scope of reach so you could access reach's nl parameter to compare every node given to nl.

Complexity for graphs, the viewer asked to think about what the complexity of a graph should be.

Lecture Fri 10/19/18 video starts postage stamp size, becomes regular size at 04:02. The first 20 minutes were students figuring out how to architect a reach function. The function reach-3 he's walking through is in PAPL in 20.4.4 and he answers a lot of questions about it. This whole lecture is trying to figure out if reach-3 is correct and will actually terminate.