Programming Assignment

Step 1: Generate n random integers from 1 to m.

import random
def generate_random_integers(n, m):
return [random.randint(1, m) for _ in range(n)]

Step 2: Store the generated numbers in a linked list.

class ListNode:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
def insert_into_linked_list(head, value):
new_node = ListNode(value)
if head is None:
return new_node
current = head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
return head

Step 3: Count how many numbers in the linked list are larger than 50.

def count_larger_than_50(head):
count = 0
current = head
while current:
if current.value > 50:
count += 1
current = current.next
return count

Step 4: Depending on the count, sort and delete elements from the linked list.

def sort_linked_list(head, ascending=True):
if head is None or head.next is None:
return head
def merge(left, right):
result = None
if left is None:
return right
if right is None:
return left
if ascending:
if left.value <= right.value:
result = left
result.next = merge(left.next, right)
else:
result = right
result.next = merge(left, right.next)
else:
if left.value >= right.value:
result = left
result.next = merge(left.next, right)
else:
result = right
result.next = merge(left, right.next)
return result
def merge_sort(head):
if head is None or head.next is None:
return head
mid = get_middle(head)
left_half = head
right_half = mid.next
mid.next = None
left = merge_sort(left_half)
right = merge_sort(right_half)
return merge(left, right)
def get_middle(head):
if head is None:
return head
slow_ptr = head
fast_ptr = head
while fast_ptr.next and fast_ptr.next.next:
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next.next
return slow_ptr
return merge_sort(head)
def delete_nth_element(head, n):
if head is None or n <= 0:
return head
current = head
count = 1
while current:
if count == n:
prev_node = current.prev
next_node = current.next
if prev_node:
prev_node.next = next_node
if next_node:
next_node.prev = prev_node
if count == 1:
head = next_node
return head
count += 1
current = current.next
return head

implement the main logic to perform the steps for both linked lists and arrays.

def count_larger_than_50(head):
count = 0
current = head
while current:
if current.value > 50:
count += 1
current = current.next
return count
def main():
m = int(input("Enter the upper bound (m): "))
r = int(input("Enter the number of repetitions (r): "))
n_values = [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]
for n in n_values:
total_time = 0
total_space = 0
for _ in range(r):
random_numbers = generate_random_integers(n, m)
# Create a linked list
linked_list_head = None
for num in random_numbers:
linked_list_head = insert_into_linked_list(linked_list_head, num)
# Count numbers larger than 50
count = count_larger_than_50(linked_list_head)
if count > 5:
# Sort and delete the fifth element
linked_list_head = sort_linked_list(linked_list_head)
linked_list_head = delete_nth_element(linked_list_head, 5)
else:
# Sort in non-increasing order and delete the second element
linked_list_head = sort_linked_list(linked_list_head, ascending=False)
linked_list_head = delete_nth_element(linked_list_head, 2)
# Insert 10 into the linked list
linked_list_head = insert_into_sorted_linked_list(linked_list_head, 10)
# Record time and space usage (you can use appropriate functions to measure time and space)
# Record time here
# Record space here
if n > 100:
continue
# Print the final linked list (or array)
current = linked_list_head
result = []
while current:
result.append(current.value)
current = current.next
print(f"n = {n}, Result: {result}")
# Calculate average time and space complexity for n
# Output the average time and space complexity here
if __name__ == "__main__":
main()

6) Redo steps 2) to 5) with array instead of linked list;

