CREATE TEST

ERASED TEST, YOU MAY BE INTERESTED ON algos

COMMENTS	STATISTICS	RECORDS

TAKE THE TEST

Title of test: algos Description: algorithms galore Author: shao kahn Other tests from this author Creation Date: 29/08/2024 Category: Computers Number of questions: 12

Share the Test:

New Comment

No comments about this test.

Content:

Let TA(n) and TB(n) be the worst-case execution times of two algorithms A and B proposed for the same computational problem, as a function of a certain parameter n. We say that algorithm A is more efficient than algorithm B asymptotically in the worst case when a) TA(n) = o(TB(n)). b) TB(n) = o(TA(n)). c) TA(n) = O(TB(n)). e) TA(n) = Θ(TB(n)). d) TB(n) = O(TA(n)). . Consider, below, the transaction execution scales S1 and S2 (T). Based on this information, consider the following statements. I. S2 is serializable in conflict. II. S1 is serializable in conflict. III. S1 is serializable in view. IV. S2 is serializable in view. Select the correct alternative. remember: a schedule (or scheduling) is serializable if the outcome of executing transactions concurrently (i.e., interleaving their operations) is the same as if the transactions were executed serially, one after another, without overlapping in time. Conflict serializability: Focuses on avoiding step-by-step conflicts when tasks are mixed. View serializability: Ensures the final outcome looks the same, even if steps were mixed. View Serializability is just the ends justify the means writ large as for conflict serialisability, Imagine you and a friend are both trying to bake a cake in the same kitchen at the same time. You both need to use the oven, mix ingredients, and grab utensils. Conflict serializability checks if the order in which you do these things could cause problems. For example, if you both try to use the oven at the same time, it might cause a conflict. So, we look at these "conflicts" and see if we can rearrange the tasks in a way that avoids them, making sure everything turns out okay. If we can rearrange your tasks so there's no conflict (like one of you waits until the other is done with the oven), then the schedule is conflict serializable—it’s safe to mix the tasks because they don’t interfere with each other. a) Only statements I and II are correct. b) Only statements I and III are correct. c) Only statements III and IV are correct. d) Only statements I, II and IV are correct. e) Only statements II, III and IV are correct. Consider the A* algorithm (A Star / A Star ) used to search for a path (pathfinding), being applied on an occupation grid map, with passage costs associated with each of the grid cells and with the following configuration of nodes listed in the open-set : Node 1: g(1)=19; h(1)=6; L=6; C=8 Node 2: g(2)=18; h(2)=4; L=7; C=9 Node 3: g(3)=13; h(3)=5; L=5; C=10 Node 4: g(4)=16; h(4)=3; L=9; C=8 Node 5: g(5)=16; h(5)=3; L=10;C=7 where “L” and “C” are the row and column of the respective node within the occupation grid. The target position to be reached within the trajectory of this example is defined by the row and column L_Target=10 and C_Target=10, that is, the coordinate (10,10). “g(n)” represents the cost (expense) of the path taken and “h(n)” represents the heuristic cost estimate to the target of the cell in question, where “n” represents the number of the node that identifies the cells, and this cell occupies a certain position (L,C) within the grid. Which of the following nodes will be selected from the open set as the next node to be evaluated, then removed from the open-set and placed in the list of nodes already visited (closed-set)? remember: To determine which node will be selected from the open set and placed in the closed set, the A* algorithm calculates the f(n) value for each node. The f(n) value is the sum of the actual cost from the start node to the current node g(n) and the estimated cost from the current node to the target h(n) f(n)=g(n)+h(n) ex.: Node 1: g(1)=19; h(1)=6; L=6; C=8 f(n) = 19 + 6 = 25 The coordinates (L,C) place the node on the grid and are crucial when evaluating neighbors and calculating heuristic values. BUT THEY HAVE NO BEARING ON THE COST OF THE NODE!! a) Node 1 b) Node 2 c) Node 3 d) Node 4 e) Node 5. Observe the following properties. i. Inductive Learning Algorithm as an integrated part of the method. ii. Ability to generalize learning from examples and evaluate training using cross-validation. iii. Use of information gain as a decision criterion when considering the choice of attributes. iv. Algorithm accepts the treatment of continuous (quantitative) or discrete (qualitative) attributes. Select the alternative that presents the Artificial Intelligence technique that combines all the properties listed. a) Decision Trees (C4.5). b) Artificial Neural Networks (Back-Propagation). c) Genetic Algorithms (Michigan Approach). d) Fuzzy Sets and Logic (FIS - Fuzzy Inference System). e) Expert Systems (Forward Chaining). Regarding file search techniques, select the correct alternative. a) For binary search to work, the file must be sorted according to some random field. b) For sequential search to work, the file must be sorted. c) For binary search to work, the file must be sorted according to the search field. d) For sequential and binary searches to work, the file must be sorted according to the search field. e) For sequential and binary searches to work, the file does not need to be sorted. Regarding grammars and languages, consider the following statements. I. A grammar in Chomsky Normal Form can be ambiguous. II. An ambiguous grammar can generate an inherently unambiguous language. III. A grammar in Greibach Normal Form can be converted to Chomsky Normal Form. IV. The algorithm for converting a Context-Free Grammar to a Grammar in Chomsky Normal Form can be directly applied to a grammar that is not λ-free. Select the correct alternative. a) Only statements I and II are CORRRRECT b) Only statements I and IV are correct. c) Only statements III and IV are correct. d) Only statements I, II and III are correct. e) Only statements II, III and IV are correct. Select the alternative that correctly presents a regular expression that denotes all strings of a’s and b’s that have at least two consecutive b’s. (a*+bb)(a+ba)*(a+b)* (a+ba)*bb(ba+a)* (a+b)*ba*b(a+b)* (a+bb)*(bb+a)* (a+ba)*bb(a+b)*. Consider a Non-Deterministic Finite Automaton (NFA) with 6 states. Applying the conversion algorithm from an NFA to a Deterministic Finite Automaton (DFA), in how many states, at most, would the DFA result, considering the useless states? a) 12 b) 36 c) 64 d) 1024 e) 46656. Consider the logic circuit below, in which the connection points between the lines are highlighted by the small black circles. Select the alternative that correctly presents the minimized Boolean expression for output S. a) b c d e. The designer of an operating system realized, after performance measurements, that the system had problems accessing the disk, with a very high average waiting time. Indicate the alternative that presents, correctly and respectively, a plausible cause and its solution. a) Inefficient disk scheduling algorithm; switch to some shortest distance first algorithm. b) Queue-based device control; switch to priority-based device control. c) Priority-based device control; switch to queue-based device control. d) Inefficient disk scheduling algorithm; switch to some scan-type algorithm. e) Stack-based device control; switch to priority-based device control. Consider the grammar of the following expressions. S → E$ E → E + T E → T T → T ∗ F T → F F → id F → (E) About this grammar, consider the following statements. I. The grammar is LL(1). II. The operator + has a higher precedence than the operator ∗. III. It is not possible to build a recursive descent parser for the grammar. IV. The terminals + ∗ ) $ belong to the FOLLOW set of F. Select the correct alternative. a) Only statements I and II are correct. b) Only statements I and IV are correct. c) Only statements III and IV are correct. d) Only statements I, II and III are correct. e) Only statements II, III and IV are correct. Consider the following grammar. S → E$ E → T + E E → T T → x Regarding this grammar, assign T (true) or F (false) to the following statements. ( ) The grammar is LR(0). ( ) In an SLR analysis table, the production T → x will have reductions only at the terminals + and $. ( ) The grammar is SLR. ( ) In an LR(0) analysis table, the production E → T will have reductions only at the terminals x and +. ( ) The grammar is LR(1). Select the alternative that contains, from top to bottom, the correct sequence. V, V, F, F, V. V, F, V, F, F. V, F, F, V, F F, V, V, F, V. F, V, F, V, F.

Report abuse