Session 1

def gcd_with_stats(a, b):
    """
    Computes GCD and tracks modulo and assignment operations.
    """
    mod_count = 0
    assign_count = 0

    # Absolute values for mathematical consistency
    a, b = abs(a), abs(b)
    assign_count += 2

    while b:
        # Modulo operation
        remainder = a % b
        mod_count += 1

        # Assignment operations (a = b, b = remainder)
        a = b
        b = remainder
        assign_count += 2

    return a, mod_count, assign_count

# Input values
val_a, val_b = 15265, 15
result, mods, assigns = gcd_with_stats(val_a, val_b)

print(f"GCD({val_a}, {val_b}) = {result}")
print(f"Modulo Operations: {mods}")
print(f"Assignment Operations: {assigns}")

#include <stdio.h>
#include <stdlib.h>

/**
 * Calculates GCD and updates operation counters via pointers.
 */
long long gcd_metrics(long long a, long long b, int *mods, int *assigns) {
    *mods = 0;
    *assigns = 0;

    a = llabs(a);
    b = llabs(b);
    *assigns += 2;

    while (b != 0) {
        long long remainder = a % b;
        (*mods)++;

        a = b;
        b = remainder;
        *assigns += 2;
    }

    return a;
}

int main() {
    int mod_count, assign_count;
    long long a = 15265, b = 15;

    long long result = gcd_metrics(a, b, &mod_count, &assign_count);

    printf("GCD(%lld, %lld) = %lld\n", a, b, result);
    printf("Total Modulo Operations: %d\n", mod_count);
    printf("Total Assignment Operations: %d\n", assign_count);

    return 0;
}

fn gcd_with_metrics(mut a: i64, mut b: i64) -> (i64, u32, u32) {
    let mut mod_ops = 0;
    let mut assign_ops = 0;

    // Initial assignments to absolute values
    a = a.abs();
    b = b.abs();
    assign_ops += 2;

    while b != 0 {
        let remainder = a % b;
        mod_ops += 1;

        a = b;
        b = remainder;
        assign_ops += 2;
    }

    (a, mod_ops, assign_ops)
}

fn main() {
    let (result, mods, assigns) = gcd_with_metrics(15265, 15);
    println!("GCD: {}", result);
    println!("Modulo Ops: {}, Assignment Ops: {}", mods, assigns);
}

def horner_rule_analysis(coeffs, x):
    # n is the degree (length of coeffs - 1)
    # result starts as the first coefficient (6 in this case)
    result = coeffs[0]

    mult_count = 0
    add_count = 0
    loop_count = 0

    # The loop starts from the second coefficient to the last
    for i in range(1, len(coeffs)):
        loop_count += 1

        # Every step involves 1 multiplication and 1 addition
        result = (result * x) + coeffs[i]

        mult_count += 1
        add_count += 1

    return result, mult_count, add_count, loop_count

# P(x) = 6x^6 + 5x^5 + 4x^4 - 3x^3 + 2x^2 + 8x - 7
coeffs = [6, 5, 4, -3, 2, 8, -7]
x_val = 3

res, m, a, lp = horner_rule_analysis(coeffs, x_val)

print(f"Result: {res}")
print(f"(a) Multiplications: {m}, Additions: {a}")
print(f"(b) Loop Iterations: {lp}")

#include <stdio.h>

void evaluate_horner(int coeffs[], int n, int x) {
    long long result = coeffs[0];
    int mults = 0, adds = 0, iterations = 0;

    // The loop iterates from 1 to n-1 (total iterations = degree)
    for (int i = 1; i < n; i++) {
        iterations++;

        result = (result * x) + coeffs[i];

        mults++; // One multiplication per step
        adds++;  // One addition per step
    }

    printf("Result: %lld\n", result);
    printf("(a) Multiplications: %d, Additions: %d\n", mults, adds);
    printf("(b) Loop Iterations: %d\n", iterations);
}

int main() {
    int coeffs[] = {6, 5, 4, -3, 2, 8, -7};
    int n = sizeof(coeffs) / sizeof(coeffs[0]);
    evaluate_horner(coeffs, n, 3);
    return 0;
}

struct Analysis {
    result: i64,
    multiplications: usize,
    additions: usize,
    iterations: usize,
}