import random
def generate_random_integers(n, m):
return [random.randint(1, m) for _ in range(n)]
def count_larger_than_50(arr):
count = 0
for num in arr:
if num > 50:
count += 1
return count
def sort_array(arr, ascending=True):
return sorted(arr) if ascending else sorted(arr, reverse=True)
def delete_nth_element(arr, n):
if n < len> arr.pop(n)
return arr
def insert_into_sorted_array(arr, value):
arr.append(value)
arr.sort()
return arr
def main():
m = int(input("Enter the upper bound (m): "))
r = int(input("Enter the number of repetitions (r): "))
n_values = [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]
for n in n_values:
total_time = 0
total_space = 0
for _ in range(r):
random_numbers = generate_random_integers(n, m)
# Count numbers larger than 50
count = count_larger_than_50(random_numbers)
if count > 5:
# Sort the array
random_numbers = sort_array(random_numbers)
# Delete the fifth element
random_numbers = delete_nth_element(random_numbers, 4)
else:
# Sort in non-increasing order
random_numbers = sort_array(random_numbers, ascending=False)
# Delete the second element
random_numbers = delete_nth_element(random_numbers, 1)
# Insert 10 into the sorted array
random_numbers = insert_into_sorted_array(random_numbers, 10)
# Record time and space usage (you can use appropriate functions to measure time and space)
# Record time here
# Record space here
if n > 100:
continue
# Print the final array
print(f"n = {n}, Result: {random_numbers}")
# Calculate average time and space complexity for n
# Output the average time and space complexity here
if __name__ == "__main__":
main()
n = 10, Result: [1, 1, 1, 2, 2, 2, 2, 2, 2, 10]
n = 10, Result: [1, 1, 1, 2, 2, 2, 2, 2, 2, 10]
n = 50, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
n = 50, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
n = 100, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
n = 100, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]

7) Perform a theoretical complexity analysis of your design (i.e., count number of operations/instructions and space usage) and then express that using asymptotic notation as a function of the input size (Pause: what is the input size of your problem?)

To perform a theoretical complexity analysis of the provided design, we'll count the number of key operations/instructions and estimate space usage. The input size of the problem is 'n', the number of random integers generated. Let's analyze the time and space complexity of each step:

Step 1: Generate n Random Integers

• Time Complexity: O(n)
• Space Complexity: O(n)

Step 2: Store the Generated Numbers (Linked List)

• Time Complexity: O(n)
• Space Complexity: O(n)

Step 3: Count Numbers Larger than 50

• Time Complexity: O(n)
• Space Complexity: O(1) (constant space for the count variable)

Step 4: Sort the Data

• Time Complexity: O(n log n) (assuming a comparison-based sorting algorithm like Python's built-in sorted())
• Space Complexity: O(1) (constant space for sorting in-place)

Step 5: Delete an Element

• Time Complexity: O(n) (in the worst case, if deleting an element from the middle of an array, shifting is required)
• Space Complexity: O(1)

Step 6: Insert a Number

• Time Complexity: O(n) (in the worst case, if inserting a number at the beginning or middle of an array, shifting is required) Space Complexity: O(1)Overall Time Complexity (steps 1 to 6):
• Dominated by the sorting step, so O(n log n)
• Overall Space Complexity (steps 1 to 6):

Dominated by the storage of generated random integers and the linked list (or array), so O(n)

Step 7: Complexity as a Function of Input Size (n):

Time Complexity: O(n log n) - due to sorting (Step 4) Space Complexity: O(n) - due to storage of generated numbers The theoretical complexity analysis expresses the time and space complexity in terms of the input size 'n' using asymptotic notation. The most time-consuming operation in this process is the sorting step, which has a time complexity of O(n log n) when using a comparison-based sorting algorithm. The overall space complexity is O(n) because of the storage of generated numbers.

8) Empirically measure the time and space complexity of your code.

