Lecture Note 05.1

hadoken

Algorithm

An ordered set of unambiguous, executable steps that defines a terminating process.

Terminating Process

A process that culminates with a result and produces an answer.

Abstract Nature of Algorithms

The difference between an algorithm and its representation.

Algorithm Representation

The formal or informal way of representing an algorithm.

Primitives

Well-defined components used in algorithm representation.

Pseudocode

A language that is between natural language and a programming language used for algorithm representation.

Conditional selection

A primitive that allows for conditional execution of activities based on a condition.

Repeated execution

A primitive that allows for the repetition of a set of instructions until a condition is met.

Indentation

A way of showing nested conditions in pseudocode.

Function

A named set of instructions that can be executed.

Pseudocode Primitives

The building blocks of pseudocode, including assignment, conditional selection, repeated execution, indentation, and defining and executing functions.

Algorithm Discovery

The process of developing an algorithm for a given problem.

Polya's Problem Solving Steps

A set of steps for problem-solving, including understanding the problem, devising a plan, carrying out the plan, and evaluating the solution.

Getting a Foot in the Door

A problem-solving technique that involves working the problem backwards or solving an easier related problem.

Iterative Structures

A collection of instructions repeated in a looping manner.

Sequential Search Algorithm

An algorithm for searching for a target value in a list.

Components of Repetitive Control

The pretest loop and posttest loop used in iterative structures.

Insertion Sort Algorithm

An algorithm for sorting a list.

Recursive Structures

Repeating a set of instructions as a subtask of itself.

Binary Search Algorithm

An algorithm for searching for a target value in a sorted list.

Efficiency

The measure of the number of instructions executed by an algorithm.

Correctness

The property of an algorithm producing the correct result for a given input.

Software Verification

The process of proving the correctness of a software program.

Assertions

Preconditions and loop invariants are used to verify the correctness of a program.

Testing

The process of verifying software by running test cases.

Chain Separating Problem

A problem where a traveler needs to cut the fewest number of links from a chain to pay for lodging each morning.

Separating the Chain using only Three Cuts

A strategy to solve the Chain Separating Problem by making three cuts in the chain.

Solving the problem with only One Cut

A strategy to solve the Chain Separating Problem by making only one cut in the chain.

Flowchart Symbols

Symbols used in flowcharts to represent different actions and decisions in a program.