AL101 QUIZ (copy)

a comparative tracking algorithm. It uses nested loops to pass through an array. During a single pass, it evaluates index A[j] and its immediate neighbor. If the value at A[j] is strictly greater than the value at A[j+1], a swap is executed using a temporary variable (temp) to prevent data loss. The outer loop decreases the boundary of evaluated elements because, after the first full pass, the absolute largest number is guaranteed to have shifted to the very end of the array.

Bubble Sort

virtually divides the target array into two distinct areas: a “sorted” sublist on the left and an “unsorted” sublist on the right. It begins at index 2 (the second element) and stores this value in a variable called index (or the key). It then looks backward through the sorted sublist to its left. While the items on the left are larger than the current index, the algorithm continually shifts those larger elements one space to the right to make a vacancy. Once it finds the correct relative position, it “inserts” the stored value into that slot.

Insertion Sort

operates on a “search and capture” mechanism. The algorithm loops through the array from left to right. For every position i, it assumes the current item is the minimum (min = i). It then scans the rest of the remaining unsorted items to the right to find if an even smaller value exists. If it finds a smaller element, it updates the minimum index tracking pointer (Min = j). After completing the internal scan for that pass, it performs exactly one swap to place that absolute minimum value into position A[i].

Selection Sort

is an advanced optimization of Insertion Sort designed by Donald Shell. Insertion Sort’s primary weakness is that it only shifts elements one position at a time. It solves this by establishing a structural spacing factor called an “increment” (k). It breaks the array into interleaved segments where elements are separated by k positions. It then runs a standard Insertion Sort on each isolated segment. As the algorithm loops, the increment k is systematically reduced (divided by 2) until k=1. Because elements were sorted over large gaps early on, the final k=1 pass requires very few shifts.

Shell Sort

a highly optimized, recursive algorithmic paradigm built on a “Divide-and-Conquer” architectural layout.

Quick Sort

entirely built upon the distributive property of real numbers. When you multiply a group inside parentheses by a term outside, you are scaling the entire value of that expression. This means every single isolated item within the boundaries of the parentheses must be multiplied by the external factor equitably. If there are signs involved (negatives or positives), they stick to the terms during the process.

Polynomial Multiplication

Single term multiplication: -5(2x 2 )  (-5)(2)(x 2 )  -10x 2

: 3(4a 2 b)(3)(4)(a 2 )(b)  12a 2 b

Distributing a Constant

A polynomial with only one single term.

Example: (4a 2 )(-5a 7 )  (4)(-5)(a 2+7 )  -20a 9

(12x 2 y)(12x 5 y 3 z) 

Multiplying Single Terms

Multiplication can be shown by juxtaposition (putting the term right next to the parenthesis).

Example: x(x 2 +12)  (x)(x 2 ) + (x)12  x 3 + 12x

3x 2 (x 2 -5)  (3x 2 )(x 2 ) - (3x 2 )(5)  3x 4 + 15x 2

Advanced Distribution

Example: (x+4)(x-3)
- Vertical Method - Horizontal Method (FOIL method)
x + 4 First= (x)(x)

* x – 3 Outer = x(-3)

---------------- Inner = (4)(x)

- 3x – 12 Last = (4)(-3)

+ x 2 + 4x x^2 + (-3x) + 4x + (-12)  x 2 + x – 12 or x^2 + x + (-12)

-----------------

x 2 + x – 12

Terms Times Two Terms

When polynomials get past two terms, horizontal multiplication becomes painful and risky.

Example: (x+3) (4x 2 – 4x – 7)
Way 1(Distributive Way): {[(x)(4x 2 )] – [(x)(4x)] – [(x)(7)]} + {[(3)(4x 2 )] – [(3)(4x)] – [(3)(7)]}
4x 3 – 4x 2 – 7x + 12x 2 – 12x – 21  4x 3 + 8x 2 – 19x – 21
Way 2 (Vertical Method): 4x 2 – 4x – 7
* x + 3
---------------------

12x 2 - 12x - 21

4x 3 - 4x 2 - 7x

- -----------------------------

4x 3 + 8x 2 -19x - 21

Multiplying Larger Polynomials

Iteration and Recursion.

There are two distinct paths to handle repetitive logic in programming

Uses traditional loops (like for or while) where logic relies solely on variables/parameters,

not the algorithm itself.

Iteration

-A repetitive process where an algorithm calls itself directly or indirectly to solve a problem.

