Question

CSCI4520Programing Project for algorithm analysis: Sorting, searching, and efficiency analysis

Project introduction In the project, you will apply the theory in the class to actual computer simulation to verify your results. Project Description You will simulate the procedure of search, sorting by programming and analyze the efficiency based on the computer simulation and theoretical result.

1.Generate 100000positive numbers between (0,150)

2.Search the position of the first “58”in the array

3.Count how many “58”inthe array

4.After you finished the first three steps,sort the array by the one required algorithm.

5.Repeat step 3 on the sorted array

6.Compute the time cost difference between the time from step 3 only, and time from step 4 and 5 together.

7.Run your program three times and calculate the time:

1)The time to generate 100000#

2)The time to search the element 58s

3)The time to count the 58’s

4)The time to sort the array

Project Learning Objectives • Students will be knowledgeable of the concepts and techniques of computation • Develop code and understanding software life cycle. • Familiar with algorithm efficiency analysis Computer Programming Learning Objectives Students will enhance knowledge in following areas: • Arrays (Bounded) • Algorithm design • Data structure • Interface design • Graphic user interface design Learning Objectives • Upon the successful completion of the project, the students will gain a better understanding of following course concepts • The efficiency analysis of algorithms • The student will enhance the knowledge and skills in writing a well-documented Java program with object oriented concepts involved Program structure The program should include the following sections: • Algorithms design: Describe the algorithm in pseudocode• Implementation of the algorithm: The code to realize the algorithms• The efficiency analysis of the algorithm: The time and space efficiency

Answer 1

import random
import time

def program(print_result=True):
        # ============== Generate numbers =========================
        numbers = [] #array to store the numbers
        
        # clock for generating numbers
        # start the clock....
        start1 = time.time()

        for _ in range(100000):
            numbers.append(random.randint(0, 150))
        
        end1 = time.time()   
        # end the clock 

        
        if print_result:
                print("Step1: First 20 numbers: ", numbers[:20])

        
        # Function to find Position of first 58 in array
        def find58(numbers):
            for index, num in enumerate(numbers):
                if num is 58:
                        return index

        # clock for searching....
        start2 = time.time()
        if print_result:
                print("Step2: Position of 58 is:", find58(numbers))
        end2 = time.time()



        # Function to Count numbers of 58:
        def count58(numbers):
            count = 0
            for num in numbers:
                if num is 58:
                    count += 1
                    
            return count

        if print_result:
                print("Step3: Total count of occurences of 58:", count58(numbers))


        # clock for counting the occurences of 58
        start3 = time.time()
        count58(numbers)
        end3 = time.time()


        # clock for sorting and counting
        start45 = time.time()
        
        # clock for sorting
        start4 = time.time()
        numbers.sort()
        end4 = time.time()
        # end clock for sorting  
        
        if print_result:
                print("Step5: count of 58 after sorting:", count58(numbers))
        end45 = time.time()
        # end clock for counting


        if print_result:
                print("Step6:")
                print("Runtime of step3",end3-start3)
                print("Combined runtime of step 4 and 5", end45-start45)
                if(end3-start3 > end45-start45):
                        print("step3 is faster")
                else:
                        print("step 4 and 5 is faster")

        return end1-start1, end2-start2, end3-start3, end4-start4


# Covers step1-step6
program()



print()
print("Step7")
# Running program for 3 times without printing results of step1-step6
for i in range(3):
        print("Iteration", i+1)
        time_generate, time_search, time_count, time_sort = program(print_result=False)
        print("Time to generate", time_generate)
        print("Time to search", time_search)
        print("Time to count", time_count)
        print("Time to sort", time_sort)
        print()

Screeshot of program:

Sample run: