(c). Two Computer Science students, Priscilla and Julius, are discussing how to compare two algorithms for solving a given problem. Priscilla suggests that they should use the execution times of the algorithms as criterion; but Julius insists that they should use the number of statements the algorithms execute as criterion. Discuss the reasons why both criteria they are considering are not good for comparing algorithms; and recommend an ideal solution/criterion that Priscilla and Julius should rather use for comparing algorithms.

(c). Two Computer Science students, Priscilla and Julius, are discussing how to compare two algorithms for solving a given problem. Priscilla suggests that they should use the execution times of the algorithms as criterion; but Julius insists that they should use the number of statements the algorithms execute as criterion. Discuss the reasons why both criteria they are considering are not good for comparing algorithms; and recommend an ideal solution/criterion that Priscilla and Julius should rather use for comparing algorithms.

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

1. (a)The objective is to shuffle a given array of n different elements. You would like to compare various shuffling algorithms and select the best of them. What does it mean: “the best shuffling algorithm”? What is a requirement for the perfect shuffling algorithm? (b) Is the Fisher-Yates Shuffle the perfect shuffling algorithm? Present a formal mathematical proof that this algorithm meets (or does not meet) the requirement given in (a). (c) Evaluate empirically performance of the Fisher-Yates Shuffle for selected numerical values of n. Propose your evaluation criteria and explain your evaluation methodology. Report your observations and conclusions.
a)(i). People often use recursive algorithms. Discuss the difference between direct recursion and indirect recursion. In which situations would a direct or indirect recursion be a better choice to use?(ii). Two Level 200 IT students, James and Morris, are discussing how to compare two algorithms for solving a given problem. James suggests that they should use the execution times of the algorithms as criterion; but Morris insists that they should use the number of statements the algorithms execute as criterion. (α)Explain the reasons why both criteria they are considering are not good for comparing algorithms. (β)Recommend an ideal solution/criterion that they should rather use for comparing algorithms. Give a practical example to illustrate your answer.
(i) The time complexity of an'algorithm gives an indication of the amount of time the algorithm will take to run completely. (a) Is the time complexity of an algorithm based on the best-case or the worst-case scenario of the Algorithm? (b) Give the tight upper bound for the algorithms with the following time functions. Use the big O notation for your answers. 1. n°+3n+1 2. 2n + logn 3. n+n'+2" (c) Which of the algorithms in (i)(b) is most efficient?
[a] Prove that the "Bin Packing Problem" (BPP) is NP-Complete. Like the rest of the exam, you may use online resources but should cite your source and summarize the proof in your own words. [b] Write an approximation algorithm for the online version of BPP that randomly considers up to three partially filled bins, and if none have room, then create a new bin and use that. [c] What modification to your solution in [b] would you recommend to solve the offline version of BPP. [d] In light of your prior knowledge of and experience with approximation algorithms for BPP, provide a reasonable estimate of the error bound
A randomized algorithm makes random choices during its execution. The behavior of such an algorithm may thus be random even on a fixed input. The process of designing and analyzing a randomized algorithm focuses on establishing that it is likely to behave “well” on every input. - (c) Motwani and Raghavan, Probabilistic Methods for Algorithmic Discrete Mathematics: Algorithms and Combinatorics " An Overview of Randomized Algorithms", pp 93-115.Question 1:Define and cite examples fo the following under randomized algorithms:1. Bipartite Graph 2. Polynomial Identity 3. Random Choice 4. Deterministic Algorithm 5. Monte Carlo Algorithm 6. Miller-Rabin primality test7. Randomized Quicksort7. Linearity of Expectations
Correct answer will be upvoted else downvoted. Computer science. You are provided a program with that comprises of n directions. At first a solitary variable x is doled out to 0. A while later, the guidelines are of two kinds: increment x by 1; decline x by 1. You are given m inquiries of the accompanying organization: question l r — what number of particular qualities is x appointed to if every one of the directions between the l-th one and the r-th one comprehensive are disregarded and the rest are executed without changing the request? Input The primary line contains a solitary integer t (1≤t≤1000) — the number of testcases. Then, at that point, the depiction of t testcases follows. The main line of each testcase contains two integers n and m (1≤n,m≤2⋅105) — the number of directions in the program and the number of questions. The second line of each testcase contains a program — a line of n characters: each character is either '+' or '- ' — addition and…
(b) Precisely specify the conditions under which the following algorithm returns true, and then discuss, in detail, the running time of the algorithm. If you think it has different best- and worst-case running times then these should be considered separately, and you should explain the conditions under which best and worst-cases arise. You must fully explain your answer and use O, and 0 appropriately Algorithm Ex2 ((a₁, ... an)), such that n ≥ 3 q← true i← 1 while in-2 and q == true do subTotal = 0 for j← 0 to 2 do subTotal subTotal + ai+j If subTotal == 0 q = false i + i + 1 return q
Consider a sequential search algorithm. Given a value, the algorithm scans a linear array until the value is found. If the value is not found, that algorithm returns a fail code
Correct answer will be upvoted else downvoted. Computer science. Vasya concentrates on the properties of right triangles, and he utilizes a recipe that decides whether some triple of integers is Pythagorean. Lamentably, he has failed to remember the specific recipe; he recalls just that the recipe was some condition with squares. Along these lines, he concocted the accompanying equation: c=a2−b. Clearly, this isn't the right recipe to check if a triple of numbers is Pythagorean. Yet, amazingly, it really dealt with the triple (3,4,5): 5=32−4, thus, as indicated by Vasya's equation, it is a Pythagorean triple. When Vasya tracked down the right recipe (and comprehended that his equation is off-base), he pondered: what number of are there triples of integers (a,b,c) with 1≤a≤b≤c≤n to such an extent that they are Pythagorean both as per his equation and the genuine definition? He requested that you count these triples. Input The principal line contains one integer t…
a)Write a computer program for the Gauss elimination method using the C programming language. Decide the number of significant figures yourselves. While writing your program, consider the effects of the number of significant figures, pivoting, scaling, and do not forget to check if the system is ill-conditioned.b)Repeat the same procedures for the Gauss-Jordan method.c)Solve an example system using your Gauss elimination and Gauss-Jordan method. Measure the time your computer solves the system for both programs.d)Write a report in which you discuss and compare your Gauss elimination and Gauss-Jordan programs. NOTE: BY USING C PROGRAMMING PLEASE SOLVE THIS QUESTION STEP BY STEP TO UNDERSTAND WELL.THE SUBJECT (Numerical Methods for Engineers) THANK YOU FOR HELPING AND HAVE A NICE DAY. I WILL RATE THE COMPLETE ANSWER
Correct answer will be upvoted else Multiple Downvoted. Computer science. couple of realize that Pan and Apollo weren't just engaging for the title of the GOAT performer. A couple of millenniums later, they likewise tested each other in math (or rather in quick estimations). The errand they got to address is the accompanying: Let x1,x2,… ,xn be the arrangement of n non-negative integers. Track down this worth: ∑i=1n∑j=1n∑k=1n(xi&xj)⋅(xj|xk) Here and means the bitwise and, and | indicates the bitwise or. Skillet and Apollo could tackle this in no time flat. Would you be able to do it as well? For comfort, find the appropriate response modulo 109+7. Input The principal line of the input contains a solitary integer t (1≤t≤1000) indicating the number of experiments, then, at that point, t experiments follow. The main line of each experiment comprises of a solitary integer n (1≤n≤5⋅105), the length of the succession. The subsequent one contains n non-negative…
2. In Africa there is a very special species of bee. Every year, the female bees of such species give birth to one male bee, while the male bees give birth to one male bee and one female bee, and then they die! Now scientists have accidentally found one “magical female bee” of such special species to the effect that she is immortal, but still able to give birth once a year as all the other female bees. The scientists would like to know how many bees there will be after N years. Please write a program that helps them find the number of male bees and the total number of all bees after N years. Input Each line of input contains an integer N (≥ 0). Input ends with a case where N = −1. (This case should NOT be processed.) Output Each line of output should have two numbers, the first one being the number of male bees after N years, and the second one being the total number of bees after N years. (The two numbers will not exceed 232.) Sample Input 1 3 -1 Sample Output 1 2 4 7