Artificial Intelligence: A Modern Approach
3rd Edition
ISBN: 9780136042594
Author: Stuart Russell, Peter Norvig
Publisher: Prentice Hall
expand_more
expand_more
format_list_bulleted
Videos
Textbook Question
Chapter 5, Problem 15E
Suppose you have a chess program that can evaluate 10 million nodes per second. Decide on a compact representation of a game state for storage in a transposition table. About how many entries can you fit in a 2-gigabyte in-memory table? Will that be enough for the three minutes of search allocated for one move? How many table lookups can you do in the time it would take to do one evaluation? Now suppose the transposition table is stored on disk. About how many evaluations could you do in the time it takes to do one disk seek with standard disk hardware?
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Create a BST implementation that uses three arrays to represent the BST: one with keys, one with array indices for left links, and one with array indices for right links. The arrays should be preallocated to the maximum size specified in the constructor. Compare your program's performance against that of the usual implementation.
Implement a program that will populate a 6x5 matrix with randomly generated
integers from 100 to 500.
(1) print your matrix in a table form.
(2) modify your code to multiply all odd numbers by 2 and print the matrix.
Sample run:
Initial Matrix:
145 | 437 | 222 | 101 | 100 |
278 500 | 190 | 415 | 288 |
466 322 377 | 240 | 451 |
331 186
186
432
102 | 106 |
105 249
248 | 117 | 213 |
499 488
355 | 266 | 396 |
New Matrix:
290 | 874 | 222 | 101 | 100 |
278
500 | 190 | 830 288 |
466 322
754 | 240 | 902 |
662 186
432 | 102 | 106 |
210| 498
248 | 234 | 426 |
998 488 710 | 266 | 396 |
The way the Spaghetti Sort algorithm "cheated", if it did, was in claiming that the operation of my
left hand's palm detecting the tallest remaining piece of spaghetti in my right hand, and then pulling
it out, could be accomplished in O(1) time, without explaining how this would actually be implemented
algorithmically.
If you wanted to fill in the details for how this would work, one of the big decisions to make would be to
choose the data structure you use to implement the fist of spaghetti, and there are several potential options
(though they won't of course provide the desired O(1) time). Note that in the course of the algorithm
running, first you would insert all the numbers (spaghetti pieces) into the data structure, and then you
would repeated delete the largest remaining number (tallest remaining piece of spaghetti) from it.
a) If you used an unsorted array as the data structure, what would the big-O cost of each delete-max
operation be?
b) What would the total big-O cost of…
Chapter 5 Solutions
Artificial Intelligence: A Modern Approach
Additional Engineering Textbook Solutions
Find more solutions based on key concepts
Write the function htoi(s), which converts a suing of hexadecimal digits (including an optional 0x or 0X) into ...
C Programming Language
Write assignments to the library, cs101. and track variables (which you defined in the previous three exercises...
Objects First with Java: A Practical Introduction Using BlueJ (6th Edition)
3.12 (Date Create a class called Date that includes three pieces Of information as data
members—a month (type ...
C++ How to Program (10th Edition)
The following statement attempts to create a Rectangle object. Find the error. Rectangle box = new Rectangle;
Starting Out with Java: From Control Structures through Data Structures (3rd Edition)
How many total stars will be displayed by each of the following program segments? A) for (row = 0; row 20; row...
Starting Out with C++: Early Objects (9th Edition)
Length Conversion Write a program to convert a U.S. Customary System length in miles, yards, feet, and inches t...
Introduction To Programming Using Visual Basic (11th Edition)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- The method to compress an image in image processing is using convolution matrix where the number of outputs is reduced by replacing the matrix multiplication with much smaller kernel matrix. This is illustrated on the figure below. In this example a black and white photograph is scanned as a rectangular array of pixels and then stored as image matrix on the left by assigning each pixel a numerical value in accordance with its gray level, (0 = white to 255 = black), then the entries in the matrix are integers between O and 255.Then multiplication is employed with much smaller kernel matrix in the middle. 0|0 21 00 o 106 85 71 1 250 231 127 63 1 250 252 250 209 56 1 250 252 250 250 83 Kernel 0 0 0 Feature map Image Boxes in red and blue frames indicate how the upper left element is formed by applying the kernel to the corresponding upper left region of the input matrix. The elements of much smaller "feature map" matrix on the right can be calculated from: 3.arrow_forwardWrite a Perl program that uses a hash and a large number of operations on the hash. For example, the hash could store people's names and their ages. A random-number generator could be used to create three- character names and ages, which could be added to the hash. When a duplicate name was generated, it would cause an access to the hash but not add a new element. Rewrite the same program without using hashes. Compare the execution efficiency of the two. Compare the ease of programming and readability of the two.arrow_forwardA set of integers 0..MAX may be implemented using an array of boolean values. This particular implementation is called a bit-vector implementation of a Set. Since C doesn’t have the Boolean data type, then substitute TRUE with 1 and FALSE with 0, or define 1 and 0 as TRUE and FALSE, respectively.For example, if the integer 3 is an element of the set, then the array element indexed by 3 is TRUE. On the other hand, if 3 is not an element, then the array element indexed by 3 is FALSE. For example, if the integer 3 is an element of the set, then the array element indexed by 3 is TRUE. On the other hand, if 3 is not an element, then the array element indexed by 3 is FALSE.For example: if s = {3,4,6,8}, the array looks like this: Implement a programmer-defined data type called BitSet to represent a set as follows:typedef int BitSet[MAX];Implement the following functions:void initialize(BitSet s); - set all array elements to FALSEvoid add(int elem,BitSet s);- set the item indexed by elem to…arrow_forward
- Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to youwith the following problem. They have a collection of n bank cards that they’ve confiscated, suspectingthem of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe withsome encrypted data, and it corresponds to a unique account in the bank. Each account can have manybank cards corresponding to it, and we’ll say that two bank cards are equivalent if they correspond to thesame account.It’s very difficult to read the account number off a bank card directly, but the bank has a high-tech “equivalence tester” that takes two bank cards and, after performing some computations, determines whether theyare equivalent.Their question is the following: among the collection of n cards, is there a set of more than n/2 of themthat are all equivalent to one another? Assume that the only feasible operations you can do with the cardsare to pick two of them and plug them…arrow_forwardThe Java Virtual Machine (and your computer’s assembly language) support a goto instruction so that the search can be “wired in’’ to machine code, like the program at right (which is exactly equivalent to simulating the DFA for the pattern as in KMPdfa, but likely to be much more efficient). To avoid checking whether the end of the text has been reached each time i is incremented, we assume that the pattern itself is stored at the end of the text as a sentinel, as the last M characters of the text. The goto labels in this code correspond precisely to the dfa[] array. Write a static method that takes a pattern as input and produces as output a straight-line program like this that searches for the pattern. Straight-line substring search for A A B A A A int i = -1;sm: i++;s0: if (txt[i]) != 'A' goto sm;s1: if (txt[i]) != 'A' goto s0;s2: if (txt[i]) != 'B' goto s0;s3: if (txt[i]) != 'A' goto s2;s4: if (txt[i]) != 'A' goto s0;s5: if (txt[i]) != 'A' goto s3; return i-8;arrow_forwardAnswer the given question with a proper explanation and step-by-step solution. please solve it in python. And explain the work in words with some lines and also explain the simulation. Thank You.arrow_forward
- you are to design a printer queue that is responsible for handling the printing requests coming from different users. You have to take into consideration that users have different levels of priorities. Each user has an identification number and a password, in addition to printing priorities. One good idea is to design the queue using an array or pointers while preserving the first-in first-out concept of the queue. For every printing request received, the program should check the priorities of that request and whether it can be moved forward in the queue to be served by the printer prior to serving the other requests. Using the programming language of your choice (preferably C++), write the printer queue that would handle the user request. The program must allow for requests coming from different users or from one user. Note: I need a working C++ code for this problem, and i need priorities.arrow_forwardGiven the contents of the Scoreboard (capacity=5) as {[''Kristoff'', 75], ["Anna", 72], ["Elsa", 67], ["Olaf", 64]}, it would need how many movement/s or shift/s to accommodate the GameEntry ["Samantha", 75]?arrow_forwardWrite a python code in multiprocessing (from mpi4py import MPI) Consider a system of 2 processes. The master process generates an array of random numbers of the size n. It shares the array with the slave. The slave is asked to do the sum of numbers. The result returned by the slave is printed by the master process. The master process is simultaneously counting the numbers less than 50 in the array and printing the same.In all the above cases, print the details of who is printing and what is being printed. Use mpi4py Python Package in the coding.arrow_forward
- Implement a quicksort with a sample size of 2k 1. Sort the sample first, then have the recursive procedure partition on the sample's median and shift the two halves of the rest of the sample to each subarray so that they may be utilised in the subarrays without having to be sorted again. This algorithm is known as samplesort. Put into practise a quicksort based on a 2k sample. The sample should be sorted first, after which you should set up the recursive procedure to split the sample based on its median and to shift the two halves of the remaining sample to each subarray so they can be utilised in the subarrays without needing to be sorted again. The name of this algorithm is samplesort.arrow_forwardAn early attempt to force users to use less predictable passwords involved computer supplied passwords. The passwords were eight characters long and were taken from the character set consisting of lowercase letters and digits. They were generated by a pseudo-random number generator with 2^15 possible starting values. Using the technology of the time, the time required to search through all character strings of length 8 from a 36-character alphabet was 112 years. Unfortunately, this is not a true reflection of the actual security of the system. Explain the problemarrow_forwardA certain computer algorithm executes twice as many operations when it is run with an input of size k as when it is run with an input of size k – 1 (where k is an integer that is greater than 1). When the algorithm is run with an input of size 1, it executes seven operations. How many operations does it execute when it is run with an input of size 26? For each integer n 2 1, let s, -1 be the number of operations the algorithm executes when it is run with an input of size n. Then s, = and s = for each integer k 2 1. Therefore, So, S1, S21 -Select--- with constant Select--- |, which is So, for every integer n 2 0, s, It follows that for an input of size 26, the number of ... is operations executed by the algorithm is s which equals ---Select--- varrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Definition of Array; Author: Neso Academy;https://www.youtube.com/watch?v=55l-aZ7_F24;License: Standard Youtube License