‹ go back

CPSC 110: Weeks 5 and 6.

Published 28 March 2021 at Yours, Kewbish. 1,542 words. Subscribe via RSS.


This post is unlisted and has been archived. This doesn't represent my best work; please check out the posts listed here instead.

Introduction

Spring break is almost over, and perhaps so is my CPSC 110 sprint. For a lack of creative inspiration to work on anything other than practise problems, I’ve been spending a good amount of my remaining break on very routine homework, including CPSC 110. The course’s started to delve further into the theory side of things this couple weeks, and it’s been very interesting to see how my methods for designing things in Racket have evolved with each successive module.

Part of me being able to complete a rather surprising (to me, at least) number of weeks over a short amount of calendar weeks was conveniently forgetting to do both the problem sets or labs for the past couple weeks. I’d become part of my habit to do those after writing up a week’s set of notes, but I think I got a bit too carried away somewhere in between weeks. In the process of having to go back and do said problem sets and labs, it was interesting to see how difficult it was to remember what techniques I was ‘allowed’ to use. Somewhere between 6 and 7, some template rules get changed, and some shorthand is now added, which I almost reflexively tried to use before realizing I was supposed to operate in on a past set of guidelines while looking at problem set solutions. It’s remarkable that I even forgot that there was a change in shorthand allowed - I think that’s part of what makes CPSC 110 one of those fundamental courses: it encourages you to look at things very systematically, and builds on what you’re supposed to do systematically, systematically. (In other words, the addition of new parts of information follows nicely from past weeks, and everything is consistent.)

As always, you’re probably uninterested in the contents of this post unless you’re taking CPSC 110 yourself or have the very niche interest of learning how to program in Racket. Feel free to check out some of my other posts (I promise I don’t blather on about Racket this frequently usually, but Spring Break sort of encouraged me to do as much CPSC 110 as I could).

Notes - Week 5

This week dealt with helper function design, as well as more information on inbuilt natural number functions.

  • natural numbers are good to illustrate examples of self-referential data definitions
    • unlike lists, don’t need to cons at all
      • the one off statement is either zero or (add1 n) => why it presents recursion
    • use (add1 n) to add 1 to a number and (sub1 n) to subtract 1 => useful for recursion
    • add n to the template => easier to work with contribution of first rule
  • function decomposition => breaking design problems down to one atomic purpose
    • in past weeks, we’ve added helper functions: this week dives further into when to add them and how to do so
  • places to put helper functions:
    • where there’s a reference => natural place to insert a helper function
      • world design recipe => also using helpers
      • where types of what you’re operating really changes
    • when an expression operates on a list => arbitrarily far into the list
      • because this is a form of recursion
    • when a function shifts into a new knowledge domain
      • knowledge domain => when you need to operate on a new facet of the data, or change what you need to ‘know’
  • essentially breaking everything down into individual steps for the problem => can begin seeing this in the (check-expects)
    • sometimes avoid referring to constants in these to fully illustrate the example
    • function composition only needs to test the composition
      • no need to deal with base case
      • can essentially test the two only together and call function in the check-expect
      • make it as obvious as possible if something’s gone wrong
    • work systematically referencing the wishlist as a todo list

Notes - Week 6

This week describes binary search trees, as well as mutually referential data.

  • have now graduated to BSL with List Abbreviations => use (list 1 2 3) to declare a list without all the (cons)s
    • if (cons) is applied to a list, concatenates it to the beginning
    • (append l1 l2) takes two lists (not elements), and appends l2 to l1 so the list is flattened into (list [elements of l1] [elements of l2])
      • if you instead run list (or cons) on the two lists, you get a list containing two lists (not flattened, and with 1 list for (cons))
  • here, we could use a self-referential data definition to create a list of any given element => concatenating an element onto the self-referential data def
    • can sort the list and use (first) and (rest) to traverse the list in order of magnitude
      • on average, n/2 elements searched
    • however, faster on average to use a binary search tree, where elements are ordered on branches
      • middle value goes on the ’top’ of any given fractal part of the tree
      • smaller values go on the left, larger values go on the right => of a given element
      • balance the tree (shift things around) if it’s looking sort of like a list => at that point you have no advantage
  • BST data definition utilizes compound data definitions with 2 self-reference cycles
    • create a struct with fields for BSTs for both left and right branches stemming from the given element
      • specify invariant rule => right/left interpretations
    • run (fn-for-bst) on each self-reference => natural recursion
    • rendering BSTs => also with recursion
      • for the check-expects, remember to order according to test ‘difficulty’ and test each case (right/left to right/left)
  • searching BSTs is a matter of determining whether the searched-for value is greater than, equal to, or less than the current node
    • then traverse either the left or right BSTs depending on above condition
  • arbitrary arity tree => form of data that’s arbitrarily large in two dimensions
    • arbitrary (as in length, can be an unspecified number of elements long), arity => arbitrarily long in two dimensions (folder => file)
    • to deal with these two dimensions, will need 2 cycles in type reference graph
      • generally have a data definition for an element, and one for its listofelement => use arbitrary data definition template
      • these two data definitions refer to each other => Element has a ‘children’ field that refers to its list, and ListOfElement refers to Element in its (cons) branch of the one-of
      • known as mutual reference
      • reference arrows => describe mutual ref, then self ref, then find the normal ref
  • mutual reference template involves two HtDF problems, one of each type
    • name them with ([fn]--element) and ([fn]--loe), or similar
    • at the points with a reference to the other type of mutual reference => insert a natural mutual reference recursion helper
    • test the base case (may not be the element case that’s the simplest)
      • base case is the case in which no mutual reference is invoked => generally the empty or false of the LOE type
      • use (check-expect)s to clarify what the expected output will be
    • usually, both functions produce the same type of data in the end
  • backtracking search => use special signature of [type] or [base]
    • usually would be using something like an exception, except BSL doesn’t have those
    • search for the desired value in all children, if not, runs on all siblings as well
      • if it produces false => check the siblings / rest of the LOE
      • use the (if (not (false? (fn-for-loe)))) to check above condition

Conclusion

I’ll save the notes for Week 7 for the next week I’m looking for something share - I’d rather keep the amount of double-weeks to a minimum. (I also doubt there’ll be many more double weeks, since school’s started again.) I’m now past the midway point and on a good streak of work, so I hope I’ll be able to finish the course well before school ends in June. I plan to spend some of the summer revising for the challenge before I actually take it, which I hope will be enough time. I’ve looked at past exam papers, and they don’t seem too bad at first glance, so let’s hope a couple months of review is enough.

In other news, I helped run a hackathon this weekend, which was an amazing experience. vhHacks 2021 was a super fun event to organize, mentor, judge, and run workshops for, and I was incredibly impressed at everything that was submitted (so congrats!). The majority of hackathon-esque events I’ve been to have been online, which is usually something people label as ‘unfortunate’, but to be honest, there’s something sort of nice about async hackathons and weekends spent grinding away alone at a project in the comfort of your office. I hope some of the wholesome hacker vibe that I personally got at my first online hackathon was successfully transmitted somewhere in the process, and that, most of all, it was fun1. I might write a bit about organizing the hackathon (not that I know what to write about regarding the entire event) in the future, but for now, I’ll go back to catching up on problem sets and labs.


  1. Preliminary survey results with people I know has been positive, but I’m entirely sure they’re biased and at least 50% trying to validate me, which is still much appreciated. ↩︎


‹ go back