Algorithms that Changed the World Flashcards
What is an Algorithm?
A finite set of precise instructions for performing a computation or for solving a problem.
What is the PageRank algorithm designed to do?
To rank web pages by importance based on their hyperlink structure, helping users find the most relevant pages in a massive, unstructured web.
What are the two main ideas behind PageRank?
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.
How does PageRank define page importance?
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.
What is the sink page problem in PageRank?
Sink pages have no outbound links, which can absorb all rank. The solution is to redistribute their rank equally across all pages.
What is the cycle page problem in PageRank?
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.
What is the damping factor in the Random Surfer Model?
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.
What is the time complexity of the PageRank algorithm?
O(kN²), where k is the number of iterations and N is the number of pages.
What are the five key components of the TCP/IP Stack?
Application Layer, Transport Layer,
Network Layer,
Data Link Layer,
Physical Layer
What is routing and forwarding?
Routing - Determines the full end-to-end path through a network.
Forwarding - Determines how a router handles an individual packet using a forwarding table.
What is Packet Switching?
A communication method where data is split into packets and sent independently through a network.
What are global and decentralised routing algorithms?
Global routing algorithms have full knowledge of topology and link costs, and decentralised routing algorithms only know local neighbours and link costs.
What are static and dynamic routing algorithms?
Static ones change slowly, and dynamic ones update periodically and react to network changes.
What does Dijkstra’s algorithm compute?
The least-cost path from a source node to all other nodes in a network with non-negative link costs.
What type of routing algorithm is Dijkstra’s?
Link State routing algorithm, meaning it is global and static.
What is the main principle behind Dijkstra’s algorithm?
Greedy and iterative: after k iterations, the shortest paths to k nodes are known.
What is the complexity of Dijkstra’s algorithm (naive implementation)?
O(n^2), where n is the number of nodes.
Why does the Internet need more than one routing algorithm?
Because link state algorithms respond slowly to changes, consume bandwidth with large tables, and don’t scale well for large or dynamic networks.
What are the three main characteristics of DV routing algorithms?
Distributed (no global knowledge), Iterative (keep updating), Asynchronous (don’t all update at the same time).
How do DV routing algorithms work?
WAIT for changes in local links. RECOMPUTE its DVs. NOTIFY only if DV to any destination has changed.
What is the purpose of Poisoned Reverse in DV routing?
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.
What is the O notation of Bellman-Ford?
O(|N||E|)
Why is hierarchical routing necessary on the Internet?
Because the Internet is too large to maintain a flat routing structure; storing all destinations and exchanging updates would consume too much bandwidth.
What is an Autonomous System (AS)?
A group of routers under a single administrative domain that run the same intra-AS routing protocol.
What are the two types of routing in a hierarchical routing system?
Intra-AS, and Inter-AS
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.
What does intra-AS routing focus on?
Performance — since all routers are under one admin, there’s no need for policy decisions.
What does inter-AS routing focus on?
Policy — administrators decide how traffic is routed between ASes.
What are the benefits of hierarchical routing?
Reduces routing table size, limits traffic update scope, improves performance, and supports routing policies
Which protocols are typically used for intra-AS routing?
Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)
Which protocol is typically used for inter-AS routing?
BGP (Border Gateway Protocol)
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.
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.
