AL101 - MIDTERM

a simplification of reality. We use them because real-world systems are often too complex, expensive, or time-consuming to build or manipulate directly.

Mathematical Models

THREE MAIN TYPES OF MODELS

• iconic

• analog

• mathematical

This is a physical replica of a system, usually built on a different scale (smaller or larger) than the original.

3D Examples: Scaled-down versions of airplanes, cars, or bridges.

2D Examples: Photographs

Iconic Model

These do not look like the real system at all, but they behave like it. They are more abstract than iconic models.

• Illustrations, graphs, tables, etc.

Analog Model

Otherwise known as “The Equation”, is the most abstract type, using symbols and math to represent relationships. Management science relies heavily on these

Mathematical Model

What Makes a Model “Good”

• Simple & Understandable

• Reasonable

• Easy to Maintain

• Adaptive

• Complete

ADVANTAGES OF MATHEMATICAL MODEL

• Cost-Efficiency

• Identifies Gaps

• Speed

• Decision Tool

DISADVANTAGES OF MATHEMATICAL MODELS

• Oversimplification

• Human Error

• High Initial Cost

Sample values arranged in ascending order.

Order Statistics

Order Statistics is a fundamental part of this subject because:

• Selection Algorithms

• Extreme Value Analysis

• Data Partitioning

The middle value of an ordered set.

Different formulas for even vs. odd sample sizes (n).

Median

This is the total distance between the maximum and the minimum

Range (X(n) - X(1))

This is the difference between the third and first quartiles

Interquartile Range (Q3 - Q1)

A well-known searching technique used to map data of arbitrary size to fixed- size values (indices).

Hashing

identifier of data

Hash function

This occurs when the hash function generates the same index (bucket) for two different keys.

Collision

A method where all keys are stored directly inside the hash table. Unlike Separate Chaining, no key is stored outside the table.

Open Addressing (Closed Hashing)

The system calculates the hash value to find an index.

Insertion

If that spot is occupied, it performs _—checking other buckets one by one—until an empty spot is found.

Probing

The system checks the calculated hash index first. If the key isn’t there, it continues checking subsequent buckets until the key is found or an empty bucket is encountered (which means the key doesn’t exist).

Searching

When a key is removed, the bucket is marked as “deleted”. During future searches, the system will not stop at a “deleted” marker; it keeps looking until it finds the key or a truly empty spot.

Deletion

CORE OPERATIONS IN OPEN ADDRESSING

Insertion

Searching

Deletion

If a collision occurs, the system simply checks the very next bucket (index + 1). It is easy to calculate but can lead to clustering, where many elements group together in one area of the table.

Linear Probing

Instead of checking the next spot, the system “jumps” using a squared interval (e.g., ) to find an empty bucket. This reduces primary clustering.

Quadratic Probing

This uses a second hash function to determine the ”jump” size. It is the most efficient at avoiding clustering but requires more computation time.

Double Hashing

PROBING TECHNIQUES

Linear Probing

Quadratic Probing

Double Hashing

a non-linear data structure used to represent data with a hierarchical relationship. Unlike Arrays or Linked Lists, which store data in a linear sequence, it organizes data in levels, starting from a single point and branching outwards.

Tree

The top-most node of the tree. It is the only node that has no parent.

Root

The connecting link or line between two nodes. It represents the relationship between them.

Edge

In any connected pair of nodes, the node physically “above” is the Parent, and the node ”below” is the Child.

Parent and Child

A node that does not have any children. These are the “end-points” of the tree.

Leaf Node

Nodes that belong to the same parent.

Siblings

Every child node can be seen as the root of its own smaller tree, consisting of all its descendants.

Subtree

PARTS OF A TREE

• Root

• Edge

• Parent and Child

• Leaf Node

• Siblings

• Subtree

a specialized version of a general tree. The defining rule is the ”Degree of Two”: no node is allowed to have more than two child nodes. These children are specifically referred to as the Left Child and the Right Child.

Binary Tree

A tree where every node has either zero or two children. No node has just “one” child.

Full Binary Tree

A tree that is completely filled at every level, except possibly the last level, which must be filled from left to right. This is crucial for storing trees in arrays efficiently. Since trees are non-linear, we cannot just read them from start to finish like a list. We use Traversals to visit every node in a systematic order.

Complete Binary Tree

In this method, the root is processed first. It is often used to create a copy of the tree or to get a prefix expression from an expression tree.

Preorder Traversal (Root  Left  Right)

In this method, the root is processed between the subtrees.

Inorder Traversal (Left  Root  Right)

In this method, the root is processed last. This is commonly used to delete a tree (since you must delete the children before the parent) or to evaluate postfix expressions.

Postorder Traversal (Left  Right  Root)