fn horner_analysis(coeffs: &[i64], x: i64) -> Analysis {
    let mut res = coeffs[0];
    let mut m = 0;
    let mut a = 0;
    let mut i_count = 0;

    // Skipping the first element as it's our starting 'res'
    for &c in coeffs.iter().skip(1) {
        i_count += 1;
        res = (res * x) + c;
        m += 1;
        a += 1;
    }

    Analysis {
        result: res,
        multiplications: m,
        additions: a,
        iterations: i_count,
    }
}

fn main() {
    let coeffs = [6, 5, 4, -3, 2, 8, -7];
    let x = 3;
    let stats = horner_analysis(&coeffs, x);

    println!("Result: {}", stats.result);
    println!(
        "(a) Multiplications: {}, Additions: {}",
        stats.multiplications, stats.additions
    );
    println!("(b) Loop Iterations: {}", stats.iterations);
}

def brute_force_analysis(coeffs, x):
    n = len(coeffs) - 1 # The degree of the polynomial (6 in this case)
    total_sum = 0
    mult_count = 0
    add_count = 0

    # Loop through each coefficient and its index
    for i, coeff in enumerate(coeffs):
        # Calculate current power: e.g., for the first term (index 0), power is 6
        power = n - i

        # Calculate x^power by multiplying x, 'power' number of times
        current_pow_val = 1
        for _ in range(power):
            current_pow_val *= x
            mult_count += 1 # Tracking multiplications for powers

        # Multiply coefficient by the calculated power
        if power > 0:
            total_sum += coeff * current_pow_val
            mult_count += 1 # Tracking multiplication by coefficient
        else:
            # Constant term (x^0) has no power or coefficient multiplication
            total_sum += coeff

        # Every coefficient after the first one involves an addition operation
        if i > 0:
            add_count += 1

    return total_sum, mult_count, add_count

# P(x) = 6x^6 + 5x^5 + 4x^4 - 3x^3 + 2x^2 + 8x - 7
coeffs = [6, 5, 4, -3, 2, 8, -7]
res, m, a = brute_force_analysis(coeffs, 3)

print(f"Brute Force Result: {res}")
print(f"Total Multiplications: {m}")
print(f"Total Additions: {a}")

#include <stdio.h>

void brute_force_eval(int coeffs[], int n, int x) {
    long long total_sum = 0;
    int mult_count = 0, add_count = 0;
    int degree = n - 1;

    // Iterate through the array of coefficients
    for (int i = 0; i < n; i++) {
        int power = degree - i;
        long long current_pow_val = 1;

        // Inner loop: Calculate x to the power of 'power'
        // This is the source of extra multiplications compared to Horner
        for (int j = 0; j < power; j++) {
            current_pow_val *= x;
            mult_count++;
        }

        // Multiply the resulting power by the coefficient
        if (power > 0) {
            total_sum += (long long)coeffs[i] * current_pow_val;
            mult_count++;
        } else {
            // Constant term (last element)
            total_sum += coeffs[i];
        }

        // Add to the running total (Addition operation)
        if (i > 0) add_count++;
    }

    printf("Brute Force Result: %lld\n", total_sum);
    printf("Multiplications: %d, Additions: %d\n", mult_count, add_count);
}

int main() {
    // Array representing 6x^6 + 5x^5 + 4x^4 - 3x^3 + 2x^2 + 8x - 7
    int coeffs[] = {6, 5, 4, -3, 2, 8, -7};
    brute_force_eval(coeffs, 7, 3);
    return 0;
}

fn brute_force(coeffs: &[i64], x: i64) {
    let mut total_sum = 0;
    let mut mults = 0;
    let mut adds = 0;
    let n = coeffs.len() - 1; // Highest degree

    // Loop through coefficients from highest degree to constant
    for (i, &coeff) in coeffs.iter().enumerate() {
        let power = n - i;
        let mut current_pow_val = 1;

        // Manually compute power to track multiplication overhead
        for _ in 0..power {
            current_pow_val *= x;
            mults += 1;
        }

        // Perform: coefficient * (x^power)
        if power > 0 {
            total_sum += coeff * current_pow_val;
            mults += 1;
        } else {
            // Constant term (x^0)
            total_sum += coeff;
        }

        // Perform the addition to the total sum
        if i > 0 {
            adds += 1;
        }
    }

    println!("Brute Force Result: {}", total_sum);
    println!("Multiplications: {}, Additions: {}", mults, adds);
}

