Previous Series Links:
Intro to “Introduction to Systematic Programming” Course
Introduction to Systematic Programming – Week 1
Introduction to Systematic Programming – Week 2
Introduction to Systematic Programming – Week 3
Introduction to Systematic Programming – Week 4
Introduction to Systematic Programming – Week 5
Introduction to Systematic Programming – Week 6
Introduction to Systematic Programming – Week 7
Week 8 is the final week of Introduction to Systematic Programming! It’s been a crazy ride and I know I’m a touch behind in the blogging schedule, but I wanted to make sure I got this last blog out to you all before I start working through my next class – Python! Anyhow, here goes, week 8 of Systematic Programming – Generative Recursion!
Lesson 1 – Generative Recursion
Generative recursion is when at each recursive call, you generate new data with each subsequent recursive call. This is as opposed to structural recursion, where you take the next item on a list/from a group. This also means that there is no guaranteed end to the recursion, so that must be addressed in your program/function structure.
Lesson 2 – Fractals
Fractals are images that have a recursive structure, and are sometimes known as “math art.” The example used in this lesson is a Sierpinski Triangle, and it’s essentially a design of triangles that repeats and grows through each recursive call. What’s important to remember when using HtDF for Generative Recursion is that when you run the check-expect, you’re looking at the image produces. This can really help you figure out what your pattern is and correct errors before you get too deep into your code. Additionally, you have to define a constant of “cutoff” to answer the problem of no natural end to the recursive calls!
Lesson 3 – Termation Arguments
Colat’s Conjecture states that:
– If a # is even, the next is n/2
– If a # is odd, the next is 3n+1
This fractal is commonly known as “hailstones,” and it’s a recursive function that has no base case. How does it stop? With the 3 Part Termination Argument, of course!
– Part 1: Base Case – Usually in the Function
– Part 2: Reduction Step – What is the next problem?
– Part 3: Argument – The argument is what is the repeated application of the reduction step that eventually results in reaching the base case.
This 3 part termination argument should ALWAYS be used with Generative recursion! You need it in order to end the function!
Lesson 4-12 – Introduction to Search Problems
The rest of the videos in this week are honestly just setup for the students to be able to create a Sudoku puzzle. There’s really nothing relevant to the learning of Dr. Racket or the Intermediate Student Language. SO! I’m going to summarize them by saying:
The search algorithm that is used in this Sudoku solution is the brute force search, which generates all possible solutions and then picks the most ideal one.
Lesson 13: Course Wrap-Up
According to the awesome professor’s summary, what he hopes the students were able to take away from this course on a base level, is how the computational systems in our everyday life function. Additionally, it was intended that the students can now design small programs with confidence! The point here is not that programmers will be infallible, but that mistakes don’t completely derail your design process, and that you always have a tool in your kit to try out to fix an issue.
Next, we went over a bunch of the Recipes in:
Finally, two important questions were answered from the course forums…
- Will the HtDF Recipe work in other languages?
- The answer given is OF COURSE! It’s important to note though that some languages may have more concise solutions to problems, but the concepts learned in this course do translate and give you a solid base for how to begin any design problem.
Q. What’s the most important thing we learned?
A. How to see structure in code! Being able to identify templates, references, idioms and other higher-level code structures will develop into a strong background in being able to not only code, but in being able to read and understand the code of others.
Week 8 & Course Summary
So overall taking a look back at this course, it was TOTALLY worth the time put in. Although I’m not sure when I’ll ever actually utilize the Intermediate Student Language, I think the concepts of the How to Design Functions recipe are sound. Not only do they work for ISL/BSL, but they, in my opinion, most certainly serve to support the concept of breaking complex problems into smaller, more manageable chunks in order to avoid frustration and feeling overwhelmed. PLUS this class went over a lot of programming basics and helped me to solidify my understanding of tough topics (*cough*recursion*cough*), which will be useful in whatever language or project I decide to tackle next.
All that said, I do believe I passed the course with the requisite stats to gain myself a certificate of completion with distinction, so let’s play some fanfare and get on to the next challenge!
Questions/Comments?
Feel free to comment here on my blog, or find me on Twitter @DokiDara.
