Discrete Math Quiz: Choosing Discrete Methods
19 questions · exam conditions
0:00
Choosing Discrete MethodsQuestion 1 of 19

A telecommunications company is designing a network where data packets must be routed through multiple nodes to reach their destinations. Each node has a limited processing capacity, and the company wants to maximize the total data throughput from multiple source nodes to multiple destination nodes. The network has redundant paths, and the goal is to utilize them optimally without exceeding any node's capacity constraints. Which approach should the company use?

Shortest path algorithms with capacity constraints to find efficient routes that respect node processing limitations
Minimum cost flow to find the most economical routing paths while maintaining acceptable data transmission rates
Maximum bipartite matching to optimally pair source nodes with destination nodes for balanced load distribution
Multi-commodity flow algorithms to handle multiple source-destination pairs while respecting individual node capacity limits
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Choosing Discrete Methods

Practice Choosing Discrete Methods in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Choosing Discrete Methods, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

A telecommunications company is designing a network where data packets must be routed through multiple nodes to reach their destinations. Each node has a limited processing capacity, and the company wants to maximize the total data throughput from multiple source nodes to multiple destination nodes. The network has redundant paths, and the goal is to utilize them optimally without exceeding any node's capacity constraints. Which approach should the company use?

  1. Shortest path algorithms with capacity constraints to find efficient routes that respect node processing limitations
  2. Minimum cost flow to find the most economical routing paths while maintaining acceptable data transmission rates
  3. Maximum bipartite matching to optimally pair source nodes with destination nodes for balanced load distribution
  4. Multi-commodity flow algorithms to handle multiple source-destination pairs while respecting individual node capacity limits (correct answer)
Explanation: When you encounter network optimization problems involving multiple sources, multiple destinations, and capacity constraints, you're dealing with flow network theory. The key insight here is recognizing that this scenario requires handling simultaneous flows between different source-destination pairs while respecting node capacity limits. Multi-commodity flow algorithms (D) are specifically designed for exactly this situation. They can optimize multiple simultaneous flows from different sources to different destinations while ensuring that the total flow through any node doesn't exceed its processing capacity. This approach treats each source-destination pair as a separate "commodity" and finds the optimal routing that maximizes overall throughput across all pairs simultaneously. Option A falls short because shortest path algorithms, even with capacity constraints, typically handle single source-destination pairs and don't optimize across multiple simultaneous flows. They might find good individual paths but won't achieve global optimization. Option B focuses on cost minimization rather than throughput maximization. Minimum cost flow algorithms optimize for economic efficiency, not maximum data transmission, which misses the primary objective. Option C addresses a different problem entirely. Maximum bipartite matching creates one-to-one pairings between sources and destinations but doesn't handle the routing paths or capacity constraints that are central to this network design challenge. Remember: when you see "multiple sources," "multiple destinations," and "capacity constraints" together, think multi-commodity flow. This is the standard approach for telecommunications network optimization where you need to balance competing flows while respecting infrastructure limitations.

Question 2

A software development team is managing dependencies between modules in a large codebase. Some modules must be compiled before others due to dependencies, and the team wants to identify the optimal build order that minimizes compilation time. Additionally, they need to detect any circular dependencies that would make the build impossible. The team has a complete list of which modules depend on which other modules. Which discrete method should they employ?

  1. Graph coloring to assign compilation priorities to modules while avoiding conflicts between dependent modules
  2. Critical path method to find the longest dependency chain and optimize the overall compilation schedule
  3. Minimum spanning tree to reduce the number of dependencies while maintaining necessary compilation relationships
  4. Topological sorting to determine a valid build order, combined with cycle detection to identify circular dependencies (correct answer)
