Single-dimensional array and simple looping activities of significance

Question

I give a lab on single-dimensional loops and arrays. By "single dimensional loops", I mean that there is no nesting of loops. (I will later give a second lab on multi-dimensional loops and arrays, but that is not this lab.)

The problem is that few of the problems on my lab right now are of any consequence. What I want is to provide activities that are significant in computer science. These students are still early enough that I'm not requiring nested loops, but that doesn't mean that they can't be exposed to significant ideas. The trouble is, what are those ideas?

Good activities would either be algorithms of significance, or they will set the stage for later comprehension of deep and important ideas in CS.

What are lab activities that can be done without nested loops that reflect important problems in Computer Science?

Answer 1

A variant on the ENIGMA machine encryption works well in a single loop, and is sufficiently complex to give students a real challenge.

The core idea of the ENIGMA machine for this assignment is that (1) a number is given as an initial key, and (2) every prior letter used influences how the next letter will be encrypted.

So, use a modular circle of encryptable characters (I chose ASCII 32 () to 126 (~), and just like a Caesar cipher, take your first letter and move it over by the key values. But now modify key itself by adding the ASCII value of the inputted letter that you just encrypted to it.

Unstated in that description is the idea of creating a modular circle that doesn't begin from 0. This is a pretty complex idea for students at this level to work with, and it helps to give them some guidance in this department.

Following this formula with the initial key 16, the statement

Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.

Should get you:

Vf|0Pdhx,2RTch)=CZ`o0JPRey:<DTt%;Nnuw-6<Oc$':J`hq'GN^q'0P`o0ENXl-1APeo~%4Iu68Xgm&FUWlv'6b#'7FJPZqw|=GVvcmpv*?Y&FHW\|"(-7;=RX]}3Ccx"(HYl|.>R\q{,;[py{1QS`m.<BQqs'-MQdjl"(-MSe{}+Y 

Ask students to similarly create a decrypt method, but offer far less guidance than you did for encrypt. It will require them to make sense of all of the mathematical operations that they performed in encrypt in order to successfully undo it.

You can also provide them with a few mystery strings to uncover. The first student who successfully follows the directions given by the mystery strings gets some sort of prize or extra credit. (The mystery strings themselves explain this; no need to give the secret away in advance.)

Answer 2

The Dutch National Flag problem is linear in running time. Essentially sort an array with only 3 distinct values each of which may appear 0 or more times. (not length 3). You are allowed only one pass over the array, so the solution is a single while loop with some prior initialization.

It was probably originally posed by Dijkstra. It is mentioned in David Grits's The Science of Programming where it can be solved very nicely by posing pre and post conditions using David's ideas of finding invariants from pre and post conditions.

You can also make it a simple object oriented problem if you like by using objects as the array elements, for example.

A more interesting formulation of the problem refers to the Dutch National Flag which is a Tricolor: Red over White over Blue. You have an array that has some jumbled up red and white and blue cells, zero or more of each. You want to move all of the red cells to the left end, all of the blue cells to the right end, with the white cells in the middle. The restriction is that you may make only a single pass over the array. The correct solution is very creative and demonstrates the power of loop invariants.

I have mentioned this problem in answers to other questions here. A search for "dutch" on the questions page will reveal them.

Solving it without hints can provide a gigantic a-ha moment for almost everyone.

If students can do the classic version, they can also think about a modification that will handle 4 values instead. From that you can talk about the inherent complexity of sorting values from any finite set.

Answer 3

You could use introduce elementary (one-dimensional) cellular automata.

Basically, you represent a single row of cells as a simple array. Then you write a function that takes an array and applies the rules of the cellular automata to each cell (usually based on the old value of the cell and its two neighbors) to return a new array representing the next generation.

It's dead simple, but still results in pretty cool patterns if you display (or just print to console) the generations one after another. Here are some examples:

Answer 4

Grades. Works especially well around final exam time.

You can find the average. Find the highest and lowest. Find the average with the lowest dropped. Find the most common grade. Count how many are in the range 90-100%.

Given an array of grades assigned for each class, calculate GPA.

Given 3 arrays that represent labs, quizzes, and tests calculate the final average. Each array can be weighted differently to match whatever your grading scale is. Ex: I would have labs weighted at 10%, quizzes at 20% and tests at 70%.

Answer 5

I recommend to check out <algorithm>, <numeric>, and related C++ headers. There are literally tons of linear algorithms of utter significance. From the top of my head, copy, reverse, find, lower_bound, accumulate, iota, partial_sum, adjacent_difference, inner_product are well deserving much attention.

Answer 6

One small, but significant, algorithm is to find Euler's Number.

The irrational number $e$, also called Euler’s number, is approximately 2.71828. The number is significant both to the culture of computing and has a role in such functions as computing continually compounding interest.

Euler proved that this number was irrational by showing that it was equal to the infinitely expanding series $1 + \frac{1}{1} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!}$…

Ask students, then, to create a function that, given a number of iterations, returns the approximation of $e$ given by that many steps.