CPSC 110: Week 11.

Introduction

Last summer, I wrote a series of posts about my experience with Harvard’s CS50 course, and this spring, I worked through the majority of another series of notes, this time on UBC’s CPSC 110 course. Over this summer, I’ve decided to finally spend some time just developing whatever I feel like, and self-studying topics that I find interesting, one of those topics being reviewing CPSC 110 for the upcoming winter session¹. While I was going through the course for a second round and looking through the notes I took the first time, I realized I never posted the final week’s worth of notes for CPSC 110.

So here they are, along with an overview of the course, my likes and dislikes, strategies I’m using in order to prepare, and my feelings about the course as whole. The notes that follow were written as I went through the course the first time, and while there’s a lot of conceptual understanding that’s changed since then, I think the module summary’s decent as it is. I’ll save the more introspective musing and thoughts on the course for the latter sections of this post.

Like the other posts in the CPSC 110 saga, these notes probably won’t be useful for you, unless you’re also taking the course, or have decided to implement some sort of cyclic data structure in Racket as well. If you belong to one of those two sets of people, you’ll probably want to start at the beginning, and if not, you might want to check out my other posts: I like rambling about CS, personal knowledge management, and vaguely tech-oriented things.

Notes - Week 11

This week covers graph structures, including those that have self-referential loops through the introduction of the (shared) expression.

• information naturally forms a graph when there are multiple connections to other nodes
  • directed graph => arrows only go in one direction
  • cyclic => cycles (or loops) can exist in the graph
  • unlike lists, there isn’t a natural order of sorts, and unlike arbitrary-arity trees, there isn’t a direct or unique one-to-one mapping and cycles can appear
• HtDD for graphs is similar to other HtDD recipes
  • define a struct for the room, and include a field for a list of other nodes to link to
  • cannot define variables normally as there can be cycles in graph
• use (shared) to define looping variables
  • only available in ASL => check if correct language used
  • same structure as (local) with the square brackets for definitions and the final expression
  • similar scoping as (local) where variables are only valid within the expression
  • define each -X- variable and use the same variable in the list of linking nodes => numbers are convention, letters are preferred
  • i.e.

    (shared ((-A- (make-room "A" -B-))
            (-B- (make-room "B" -A-)))
            -A-)
    

• use accumulators (visited accumulator) to check that you’re not in a cyclic loop
  • HtDF for graphs combines the local and accumulators modules extensively
    • also make use of the worklist and context preserving accumulators when necessary (depends on problem)
  • remember that variables that don’t change over the evaluation of a function don’t need to be set as an accumulator (!)

Self-Study

Somewhere through the first module of the course, Kiczales (the professor) points out that just following along with the video lectures, and even taking meticulous notes, isn’t enough to learn the material in CPSC 110. A large part of the learning comes from the practice: be it through problem sets, labs, or the extensive problem bank. I agree - though maybe with a caveat. I found practicing all the concepts to be pretty straightforward the first time round, but coming back this summer to re-attempt many of the problems was a decent challenge. I wanted to see how much I could remember in terms of design recipes and function calls without having the lectures to hold my hand through everything, so I’ve just been jumping straight into each module’s practice problems.

I’ve been trying to choose problems that are marked at least a blue square, though I will sometimes go through the shorter green circles if I’d like to rebuild my understanding of a topic. CPSC 110 was designed to be an introductory CS course, so besides the first couple weeks of learning design templates and familiarizing myself with the language, the theory behind topics isn’t that difficult. I didn’t really see a point in grinding through easy problems to falsely feel productive, so I thought I’d try to tackle some of the more difficult problems. Another point about CPSC 110 being designed for beginners: there’ll be a lot of tedious template syntax and repetition in the beginning. I sort of ignored this my first time round, completely forgoing the spd/tags expressions and copy-pasting trivial tests. In hindsight, that wasn’t a good idea - going through all the templates, though very tedious and boring, drills them into muscle memory, and is good practice for further modules. The bit about tests and monotony also goes into my last overall goal: not relying on solution sets or videos for help. In the exam, I won’t have these resources at hand, so since I’ve sort of got the basics down, I want to ensure that I actually do understand what I’m doing. That’s also part of the reason I like the labs so much - there’s no answer key, so even if you’re tempted to go check and see if your tests and function design is formed correctly, you can’t. Coming back to Kiczales’ point, I think practice is certainly an important part of the process, but so is choosing practice at a difficult enough level, persisting through the tedium, and teaching yourself through it without opening solutions or even watching the lectures, if you’ve gotten to that point².

Conclusion

Altogether, CPSC 110’s been an insightful learning experience, and one that’s been pretty positive. One of my favourite parts of the course was by far module 8, on abstraction, though the (local) expressions covered in module 7 would be a close second. There was something about the way creating fold functions obviated the need for a lot of repetitive function design that somehow clicked with me. I found everything about encapsulating templates into abstract functions, and using built-in functions very intuitive. Composing built-in abstract functions was like putting together a puzzle, and I had a lot of fun working out where I’d need a (filter) as opposed to a (map), and so on. It was also interesting to see the role abstract functions played in functional programming, and I’m beginning to see why developers in Javascript or Python sometimes tend to this sort of paradigm.

On the other hand, one of the things I didn’t quite like was module 9, on generative recursion - or at least, I didn’t like it the first time round. The module was a lengthy series of videos playing off one central problem set, and while I’m happy it was explained in great detail, it was honestly a bit boring to sit through. Maybe it’s just my brain not being used to recursion, but the concepts of backtracking and generative recursion as opposed to structural recursion didn’t really stick. Oh well - here’s to hoping it’ll be more manageable this time round.

My opinion on CPSC 110’s definitely changed since I first looked into the course late last year. In the beginning, I was definitely very skeptical about Racket and the whole design recipe system - I was one of those “oh, but Racket isn’t used in the ‘real world’” people. At first, I thought the unique (to me, at the time) syntax was a bit constraining, but after going through a good chunk of things a second time, I think I’ve gained more of an appreciation for how structured and logical everything is. For example, the first couple weeks of trudging through HtDD and HtDF recipes sort of turned me off them: I thought they were tedious, repetitive, and annoying. Looking back, I appreciate how orderly everything is presented: the course certainly lives up to its moniker of “Systematic Program Design”. Having a bit of hindsight’s made me more appreciative of the theory and concepts that were taught in the course, and besides just understanding them better, knowing where each topic’ll be used again in the course gives me an overview and a map³ of sorts to guide me through my studying.

I’m still working through my second run of the course - I’m currently somewhere around module 9 (which, as an aside, I sort of hated the first time, but we’ll see how it is this time). For the rest of the summer, I’ll likely be spending some time here and there to continue reviewing, and start attempting practice exams soon. Successfully challenging the course means I won’t have to suffer through six courses in my first term, so that’s an excellent motivator for me to do my absolute best. Besides CPSC 110, I’ve been looking into some maths and some CS theory - spending a bit of time researching and looking into topics that I’m interested in. It’s been really nice to have the freedom to finally cross some of the learning I’ve wanted to do for ages off my todo list, and I’m looking forward to what the rest of the summer holds.