Explanation: When you encounter problems involving dependencies, ordering, and cycle detection in computer science, you're dealing with directed graph algorithms. The key insight is recognizing that modules and their dependencies form a directed acyclic graph (DAG) - assuming no circular dependencies exist. Topological sorting (answer D) is exactly the right tool here because it produces a linear ordering of vertices where every directed edge goes from an earlier vertex to a later one. This perfectly matches the compilation requirement: if module A depends on module B, then B must be compiled before A. Additionally, topological sorting algorithms inherently detect cycles - if a cycle exists, no valid topological order is possible, which directly identifies circular dependencies. Answer A is incorrect because graph coloring assigns labels to vertices based on adjacency constraints, not dependency ordering. It doesn't solve the sequencing problem or detect cycles in the required way. Answer B confuses this with project scheduling. While critical path method finds the longest path in a project network, the problem asks for a valid build order for all modules, not just identifying the bottleneck path. CPM also typically works with weighted graphs representing task durations. Answer C misapplies minimum spanning tree concepts. MST finds the cheapest way to connect all vertices in an undirected graph, but dependencies are directional relationships that cannot be arbitrarily reduced without breaking functionality. Remember: dependency problems almost always point to topological sorting. Look for keywords like "ordering," "prerequisites," "dependencies," and "circular dependencies" as strong indicators.

Question 3

A city planner is designing evacuation routes for emergency situations. The city has multiple exit points, and residents must be able to reach any exit point through routes that remain functional even if any single road is blocked. The planner wants to ensure maximum resilience by designing a road network where there are always alternative paths available. Which graph theory concept should guide the design?

  1. Minimum cut algorithms to identify the most vulnerable points in the network that could isolate residential areas
  2. Hamiltonian paths to guarantee that every neighborhood can be visited in a single evacuation route without repetition
  3. kk-connectivity to ensure multiple edge-disjoint paths exist between residential areas and exit points for fault tolerance (correct answer)
  4. Maximum flow to determine the theoretical capacity limits for evacuating residents through the available road network
Explanation: When you encounter emergency planning or fault-tolerant network design problems, think about connectivity and redundancy. The key challenge here is ensuring the network remains functional even when components fail. The correct approach is C) kk-connectivity. This concept measures how many vertex-disjoint or edge-disjoint paths exist between any two points in a network. For evacuation routes, you need edge-disjoint paths (paths that don't share roads) so that if any single road is blocked, alternative routes remain available. A 2-edge-connected graph guarantees that removing any single edge won't disconnect the network, which directly addresses the "single road blocked" requirement. A) Minimum cut algorithms identify bottlenecks but don't inherently provide the redundant path structure needed. Finding vulnerable points is useful analysis but doesn't guide the actual design of resilient connections. B) Hamiltonian paths require visiting every vertex exactly once in a single path. This is irrelevant for evacuation scenarios where residents need flexible routes to the nearest exit, not a grand tour of all neighborhoods. D) Maximum flow calculates capacity limits for moving resources through a network, but the question emphasizes route availability under failure conditions, not throughput capacity. Flow analysis assumes the network structure is already established. Study tip: In graph theory applications, match the problem type to the concept. Fault tolerance and redundancy → connectivity; capacity and throughput → flow; optimization tours → Hamiltonian/Eulerian paths. The phrase "alternative paths" is your cue that connectivity concepts are needed.

Question 4

A logistics company needs to schedule deliveries to 12 cities, where certain pairs of cities have time conflicts due to traffic patterns and driver availability. The company has data showing which pairs of cities cannot be visited on the same day. They want to find the minimum number of days needed to complete all deliveries while respecting these constraints. Additionally, they want to ensure that cities with the highest priority are scheduled first within each day. Which combination of discrete methods should they apply?

  1. Graph coloring for day assignment followed by topological sorting for priority ordering within each day (correct answer)
  2. Minimum spanning tree to connect cities efficiently, then greedy scheduling based on distance priorities
  3. Maximum matching to pair cities optimally, followed by bin packing to group pairs into days
  4. Network flow modeling to balance daily workloads, combined with dynamic programming for optimal sequencing