import random
import time
import sys
def generate_random_integers(n, m):
return [random.randint(1, m) for _ in range(n)]
def count_larger_than_50(arr):
count = 0
for num in arr:
if num > 50:
count += 1
return count
def sort_array(arr, ascending=True):
return sorted(arr) if ascending else sorted(arr, reverse=True)
def delete_nth_element(arr, n):
if n < len> arr.pop(n)
return arr
def insert_into_sorted_array(arr, value):
arr.append(value)
arr.sort()
return arr
def main():
m = int(input("Enter the upper bound (m): "))
r = int(input("Enter the number of repetitions (r): "))
n_values = [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]
for n in n_values:
total_time = 0
total_space = 0
for _ in range(r):
random_numbers = generate_random_integers(n, m)
# Start measuring time
start_time = time.process_time()
# Count numbers larger than 50
count = count_larger_than_50(random_numbers)
if count > 5:
# Sort the array
random_numbers = sort_array(random_numbers)
# Delete the fifth element
random_numbers = delete_nth_element(random_numbers, 4) else:
# Sort in non-increasing order
random_numbers = sort_array(random_numbers, ascending=False)
# Delete the second element
random_numbers = delete_nth_element(random_numbers, 1)
# Insert 10 into the sorted array
random_numbers = insert_into_sorted_array(random_numbers, 10)
# Stop measuring time
end_time = time.process_time()
# Calculate elapsed time
elapsed_time = end_time - start_time
# Measure space usage (in bytes)
space_usage = sys.getsizeof(random_numbers)
# Accumulate total time and space
total_time += elapsed_time
total_space += space_usage
if n > 100:
continue
# Print the final array
print(f"n = {n}, Result: {random_numbers}")
# Calculate average time and space complexity for n
avg_time = total_time / r
avg_space = total_space / r
print(f"Avg. Time for n={n}: {avg_time} seconds")
print(f"Avg. Space for n={n}: {avg_space} bytes")
if __name__ == "__main__":
main()
n = 10, Result: [1, 1, 1, 1, 1, 1, 2, 2, 2, 10]
n = 10, Result: [1, 1, 1, 1, 1, 1, 2, 2, 2, 10]
Avg. Time for n=10: 0.0 seconds
Avg. Space for n=10: 136.0 bytes
n = 50, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
n = 50, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
Avg. Time for n=50: 0.0 seconds
Avg. Space for n=50: 456.0 bytes
n = 100, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
n = 100, Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
Avg. Time for n=100: 0.0 seconds
Avg. Space for n=100: 856.0 bytes
Avg. Time for n=500: 0.0 seconds
Avg. Space for n=500: 4056.0 bytes
Avg. Time for n=1000: 0.0 seconds
Avg. Space for n=1000: 8056.0 bytes
Avg. Time for n=5000: 0.0 seconds
Avg. Space for n=5000: 40056.0 bytes
Avg. Time for n=10000: 0.0 seconds
Avg. Space for n=10000: 80056.0 bytes
Avg. Time for n=50000: 0.0 seconds
Avg. Space for n=50000: 400056.0 bytes
Avg. Time for n=100000: 0.015625 seconds
Avg. Space for n=100000: 800056.0 bytes

9) Compare the complexities from steps 7) and 8). (Long pause: in order to compare, what all you will need to do? We will discuss some alternatives in class, so stay tuned and this writeup will be modified accordingly at a later date.) Input m and r from the console (m is the upper bound on the range of numbers to be generated, and r is the number of times to repeat the computation of steps 2 – 4 for each value of n for better measurement of average-time); use the following values of n=10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000 etc – push the limit of your machine to maximum n that your machine can handle for your implementation; no need to output the final linked list or array when n > 100.

If the empirical measurements closely match the theoretical analysis, it indicates that your code behaves as expected based on the theoretical complexity analysis.

If there are significant differences, consider the following:

Factors like hardware, compiler optimizations, and Python implementation can influence empirical results. If the empirical measurements show better performance (faster or more efficient) than the theoretical analysis, it might be due to implementation-specific optimizations or hardware capabilities. If the empirical measurements show worse performance (slower or less efficient) than the theoretical analysis, it might indicate suboptimal code or additional hidden complexities. To summarize, the comparison helps validate the theoretical complexity analysis by checking how well it aligns with actual performance measurements. Any significant deviations should be investigated to understand the underlying factors affecting the code's behavior.

Are you struggling to keep up with the demands of your academic journey? Don't worry, we've got your back! Exam Question Bank is your trusted partner in achieving academic excellence for all kind of technical and non-technical subjects.

Our comprehensive range of academic services is designed to cater to students at every level. Whether you're a high school student, a college undergraduate, or pursuing advanced studies, we have the expertise and resources to support you.

To connect with expert and ask your query click here Exam Question Bank