-is more than a syntax choice; it is a fundamental shift in how program tasks are broken
down. In traditional loop logic (iteration), a task runs within a single memory block, modifying local tracking variables step-by-step. In recursion, the execution stack generates completely independent frames for every layer of processing.

Recursion

Multiplies numbers sequentially from 1 up to n.

• Formula:

{Factorial}(n) = n x (n-1) x … x 1

Example Comparison (4!):
Iterative: 4 x 3 x 2 x 1 = 24.

Iterative Approach PDF

The algorithm appears directly within its own definition.

• Formula:

{Factorial}(n) = n x {Factorial}(n-1)

Example Comparison (4!):
Recursive: 4 x {Factorial}(3).

Recursive Approach PDF

is never a one-way street; it always involves a two-way journey.

Recursion

Decomposing the big problem into smaller, identical pieces from top to

bottom.

The Downward Journey

Solving the individual pieces step-by-step from bottom to top once the base limit

is hit.

Example: 4!
- Factorial (4) = 4 x Factorial (3) - 4 x 6 = 24

 Factorial (3) = 3 x Factorial (2) - 3 x 2 = 6

 Factorial (2) = 2 x Factorial (1) - 2x 1 = 2

 Factorial (1) = 1 x Factorial (0) - 1 x 1 = 1

 Factorial (0) = 1 | Base limit

The Upward Journey

 Recursion relies strictly on a standard underlying framework of function/method calls.

 When a program executes a call, the current system module suspends its processing.

 Control is completely handed over to the newly called subprogram.

 Once the subprogram completes its execution and returns, the parent module resumes exactly where it left off.

Anatomy of a Subprogram Call

Numbered List:

1. Determine the Base Case: Identify the statement or condition that solves and stops the

problem directly without calling itself again. (Example: {Factorial}(0) = 1).

2. Determine the General Case: Establish the rest of the algorithm, which focuses on reducing the size of the operational problem. (Example: n x {Factorial}(n-1)).

3. Combine Both Blocks: Unify the structural base case and general case logic cleanly into an

integrated conditional algorithm.

Three Core Steps to Design a Recursive Algorithm

Factorial(n)

{

If (n == 0) then

Fact = 1 <-- Base Case

Else

Fact = (n * (Factorial (n - 1))) <-- General Case

}

Factorial Implementation in Code

Advantage: It provides incredibly powerful and elegantly simple solutions to complex computational problems, especially when handling tree-like data structures.

Disadvantage (Overhead): It requires substantial system memory and execution time overhead because each nested function call consumes extra stack allocations.

Performance: A recursive algorithm generally runs slower compared to its direct, non-recursive iterative equivalent.

Pros and Cons: Is Recursion Always Best?

o Computer systems store massive amounts of data from which specific records must be

retrieved.

o Efficiency depends heavily on how data is stored and the choice of algorithm.

o Today, we look at the two primary methods: Sequential (Linear) Search and Binary Search.

Why Do We Need Searching Algorithms?

o Used primarily whenever the targeted list is not ordered (unsorted).

o Recommended only for small lists or lists that are not searched frequently.

o Starts at the very beginning of the list and checks element by element until the target is found

or the end of the list is reached.

Sequential (Linear) Search

Visual Array Layout: [35, 25, 40, 60, 80, 95, 26, 42, 76, 83]

 Case A: Target is 60

o Check A[1] (35)  No

o Check A[2] (25)  No

o Check A[3] (40)  No

o Check A[4] (60)  Found!

 Case B: Target is 70 (Not in list)

o Since the list is unordered, the computer is forced to check every index from A[1] until A[10]

before it can confidently conclude: "Does not exist".

Sequential Search in Action

Relies strictly on the Divide-and-Conquer technique.

o CRITICAL REQUIREMENT: The array must be sequenced/ordered (e.g., ascending order).

o The Three Core Steps:

1. Divide: Split the instance into two smaller halves.

2. Recur: Solve the smaller instance recursively.

3. Conquer: Discard the unneeded half; no extra step is needed to combine solutions.

o Example: 3 6 9 12 15 18 21 24 27 30 | 33 36 39 42 45 48 51 54 57 60

o Target: 33

Binary Search (Divide and Conquer)

o Find the middle element (mid).

o Rule 1: If Key (K) is smaller than the middle element, pick the left sub-array.

o Rule 2: If Key (K) is larger than the middle element, pick the right sub-array.

o Rule 3: Stop when the key is found (K = A[mid]) or the sub-array cannot be split further.

How Binary Search Thinks