Explanation: This requires graph coloring to assign cities to days (where conflicts represent edges and colors represent days), followed by topological sorting to order priorities within each day. MST (B) doesn't address scheduling conflicts. Maximum matching (C) pairs items but doesn't handle the constraint satisfaction aspect. Network flow (D) doesn't directly solve the coloring problem for conflict resolution.

Question 5

A genetic research lab is studying inheritance patterns where certain traits are passed from parents to offspring following specific rules. The researchers have identified that some gene combinations are lethal and cannot appear in viable offspring, while others follow standard Mendelian inheritance. They want to calculate the probability of specific trait combinations appearing in the third generation, given the constraints on viable gene combinations. Which discrete method is most appropriate?

  1. Constrained combinatorial enumeration to count valid genetic combinations while excluding lethal combinations from probability calculations
  2. Markov chain modeling to track genetic state transitions across generations with transition probabilities based on inheritance rules (correct answer)
  3. Dynamic programming to build up generational probabilities while memoizing intermediate results for complex trait interactions
  4. Graph-based dependency analysis to model the relationships between different genes and their expression patterns
Explanation: This is a multi-generational probability problem where each generation's genetic composition depends only on the previous generation (Markov property). Inheritance rules define transition probabilities between genetic states. Constrained enumeration (A) counts combinations but doesn't handle generational transitions. Dynamic programming (C) could work but isn't the most natural fit for this state-transition problem. Graph dependency analysis (D) models relationships but not probabilistic inheritance.

Question 6

A tournament organizer needs to create a bracket system for 16 teams where each team must play exactly once against every other team in their group before advancing to elimination rounds. The organizer wants to minimize the total number of rounds while ensuring that no team has more than one game per round. After the round-robin phase, teams will be ranked and entered into a single-elimination tournament. Which discrete method should be used to design the optimal round-robin schedule?

  1. Graph theory using Hamiltonian cycles to create rotation schedules that minimize the number of required rounds
  2. Integer programming to optimize team assignments while satisfying scheduling constraints and fairness requirements
  3. Combinatorial design theory to construct balanced incomplete block designs for equitable team pairings
  4. Matching theory to create perfect matchings for each round, ensuring all teams play simultaneously (correct answer)
Explanation: This is a round-robin tournament scheduling problem that requires creating perfect matchings for each round so all teams play simultaneously. Each round needs a perfect matching of the 16 teams into 8 games. Hamiltonian cycles (A) don't directly solve the simultaneous pairing problem. Integer programming (B) could work but is overly complex for this standard matching problem. Block designs (C) are for different combinatorial structures.

Question 7

A cryptography researcher is analyzing the security of a communication protocol where messages are encoded using a sequence of mathematical operations. Each operation depends on the result of previous operations, and the researcher wants to determine how many distinct encoding sequences are possible for messages of length nn. The encoding rules specify that certain operation pairs cannot be adjacent, and some operations can only appear after specific prerequisite operations have been used. Which approach should be used?

  1. Recurrence relations with constraint satisfaction to count valid sequences while enforcing adjacency and prerequisite rules
  2. Generating functions to encode the combinatorial structure of valid operation sequences with forbidden patterns
  3. Dynamic programming on sequence states to build up counts of valid encodings while tracking constraint satisfaction (correct answer)
  4. Graph enumeration algorithms to count valid paths through the state space of allowable operation transitions
Explanation: This is a constrained sequence counting problem where the state at each position depends on previous operations (for prerequisites) and adjacent operations (for forbidden pairs). Dynamic programming with state tracking is ideal for building up valid sequence counts. Recurrence relations (A) work but don't naturally handle complex state dependencies. Generating functions (B) are powerful but overly complex for this state-dependent problem. Graph enumeration (D) could work but is less direct than DP.

Question 8

