Task: Learn how algorithms with different order of complexity behaves through ex
ID: 3678331 • Letter: T
Question
Task:
Learn how algorithms with different order of complexity behaves through experiments
Code:
Fill in the brute-force methods for conducting 1, 2 and 3-sum problems
one_sum(), two_sum() and three_sum() in NSum.java
Each method should return the number of singles/doubles/triples that gives sum of 0.
Modify the main function in NSum class to perform and measure the time
For 1-sum function,
Run 100 executions for each dataset size (N) of {8k, 16k, 32k, 64k, 128k}
For each dataset size, compute avg time of 100 executions
Compute slope in log-log for each N by comparing to the next N (e.g. slope between N=8k and N=16k
Compute avg of all slopes
For 2-sum function,
Do same as 1-sum for N of {2k, 4k, 8k, 16k}
For 3-sum function,
Do same as 1-sum for N of {1k, 2k, 4k}
Experiment:
Run the main function
Create an Excel file called "NSum_OrderComplexity.xlsx"
Record the time and confirm the slope is appropriate
_______________________________________________
Modify the binary search so that it always returns the smallest index of a key of an item matching the search key in logarithmic time.
What it is:
For instance, for an array of [1 2 2 3 4 5 6 7 8], search key of 2 will return value of 1. Note that index of array starts with 0.
Code:
Revise indexOf() method of BinarySearchSmallest.java
Experiment:
Goal: Demonstrate that the program runs in logarithmic time empirically.
Run the main function in BinarySearchSmallest class to perform and measure the time
For each of N = {100k, 400k, … 25.6M}
Run this 100 times record execution time for each method.
Note that for each execution, the input array is different as it is randomized.
Create an Excel file called "BinarySearchSmallest_OrderComplexity.xlsx" which has same format of numbers as example run shown on the right
Record the time and confirm the look of the plot is logarithmic
_______________________________________________
Binary Search Smallest
import edu.princeton.cs.algs4.*;
import java.util.*;
public class BinarySearchSmallest
{
public static void main(String[]args){
Stopwatch timer; // Timer for method execution (seconds)
int[]numbers; // Random sorted integers
int k; // Random search value index
int index; // Index of search result
int N_exp = 100; // Number of experiments for each algorithm-N pairs
for ( int N = 100000; N <= 25600000; N = N * 4 ) {
double totalRunTime = 0.0;
for ( int i = 0; i < N_exp; i++ ) {
numbers = randomIntegers( N );
k = StdRandom.uniform(0, numbers.length);
timer = new Stopwatch();
index = indexOf(numbers[k],numbers);
totalRunTime += timer.elapsedTime();
}
StdOut.printf ( "N (%d) - avg time (%.9f) seconds ",
N, totalRunTime/N_exp );
}
}
/** Returns the first index of a key value found in an array */
public static int indexOf(int key, int[] a){
}
/** Returns sorted array of random integers */
public static int[] randomIntegers(int size){
int[] a = new int[size];
for(int i = 0; i < a.length; i++){
a[i] = StdRandom.uniform(0,a.length*2+1);
}
Arrays.sort(a);
return a;
}
/** Custom stopwatch. Converts from nanoseconds to seconds to avoid decimal loss */
public static class Stopwatch{
long start;
public Stopwatch(){
start = System.nanoTime();
}
public double elapsedTime(){
return (double)(System.nanoTime() - start)*1e-9;
}
}
}
_______________________________________________
NSum
import edu.princeton.cs.algs4.*;
public class NSum
{
public static void main(String[]args){
Stopwatch timer; // Timer for method execution (seconds)
int []numbers; // Array of random integers
int cnt; // Number of singles/doubles/triples that give sum 0
// example code
double totalRunTime = 0.0;
for ( int i = 0; i < N_exp; i++ ) {
numbers = randomIntegers( N );
timer = new Stopwatch();
cnt = one_sum(numbers);
totalRunTime += timer.elapsedTime();
}
}
/** Returns the number of times a single value in an array sums to 0 */
public static int one_sum(int[]a){
}
/** Returns the number of times two values in an array sum to 0 */
public static int two_sum(int[]a){
}
/** Returns the number of times three values in an array sum to 0 */
public static int three_sum(int[]a){
}
/** Returns an array of random negative and positive integers */
public static int[] randomIntegers(int size){
int[]a = new int[size];
for(int i = 0; i < a.length; i++){
a[i] = StdRandom.uniform(0-a.length, a.length+1);
}
return a;
}
/** Custom stopwatch. Converts from nanoseconds to seconds to avoid decimal loss */
public static class Stopwatch{
long start;
public Stopwatch(){
start = System.nanoTime();
}
public double elapsedTime(){
return (double)(System.nanoTime() - start)*1e-9;
}
}
}
Explanation / Answer
Hey I have written code for two programs but I coudlnt execute for 100 times and check for output becuase I dont have the jar files and unable to install them, heres the code :
NSum.java:
import edu.princeton.cs.algs4.*;
public class NSum
{
public static void main(String[]args){
Stopwatch timer;
int []numbers;
int cnt;
double totalRunTime = 0.0;
for ( int i = 0; i < N_exp; i++ ) {
numbers = randomIntegers( N );
timer = new Stopwatch();
cnt = one_sum(numbers);
totalRunTime += timer.elapsedTime();
}
}
public static int one_sum(int[]a){
int l;
for(int i=0;i<a.length;i++)
if(a[i]==0)
l++;
return l;
}
/** Returns the number of times two values in an array sum to 0 */
public static int two_sum(int[]a){
min_l = 0;
min_r = 1;
min_sum = a[0] + a[1];
int l;
for(int i = 0; i< a.length - 1; i++)
{
int sum=0;
for(int r = i+1; r <a.length; r++)
{
sum = a[i] + a[r];
if(sum==0)
l++;
}
}
return l;
}
/** Returns the number of times three values in an array sum to 0 */
public static int three_sum(int[]a){
int l, r;
int c;
for (int i = 0; i <a.length-1; i++)
{
for (int j = i+1; j <a.length-1; j++)
{
for (int k = j+1; k < a.length; k++)
{
if (a[i] + a[j] + a[k] == 0)
{
c++;
}
}
}
}
return c;
}
/** Returns an array of random negative and positive integers */
public static int[] randomIntegers(int size){
int[]a = new int[size];
for(int i = 0; i < a.length; i++){
a[i] = StdRandom.uniform(0-a.length, a.length+1);
}
return a;
}
/** Custom stopwatch. Converts from nanoseconds to seconds to avoid decimal loss */
public static class Stopwatch{
long start;
public Stopwatch(){
start = System.nanoTime();
}
public double elapsedTime(){
return (double)(System.nanoTime() - start)*1e-9;
}
}
}
BinarySeacrhSmallest.java:
import edu.princeton.cs.algs4.*;
import java.util.*;
public class BinarySearchSmallest
{
public static void main(String[]args){
Stopwatch timer; // Timer for method execution (seconds)
int[]numbers; // Random sorted integers
int k; // Random search value index
int index; // Index of search result
int N_exp = 100; // Number of experiments for each algorithm-N pairs
for ( int N = 100000; N <= 25600000; N = N * 4 ) {
double totalRunTime = 0.0;
for ( int i = 0; i < N_exp; i++ ) {
numbers = randomIntegers( N );
k = StdRandom.uniform(0, numbers.length);
timer = new Stopwatch();
index = indexOf(numbers[k],numbers);
totalRunTime += timer.elapsedTime();
}
StdOut.printf ( "N (%d) - avg time (%.9f) seconds ",
N, totalRunTime/N_exp );
}
}
/** Returns the first index of a key value found in an array */
public static int indexOf(int key, int[] a){
int search = key;
int index;
int first = 0;
int last = a.length - 1;
int middle = (first + last)/2;
while( first <= last )
{
if ( a[middle] < search )
first = middle + 1;
else if ( a[middle] == search )
{
index=middle;
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if ( first > last )
System.out.println(search + " is not present in the list. ");
else
{
for(int i=index-1;i>=0;i--)
{
if(a[i]==a[index])
{
index=i;
}
}
return index;
}
}
/** Returns sorted array of random integers */
public static int[] randomIntegers(int size){
int[] a = new int[size];
for(int i = 0; i < a.length; i++){
a[i] = StdRandom.uniform(0,a.length*2+1);
}
Arrays.sort(a);
return a;
}
/** Custom stopwatch. Converts from nanoseconds to seconds to avoid decimal loss */
public static class Stopwatch{
long start;
public Stopwatch(){
start = System.nanoTime();
}
public double elapsedTime(){
return (double)(System.nanoTime() - start)*1e-9;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.