Foundations of Computer Science/Algorithm Design

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Algorithm Design[edit]

Algorithm design is a specific method to create a mathematical process in solving problems. One powerful example of algorithm design can be seen when solving a Rubik's cube. When solving a Rubik's cube (of any size), it is important to know the step by step instructions or algorithm to reach an efficient solution. This is where algorithm design comes into place. There are designs that breakdown the seemingly complex solution by addressing each layer (First, Middle, and Last and colors.

Please follow the link on solving the last layer of a 3X3 Rubik's cube.

Approaches to algorithm design[edit]

Top Down[edit]

The top down approach to design is starting by examining the full problem or one way to think of it is to look at the big/whole picture first. Once you have assessed the main problem then you divide the problem into smaller components or parts.

The next portion of the top down approach is to begin testing. Initially, we will have portions that are missing due to focusing on the bigger picture. In situations where parts of the problem have not been solved stubs or placeholders are used to as temporary holders.

One way to think about the top down approach is in a hierarchical setting such as a general command his troops. The general will breakdown a mission by assigning each soldier with a specific task to complete that in turn contributes to a critical part of the overall mission.

Bottom Down[edit]

The bottom down approach to algorithm design starts with the smallest units or parts of a problem. This approach solves the smallest units first and then gradually builds out the next layer or solution. Using this method ensures that the smallest unit has been successfully tested and therefore, when you start solving or implementing the next sub-solution that it will work due to the previous layers working successfully.

One example is building a car. Each piece of the car is engineered, created, and tested piece by piece. Knowing that the smaller parts work correctly the parts are then gradually added on an assembly line. As the parts are added, you know that the smaller components work due to thoroughly testing each piece. Eventually, as you walk through this process the end result is a properly functioning car.

Algorithm Design: Building Blocks[edit]

There are basic logic structures and operations involved in algorithm design. Building blocks are necessary to decide how we want to manipulate units of work. The basis of every algorithm is steps or blocks of operations. These steps/blocks of operation can be as simple as adding two numbers together. However, these blocks of operation can also be complex, for example, finding the maximum value in a list of numbers.

Logic structures in important for organizing steps into a process/solution. The following four basic logic structures describe the type of blocks used for creating algorithms:

  • procedure/function call - one example would be a single block in Scratch
  • sequence - in order to create a sequence you need a stack of blocks
  • alternatives - use of the if-then-else blocks to indicate alternate solutions for a particular problem
  • iteration - using the "repeat", "for", and "forever" blocks to build loops to solve problems

Most languages have programming constructs for basic operations and logic structures. In order to understand programming constructs you must first learn about constructed language. According to Wikipedia, a constructed language "is a language whose phonology, grammar, and vocabulary has been consciously devised for human or human-like communication, instead of having developed naturally". Similarly, a programming construct is "designed to communicate instructions to a machine, particularly a computer."