A computer science researcher is designing an error-correcting code for data transmission where each message is encoded with additional redundancy bits. The goal is to create a code that can detect and correct any single-bit error while using the minimum number of redundancy bits. The researcher needs to determine the optimal placement of these bits within the encoded message and verify that the resulting code can distinguish between all possible single-bit error patterns. Which discrete mathematics approach is most appropriate?

  1. Graph theory to model bit dependencies and find optimal redundancy placement using domination and covering concepts
  2. Combinatorial design theory to arrange redundancy bits in patterns that maximize error detection and correction capabilities
  3. Linear algebra over finite fields to construct generator and parity-check matrices for systematic error-correcting codes (correct answer)
  4. Boolean algebra and logic circuits to design efficient encoding and decoding algorithms for real-time error correction
Explanation: When you encounter problems about error-correcting codes that need to detect and correct single-bit errors with minimum redundancy, you're dealing with the mathematical foundation of coding theory. The key insight is that error correction requires systematic mathematical structures that can uniquely identify and fix corruption patterns. Linear algebra over finite fields (option C) provides the correct framework because error-correcting codes like Hamming codes are fundamentally built using matrices over finite fields (typically GF(2) for binary data). The generator matrix creates codewords with built-in redundancy, while the parity-check matrix enables syndrome decoding—where each single-bit error produces a unique syndrome that pinpoints the error location. This mathematical structure guarantees minimum redundancy while achieving single-error correction capability. Option A is incorrect because while graph theory can model relationships, it doesn't provide the algebraic structure needed for systematic error correction or the mathematical guarantees about minimum distance properties. Option B fails because combinatorial designs focus on arrangement patterns but lack the linear algebraic framework essential for encoding/decoding operations and syndrome calculation. Option D is wrong because Boolean algebra addresses circuit implementation details, not the underlying mathematical theory that determines code parameters and proves error-correction capabilities. The linear algebra approach directly determines the minimum number of redundancy bits needed (using the Hamming bound) and constructs codes that achieve this theoretical limit. Study tip: For coding theory problems, remember that the mathematical foundation always involves linear algebra over finite fields—this distinguishes true error-correcting codes from simple detection schemes or implementation details.

Question 9

A social media company wants to analyze the spread of misinformation through their platform. They model users as nodes and connections as edges, where misinformation can spread from any user to their direct connections. The company has identified 5 key influencers who might be sources of misinformation, and they want to determine the minimum number of users they need to monitor to ensure that any misinformation from these sources is detected before it spreads beyond 2 degrees of separation. Which discrete method is most appropriate for solving this optimization problem?

  1. Graph coloring to assign monitoring roles while avoiding conflicts between adjacent users
  2. Minimum dominating set to find the smallest collection of users that can observe all potential spread paths (correct answer)
  3. Maximum flow algorithms to determine the bottlenecks in information transmission across the network
  4. Shortest path algorithms to calculate the fastest routes for misinformation to travel between users
Explanation: This is a dominating set problem where we need to find the minimum number of monitors such that every user is either a monitor or adjacent to a monitor, ensuring detection within 2 degrees. Graph coloring (A) deals with assignment conflicts, not coverage. Maximum flow (C) measures capacity, not monitoring coverage. Shortest paths (D) find routes but don't solve the monitoring optimization problem.

Question 10

A cybersecurity team is analyzing network vulnerabilities where an attacker needs to compromise a sequence of systems to reach a target. Each system has multiple possible entry points, and the attacker must find a path where each step depends on successfully compromising the previous system. The team wants to calculate the total number of distinct attack sequences possible, considering that some systems can be compromised through multiple independent methods. Which discrete method is most suitable for this analysis?

  1. Dynamic programming with memoization to count paths while avoiding redundant calculations across overlapping subproblems (correct answer)
  2. Breadth-first search to systematically explore all possible attack routes from the starting point to the target
  3. Greedy algorithms to identify the most efficient attack path based on system vulnerability scores
  4. Linear programming to optimize the attack strategy subject to resource and time constraints
