Unit 3 Notes: Advanced Procedural Abstraction and Algorithmic Logic

Procedure

A named group of programming instructions that may have parameters and return values.

Parameters

Input variables defined in the procedure's header that act as placeholders.

Arguments

Actual specific values passed into the procedure when it is called.

Return Value

Data passed back to the main program using a return statement.

Library

A collection of pre-written procedures that you can import into your program.

API

Provides documentation and specifications for how the procedures in a library behave.

Linear Search

A search algorithm that checks each element one by one and can work on unsorted data.

Binary Search

A search algorithm that repeatedly divides the search interval in half and requires sorted data.

Reasonable Time

The number of steps is a polynomial function of the input size.

Unreasonable Time

The number of steps grows exponentially or factorially with input size.

Heuristic

A technique that provides an approximate solution, trading accuracy for speed.

Decidable Problem

A problem for which an algorithm can be constructed to always answer 'yes' or 'no'.

Undecidable Problem

A problem for which no algorithm can be constructed that always provides a correct answer.

Halting Problem

The undecidable problem of determining if a program will halt or run forever.

Simulation

Mimicking real-world phenomena through computer programs.

Modularity

Simplifying complex programs by abstracting details using libraries.

Execution Time

How the time to complete an algorithm grows as the input size increases.

Bias in Simulations

When programmers unintentionally introduce bias into the rules of a simulation.

Random Number Generator

A tool used in simulations to model unpredictability in real-world scenarios.

Safety in Simulations

Testing dangerous scenarios virtually instead of in real life.

Cost in Simulations

Simulations are generally cheaper than building physical prototypes for experiments.

Best Case (Linear Search)

1 step if the item is found at index 0.

Best Case (Binary Search)

1 step if the item is found in the middle.

Worst Case (Linear Search)

N steps if the item is not found.

Worst Case (Binary Search)

Logarithmic steps, approximately log2(N), if the item is not found.

Trade-off in Heuristics

Heuristics provide a good enough solution without guaranteeing the best solution.