fn main() {
    let coeffs = [6, 5, 4, -3, 2, 8, -7];
    brute_force(&coeffs, 3);
}

def matrix_multiply_4x4(A, B):
    C = [[0]*4 for _ in range(4)]
    outer_count = inner_count = mul_count = add_count = 0

    for i in range(4):
        outer_count += 1
        for j in range(4):
            for k in range(4):
                C[i][j] += A[i][k] * B[k][j]
                inner_count += 1
                mul_count += 1
                add_count += 1

    return C, outer_count, inner_count, mul_count, add_count

A = [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]
B = [[1,0,0,1], [0,1,0,1], [0,0,1,1], [1,1,1,0]]

C, outer, inner, mul, add = matrix_multiply_4x4(A, B)

print("Result Matrix C:")
for row in C:
    print([f"{x:4}" for x in row])
print(f"\nOuter-most loop runs: {outer} times")
print(f"Inner-most loop runs: {inner} times")
print(f"Total Multiplications: {mul}")
print(f"Total Additions: {add}")

#include <stdio.h>

int main() {
    int A[4][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
    int B[4][4] = {{1,0,0,1}, {0,1,0,1}, {0,0,1,1}, {1,1,1,0}};
    int C[4][4] = {0};

    int outer_count = 0, inner_count = 0;
    int mul_count = 0, add_count = 0;

    for (int i = 0; i < 4; i++) {
        outer_count++;
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                C[i][j] += A[i][k] * B[k][j];
                inner_count++;
                mul_count++;
                add_count++; // accumulation
            }
        }
    }

    printf("Result Matrix C:\n");
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) printf("%4d ", C[i][j]);
        printf("\n");
    }
    printf("\nOuter-most loop runs: %d times\n", outer_count);
    printf("Inner-most loop runs: %d times\n", inner_count);
    printf("Total Multiplications: %d\n", mul_count);
    printf("Total Additions: %d\n", add_count);
    return 0;
}

fn main() {
    let a: [[i32; 4]; 4] = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 16],
    ];
    let b: [[i32; 4]; 4] = [[1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [1, 1, 1, 0]];

    let mut c = [[0i32; 4]; 4];
    let (mut outer, mut inner, mut mul, mut add) = (0, 0, 0, 0);

    for i in 0..4 {
        outer += 1;
        for j in 0..4 {
            for k in 0..4 {
                c[i][j] += a[i][k] * b[k][j];
                inner += 1;
                mul += 1;
                add += 1;
            }
        }
    }

    println!("Result Matrix C:");
    for row in &c {
        println!("{:4} {:4} {:4} {:4}", row[0], row[1], row[2], row[3]);
    }
    println!("\nOuter-most loop runs: {} times", outer);
    println!("Inner-most loop runs: {} times", inner);
    println!("Total Multiplications: {}", mul);
    println!("Total Additions: {}", add);
}

def right_to_left(base, exp):
    """Computes base^exp using Right-to-Left binary exponentiation."""
    result = 1
    running_square = base
    loops, multiplications = 0, 0

    temp_exp = exp
    while temp_exp > 0:
        loops += 1
        # If the bit is 1, multiply the result by current square
        if temp_exp % 2 == 1:
            result *= running_square
            multiplications += 1

        # Square the base for the next bit
        if temp_exp > 1:
            running_square *= running_square
            multiplications += 1

        temp_exp //= 2
    print(f"After processing bit: result={result}")
    return loops, multiplications


def left_to_right(base, exp):
    """Computes base^exp using Left-to-Right binary exponentiation."""
    result = 1
    loops, multiplications = 0, 0

    # Process bits from the Most Significant Bit to the Least
    binary_str = bin(exp)[2:]
    for bit in binary_str:
        loops += 1
        # Always square the result
        result *= result
        multiplications += 1

        # If the bit is 1, multiply by the original base
        if bit == "1":
            result *= base
            multiplications += 1
    print(f"After processing bit: result={result}")
    return loops, multiplications


def run_all():
    problems = [(4, 512), (3, 31)]
    for b, e in problems:
        print(f"--- Problem: {b}^{e} ---")

        r_loops, r_mults = right_to_left(b, e)
        print(f"R2L Method: Loops={r_loops}, Multiplications={r_mults}")

        l_loops, l_mults = left_to_right(b, e)
        print(f"L2R Method: Loops={l_loops}, Multiplications={l_mults}\n")