Explanation: This is a path counting problem with overlapping subproblems (multiple ways to reach intermediate systems), making dynamic programming with memoization ideal for efficient enumeration. BFS (B) explores paths but doesn't efficiently count all distinct sequences. Greedy algorithms (C) find one optimal path, not count all paths. Linear programming (D) optimizes continuous variables, not combinatorial counting.

Question 11

A data scientist is analyzing user behavior patterns on an e-commerce website. Users can be in one of several states (browsing, comparing, purchasing, abandoned cart), and they transition between states based on specific triggers. The scientist wants to predict the long-term probability distribution of users across these states and identify which states are most likely to lead to purchases. The transition probabilities between states are known and remain constant over time. Which mathematical framework should be applied?

  1. Markov chain analysis to find steady-state probabilities and analyze transition patterns between user behavior states (correct answer)
  2. Hidden Markov models to account for unobserved factors that influence user transitions between different behavioral states
  3. Bayesian networks to model the conditional dependencies between user characteristics and their behavioral state transitions
  4. Game theory to model the strategic interactions between users and the platform's recommendation algorithms
Explanation: This describes a standard Markov chain with known transition probabilities and observable states, perfect for steady-state analysis. Hidden Markov models (B) are for when states are unobserved, but here states are clearly defined and observable. Bayesian networks (C) model complex dependencies, but this is a simpler state-transition system. Game theory (D) models strategic interactions, not probabilistic state transitions.

Question 12

A research laboratory is designing experiments to test 6 different drug compounds across 4 treatment conditions. Each compound must be tested under each condition, but due to equipment limitations, only 3 experiments can be run simultaneously. The lab wants to minimize the total number of experimental sessions while ensuring that if any single session fails, the remaining data still allows for statistical analysis of each compound-condition combination.

Given the constraints described in the passage above, which experimental design approach would be most suitable for this scenario?

  1. Create a Latin rectangle design with compounds as rows and conditions as columns, then replicate for redundancy
  2. Implement orthogonal arrays to systematically cover all compound-condition interactions with minimal replication
  3. Use factorial design principles with blocking to account for session limitations and failure tolerance
  4. Apply resolvable balanced incomplete block design (RBIBD) with compound-condition pairs as treatments (correct answer)
Explanation: When you encounter experimental design problems involving coverage requirements, capacity constraints, and failure tolerance, you're dealing with combinatorial design theory. The key insight here is recognizing that you need complete coverage of all treatment combinations (6 compounds × 4 conditions = 24 pairs) while building in redundancy and respecting the 3-experiments-per-session limit. A resolvable balanced incomplete block design (RBIBD) perfectly fits these requirements. In this context, each "block" represents a session of 3 experiments, and "treatments" are the 24 compound-condition pairs. The design ensures every treatment appears multiple times across different blocks, providing the redundancy needed so that if one session fails, no treatment combination is completely lost. The "resolvable" property means you can partition the blocks into parallel classes where each treatment appears exactly once per class, giving you systematic coverage. Option A's Latin rectangle approach doesn't inherently provide failure tolerance or address the session size constraint. Option B's orthogonal arrays focus on factor interactions rather than treating each compound-condition pair as a distinct treatment requiring redundancy. Option C's factorial design with blocking doesn't specifically address the incomplete block structure needed when you can only run 3 experiments per session out of 24 total treatments. For discrete math design problems, always identify three key elements: what needs coverage (treatments), what the capacity constraints are (block sizes), and what redundancy requirements exist (replication). RBIBD is your go-to solution when you need systematic, balanced coverage with built-in redundancy across multiple incomplete sessions.

Question 13

A cybersecurity team needs to monitor network traffic by strategically placing intrusion detection sensors. The network has 25 nodes connected in a complex topology, and each sensor can monitor its host node plus all directly connected neighbors. The team wants to detect any intrusion with minimum sensor deployment cost, but also needs redundancy so that if any single sensor fails, the remaining sensors still provide complete network coverage. Which approach would be most effective?

  1. Find the minimum dominating set and then add sensors to ensure 2-domination coverage
  2. Solve the minimum 2-dominating set problem directly on the network graph
  3. Apply set cover with redundancy constraints where each network node must be covered by at least 2 sensor ranges (correct answer)
  4. Use vertex cover algorithms to ensure all network connections are monitored
