design and analysis prelim

Algorithm

A set of finite and detailed step-by-step instructions performed to complete a specific task

Algorithmics

The design and analysis of computer algorithms

Input Specification

The inputs of an algorithm must be clearly identified and can be zero or more values taken from a specified set

Output Specification

The output of an algorithm and its relationship to the input must be clearly identified and an algorithm must have at least one output

Definiteness

All steps in an algorithm must be precisely and unambiguously defined

Finiteness

An algorithm must terminate after a finite number of steps using a finite amount of resources

Effectiveness

All operations in an algorithm must be basic enough to be performed exactly and in finite time

Pseudocode

A generic way of describing an algorithm without using any specific programming language syntax

Flowchart

A graphical representation of an algorithm using connected symbols to show the sequence of steps

Exact Problem Solving

A problem-solving approach that produces a definite and quantifiable result

Approximate Problem Solving

A problem-solving approach that produces a near result to the actual value

Algorithm Design Technique

A general strategy used to solve problems algorithmically

Brute Force

A straightforward approach that directly follows the problem definition

Divide and Conquer

An approach that breaks a problem into smaller subproblems, solves them, and combines the results

Data Structure

A method of organizing data in a computer for efficient use

Linear Data Structure

A data structure where elements are arranged sequentially and each element has a unique successor

Array

A linear data structure containing a fixed number of elements of the same data type

Linked List

A data structure consisting of nodes connected using pointers

Singly Linked List

A linked list where each node contains a pointer to the next node

Doubly Linked List

A linked list where each node contains pointers to both the previous and next nodes

Circularly Linked List

A linked list where the last node points back to the first node

Graph Data Structure

A collection of vertices and edges representing relationships between objects

Directed Graph

A graph where edges have a specific direction

Undirected Graph

A graph where edges have no direction

Tree Data Structure

A hierarchical data structure consisting of nodes and directed branches

Root

The first node of a tree

Leaf

A node in a tree with no outgoing edges

Internal Node

A node that is neither the root nor a leaf

Binary Tree

A tree in which each node has at most two children

Binary Search Tree

A binary tree where left subtree values are less than the root and right subtree values are greater or equal

AVL Tree

A self-balancing binary search tree with a balance factor

Heap Tree

A complete or nearly complete binary tree that satisfies the heap property

Algorithm Correctness

The property that ensures an algorithm produces the correct output for every valid input

Algorithm Analysis

The process of evaluating an algorithm’s performance

Time Complexity

A measure of how an algorithm’s running time grows with input size

Space Complexity

A measure of how much memory an algorithm uses

Sorting Problem

A problem that involves rearranging elements in a list into a specific order

Searching Problem

A problem that involves finding a specific value in a data set

String Processing Problem

A problem involving sequences of characters

Graph Problem

A problem involving objects and the connections between them

Breadth First Search

A graph traversal algorithm that explores nodes level by level

Depth First Search

A graph traversal algorithm that explores as far as possible along each branch before backtracking

Combinatorial Problem

A problem that involves finding combinations, permutations, or subsets under constraints

Geometrical Problem

A problem involving geometric objects such as points, lines, and polygons

Numerical Problem

A problem involving continuous mathematical computation