if __name__ == "__main__":
    run_all()

#include <stdio.h>

// Struct to hold our operation metrics
typedef struct {
    int loops;
    int mults;
} Metrics;

Metrics right_to_left(unsigned long long base, unsigned int exp) {
    Metrics m = {0, 0};
    unsigned long long res = 1;
    while (exp > 0) {
        m.loops++;
        if (exp & 1) {
            res *= base;
            m.mults++;
        }
        if (exp > 1) {
            base *= base;
            m.mults++;
        }
        exp >>= 1;
    }
    return m;
}

Metrics left_to_right(unsigned long long base, unsigned int exp) {
    Metrics m = {0, 0};
    unsigned long long res = 1;
    int msb = 0;

    // Find highest bit position
    for (int i = 31; i >= 0; i--) {
        if ((exp >> i) & 1) {
            msb = i;
            break;
        }
    }

    for (int i = msb; i >= 0; i--) {
        m.loops++;
        res *= res;
        m.mults++;
        if ((exp >> i) & 1) {
            res *= base;
            m.mults++;
        }
    }
    return m;
}

int main() {
    unsigned long long bases[] = {4, 3};
    unsigned int exps[] = {512, 31};

    for (int i = 0; i < 2; i++) {
        printf("--- Problem: %llu^%u ---\n", bases[i], exps[i]);

        Metrics r = right_to_left(bases[i], exps[i]);
        printf("R2L Method: Loops=%d, Multiplications=%d\n", r.loops, r.mults);

        Metrics l = left_to_right(bases[i], exps[i]);
        printf("L2R Method: Loops=%d, Multiplications=%d\n\n", l.loops, l.mults);
    }
    return 0;
}

fn right_to_left(mut base: u128, mut exp: u32) -> (u32, u32) {
    let (mut res, mut loops, mut mults) = (1u128, 0, 0);
    while exp > 0 {
        loops += 1;
        if exp % 2 == 1 {
            res = res.wrapping_mul(base);
            mults += 1;
        }
        if exp > 1 {
            base = base.wrapping_mul(base);
            mults += 1;
        }
        exp /= 2;
    }
    (loops, mults)
}

fn left_to_right(base: u128, exp: u32) -> (u32, u32) {
    let (mut res, mut loops, mut mults) = (1u128, 0, 0);
    let bit_len = 32 - exp.leading_zeros();

    for i in (0..bit_len).rev() {
        loops += 1;
        res = res.wrapping_mul(res); // Square
        mults += 1;
        if (exp >> i) & 1 == 1 {
            res = res.wrapping_mul(base); // Multiply by original base
            mults += 1;
        }
    }
    (loops, mults)
}

fn main() {
    let problems = [(4, 512), (3, 31)];
    for (b, e) in problems {
        println!("--- Problem: {}^{} ---", b, e);
        let r = right_to_left(b, e);
        let l = left_to_right(b, e as u32);
        println!("R2L: Loops={}, Multiplications={}", r.0, r.1);
        println!("L2R: Loops={}, Multiplications={}\n", l.0, l.1);
    }
}

def bubble_sort(numbers):
    n = len(numbers)
    # Counters for the requested metrics
    exchanges = 0
    comparisons = 0
    outer_iterations = 0
    inner_iterations = 0

    # The outer loop runs 'n' times (once for each element)
    for i in range(n):
        outer_iterations += 1

        # The inner loop runs from the start to the 'unsorted' portion.
        # We subtract 'i' because the last 'i' elements are already sorted.
        for j in range(0, n - i - 1):
            inner_iterations += 1
            comparisons += 1

            # Comparison: Is the current element larger than the next?
            if numbers[j] > numbers[j + 1]:
                # Exchange: Swap the elements
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                exchanges += 1

    return exchanges, comparisons, outer_iterations, inner_iterations


# Input data
data = [55, 25, 15, 40, 60, 35, 17, 65, 75, 10]
ex, comp, out, inn = bubble_sort(data)