Explanation: The problem requires that every node be covered by at least 2 sensors to handle single sensor failures, which is exactly set cover with redundancy constraints. Each sensor defines a set (itself plus neighbors), and we need sets such that every node appears in at least 2 chosen sets. Simply finding minimum dominating set then adding sensors (A) is not optimal. The 2-dominating set (B) requires every node to be within distance 2 of a dominating vertex, which is different from redundant coverage. Vertex cover (D) focuses on edges, not node coverage.

Question 14

A logistics company wants to determine the minimum number of distribution centers needed to serve 50 cities, where each center can serve cities within a 200-mile radius. The company has data on inter-city distances and wants to ensure every city is served by at least one center while minimizing total setup costs. Which discrete optimization approach best captures this problem structure?

  1. Minimum dominating set on a graph where edges connect cities within 200 miles
  2. Facility location problem with binary variables for center placement and service assignments
  3. Set cover problem where each potential center location covers a subset of cities (correct answer)
  4. Traveling salesman problem variant with multiple depot locations
Explanation: This is a classic set cover problem: each potential distribution center location defines a set (cities within 200 miles), and we want the minimum number of sets that cover all cities. Set cover directly models the coverage constraints and minimization objective. Minimum dominating set (A) is related but doesn't naturally incorporate the cost minimization aspect. Facility location (B) typically involves continuous location decisions and service costs, not just binary coverage. TSP (D) focuses on routing, not coverage.

Question 15

A university dining service wants to create weekly meal plans for students with dietary restrictions. There are 21 meals per week (3 per day), 8 different dietary categories (vegetarian, vegan, gluten-free, etc.), and each meal must satisfy multiple categories simultaneously. The service wants to maximize variety while ensuring each category appears in at least 6 meals per week. Which discrete method would best handle this multi-constraint optimization?

  1. Model as a Latin square design with meals as rows and dietary categories as symbols
  2. Use combinatorial design theory to create a balanced incomplete block design
  3. Apply graph coloring where meals are vertices and dietary conflicts create edges
  4. Formulate as a multi-objective integer programming problem with variety and coverage constraints (correct answer)
Explanation: When you encounter optimization problems with multiple simultaneous constraints and objectives, you need to identify whether the problem requires balancing competing goals while satisfying hard limits. This scenario involves maximizing meal variety while ensuring minimum coverage across dietary categories - a classic multi-objective optimization with constraint satisfaction. Option D correctly captures this as a multi-objective integer programming problem. You have integer variables (number of meals per category), multiple objectives (maximize variety, ensure coverage), and hard constraints (at least 6 meals per category, exactly 21 total meals). Integer programming excels at handling these simultaneous requirements and can optimize the trade-offs between variety and coverage systematically. Option A fails because Latin squares require each symbol to appear exactly once per row and column, but meals can satisfy multiple dietary categories simultaneously - the structure doesn't match. Option B misapplies combinatorial design theory; while balanced incomplete block designs handle coverage elegantly, they don't address the variety maximization objective or the flexibility of meals satisfying multiple categories. Option C incorrectly frames this as a graph coloring problem - there are no "conflicts" to avoid between dietary categories, and coloring focuses on avoiding adjacencies rather than optimizing coverage and variety. The key insight is recognizing when a problem has multiple competing objectives alongside hard constraints. Integer programming provides the mathematical framework to balance these trade-offs optimally, unlike purely structural approaches (Latin squares, block designs) or conflict-avoidance methods (graph coloring) that miss essential problem dimensions.

Question 16

