Backtracking, Branch and Bound, Greedy Method Quiz

Reliable Data Transfer with TCP Sliding Window

• TCP sliding window ensures reliable data transfer by allowing the sender to transmit multiple packets before waiting for an acknowledgment from the receiver.
• It helps to improve network efficiency by reducing the number of acknowledgments and increasing the amount of data transmitted.

ALOHA Protocol

• ALOHA is a protocol used for multiple access in a network.
• It works by allowing each node to transmit data at any time, but if a collision occurs, the nodes wait for a random time before retransmitting.
• Pure ALOHA and Slotted ALOHA are two variations of the protocol, with Slotted ALOHA being more efficient.

Optimality Principle in Routing

• The optimality principle in routing states that the best path to a destination is the one that minimizes the total cost or distance.
• In circuit switching, the optimality principle is used to establish a dedicated connection for the entire duration of the communication.
• In packet switching, the optimality principle is used to route each packet individually, allowing for more flexibility and adaptability.

Flooding and Multicast

• Flooding is a technique used to send a packet to every node in a network, which can be inefficient and cause network congestion.
• Multicast is a technique used to send a packet to a group of nodes in a network, reducing network traffic and improving efficiency.

Kruskal's Algorithm

• Kruskal's algorithm is used to find the minimum spanning tree of an undirected graph.
• It works by sorting the edges of the graph in non-decreasing order and then selecting the edges that do not form a cycle.
• The algorithm is justified because it ensures that the total weight of the selected edges is minimum.

Longest Common Subsequence (LCS)

• The LCS algorithm is used to find the longest common subsequence of two strings.
• The algorithm works by building a matrix and filling it in a bottom-up manner, with the final answer being the top-right element of the matrix.

Bellman-Ford Algorithm

• The Bellman-Ford algorithm is used to find the shortest path from a source vertex to all other vertices in a graph.
• It works by relaxing the edges of the graph and updating the distances of the vertices.
• The algorithm can handle negative weight edges and detects negative weight cycles.

Backtracking and Branch and Bound Algorithms

• The Backtracking algorithm is used to find a solution by recursively exploring all possible solutions.
• The Branch and Bound algorithm is used to find a solution by recursively exploring all possible solutions and bounding the search space.
• The key difference between the two algorithms is that Branch and Bound uses bounding to prune the search space.

Greedy Method

• The Greedy Method is a technique used to find a solution by making the locally optimal choice at each step.
• Three properties of the Greedy Method are:
  • Optimal substructure: the problem can be broken down into smaller subproblems.
  • Greedy choice: the locally optimal choice is made at each step.
  • Feasibility: the solution is feasible at each step.

Disjoint Set

• A Disjoint Set is a data structure used to keep track of a set of disjoint sets.
• Supported operations by the algorithm are:
  • MakeSet: creates a new set.
  • Find: finds the representative of the set.
  • Union: merges two sets.

Deterministic and Nondeterministic Algorithms

• Deterministic algorithms are algorithms that always produce the same output for a given input.
• Nondeterministic algorithms are algorithms that may produce different outputs for a given input.
• Greedy methods are generally deterministic, but may not always produce the optimal solution.

Dynamic Programming and Shortest Path Problem

• Dynamic Programming is a technique used to solve problems by breaking them down into smaller subproblems and solving each subproblem only once.
• The Shortest Path problem is a problem of finding the shortest path between two vertices in a graph.
• Dynamic Programming can be used to solve the Shortest Path problem by building a table and filling it in a bottom-up manner.

Time Complexity

• The time complexity for finding 'n' and 'e' edges is O(n + e), where 'n' is the number of vertices and 'e' is the number of edges.

Algorithm

• An algorithm is a well-defined procedure that takes some input and produces a corresponding output.
• An algorithm must satisfy the following criteria:
  • Finiteness: the algorithm must terminate after a finite number of steps.
  • Definiteness: the algorithm must be well-defined and produce the same output for a given input.
  • Effectiveness: the algorithm must be efficient and produce the output in a reasonable amount of time.
  • Correctness: the algorithm must produce the correct output for a given input.

Maximum Flow Problem

• The maximum flow problem is a problem of finding the maximum flow that can be sent from a source vertex to a sink vertex in a network.
• The maximum flow can be computed in O(m) time using the Ford-Fulkerson algorithm, where 'm' is the number of edges.