OAE Computer Science (054)

An algorithm is a step-by-step procedure for solving a problem or accomplishing a task. Algorithm design involves creating these procedures, while representation concerns how algorithms are expressed and communicated.

Every algorithm must possess certain properties to be valid and useful. Finiteness means the algorithm must terminate after a finite number of steps. An infinite loop is not a valid algorithm because it never produces a final result.

Definiteness requires each step to be precisely defined with no ambiguity. Instructions like "add some numbers" are not definite because "some" is vague. "Add all numbers in the list" is definite.

Input specification defines what data the algorithm receives. This might be nothing, a single value, or complex data structures. Output specification defines what results the algorithm produces.

Generality means the algorithm should work for all problems in the intended class, not just specific instances. A sorting algorithm should sort any list, not just one particular list.

Brute force algorithms try all possible solutions until finding one that works. While often inefficient, brute force approaches are simple to implement and guaranteed to find a solution if one exists. Searching for a value in an unsorted list by checking each element sequentially is a brute force approach.

Greedy algorithms make the locally optimal choice at each step, hoping these choices lead to a globally optimal solution. Making change with the fewest coins by always selecting the largest denomination that doesn't exceed the remaining amount is greedy. Greedy algorithms don't always find optimal solutions but work well for certain problem types.

Divide and conquer algorithms break problems into smaller sub-problems of the same type, solve them recursively, and combine results. Merge sort divides a list in half, sorts each half, and merges the sorted halves. This strategy often yields efficient algorithms.

Dynamic programming solves problems by breaking them into overlapping sub-problems and storing solutions to avoid redundant computation. Calculating Fibonacci numbers efficiently uses dynamic programming by storing previously computed values.

Natural language descriptions use everyday language to explain algorithms. While accessible to non-programmers, natural language can be ambiguous and verbose. Instructions for a recipe are natural language algorithms.

Pseudocode is a structured but informal way to describe algorithms using programming-like constructs without strict syntax rules. Pseudocode bridges natural language and programming languages. It uses indentation to show structure, keywords like IF, WHILE, and FOR, and mathematical notation for operations.

Example pseudocode for finding the maximum value:

Flowcharts use graphical symbols to represent algorithm steps and flow. Standard symbols include ovals for start and end points, rectangles for processes, diamonds for decisions, parallelograms for input and output, and arrows for flow direction. Flowcharts make algorithm structure visually clear and are useful for explaining logic to non-technical audiences.

Structured English uses a limited vocabulary and specific formatting to describe algorithms. It's more formal than natural language but less technical than pseudocode. Business analysts often use structured English to document procedures.

Sequence is the default control structure where steps execute one after another in order. Most algorithm steps follow sequentially unless directed otherwise.

Selection structures make decisions based on conditions. IF-THEN-ELSE is the primary selection structure. Simple selection (IF-THEN) executes steps only when a condition is true. Two-way selection (IF-THEN-ELSE) provides alternative steps when the condition is false. Multiple selection (CASE or nested IF statements) handles more than two alternatives.

Iteration structures repeat steps. Count-controlled loops (FOR loops) repeat a specified number of times. Condition-controlled loops (WHILE and DO-WHILE loops) repeat until a condition changes. WHILE loops test the condition before executing; DO-WHILE loops test after, guaranteeing at least one execution.

Accumulator patterns build up a result through iteration. Summing list elements initializes a total to zero, then adds each element. Counting pattern is similar but increments by one for each item meeting criteria.

Search patterns find items in collections. Linear search checks each element sequentially. Binary search repeatedly divides a sorted collection in half, eliminating half the remaining elements each step.

Transformation patterns create new collections by modifying each element of an existing collection. Mapping applies a function to each element. Filtering selects elements meeting criteria.

Sorting patterns arrange elements in order. Simple sorts like bubble sort and selection sort compare and swap adjacent elements. Efficient sorts like merge sort and quicksort use divide and conquer.

Binary search is the classic divide-and-conquer pattern. It works only on a sorted list: each comparison discards half of the remaining items.