A social media platform wants to recommend friend connections by analyzing user interaction patterns. The platform has a graph of 10,000 users where edges represent interactions, and it wants to identify groups of users who interact frequently within the group but rarely with users outside the group. The goal is to suggest connections within these groups. Which method would be most appropriate for this analysis?

  1. Apply maximum clique finding algorithms to identify densely connected user subsets
  2. Use community detection algorithms like modularity optimization or spectral clustering (correct answer)
  3. Implement minimum spanning tree algorithms to find the strongest connection patterns
  4. Apply graph coloring to partition users into non-interacting groups
Explanation: Community detection algorithms are specifically designed to find groups with dense internal connections and sparse external connections, which matches the problem description exactly. Maximum clique (A) finds completely connected subgroups, which is too restrictive for social networks. Minimum spanning tree (C) finds connectivity but doesn't identify community structure. Graph coloring (D) creates groups with no internal connections, which is the opposite of what's desired.

Question 17

A manufacturing company produces 5 different products using 3 machines. Each product requires specific processing times on each machine, and products must follow a fixed sequence through the machines. The company wants to determine the optimal production schedule to minimize total completion time when processing 20 jobs (4 of each product type). Which approach would be most suitable?

  1. Model as a job shop scheduling problem using mixed-integer programming with precedence constraints (correct answer)
  2. Apply the Hungarian algorithm for optimal assignment of jobs to machine time slots
  3. Use critical path method (CPM) to determine the longest processing sequence
  4. Implement a greedy algorithm based on shortest processing time first
Explanation: This is a classic job shop scheduling problem with precedence constraints (fixed sequence through machines) and the objective to minimize makespan. Mixed-integer programming can handle the complex sequencing and timing constraints. The Hungarian algorithm (B) is for assignment problems without sequencing constraints. CPM (C) is for project scheduling with fixed precedence, not manufacturing with machine capacity constraints. Greedy shortest-processing-time (D) doesn't account for machine sequencing requirements.

Question 18

A telecommunications company needs to design a network connecting 12 cities with fiber optic cables. The network must be resilient to single cable failures, meaning there should be at least two independent paths between any pair of cities. The company wants to minimize the total cable length while satisfying this reliability requirement. Which network design approach would be most appropriate?

  1. Find the minimum spanning tree and add the shortest additional edges for redundancy
  2. Solve the minimum 2-edge-connected spanning subgraph problem (correct answer)
  3. Apply Dijkstra's algorithm to find shortest paths and combine them into a network
  4. Use maximum flow algorithms to ensure sufficient capacity between all city pairs
Explanation: The requirement for resilience to single cable failures means the network must be 2-edge-connected (removing any single edge doesn't disconnect the network). The minimum 2-edge-connected spanning subgraph problem directly optimizes for minimum total length while ensuring this property. Simply adding edges to MST (A) is not guaranteed to be optimal. Dijkstra's algorithm (C) finds shortest paths but doesn't ensure the resulting network is 2-edge-connected. Maximum flow (D) addresses capacity, not connectivity requirements.

Question 19

A university scheduling system must assign 15 courses to 8 time slots such that no student has conflicts. Each student is enrolled in 3-5 courses, and the enrollment data shows complex overlapping patterns. The system also needs to minimize the number of back-to-back classes for students. If the primary goal is to find any feasible schedule quickly, which approach would be most effective?

  1. Formulate as a constraint satisfaction problem using backtracking with conflict-directed heuristics (correct answer)
  2. Apply simulated annealing with a cost function based on student conflicts and scheduling preferences
  3. Use dynamic programming on subsets of courses ordered by enrollment size
  4. Model as a minimum vertex cover problem on the course conflict graph
Explanation: For finding any feasible schedule quickly with hard constraints (no conflicts), constraint satisfaction with backtracking is most appropriate. The conflict-directed heuristics can efficiently prune the search space when conflicts arise. Simulated annealing (B) is better for optimization problems where some constraint violations might be acceptable. Dynamic programming (C) doesn't naturally fit this assignment structure. Minimum vertex cover (D) solves a different problem and doesn't address the scheduling assignment.