Consider the following algorithms. Each algorithm operates on a list containing n elements, where nis a very large integer. I. An algorithm that accesses each element in the list twice II. An algorithm that accesses each element in the list n times II. An algorithm that accesses only the first 10 elements in the list, regardless of the size of the list Which of the algorithms run in reasonable time? I nly B IIl only c I and Il only I, I, and II D.

Consider the following algorithms. Each algorithm operates on a list containing n elements, where nis a very large integer. I. An algorithm that accesses each element in the list twice II. An algorithm that accesses each element in the list n times II. An algorithm that accesses only the first 10 elements in the list, regardless of the size of the list Which of the algorithms run in reasonable time? I nly B IIl only c I and Il only I, I, and II D.

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

Develop Pseudo-code (English-like) for: In the Find Largest pseudo-code algorithm of Figure 2.14, listed below, if the numbers in our list were not unique and therefore the largest number could occur more than once. Modify the algorithm below to find all the occurrences of the largest number and their position in the list.
Write for the following problem a recursive algorithm whose worst-case timecomplexity is not worse than Θ(n ln n). Given a list of n distinct positiveintegers, partition the list into two sublists, each of size n/2, such that thedifference between the sums of the integers in the two sublists is maximized.You may assume that n is a multiple of 2.
4. Write the pseudocode for an algorithm that takes as input a list of numbers that are sorted in nondecreasing order, and finds the location(s) of the most frequently occurring element(s) in the list. If there are more than one element that is the most frequently occurring, then return the locations of all of them. Analyze the worst-case time complexity of this algorithm and give the O() estimate. (A list is in nondecreasing order if each number in the list is greater than or equal to the number preceding it.)
Euclid’s algorithm (or the Euclidean algorithm) is an algorithm that computes thegreatest common divisor, denoted by gcd, of two integers. Below are the original versions ofEuclid’s algorithm that uses repeated subtraction and another one that uses the remainder.int gcd_sub(int a, int b){ if (!a) return b; while (b) if (a > b) a = a – b; else b = b – a; return a;}int gcd_rem(int a, int b){ int t; while (b) { t = b; b = a % b; a = t; } return a;}1. Trace each of the above algorithm using specific values for a and b.2. Compare both algorithms.
1. A runner targets herself to improve her time on a certain course by 3 seconds a day. If onday 0 she runs the course in 3 minutes, how fast must she run it on day 14 to stay ontarget?2. A certain computer algorithm executes twice as many operations when it is run with aninput of size k as when it is run with an input of size k − 1 (where k is an integer that isgreater than 1). When the algorithm is run with an input of size 1, it executes sevenoperations. How many operations does it execute when it is run with an input of size 25?
In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem. Following is the problem statement: There are n people standing in a circle waiting to be executed. The counting out begins at some point (rear) in the circle and proceeds around the circle in a fixed direction. In each step, a certain number (k) of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1…
The Sieve of Eratosthenes is an elegant algorithm for finding all of theprime numbers up to some limit n. The basic idea is to first create a listof numbers from 2 to n. The first number is removed from the list, andannounced as a prime number, and all multiples of this number up to nare removed from the list. This process continues until the list is empty.For example, if we wished to find all the primes up to 10, the listwould originally contain 2, 3, 4, 5, 6, 7, 8, 9, 10. The 2 is removedand announced to be prime. Then 4, 6, 8, and 10 are removed, sincethey are multiples of 2. That leaves 3, 5, 7, 9. Repeating the process,3 is announced as prime and removed, and 9 is removed because it is amultiple of 3. That leaves 5 and 7. The algorithm continues by announcingthat 5 is prime and removing it from the list. Finally, 7 is announced andremoved, and we're done.Write a program that prompts a user for n and then uses the sievealgorithm to find all the primes less than or equal to n.
Using Java, give an algorithm for the following problem: given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the sublists is minimized. Determine the time complexityof the algorithm.you may assume that h is a multiple of 2
The intersection of two sets contains the list of elements that are common to both, without repetition. As such, you are required to write an algorithm that finds and returns the intersection of two sets A and B. The sets A and B and the resulting intersection set are all lists. Assume the size of A is n and that of B is m. (a) Write an iterative algorithm that finds the intersection. (b) Prove the correctness of your algorithm; i.e. state its loop invariant and prove it by induc- tion. (c) Analyze the time complexity of your algorithm. (d) Think of a way to enhance the complexity of your algorithm by sorting both lists A and B before calculating their intersection. Write the enhanced version and prove that it has a better time complexity.
1. Analyze the word finder with wild card characters scenario to form the algorithm and compute the time complexity. You are given a list of characters with size n, m. You need to read character data provided as input into this list. There is also a list of p words that you need to find in the given problem. You can only search in left, right, up and down direction from a position. There are two wild characters *' and '+' ,if there is any instance of wild card characters for example '+' appears you can match whatever character in your word that you are searching at this position (only one character). Similarly, if you got wildcard *' you can skip any number of characters ( A sequence of characters not necessary same in between the characters) but the last character should be matched in the given data. This means you are not allowed to match a first and last character with *' wildeard. Input: The first line of the input will give you two integers n and m. From the next line you will get…
With the Binary Search algorithm, the algorithm can be developed by the loop-based form as well as a recursive form. Which of the following is not true? O If the item is not found, the loop version returns when the range bounds reach, but the recursive version finishes when the recursive depth is more than half the initial search range. The search range starts with the whole array, and only the recursive version can work on a subrange passed through arguments. O Both forms of the program divide the search range repeatedly in half. O If the item is found, the loop version returns from the entire method, whereas the recursive version returns from one level of recursion.
Write an algorithm to calculate the average of a list of numbers. The algorithm should be understandable by a person who does not know a computer programming language (not written in code). Do not use pre-defined functions. The algorithm should be able to be converted into a computer program on a line by line basis (or at least close to it). Example of an algorithm for a binary search: Find the midpoint of the sorted array / list by dividing its length by 2. Compare the midpoint to the value of interest. If the midpoint is larger than the value, perform binary search on right half of the array. If the midpoint is smaller than the value, perform binary search on left half of the array. Repeat these steps until the midpoint value is equal to the value of interest or we know the value is not in the array. Python