Scribd
Upload
3 views4 pages

Assignment 4 (Algorithm Analysis)

The document outlines the requirements for CMPSC 462 Assignment-4, which includes four exercises worth a total of 30 points. Exercises involve analyzing program running times, designing an algorithm for disjoint arrays, sorting a list using different algorithms, and estimating input pool sizes for sorting algorithms. Students are instructed to include readable screenshots of their program results and provide answers to specific questions related to time complexity and sorting outcomes.

Uploaded by

shrijibuilds
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views4 pages

Assignment 4 (Algorithm Analysis)

The document outlines the requirements for CMPSC 462 Assignment-4, which includes four exercises worth a total of 30 points. Exercises involve analyzing program running times, designing an algorithm for disjoint arrays, sorting a list using different algorithms, and estimating input pool sizes for sorting algorithms. Students are instructed to include readable screenshots of their program results and provide answers to specific questions related to time complexity and sorting outcomes.

Uploaded by

shrijibuilds
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

CMPSC 462 – Assignment-4 (30 points)

Due date: 1 week

Note: attach screenshots of your program and results under each programming exercises. Please make
sure that the screenshot is readable. Don’t attach a very small screenshot image.

Exercise-1: 10 points
Give an analysis of the running time (Big-Oh notation) for each of the following 2 program fragments. Note that
the running time corresponds here to the number of times the operation sum++ is executed. sqrt is the function
that returns the square root of a given number.

a) sum = 0
for i in range(int([Link](n)/2)):
sum+=1
for j in range(int([Link](n)/2)):
sum+=1
for k in range(8+j):
sum+=1

Answer -

b) sum = 0
for i in range(int([Link](n)/2)):
j=i
for j in range(8+i):
k=j
for k in range(8+j):
sum+=1
Answer -

c. If it takes 10ms to run program (b) for n=100, how long will it take to run for n=400 ?
Ans – it will take 80ms
d. If it takes 10ms to run program (a) for n=100, how large a problem can be solved in
40ms ? Ans – where n = 1600, and n represents the length of the problem

Exercise-2: 5 points
Design an algorithm that takes two arrays, and returns true if the arrays are disjoint, i.e. have no
elements in common. Write down your algorithm as pseudocode. You don’t need to write a python
code. Give the asymptotic analysis for time complexity in best-case and worst-case scenario.
Answer –
Exercise-3: 10 points
Consider the following list, List1 = [5, 30, 25, 60, 55, 15, 70, 35].
What is the resulting list after two passes of the sorting phase i.e. after two iterations/recursive calls, if the
following is performed? Show the steps using a rough sketch. You can draw the steps for each sorting algorithm
in a paper, take a picture of it and attach it here.

a) Selection Sort –

b) Insertion Sort –
c) Bubble Sort –

Exercise-4: 5 points
Assume that an Insertion sort algorithm in the worst case takes 4 minutes and 10 seconds for an input of pool size
30. What will be the maximum input pool size of a problem that can be solved in 20 minutes and 50 seconds in
the worst case?

Ans –

You might also like