Algorithms that Changed the World Flashcards
(196 cards)
1
Q
What is the PageRank algorithm designed to do?
A
To rank web pages by importance based on their hyperlink structure, helping users find the most relevant pages in a massive, unstructured web.
2
Q
What are the two main ideas behind PageRank?
A
The Hyperlink Trick - Pages linked to by many others are likely more important.
The Random Surfer Model - Models a user randomly clicking links or restarting their browsing at random pages.
3
Q
How does PageRank define page importance?
A
A page’s importance is higher if it is linked to by other important pages, with rank distributed proportionally based on the number of outbound links.
4
Q
What is the sink page problem in PageRank?
A
Sink pages have no outbound links, which can absorb all rank. The solution is to redistribute their rank equally across all pages.
5
Q
What is the cycle page problem in PageRank?
A
A group of pages that only link to each other can trap rank in an infinite loop. This is mitigated using the random surfer model.
6
Q
What is the damping factor in the Random Surfer Model?
A
It represents the probability (usually 0.85) that a user continues following links. With 1 - damping factor (e.g., 0.15), the user jumps to a random page.
7
Q
What is the time complexity of the PageRank algorithm?
A
O(kN²), where k is the number of iterations and N is the number of pages.
8
Q
What are the five key components of the TCP/IP Stack?
A
Application Layer, Transport Layer,
Network Layer,
Data Link Layer,
Physical Layer
9
Q
What is routing and forwarding?
A
Routing - Determines the full end-to-end path through a network.
Forwarding - Determines how a router handles an individual packet using a forwarding table.
10
Q
What is Packet Switching?
A
A communication method where data is split into packets and sent independently through a network.
11
Q
What are global and decentralised routing algorithms?
A
Global routing algorithms have full knowledge of topology and link costs, and decentralised routing algorithms only know local neighbours and link costs.
12
Q
What are static and dynamic routing algorithms?
A
Static ones change slowly, and dynamic ones update periodically and react to network changes.
13
Q
What does Dijkstra’s algorithm compute?
A
The least-cost path from a source node to all other nodes in a network with non-negative link costs.
14
Q
What type of routing algorithm is Dijkstra’s?
A
Link State routing algorithm, meaning it is global and static.
15
Q
What is the main principle behind Dijkstra’s algorithm?
A
Greedy and iterative: after k iterations, the shortest paths to k nodes are known.
16
Q
What is the complexity of Dijkstra’s algorithm (naive implementation)?
A
O(n^2), where n is the number of nodes.
17
Q
Why does the Internet need more than one routing algorithm?
A
Because link state algorithms respond slowly to changes, consume bandwidth with large tables, and don’t scale well for large or dynamic networks.
18
Q
What are the three main characteristics of DV routing algorithms?
A
Distributed (no global knowledge), Iterative (keep updating), Asynchronous (don’t all update at the same time).
19
Q
How do DV routing algorithms work?
A
WAIT for changes in local links. RECOMPUTE its DVs. NOTIFY only if DV to any destination has changed.
20
Q
What is the purpose of Poisoned Reverse in DV routing?
A
To prevent routing loops by telling neighbors not to use certain paths (set cost to ∞). e.g If A routes. through B to get to C, A tells B its distance to C is infinity.
21
Q
What is the O notation of Bellman-Ford?
A
O(|N||E|)
22
Q
Why is hierarchical routing necessary on the Internet?
A
Because the Internet is too large to maintain a flat routing structure; storing all destinations and exchanging updates would consume too much bandwidth.
23
Q
What is an Autonomous System (AS)?
A
A group of routers under a single administrative domain that run the same intra-AS routing protocol.
24
Q
What are the two types of routing in a hierarchical routing system?
A
Intra-AS, and Inter-AS
25
What is the role of a gateway router in hierarchical routing?
It connects different ASes and runs both intra-AS and inter-AS routing protocols.
26
What does intra-AS routing focus on?
Performance — since all routers are under one admin, there’s no need for policy decisions.
27
What does inter-AS routing focus on?
Policy — administrators decide how traffic is routed between ASes.
28
What are the benefits of hierarchical routing?
Reduces routing table size, limits traffic update scope, improves performance, and supports routing policies
29
Which protocols are typically used for intra-AS routing?
Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)
30
Which protocol is typically used for inter-AS routing?
BGP (Border Gateway Protocol)
31
What is the difference between RIP and OSPF?
RIP uses distance vector with hop count, while OSPF uses link-state with a full network map and Dijkstra’s algorithm.
32
How does BGP work?
It uses TCP to send messages like OPEN (establish session), UPDATE (announce/withdraw routes), KEEPALIVE (maintain session), and NOTIFICATION (error handling). Routing decisions are based on policies set by administrators, not just shortest path.
33
What is the main goal of one-dimensional minimisation?
To find the value 𝑥 that makes a function 𝑓(𝑥) as small as possible.
34
Why is convexity helpful in optimisation?
A convex function has exactly one global minimum and no local “traps,” so simple methods will always find the true minimum.
35
State Jensen’s inequality for a convex function.
f(tx1 + (1−t)x2) ≤ tf(x1) + (1−t)f(x2) for all 𝑡∈[0,1]
36
What does 𝑓'′(𝑥) ≥ 0 tell you about 𝑓 in 1-D?
It means 𝑓 is convex (its slope is non-decreasing).
37
How do you turn a convex minimisation problem into a root-finding problem?
By noting that at the minimum 𝑥*, the derivative satisfies 𝑓′(𝑥*)=0.
38
What does it mean to “bracket” a root of g(x)?
Find a and b such that g(a) and g(b) have opposite signs, ensuring a root lies between.
39
Describe the bisection method in one sentence.
Repeatedly split the interval in half, keeping the subinterval where the sign change occurs, until the root is located sufficiently precisely.
40
How do you bracket a minimum of f(x)?
Find af(b)
41
What fraction does the golden-section search use to split the interval?
(3−
5
)/2≈0.382
42
What’s the key idea of parabolic interpolation in Brent’s method?
Fit a parabola through three points and jump to its vertex as a trial minimum.
43
Why does Brent’s method switch to golden-section steps sometimes?
To ensure the bracket always contains the minimum and to guarantee convergence when the parabola fit would step outside the bracket.
44
What are the three special vertices in Nelder–Mead and how are they named?
“Best” (lowest function value), “Good” (second-lowest), and “Worst” (highest).
45
How do you find the centroid called C?
Add up all the vertex coordinates except the worst one, then divide by the number of those remaining points.
46
What is the reflection step?
You take the centroid, move away from the worst point by the same distance, and test that new point.
47
When do you accept the reflected point?
If its function value is better than the good point but not better than the best point.
48
What triggers an expansion, and what do you do?
If the reflected point beats the best point, you move further in that direction (twice as far from the centroid).
49
How do you choose between expansion and sticking with reflection?
If the further-out point is even better, take it; otherwise keep the reflected point.
50
When do you perform outside contraction?
If the reflection is better than the worst but not better than the good point.
51
When do you perform inside contraction?
If the reflection is worse than the worst point; then you move half-way from the worst back toward the centroid.
52
What happens if both reflection and contraction fail?
You shrink the entire simplex by moving every point halfway toward the best point.
53
What are the usual default multipliers for reflection, expansion, contraction, and shrink?
Reflection uses 1× the distance, expansion 2×, contraction ½×, and shrink ½×.
54
Name two ways to decide when to stop the algorithm.
When all vertices are very close together, or when their function values differ by less than a tolerance.
55
Why is Nelder–Mead called “derivative-free”?
Because it never computes or approximates any gradients—only compares function values.
56
What is one potential downside of Nelder–Mead?
It may stall or converge slowly on high-dimensional or very noisy problems.
57
How does the method guarantee the simplex moves “downhill”?
Every new trial point must improve on the worst point, so the overall worst value can only get better over time.
58
What is a decision variable in linear programming?
It’s a quantity you choose (like how much to invest), represented by a nonnegative number.
59
How do you express a “less-than-or-equal-to” constraint in slack form?
Add a new nonnegative slack variable so that slack = right-hand side minus the weighted sum of decision variables.
60
What makes a point “feasible”?
It satisfies all constraints and has all variables nonnegative.
61
Why does the optimum of a linear program occur at a corner?
Because a linear objective over a convex feasible region always reaches its best value at a vertex.
62
In the simplex method, what are “basic” and “nonbasic” variables?
Basic variables solve the current equations and take on nonzero values; nonbasic variables are held at zero.
63
How do you pick which variable should enter the basis?
Choose a nonbasic variable whose coefficient in the objective row would increase the objective if you raised it.
64
How do you choose which variable should leave the basis?
For each basic variable, calculate how much you can increase the entering variable before the basic one hits zero; the smallest limit determines who leaves.
65
What is a pivot operation?
Rewriting one equation to swap a nonbasic entering variable into the basis and push a basic one out, then updating all other equations.
66
When does the simplex algorithm terminate?
When no nonbasic variable has a coefficient that can improve the objective—so you’re already at the best corner.
67
What is a slack variable’s geometric meaning?
It measures the “distance” from a constraint wall to the current point along that constraint’s direction.
68
Why don’t we need derivatives in simplex?
Because all changes are linear adjustments of rows; you only compare and combine numbers, no slopes involved.
69
What happens if a linear program has no feasible corners?
That means the constraints conflict and there’s no solution meeting all of them.
70
What does it mean if a pivot can increase the entering variable without bound?
The linear program is unbounded in that direction and the objective can go to infinity.
71
Give a real-world example of linear programming.
llocating advertisement budget across channels to maximize votes or sales under cost limits.
72
Why is the simplex method still widely used?
Because it’s fast in practice, simple to implement, and reliable for large, real-world problems.
73
What is a spanning tree of a graph?
A cycle-free subgraph that includes every vertex of the original graph.
74
What makes a spanning tree “minimum”?
Its total edge-weight sum is as small as possible among all spanning trees.
75
In Prim’s algorithm, how do you pick the first vertex?
Arbitrarily, you can start anywhere.
76
At each step of Prim’s, which edge do you add?
The lowest-cost edge that connects a tree vertex to a non-tree vertex.
77
Why never form a cycle in Prim’s?
Because you only add edges that go from the current tree to outside vertices.
78
How do you keep track of the cheapest way to reach each outside vertex?
Maintain for each outside vertex v: the minimum edge weight bestCost[v] and its neighbor closest[v].
79
When do you stop Prim’s algorithm?
Once every vertex has been moved into the tree set.
80
What is the time complexity of a naive Prim’s implementation?
O(v^2), because of each of the V-1 steps scans up to V vertices.
81
Why is a minimum spanning tree useful in networks?
It models the cheapest way to ensure full connectivity without redundant links.
82
Name one real-world application of MSTs.
Designing cost-effective electrical grids, road networks, or communication backbones.
83
What data structures are needed for the simple array-based Prim’s?
Two sets (or boolean arrays) for in-tree vs out-tree, plus arrays bestCost[] and closest[].
84
What is the goal of Kruskal’s algorithm?
To build a spanning tree of minimum total weight by repeatedly adding the next-lightest edge that doesn’t form a cycle.
85
How does Kruskal’s algorithm choose which edge to add next?
It takes the cheapest remaining edge that does not form a cycle with those already chosen.
86
Why does Kruskal sort all edges at the start?
So it can consider them in ascending cost order, ensuring the cheapest viable edge is always picked next.
87
What data structure trick prevents cycle formation in Kruskal’s algorithm?
A disjoint-set (union-find) that tracks which component each vertex belongs to.
88
What is the time complexity of Kruskal’s algorithm?
O(ElogE), dominated by sorting the edges (which is O(ElogV) as well).
89
In Kruskal’s pseudocode, when do you merge two vertex groups?
Exactly when you add an edge whose endpoints are currently in different groups.
90
What is the “cut property” lemma used in the correctness proof?
The cheapest edge crossing any partition of the vertices must appear in every MST.
91
How does Kruskal’s guarantee a minimal total cost?
By always choosing the least-cost edge that keeps the forest cycle-free, it never forgoes a necessary cheap connection.
92
What happens if you run out of edges before you add V – 1 edges?
The graph is disconnected and no spanning tree exists.
93
How can you derive a Travelling Sales Problem tour from an MST for a 2-approximation?
Double all MST edges to form a circuit, then shortcut repeated vertices to produce a valid tour with cost < 2× optimum.
94
Why does shortcutting in the Travelling Sales Problem heuristic not increase total cost?
Because edge weights satisfy the triangle inequality, so skipping intermediate vertices can only shorten or keep the same path length.
95
In real-world MST applications, why might edge weights be all distinct?
To guarantee a unique MST; if weights tie, any one of the minimal spans is acceptable.
96
What are the two main phases of Kruskal’s algorithm?
Sorting the edges, then repeatedly scanning the sorted list and using union-find to build the MST.
97
Why is Kruskal’s algorithm called “greedy”?
Because it makes the locally optimal (cheapest-edge) choice at each step without backtracking.
98
What is the convex hull of a finite set of points?
The smallest convex shape (intersection of all convex sets) that contains every point.
99
How do you pick the starting point in Gift-Wrapping?
Choose the point with the smallest x-coordinate (if tied, the one with largest y).
99
What role does the “previous” point r play?
It defines your incoming direction so you can measure clockwise angles from r→h.
100
How do you select the next hull point?
Scan all other points (plus the start), pick the one with the smallest clockwise angle from your current direction.
101
When does Jarvis’s Gift-Wrapping stop?
As soon as you return to the initial starting point h, having wrapped all hull edges.
102
Why does the algorithm never form a concave turn?
Because at each step it always picks the point that makes the smallest clockwise angle, ensuring you stay on the outside boundary.
103
What is the time complexity of Gift-Wrapping?
O(|S|·|H|) where |S| = total points and |H| = hull points, making it output-sensitive.
104
Name one practical application of computing convex hulls mentioned in the lecture.
Estimating an animal’s home range by “peeling” away outlier observations.
105
How does the algorithm handle ties in angular comparison?
It implicitly breaks ties by the order of scanning.
106
Why can gift-wrapping be O(n²) in the worst case?
Because it may scan all remaining points for each hull edge, leading to ∼n scans of ∼n points.
107
How do you choose the starting point p₀ in Graham’s scan?
The point with the smallest x-coordinate (if tied, the one with smallest y).
108
After picking p₀, how are the other points ordered?
By increasing polar angle around p₀ (counter-clockwise). If angles tie, keep only the farthest point.
109
What data structure does Graham’s scan use to build the hull?
A stack that holds the current hull vertices.
110
What test determines whether to pop the stack during the scan?
If the last two points on the stack and the new point make a clockwise (right) turn, you pop.
111
When do you stop popping and push the new point?
Once the stack’s top two points and the new point make a counter-clockwise (left) turn, then push the new point.
112
How many times can each point be pushed or popped?
At most once each, so the scanning phase is O(n).
113
What is the overall time complexity of Graham’s scan?
O(n log n), dominated by the initial sort.
114
What is “interior elimination” in improving Graham's Scan
Pre-discarding points that lie strictly inside a simple enclosing quadrilateral so they need not be sorted or scanned.
115
How does convex-hull help in computing cluster diameter?
The farthest pair of points in a set must both lie on the hull, so you only check hull points.
116
How does convex-hull aid classification of two point sets?
Two sets are linearly separable only if their convex hulls do not intersect.
117
What is the goal of reverse error correction (ARQ)?
To detect errors at the receiver and request a retransmission from the sender.
118
Why is ARQ unsuitable for broadcasts and real-time streams?
It requires two-way feedback and adds delay while waiting for retransmits.
119
How does a simple parity check detect errors?
By appending one extra bit equal to the XOR of all data bits, catching any odd number of bit flips.
120
What parity-check error patterns are not detected?
Any error that flips an even number of bits, since their XOR remains zero.
121
What’s the basic idea behind a CRC?
Treat the message as a polynomial, divide by a fixed generator polynomial, and append the remainder as check bits.
122
In polynomial form, what does the bit-pattern “1101” represent?
The polynomial x³ + x² + 1 (since coefficients map directly to bits).
123
Why is polynomial arithmetic helpful for CRCs?
Because shifts become multiplications by xⁿ and bitwise XOR is modular subtraction—ideal for hardware registers.
124
Outline the bitwise CRC algorithm’s two main steps per bit.
Shift the CRC register left with the next message bit in; if the shifted-out bit was 1, XOR with the low r bits of the generator.
125
How many steps does the bitwise algorithm take for an N-bit message and r-bit CRC?
Exactly N + r shift/XOR steps.
126
What classes of errors can a CRC-16 catch?
All single- and double-bit errors, all odd-numbered errors, all bursts up to 16 bits, and nearly all longer bursts.
127
Why is CRC detection so cheap in hardware?
It uses only small shift registers and XOR gates, with no multipliers or complex logic.
128
How does the receiver verify a CRC on arrival?
By dividing the received (message + CRC) by the same generator; a zero remainder means no detected errors.
129
What limitation does parity have that CRC overcomes?
Parity misses even-bit errors, whereas CRCs can catch structured bursts and patterns far beyond single bits.
130
Why must you pad the message with r zeros before computing the CRC remainder?
To reserve space for the r-bit remainder and ensure proper alignment in the polynomial division.
131
What is a repetition code and its main drawback?
Send each bit three times (000 or 111) and decode by majority vote; but it reduces throughput to one-third.
131
In a (7,4) Hamming code, how many parity bits are added, and where are they placed?
Three parity bits are interleaved among the four data bits in positions 1, 2, and 4 of the 7-bit word.
132
How are the parity bits in Hamming (7,4) computed?
p1 = d1 ⊕ d2 ⊕ d4
p2 = d1 ⊕ d3 ⊕ d4
p3 = d2 ⊕ d3 ⊕ d4
133
What linear-algebra tool encodes the 4 data bits into 7 code bits?
The 7×4 generator matrix G via the product R=G⋅D (mod 2).
134
How does the receiver locate a single flipped bit?
Multiply the received 7-bit vector by the 3×7 parity-check matrix H to get a 3-bit syndrome that indexes the error position.
134
After correcting the error in Hamming (7,4), how are the original data bits retrieved?
Apply the 4×7 decoding matrix M to the corrected codeword, yielding the 4-bit data vector.
135
What kinds of errors can Hamming (7,4) detect but not correct?
Any two-bit error in the 7-bit word.
136
What is the Hamming distance between two codewords?
The number of bit positions in which they differ—used to measure error-detecting/correcting capability.
137
Why are Hamming codes called “forward error correction”?
Because the transmitter adds redundancy so errors can be corrected at the receiver without asking for retransmission.
138
Name two more advanced error-correction codes mentioned.
Reed–Solomon codes and Turbo codes (also LDPC).
139
What is the goal of data compression?
To remove redundant bits so that information (text, audio, images) uses fewer bits.
140
Why can’t any lossless code average fewer bits per symbol than the entropy?
Because entropy measures the minimum information needed to distinguish symbols uniquely.
140
What is entropy?
The theoretical lower bound on bits per symbol.
141
What is fixed-length coding?
Assigning every symbol the same number of bits (e.g., 3 bits each for 5 symbols), regardless of frequency.
142
What is a greedy algorithm in the context of compression?
One that repeatedly makes the locally best choice, hoping this yields an overall optimal code.
143
What key property makes Huffman codes “instantaneous”?
They are prefix-free: no codeword is a prefix of another, so decoding can proceed bit by bit.
144
In Huffman coding, which two symbols are merged at each step?
The two symbols (or nodes) with the smallest probabilities.
145
After merging two lowest-probability nodes, what code bits are assigned?
One branch gets “0” and the other “1” when you link them to their parent.
146
What data structure speeds up selecting the two least-probable nodes?
A min-heap (priority queue) keyed by frequency.
147
What is the time complexity of building a Huffman tree for n symbols?
O(nlogn)
148
Name two applications that use Huffman coding.
JPEG image compression and MPEG video compression.
149
Why must symbol frequencies be known in advance for Huffman coding?
Because the tree structure—and thus code lengths—depend on those frequencies.
150
What happens if a bit error occurs in a Huffman-encoded stream?
It can misalign decoding and corrupt all subsequent symbols until resynchronization.
151
What is the main limitation of Huffman coding compared to arithmetic coding?
It codes whole symbols at a time and can’t achieve fractional-bit precision per symbol.
152
What type of model does LZW use for compression?
An adaptive dictionary model that learns new strings as it encodes.
153
What’s in the initial dictionary for LZW?
Every single symbol (e.g. each byte/character) mapped to a unique codeword.
154
How do you choose which string w to output during encoding?
Pick the longest prefix of the remaining input that exists in the dictionary.
155
After outputting w, what new entry do you add to the dictionary?
The string w followed by the very next symbol in the input.
156
Why can the decoder rebuild the same dictionary without receiving it?
It follows the same rule—after outputting the previous string, it appends the first character of the current string to form the new entry.
157
What special case must the LZW decoder handle when a code isn’t yet in its dictionary?
It constructs the entry as “previous output string + its own first character,” then outputs that.
158
Give the LZW code sequence for “ABABABABA” starting from an initial “A”→0, “B”→1 dictionary.
0 1 2 4 3.
159
Why is LZW popular in hardware implementations?
It uses only simple dictionary lookups and updates—no complex arithmetic or probability models.
160
Name two common uses of LZW.
GIF image compression and the Unix “compress” utility.
161
What happens to compression performance if the input has no repeated substrings?
LZW adds many single‐symbol entries but gains little compression, so it performs poorly on highly random data.
162
What two guarantees does Bitcoin’s blockchain provide?
That transaction history cannot be amended and double-spends are prevented.
163
How does each block in the chain “link” to its predecessor?
By including the predecessor’s cryptographic hash in its header.
164
Why does a hash chain make tampering impractical?
Any bit-flip in one block changes its hash, which then invalidates all later blocks’ hashes.
165
What is Proof-of-Work in Bitcoin mining?
Finding a nonce so that the SHA-256 hash of the block meets a difficulty target (enough leading zeros).
166
Why is PoW easy to verify but hard to compute?
Verifying just recalculates one hash; finding a valid nonce requires many trial hashes.
167
What rule decides which competing chain the network accepts?
The longest chain (i.e., the one with the most total proof-of-work)
168
Name the family of hash functions used in Bitcoin.
SHA-2, specifically SHA-256.
169
What are the three “liveness/persistence/consensus” goals of blockchain?
Ensure new transactions get added (liveness), old ones can’t change (persistence), and all nodes agree (consensus).
170
What are some major drawbacks of PoW?
It’s energy-intensive and limits transaction throughput.
171
What problem does public-key cryptography solve?
How to agree on a secret key or encrypt messages over an insecure channel with no private meeting
172
In the paint-mixing analogy for Diffie–Hellman, what does the shared final color represent?
The shared secret key that Alice and Bob both compute but never send directly
173
What is a one-way function in cryptography?
A function easy to compute in one direction but hard to invert (e.g. modular exponentiation)
174
During RSA key generation, how is the public key (n,e) formed?
Multiply two large primes p and q to get n, compute φ=(p–1)(q–1), then pick a number e less than and coprime to φ and publish (n,e)
175
How do you compute the RSA private exponent d?
A number that satisfies e*d mod φ ≡ 1
176
What are the RSA encryption and decryption formulas?
Encryption: C = Mᵉ mod n; Decryption: M = Cᵈ mod n
177
Why is RSA secure even though the public keys and algorithms are known?
Because recovering d or M from C without factoring n or solving the discrete logarithm is computationally infeasible
178
How often must Alice and Bob re-run Diffie–Hellman to get a fresh shared key?
Every time they need a new shared secret—they can repeat the exchange as often as needed
179
What underlying hard problem secures Diffie–Hellman and RSA?
The difficulty of discrete logarithms (DH) and integer factorization (RSA) respectively
180
Why do we convert time-domain signals to the frequency domain?
To see which sine-wave frequencies make up the signal, which can simplify analysis and processing.
181
What does the Continuous Fourier Transform (CFT) do?
It expresses a continuous signal as an integral of all possible sine and cosine waves, yielding a spectrum function F(ω).
182
How does the Discrete Fourier Transform (DFT) differ from the CFT?
The DFT works on a finite list of N samples, replacing integrals with sums over those samples and producing N discrete frequency coefficients.
183
What is the basic cost of computing a DFT directly for N points?
On the order of N^2 complex multiplications.
184
What does the Fast Fourier Transform (FFT) improve, and to what complexity?
It reduces the DFT’s cost from N^2 down to roughly NlogN, making large transforms practical.
185
What is aliasing, and how does it arise?
When the sample rate is too low, higher-frequency components get misinterpreted as lower ones.
186
What is spectral leakage, and how can you reduce it?
Leakage is the spreading of energy into adjacent frequency bins because you only have a finite number of samples; applying window functions (Hanning, Hamming) helps.
187
How do you recover time-domain samples from DFT coefficients?
By summing all frequency components multiplied by their complex exponentials and dividing by N (the inverse DFT).
188
Why are window functions used before a DFT?
To taper the signal edges and reduce spectral leakage in the resulting frequency spectrum.
189
How many times do you split an N-point DFT in the classic Cooley–Tukey FFT?
log^2 N times, until you reach trivial 1-point DFTs.
189
What is the main idea behind the FFT’s efficiency?
Recursively split the DFT into two half-size DFTs (even and odd samples) and then cheaply combine them, reducing work from N^2 to
Nlog^2 N.
190
Why is bit-reversal used on the input samples?
Because after successive even/odd splits, the natural processing order corresponds exactly to the bit-reverse of the original indices.
191