print(f"Sorted: {data}")
print(f"Exchanges: {ex}, Comparisons: {comp}, Outer: {out}, Inner: {inn}")

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    int exchanges = 0, comparisons = 0;
    int outer_iters = 0, inner_iters = 0;

    // Outer loop: Each pass ensures the i-th largest element is in place
    for (int i = 0; i < n; i++) {
        outer_iters++;

        // Inner loop: Reduces range as elements are sorted at the end
        for (int j = 0; j < n - i - 1; j++) {
            inner_iters++;
            comparisons++;

            // Comparison
            if (arr[j] > arr[j + 1]) {
                // Exchange logic using a temporary variable
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                exchanges++;
            }
        }
    }

    printf("Metrics for Bubble Sort:\n");
    printf("(i)   Exchanges: %d\n", exchanges);
    printf("(ii)  Comparisons: %d\n", comparisons);
    printf("(iii) Outer Iterations: %d, Inner Iterations: %d\n", outer_iters, inner_iters);
}

int main() {
    int data[] = {55, 25, 15, 40, 60, 35, 17, 65, 75, 10};
    int size = sizeof(data) / sizeof(data[0]);
    bubble_sort(data, size);
    return 0;
}

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    let (mut exchanges, mut comparisons) = (0, 0);
    let (mut outer_iters, mut inner_iters) = (0, 0);

    // Outer loop: Tracks how many elements are already placed at the end
    for i in 0..n {
        outer_iters += 1;

        // Inner loop: Comparison limit decreases as 'i' increases
        for j in 0..n - i - 1 {
            inner_iters += 1;
            comparisons += 1;

            if arr[j] > arr[j + 1] {
                // Exchange using Rust's safe swap method
                arr.swap(j, j + 1);
                exchanges += 1;
            }
        }
    }

    println!("Exchanges: {}, Comparisons: {}", exchanges, comparisons);
    println!(
        "Outer Loop Iters: {}, Inner Loop Iters: {}",
        outer_iters, inner_iters
    );
}

fn main() {
    let mut nums = [55, 25, 15, 40, 60, 35, 17, 65, 75, 10];
    bubble_sort(&mut nums);
}

def selection_sort_detailed(arr):
    n = len(arr)
    # Metric trackers
    exchanges, comparisons = 0, 0
    outer_iters, inner_iters = 0, 0

    # Outer loop: Moves the boundary of the unsorted subarray
    for i in range(n):
        outer_iters += 1

        # Step 1: Assume the first unsorted element is the smallest
        min_index = i

        # Step 2: Inner loop to find the actual minimum in the remaining unsorted list
        for j in range(i + 1, n):
            inner_iters += 1
            comparisons += 1
            if arr[j] < arr[min_index]:
                # We found a new minimum; just update the index (no swap yet!)
                min_index = j

        # Step 3: Swap the found minimum with the first unsorted element
        # This happens ONLY once per outer loop iteration.
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            exchanges += 1

    return exchanges, comparisons, outer_iters, inner_iters


# Run the analysis
data = [55, 25, 15, 40, 60, 35, 17, 65, 75, 10]
ex, comp, out, inn = selection_sort_detailed(data)
print(f"Exchanges: {ex}, Comparisons: {comp}")

#include <stdio.h>

void selection_sort(int arr[], int n) {
    int exchanges = 0, comparisons = 0, inner_loops = 0;

    // Loop through each position in the array
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;

        // Search the unsorted part of the array for the smallest value
        for (int j = i + 1; j < n; j++) {
            inner_loops++;
            comparisons++;
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // If the smallest value is not in its correct place, swap it
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
            exchanges++;
        }
    }

    printf("Result -> Exchanges: %d, Comparisons: %d, Inner Loops: %d\n",
            exchanges, comparisons, inner_loops);
}

fn selection_sort_analysis(arr: &mut [i32]) {
    let n = arr.len();
    let (mut ex, mut comp) = (0, 0);
    let (mut out, mut inn) = (0, 0);

    // Iterating through the array
    for i in 0..n {
        out += 1;
        let mut min_idx = i;

        // The inner loop scans the right side of the current index 'i'
        for j in i + 1..n {
            inn += 1;
            comp += 1;
            // Update min_idx if a smaller value is found
            if arr[j] < arr[min_idx] {
                min_idx = j;
            }
        }

        // Only swap if a new minimum was actually found at a different position
        if min_idx != i {
            arr.swap(i, min_idx);
            ex += 1;
        }
    }
    println!(
        "Exchanges: {}, Comparisons: {}, Inner Loops: {}",
        ex, comp, inn
    );
}