CSC150 — Content

Lecture Notes

Sep 14: A recursive picture with triangles: part A, and part B—part A refactored.

Sep 16: A draw and turn fractal.

Sep 19: Directory structure traversal.

Sep 19: Tracing some little recursive functions.

Constructs with their syntax: up to and including Sep 19.

Exercise: without a for loop, draw this snowflake—you may use K from lecture.

Exercise: the "Can" image. The file includes an image so must be opened in DrRacket. Here it is as text, and the image.

Exercise: trace a function drawing a mystery image.

Sep 26: Subsequences.

Sep 28: Filesystem path hierarchy/tree.

Sep 30: "Quiz" to trace list nesting functions.

Sep 30: Pairing up elements of a list.

Oct 03: Carefully traced list recursions.

Oct 05: Talked about variables, values, call-by-value, and mutation. See the bulletin board for the code. Warning: don't mutate (i.e. 'set!') in Assignment 1 — it won't help and will only distract you from the most straightforward approach.

Oct 07: Symbols. We also 'traced' the recursive definition from the assignment, and talked about incremental problem solving: in this case making a function returning a particular number, then changing it to return a random number, then either a random number or a unary minus of a fixed number, etc. Then there was a fire drill.

Oct 12: Structs used to implement lists as linked lists.

Oct 14: Is a linked list of numbers in increasing order.

Oct 17: Another look at accumulating recursion.

Oct 17: A HOF and a deep recursion.

Oct 19: Mutation during recursion.

Oct 19: Implications of (Strict) Call-by-Value.

Oct 19++: Passing variables. And COMPLETELY OPTIONAL implementation of backtracking control flow, which I showed to some students who stayed after lecture.

Oct 21: Lexical scoping.

Oct 21: Continuation of Oct 17 list recursions.

Oct 24: Stacks: via lists and trying them.

Oct 26: Stacks: via linked lists, object-based API, and trying them via both APIs.

Oct 28: Stack-based expression evaluation.

Nov 07: Binary Search Trees.

Nov 11: Binary Trees.

Nov 16: BSTs: factored out child selection in preparation for delete function.

Nov 21: A Sorted Linked List to compare runtime efficiency against BSTs.

Nov 25: Sorting by split and combine: Mergesort and Quicksort.

Dec 02: Heaps.

Tests

Midterm 1

Newish topics: Stacks, Vectors, Binary Trees, Binary Search Trees, Mutable Linked Lists.

Not included: Mergesort and Quicksort.

Quiz 1

The Quiz.

Midterm 0

Extended discussion of primitive recursion and list-min.

Quiz 0

version A and version B. Because we had just enough room to alternate the seating, only version A was used. Consider version B more practice. And you should then make up your own variations as practice in making up variations for practice (yo dawg).