Into to Alg FINAL

What is the time complexity of the basic polynomial algorithm (nested loops)?

O(n^2)

What algorithm evaluates a polynomial in O(n)time?

Horner's Method (factors out x to use only 1 multiplication and 1 addition per step).

Why does the greedy "nearest neighbor" rule fail for the Traveling Salesman Problem (TSP)?

Short-sighted choices early on can trap you into taking extremely long routes later.

What is a Bipartite Graph?

A graph whose nodes can be split into 2 teams where every connection goes between the teams (never inside the same team).

What graph feature makes a graph impossible to be bipartite?

An odd-length cycle (like a triangle).

How do you solve the Two-Clique Problem using a bipartite graph test?

Build the complement graph (flip all edges) and test if that complement graph is bipartite.

How many characters can 7-bit ASCII represent?

128 characters (2^7 = 128).

What is the difference between Lossless and Lossy compression?

Lossless: Perfect recovery, 0 data lost (e.g., ZIP, PNG). Lossy: Permanently throws away unused data for smaller size (e.g., JPEG, MP3).

How does Huffman Coding save space?

Gives frequent characters short binary codes and rare characters longer binary codes.

What is the fastest time complexity to merge k sorted lists with n total elements?

O(n log k). It uses a Min-Priority Queue of size k containing the front element of each list. Each insertion and removal takes O(log k) time across all n elements.

In modular exponentiation by repeated squaring (g^x mod p), when and how do you update the running result r?

You update r = (r * c) mod p only when the current rightmost binary bit of the exponent d is 1 (d mod 2 == 1). If the bit is 0, r remains unchanged.

In the Diffie-Hellman protocol, how does Alice compute the shared secret key using Bob's public value B, her private secret a, and modulus p?

Alice computes K = B^a mod p. Since Bob's public value is B = g^b mod p, her calculation equals (g^b)^a mod p = g^(ab) mod p.