After all your hard work studying for Algorithms you, Alice and Bob end up stuck in a room full of deadly zombies! Luckily you have a gun with plenty of ammunition and can reliably shoot one zombie dead every second. Each zombie is d; feet away and moving at a speed of s; feet per second. If a zombie reaches you then you all die. You are arguing about what order to shoot the zombies so you live as long as possible. a) Express this optimization problem formally with input and output conditions. b) Bob thinks you should always shoot the closest zombie first. Give a counter exam- ple to prove that his algorithm is not optimal.

After all your hard work studying for Algorithms you, Alice and Bob end up stuck in a room full of deadly zombies! Luckily you have a gun with plenty of ammunition and can reliably shoot one zombie dead every second. Each zombie is d; feet away and moving at a speed of s; feet per second. If a zombie reaches you then you all die. You are arguing about what order to shoot the zombies so you live as long as possible. a) Express this optimization problem formally with input and output conditions. b) Bob thinks you should always shoot the closest zombie first. Give a counter exam- ple to prove that his algorithm is not optimal.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Python answer only. Correct answer will upvoted else downvoted. It is the ideal opportunity for your very first race in the game against Ronnie. To make the race intriguing, you have wagered a dollars and Ronnie has wagered b dollars. Yet, the fans appear to be frustrated. The fervor of the fans is given by gcd(a,b), where gcd(x,y) means the best normal divisor (GCD) of integers x and y. To make the race seriously invigorating, you can perform two kinds of activities: Increment both an and b by 1. Diminishing both an and b by 1. This activity must be performed if both an and b are more noteworthy than 0. In one action, you can play out any of these activities. You can perform self-assertive (potentially zero) number of moves. Decide the greatest energy the fans can get and the base number of moves needed to accomplish it. Note that gcd(x,0)=x for any x≥0. Input The principal line of input contains a solitary integer t (1≤t≤5⋅103) — the number of experiments.…
We have n glasses which can hold a varying amount of liquid. We will say that glass1 is size q1 quarts and glass2 is size q2 quarts, etc. We now give you a size, say x quarts. You must give me a glass of exactly x quarts. You are allowed to fill any glass to exactly its size and to pour any liquid from one glass into another. When you pour, you either have to empty the glass you are pouring from or fill the glass you are pouring into. Can you do it?More concrete example: G1 has size 10 quarts. G2 has size 4 quarts. G3 has size 1 quart. You can get a 5 quart drink by filling G1, pouring 4 quarts from it into G2 and 1 quart of it into G1. After that, G1 has exactly 5 quarts. In the same problem, we could get 8 quarts by filling G2 twice and emptying it into G1 twice. Given This: Write an algorithm to do this and determine its complexity.
3. To defeat Electro, Spider-Man needs to connect all of the pylons (vertices) in the graph below, with the numbers representing the difficulty of making the connection. Use Kruskal's algorithm to determine a minimum cost spanning tree for the following graph. Briefly describe the algorithm and how it works, and include the total cost as part of your answer. 1 3 1 1 5 3 3 4. 4 2 2 4 3 4. The Green Goblin has set up a spooky (and deadly) scavenger hunt around New York City, starting and ending at LaGuardia airport. Gobby has taken Spider-Man's web shooters, so he is stuck using public transit, where the listed times below are the average number of minutes to travel between locations. In order to save Aunt May, Peter must find a circuit that will take 155 or fewer minutes. If he can find a path that takes 140 or fewer minutes, he can save Aunt May AND stop the Green Goblin (AND you hi 2.
This problem is taken from the delightful book "Problems for Mathematicians, Young and Old" by Paul R. Halmos. Suppose that 931 tennis players want to play an elimination tournament. That means: they pair up, at random, for each round; if the number of players before the round begins is odd, one of them, chosen at random, sits out that round. The winners of each round, and the odd one who sat it out (if there was an odd one), play in the next round, till, finally, there is only one winner, the champion. What is the total number of matches to be played altogether, in all the rounds of the tournament? Your answer: Hint: This is much simpler than you think. When you see the answer you will say "of course".
Fomalhaut is a star system deep in the space, and this is where the first aliens in the Man in Black film are said to be originated. Chinger are the alien breed that exist there and they like to play games with humans. They randomly picked Jack, then took him to play the Chinger-JN game. Assume that there are N piles of stones and a value K, each pile i has a counter Ci which is the maximum number of stones that can be removed from it. Initially, Ci =K for 0 <=i
Correct answer will be upvoted else downvoted. Computer science. Positive integer x is called divisor of positive integer y, in case y is distinguishable by x without remaining portion. For instance, 1 is a divisor of 7 and 3 isn't divisor of 8. We gave you an integer d and requested that you track down the littlest positive integer a, to such an extent that a has no less than 4 divisors; contrast between any two divisors of an is essentially d. Input The primary line contains a solitary integer t (1≤t≤3000) — the number of experiments. The primary line of each experiment contains a solitary integer d (1≤d≤10000). Output For each experiment print one integer a — the response for this experiment.
There are four people who want to cross a rickety bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. Write the specification of an algorithm that solves the problem.
Your checkWinner function should determine whether or not the game is over. If the game is over, it should print who won (if anyone), and return true. If the game is not over, it should return false. The game is over if someone wins by getting three X's or three O's in a row, column or diagonal. So there are 8 different combinations of 3-in-a-row moves. You may assume that the board has a size of 3 (length and width). The TicTacBoard.java file I'm giving you uses a variable for that size, but you can assume it's always 3. The game is also over if the board is full but nobody won. I recommend you write some other functions to help in determining if the game is over. Remember you should never copy and paste code if you can avoid it. Write a function to perform a common, generalizable task, and call that function every time you need it. (Like I did with my dispRow method.) Please follow the standard conventions for indentation, meaningful variable names, etc. like the examples in class…
Your checkWinner function should determine whether or not the game is over. If the game is over, it should print who won (if anyone), and return true. If the game is not over, it should return false. The game is over if someone wins by getting three X's or three O's in a row, column or diagonal. So there are 8 different combinations of 3-in-a-row moves. You may assume that the board has a size of 3 (length and width). The TicTacBoard.java file I'm giving you uses a variable for that size, but you can assume it's always 3. The game is also over if the board is full but nobody won. I recommend you write some other functions to help in determining if the game is over. Remember you should never copy and paste code if you can avoid it. Write a function to perform a common, generalizable task, and call that function every time you need it. (Like I did with my dispRow method.) Please follow the standard conventions for indentation, meaningful variable names, etc. like the examples in class…
Computer science. Correct answer will be upvoted else downvoted. You have an at first void cauldron, and you need to blend an elixir in it. The elixir comprises of two fixings: enchantment pith and water. The elixir you need to blend ought to contain precisely k % sorcery substance and (100−k) % water. In one stage, you can pour possibly one liter of sorcery pith or one liter of water into the cauldron. What is the base number of steps to mix a mixture? You couldn't care less with regards to the complete volume of the elixir, just with regards to the proportion between sorcery substance and water in it. A little update: in the event that you pour e liters of embodiment and w liters of water (e+w>0) into the cauldron, then, at that point, it contains ee+w⋅100 % (without adjusting) sorcery substance and we+w⋅100 % water. Input The primary line contains the single t (1≤t≤100) — the number of experiments. The sole line of each experiment contains a solitary integer k…
9. You are given some coins. You have to take some coins from the given coins such that the sum of the coinsyou took have a value strictly larger than the sum of the rest of the coins. However, you have to takeminimum number of coins while satisfying this conditionInputIn the first line, you are given n (n<=100), the number of integer numbers. In the next line, you will be given nintegers, separated by spaces.OutputOutput one number, the minimum number of coins you need to take to have a larger sum than the sum of thecoins you did not take.Input Output23 3 232 1 2 264 2 1 2 1 1 2In the first sample you will have to take 2 coins. If you take 1 coin, you get sum 3, 3. If you take 0 coins, you getsums 0, 6. Those variants do not satisfy you as your sum should be strictly more than the other sum.In the second sample one coin isn't enough for you, too. You can pick coins with values 1, 2 or 2, 2. In any case,the minimum…
Correct answer will be upvoted else downvoted. Computer science. first move is made by Alice, the second — by Bob, the third — by Alice, etc. During their turn, the player should pick one of the chips from the board and move it any sure number of cells to one side (along these lines, if the chip was in segment I, it can move to any segment j<i, and the chips in the furthest left segment can't be picked). Alice and Bob have q sets of numbers Li and Ri. For each such pair, they need to figure out who will be the victor of the game if l=Li and r=Ri. Note that these games ought to be thought about freely (they don't influence the condition of the board for the following games), and both Alice and Bob play ideally. Input The main line contains two integers n and m (1≤n,m≤2⋅105) — the number of lines and segments on the board, separately. The subsequent line contains n integers c1,c2,… ,cn (1≤ci≤m), where ci is the file of the segment where the chip in the I-th line is…