Algorithms

Intro to Programming Logic COMP-1029

Red River College

Introduction

The purpose of this module is to explore computational thinking and logical problem solving. We will learn how to break problems down into step-by-step solutions called algorithms.

We will then look at visually diagramming algorithms using a system called Activity Diagrams.

Prerequisite Modules:

• How Computers Work

Objective

Upon completion of this module, you should be able to:

• Define the term algorithm.
• Describe the characteristics of a computable algorithm.
• Compose algorithms to solve simple games and tasks.
• Follow pre-defined algorithms to sort collections of numbers.
• Diagram an algorithm using an activity diagram.

Directions as Algorithm

Imagine your journey to school today written out as a list of directions:

1. Leave through the front door.
2. Walk down to the end of the driveway.
3. Turn right.
4. Walk until you reach a east-bound bus stop.
5. Wait for the bus.
6. When bus arrives board and pay.
7. Etcetera

This set of instructions solves a particular problem: Navigating from your home to the RRC campus.

New Shoes How To

Your instructor needs a new pair of shoes.

Write out a step-by-step algorithm your instructor can follow to acquire new shoes.

Your algorithm should be as detailed as possible, describing not only the journey to the shoe-store but also the shoe selection and purchase process.

Algorithms

An algorithm is a set of instructions for solving a problem.

In other words, an algorithm is a way of capturing intelligence and sharing it with others.

A recipe is another example of an algorithm. One does not need to be an expert cook to create a meal by following a well-designed recipe.

Might a recipe written for a novice look different than one written for an experienced cook?

Seven Cell Checkers

Consider a single-player game with a playing board consists of 7 squares in a row.

The aim is swap the positions of the orange and blue pieces.

Setup

To begin, orange pieces are placed in the three leftmost squares. Blue pieces are placed in the three rightmost squares.

Game Play

Pieces can move either by sliding into an adjacent empty square, or by jumping a single adjacent piece into the empty square beyond.

Computer Algorithms

Five Requirements of a Computer Algorithm

1. The algorithm is well-ordered.
   The order in which the steps are executed matters and must be specified.
2. The algorithm is unambiguous.
   Each step must be clearly defined such that they cannot be further simplified.
3. All steps are computable.
   There are certain things computers cannot compute, such as division by zero.
4. The algorithm produces a result.
   Results allow us to verify if an algorithm is correctly solving a particular problem.
5. The algorithm will always finish in a finite amount of time.
   An algorithm that runs forever will never produce a result. See requirement #4.

Sorting

Sorting is a common problem handled by computers.

Consider how most webmail applications allow us to sort our email messages in several ways: date received, subject, sender, etc. Each time you reorder your email, your computer uses a sorting algorithm to sort them.

Since computers can compare a large number of items quickly, they can sort large collections at incredible speeds.

Sorting Activity

Selection Sort

1. Lay out all your unsorted items in a row.
2. Place a marker below the first item in the list.
3. Compare the item in the marked position with all the other items to the right of this item.
4. If you come across an item that is smaller than the marked one, swap these items.
5. Move the marker one to the right.
6. If the marker hasn’t yet reached the end of the list, go to step 3.

Do this a few times, each time starting with a randomized list.

How many comparisons do you need to make to sort the list each time?

Selection Sort Visualized

Efficiency of Algorithms

For any given problem, it is possible that there is more than one algorithm that represents a correct solution.

Two important considerations for judging the efficiency an algorithm are:

• Time Efficiency: How long it will take to solve the problem?
• Space Efficiency: How much memory will it use while solving the problem?

Let’s investigate the time efficiency of a number of popular sorting algorithms:

sorting-algorithms.com

Visual Algorithms

It is often useful to draw out a algorithm is such as way as to visualize the required processes and decisions. The above flow-chart describes an algorithm for making friends.

What's Next?

In this module we learned how to break a problem down into a step-by-step algorithm.

We’re now ready to bring these concepts to your work with the Scratch programming language. Programming is the art of turning algorithms into instructions that a computer can follow.