For each of the following algorithms, indicate (i) a natural size metric for itsinputs, (ii) its basic operation, and (iii) whether the basic operation count canbe different for inputs of the same size:a. computing the average of n numbersb. computing n/n!c. finding the smallest element in a list of n numbersd. reverse display a list of n numberse. reverse a list of n numbersf. pen-and-pencil algorithm for adding two n-digit decimal integers
Question
For each of the following algorithms, indicate (i) a natural size metric for itsinputs, (ii) its basic operation, and (iii) whether the basic operation count canbe different for inputs of the same size:a. computing the average of n numbersb. computing n/n!c. finding the smallest element in a list of n numbersd. reverse display a list of n numberse. reverse a list of n numbersf. pen-and-pencil algorithm for adding two n-digit decimal integers
Solution
a. Computing the average of n numbers (i) The natural size metric for this algorithm is n, the number of numbers. (ii) The basic operation is addition, as we need to add all the numbers together before dividing by n to get the average. (iii) The basic operation count is the same for inputs of the same size, as we always need to add all the numbers together, regardless of their values.
b. Computing n/n! (i) The natural size metric for this algorithm is n, the number we are computing the factorial of and then dividing n by. (ii) The basic operation is multiplication, as we need to multiply all numbers from 1 to n to get n!, and then division to divide n by n!. (iii) The basic operation count is the same for inputs of the same size, as we always need to perform the same number of multiplications and one division, regardless of the value of n.
c. Finding the smallest element in a list of n numbers (i) The natural size metric for this algorithm is n, the number of numbers in the list. (ii) The basic operation is comparison, as we need to compare each number to the current smallest number to find the smallest number in the list. (iii) The basic operation count can be different for inputs of the same size, as the number of comparisons needed can depend on the order of the numbers in the list.
d. Reverse display a list of n numbers (i) The natural size metric for this algorithm is n, the number of numbers in the list. (ii) The basic operation is accessing each element in the list. (iii) The basic operation count is the same for inputs of the same size, as we always need to access each number in the list once, regardless of their values or order.
e. Reverse a list of n numbers (i) The natural size metric for this algorithm is n, the number of numbers in the list. (ii) The basic operation is swapping elements in the list. (iii) The basic operation count is the same for inputs of the same size, as we always need to perform n/2 swaps, regardless of the values or order of the numbers.
f. Pen-and-pencil algorithm for adding two n-digit decimal integers (i) The natural size metric for this algorithm is n, the number of digits in the integers. (ii) The basic operation is addition, as we need to add each pair of digits together, possibly carrying over a value to the next pair. (iii) The basic operation count can be different for inputs of the same size, as the need for a carry operation depends on the values of the digits.
Similar Questions
Consider the following recursive algorithm.ALGORITHM Q(n)//Input: A positive integer nif n = 1 return 1else return Q(n − 1) + 2 ∗ n − 1a. Set up a recurrence relation for this function’s values and solve it to deter-mine what this algorithm computes.b. Set up a recurrence relation for the number of multiplications made by thisalgorithm and solve it.c. Set up a recurrence relation for the number of additions/subtractions madeby this algorithm and solve it.
Algorithm A 1. Set sum = 0. // 1 assignment2. Set i = 0. // 1 assignment 3. While (i <= n): // n comparisonsa.Set sum = sum + i. // n arithmetic operations, n assignmentsb.Increment i by 1. // n increments 4.Display (sum). // 1 write Algorithm B 1.Set sum = (n × (n + 1))/2. // 3 arithmetic operations, 1 assignment2.Display (sum). // 1 write Both, Algorithm A and Algorithm B, perform the same task. This means that both determine the sum of the first nnatural numbers. Algorithm A adds each number iteratively to a variable, sum. However, Algorithm B uses a formula to calculate the sum of the first n natural numbers. The execution time required for Algorithm A is given by:T = (n + 2) × a + n × b + 1 × c + n × d + n × eT = an + 2n + bn + c + dn + enT = c + n (a + b + d + e + 2)As T is a linear function of n, the algorithm is of the order, O (n).Now, determine the time required to execute Algorithm B:T = 1 × a +1 × c + 3 × eT = a + c + 3eUnlike Algorithm A, the time taken by Algorithm B is constant and does not depend on the value of n. Therefore, the algorithm is of the order __________ ?
UNIT – IOverview of data structure, Basics of Algorithm Analysis including Running Time Calculations, Abstract DataTypes, Arrays, Arrays and Pointers, Multidimensional Array, String processing, General Lists and List ADT, Listmanipulations, Single, double and circular lists. Stacks and Stack ADT, Stack Manipulation, Prefix, infix andpostfix expressions, recursion. Queues and Queue ADT, Queue manipulation.UNIT – IISparse Matrix Representation (Array and Link List representation) and arithmetic (addition, subtraction andmultiplication), polynomials and polynomial arithmetic.Trees, Properties of Trees, Binary trees, Binary Tree traversal, Tree manipulation algorithms, Expression treesand their usage, binary search trees, AVL Trees, Heaps and their implementation, Priority Queues, B-Trees, B*Tree, B+ TreBASED ON MY SYLLABUS TELL ME IN WHICH UNIT IS LINKED LIST ,SINGLY LINKED LIST DOUBLY LINK LIST THERE
Algorithm Analysis
Questiona) Write a program to read a set of numbers (between 10 to 20) from the keyboard and storethem in an array.b) Sort the numbers in ascending order with the Insertion sorting algorithm.c) Calculate how many times it executes the while of the algorithm.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.