Algorithms

Today’s lab gives you more practice designing computer algorithms: the sets of steps that a computer takes to solve a problem. You’ll design an algorithm with your lab and then implement it as a homework problem. Next we’ve set aside time for you to begin work on MP0, our first machine project checkpoint, which is due in under two weeks!

1. Algorithm Design and Implementation (30 Minutes Total)

In class we’ve begun to discuss the process of designing and implementing computer algorithms. Remember that an algorithm is not computer code—it’s a way to solve a problem that can be implemented in a variety of computer languages. In this way we distinguish between the algorithm itself and a specific implementation of that algorithm.

Today we’ll give you more practice designing and implementing a computer algorithm to solve a specific problem. Our goal is to focus your attention on the process: design first, implementation second.

1.1. Algorithm Design: Least Common Multiple (10 Minutes)

Too often beginning computer scientists tend to rush into trying to implement a solution before they really understand what they are trying to accomplish. Trust me: if you don’t know what you are trying to do, you’ll never be able to code it up. Even when you do know exactly what you are trying to do it’s still often hard to translate that into working code. But without a design you are truly lost at sea.

So today we’ve set up the homework to prevent you from just jumping right in to the code You must spend the next 10 minutes designing a algorithm with the rest of your lab. Only then can you begin to implement and test it.

The problem you are going to solve is computing the least common multiple (or LCM) of two integers. As it’s name implies, the LCM is the smallest number that is a whole multiple of each number. So, for example, the LCM of 4 and 6 is 12, because 12 is 4 * 3 and 2 * 6.

You can easily find complex and efficient algorithms for computing the LCM online. However, our goal today is not to force you to implement something sophisticated. Rather, you should take advantage of the fact that computers can repeat operations extremely quickly—one of their most important capabilities. We can frequently use this capability to our advantage, since it can allow us to use a simpler but less efficient approach to solving a problem—at least in cases where we are not too concerned with how long the computation takes.

Work with your partner and other members of your lab to come up with an algorithm to compute the LCM. Talk to each other, brainstorm on whiteboards, exchange ideas, work through examples. About the only thing that you should not do is use your computer.

Your lab may develop several different solutions to this problem. That’s great! If you do, discuss some of the tradeoffs between the two. Which is harder to understand? Which do you expect to complete more quickly?

1.2. Implement LCM (20 Minutes)

Next, you should 20 minutes on our in-lab homework problem, which you can find on PrairieLearn. Just like last week, you will only be able to access this homework beginning 10 minutes after your lab starts and ending 20 minutes later. If you are in the wrong lab you will not be able to complete the lab homework assignment—please attend the right lab next time.

Please feel free to work with a partner or in a small group on the lab homework. But every student must submit their own answers to receive credit.

2. Getting Started on MP0 (Remaining Time)

We’ve set aside the remainder of lab for you to work on MP0. Please take advantage of this opportunity to work with your lab mates and course staff! If you haven’t started, your goal should be to get to the point where you have submitted for the first time—and maybe even earned a few points! If you have started, your goal should be to make some progress. And if you’ve finished 1, then help out others around you.

3. Before You Leave

Don’t leave lab until:

You’ve designed your LCM algorithm and completed our second lab homework problem
You’ve made some progress on MP0…
And so has everyone else in your lab!

If you need more help completing the tasks above please come to office hours or post on the forum.