COS 102: Introduction to Problem Solving Comprehensive Flashcards

Comprehensive vocabulary flashcards covering basic problem solving, algorithmic concepts, representation methods, and programming fundamentals as taught in COS 102.

Problem (General)

A situation with a gap between a current state and a desired/goal state where the path to close that gap is not immediately obvious.

Problem (Computing)

A task requiring the transformation of given inputs into a required output using a well-defined set of steps.

Initial state

The situation as it currently exists before any problem-solving operations begin.

Goal state

The desired outcome or solution intended to be reached.

George Pólya's four-phase model

A systematic model for problem solving consisting of: (1) Understand the problem, (2) Devise a plan, (3) Carry out the plan, and (4) Look back/review the solution.

Well-defined (well-structured) problems

Problems where the initial state, goal state, and operations are all clearly known, such as solving a quadratic equation.

Ill-defined (ill-structured) problems

Problems where the goal or the method of reaching it is unclear or open-ended.

Routine problems

Problems solved using known, standard procedures or formulas, like computing simple interest.

Computational problems

Problems expressed as a function from inputs to outputs and solved by a computer program.

Decision problems

Problems whose answer is simply "yes" or "no".

Optimization problems

Problems requiring the discovery of the best solution among many possible ones, subject to constraints.

Trial and Error

A technique involving trying a possible solution and checking if it works, refining the approach based on failed attempts.

Divide and Conquer

A strategy where a large problem is broken into smaller sub-problems, solved individually, and then combined.

Abstraction

Focusing on the essential features of a problem while ignoring irrelevant details that do not affect the solution.

Analogy

Solving a new problem by comparing it with a similar problem that has already been solved and adapting that solution.

Reduction

Transforming an unfamiliar problem into a different, already-solved problem to reuse existing methods, such as expressing $LCM(a, b)$ using $GCD(a, b)$, where $LCM(a, b) = \frac{a \times b}{GCD(a, b)}$.

Means-End Analysis

A technique that identifies the gap between the current state and the goal state and chooses actions to reduce that specific difference.

Heuristic

A practical "rule of thumb" based on experience that helps find a good solution quickly, though it does not guarantee optimality.

Algorithm

A finite, well-defined, step-by-step set of instructions for solving a problem or performing a task.

Finiteness

A characteristic of an algorithm stating it must terminate after a finite number of steps.

Definiteness

A characteristic of an algorithm where every step must be precisely and unambiguously defined.

Effectiveness

The requirement that every algorithmic step must be basic enough to be carried out exactly in a finite amount of time.

Top-Down Approach (Stepwise Refinement)

A design strategy where a problem is stated in broad terms and then broken down into smaller, more detailed sub-problems.

Bottom-Up Approach

A design strategy where the smallest, most basic components are built first and then integrated to form the complete solution.

Flowchart

A diagrammatic representation of an algorithm using standard geometric shapes and arrows to show the sequence of execution.

Terminal Symbol

An oval or rounded rectangle in a flowchart marking the beginning (Start) or end (Stop) of an algorithm.

Decision Symbol

A diamond or rhombus in a flowchart representing a yes/no or true/false question that determines flow direction.

Predefined process

A flowchart rectangle with double vertical bars representing a call to a sub-routine, function, or module defined elsewhere.

Pseudocode

A plain-language, informal way of describing an algorithm using structured English and programming-like keywords.

Decision Table

A compact tabular way of representing all possible combinations of conditions and corresponding actions.

Decision Tree

A branching diagram where internal nodes represent tests, branches represent outcomes, and leaf nodes represent final actions.

Dry run (Desk-checking)

The process of manually tracing through an algorithm on paper with sample data to check logic before coding.

Variable

A named storage location in memory whose value can change during program execution.

Constant

A named storage location whose value is fixed and cannot change once it is set.

Assignment Statement

A statement that stores a value or result into a variable, often using the $=$ or $\leftarrow$ operator.

Selection Statement

A programming construct (like if/else) that allows a program to choose between alternative paths of execution based on a condition.

Iteration Statement (Loop)

A construct that allows a block of instructions to be repeated multiple times, either a fixed number of times or until a condition is met.

Syntax Error

A violation of the programming language's grammar rules that prevents the program from running.

Logical error (Bug)

An error where the program runs but produces incorrect results because the algorithm's logic was flawed.

Runtime error

An error occurring while the program is executing, such as division by zero or invalid memory access.