Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Write a program that interfaces with the blackbox: it should call the functions with different n-values and record the runtime of each call. I don't
Write a program that interfaces with the blackbox: it should call the functions with different n-values and record the runtime of each call. I don't know where to start when writing a program to take different n-values of different functions.
That is, as n grows larger and larger, flm begins to converge toward some (non-negative) real number. Essentially, if f(n) does not grow so that the above fraction diverges to infinity, we consider f(n) = 0(8(n)). Consider the following function: Blackbox Project (2) f(n) = 312 - 10n +51 We claim that f(n) = O(n), which we demonstrate with the following table: CSE/IT 122 Algorithms & Data Structures n 10 100 1000 10000 f(n) 251 1000 1000000 2990051 1000000000 299900051 1000000000000 29051 n- 100 10 10.0.0.0 100 1000000 1000 1000000000 10000 In this project, you will be given a black box of seven functions. You are to find their runtime complexity by testing each function with a variety of input sizes. Notice n remains on approximately the same order as f(n), which suggests that f(n) = O(n). After gathering the necessary data from each function in the blackbox, you will plot the points using gnuplot and then determine the complexity for each mystery algorithm. It is advisable to begin testing your algorithms using very small input sizes - remember that n! algorithms can increase runtime to over a minute on a standard machine with n > 13 - and increase from there. n f(n)/ f(n) 10 0.251 2.51 100 0.029051 2.9051 1000 0.002990051 2.990051 10000 0.000299900051 2.99900051 f(n) 25.1 290.51 2990.051 29990.0051 Make sure to read the "Steps of this project" and the submission guidelines at the end of this document! If you have any questions about anything, including the math and math notation, please see the instructor or a TA/tutor. Because both fm) and feventually converge, we can say that f(n) = O(n?) and f(n) = O(n). We also could write f(n) = O(n), f(n) = O(n!), or any other function g(n) which grows faster than n?. However, for the purpose of this project, we identify the slowest-growing 8(n) such that f(n) = 0(s(n)); in this instance, we choose g(n) = 12. 1 Math and Notation A set is a collection of "things." For example, Z is the set of integers; it can be written as Z = {..., -3, -2, -1,0,1,2,3,...}. An alternative criteria we can meet to define f(n) = 0(g(n)) is by choosing witnesses, ce R+ and ko Zt, such that f(n) 3n2 - 10n +51, for all n > 6. This criteria, while slightly less rigorous than the limit definition, allows us to classify functions without calculus. R is the set of real numbers and Zt is the set of positive integers. Any set of positive numbers does not include 0; thus Z+ = {1,2,3,4,... }. The "e" symbol means is an element of; for example, 5 Z (read: 5 is an element of the integers or 5 is an integer) In computer science, we use Big O notation to classify algorithms by how they respond to changes in input size: a function which is fi(n) = O(log(n)) will run much faster than f(n) = O(n) for the same value of n. Thus, de Romeans that d is a real number greater or equal to 0. Consider a machine that can perform 10 operations per second. Then for the same input, n = 1000, the time various algorithms would take to execute is: 2 Big O Notation and Time Complexity Big O Notation is used to describe the limiting behavior of a function f(n), typically as n grows to in- finity, in terms of elementary functions. If we find a simple function, g, that accurately approximates for large n, we write: f(n) = (g(n)). The formal criteria for this relationship is: Algorithm O(log(n)) On On log(n)) O(12) OP) O(2") On!) Run Time (n = 1000) 6.9 nanoseconds 1.0 microseconds 6.9 microseconds 1 millisecond 12 days 2.5. 10% universe age 9.3 - 102540 universe age f(n) lim 1 + g(n) =CERO (1) 1 3 Creating Random Test Data 1 2 In this project, you need to generate a variety of lists in three basic orders: sorted, reverse-sorted, and shuffled. /* random_number: generates a pseudo-random long unsigned between 0 and 2-64 - 1 3 seed random() with srandom(time(NULL)) before you call this */ 4 unsigned long random_number(void) { 5 As a review, the first two methods are relatively simple: 6 2 unsigned long n, p, r; int i; 8 9 /* generate a sorted list */ 2 unsigned long i; 3 unsigned long list = malloc(list_size + sizeof(unsigned long)); n = 0; for (i = 0; p = 1; i 0; i--){ /* pick a random element between 0 and i to swap / j = random() % (i+1); 8 swap(a+1, a+j); 9) In this project, you will analyze a number of mystery algorithms to determine their order of complexity. Naturally, this process necessitates some way for you to assess the runtime of various functions depending on their input size, preferably with higher accuracy than your kitchen timer. To get around this, you will utilize a number of functions with time.h to help us take a decent guess as to how long a given process took to run. 7 time. h contains several useful data types when it comes to dealing with your machine's internal clock. In this project, you will use the clock_t type to keep track of the amount of CPU ticks which elapse during a function's runtime. However, you will encounter a problem when you begin to use large values for list_size. The rand() function generates a value between 0 and RAND_MAX, which is usually 32767 (21 1) on a 32-bit machine or 2147483647 (231 - 1) on a 64-bit machine; if list_size > RAND_MAX, you are no longer truly shuffling the list. Instead you have to come up with an alternative way to generate a random number which is potentially as large as 264 - 1. Consider the following: 5 Interfacing with Blackbox #includeStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started