I am assembling some projects in my Challenge Topics repository on GitHub (https://github.com/Rachels-Courses/Challenge-Topics). These are projects that I’ve written to show in class, asking the students to come up with a better algorithm to solve some problem.
Here are some examples:
With this one, a linear and a random search are implemented to search a sorted list. The challenge is to ask students how a better searching algorithm can be done for our sorted list, where we do searching more intelligently than just going from the beginning to the end.
You can also expand this to talk about creating a data structure that auto-sorts when items are inserted, and whether to implement this by sorting immediately after an insert, or do a smart-insert and look for the appropriate position for the new object.
For this one, a list of cities are generated at random points on a map. The random paths generator essentially adds paths between cities in the order that the cities were generated. The challenge here is to ask students how to build a more intelligent route, visiting all cities once, and returning home afterward.
So for example, in the above screenshot, the salesperson goes from Grandview to Leawood to Raymore, which is a bit nonsensical.
You can also demonstrate Dijkstra’s Algorithm as well.
Another problem we can look at is detecting how two objects are colliding, such as in a game. There are multiple ways to handle it – for example, you could do bounding-box collision detection and check the perimeter of the images themselves, each edge. Pros and cons? Could be empty space colliding, such as the top-right of the bunny and bottom-left of the dog.
Another option is to use the distance formula and figure out what a good distance is before considering the two images colliding. This works well for circular objects, but might not work as well for an oblong object.
Or, you could do a combination of both, maybe each object has several bounding boxes within it (like the dog’s head, and dog’s torso).
The idea behind these exercises isn’t to necessarily get the “most efficient” algorithm to any given problem, but to have students brainstorm and actually think about the problem visually, instead of having everything be intangible. Having pure console-based applications using just cin and cout can be boring, and even when implementing something modelled on a real-life system, it can be hard to really get into it. Even many command-line programs use something like pdcurses to give more organization to the presentation of the program.
So by using the SDL library, we can still write C++ code and demonstrate some problems in a more graphical way. Even if SDL is not available on the students’ school computers, if the teacher has a laptop they can install SDL2 on their own and display it to the entire class for a more social lesson.
Learn more about SDL at: https://www.libsdl.org/
And my challenge repository is at: https://github.com/Rachels-Courses/Challenge-Topics