Test on Algorithms, Data Structures, and Numerical Methods

Question 1: The robot path planning grid in the factory includes an interconnected point at coordinates [80, 24].

A. Ano

B. Ne

Explanation: The factory grid is described as 80x24 interconnected points, with the upper left corner at [0,0]. This means the x-coordinates range from 0 to 79 and the y-coordinates range from 0 to 23. Therefore, a point at [80, 24] is outside this defined grid.

Question 2: According to the provided study materials for robot path planning, how should points lying inside an obstacle be handled within the graph structure?

A. They should be made inaccessible by other means.

B. They should be removed entirely from the graph.

C. They should be assigned a prohibitive traversal cost.

D. They should be replaced with boundary nodes.

Explanation: The study materials explicitly state: 'The program removes all the points lying inside the obstacle from the graph (or makes these points inaccessible by other means)'. Therefore, both removing the points and making them inaccessible are valid methods described.

Question 3: When constructing a table showing the time it takes to perform 'n' operations for various time complexities, it is advised to use time units that are most appropriate for humans to understand, potentially varying the units.

A. Ano

B. Ne

Explanation: The study materials state: 'Use time units most appropriate for humans to understand the impact of different time-complexities. Note: you may need to use various time units.'

Question 4: Given two arrays A and B of integers ranging from 0 to 9, an efficient algorithm to determine if their factorial products are the same should primarily rely on which principle, according to the provided study materials?

A. Directly calculating the factorial product for both arrays and comparing the final large numbers.

B. Comparing the frequency counts of prime factors for each number in both arrays.

C. Sorting both arrays and then comparing them element by element.

D. Converting all factorials into logarithms, summing them, and comparing the sums.

Explanation: The study materials provide a hint for the 'factorial product comparison algorithm': 'do not calculate the factorial product, think about the definitions of the factorial'. This suggests avoiding direct computation of potentially very large factorial products. Instead, by considering the prime factorization of factorials, one can efficiently compare the products. If two factorial products are equal, their prime factorizations must also be identical. Thus, counting the occurrences of each prime factor across all factorials in both arrays allows for comparison without calculating the large numbers themselves. Sorting and element-by-element comparison would not work for products of factorials (e.g., 0!*4! is not equal to 1!*3!), and converting to logarithms is not directly suggested by the hint 'think about the definitions of the factorial' in the context of efficiency, though it is a mathematical approach to large products.

Question 5: When computing the sum ∑ 1/i from i = 1 to n = 1,000,000, using a standard loop from 1 to n with single-precision floating-point numbers is expected to be more accurate than using double-precision floating-point numbers for the same calculation.

A. Ano

B. Ne

Explanation: The study materials describe comparing results when computing the sum using both single-precision and double-precision floating-point numbers. Double-precision floating-point numbers (IEEE 754) generally offer higher accuracy than single-precision, making it unlikely that single-precision would be more accurate for this calculation.