Algorithmic Toolbox | Week 4
Course Name: Algorithmic Toolbox
Course Link: Algorithmic Toolbox
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
Programming Assignment 4: Divide and Conquer
4-1: Binary Search
def binary_search(keys, query):
left = 0
right = len(keys) - 1
while right >= left:
middle = (left + right) // 2
if keys[middle] == query:
return middle
elif keys[middle] < query:
left = middle + 1
else:
right = middle - 1
return -1
if __name__ == '__main__':
num_keys = int(input())
input_keys = list(map(int, input().split()))
assert len(input_keys) == num_keys
num_queries = int(input())
input_queries = list(map(int, input().split()))
assert len(input_queries) == num_queries
results = []
for q in input_queries:
results.append(binary_search(input_keys, q))
print(' '.join(map(str, results)))These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
4-2: Binary Search with Duplicates
def binary_search_first_occurrence(keys, query):
left = 0
right = len(keys) - 1
result = -1
while right >= left:
middle = (left + right) // 2
if keys[middle] == query:
result = middle
right = middle - 1 # Continue to search in the left half
elif keys[middle] < query:
left = middle + 1
else:
right = middle - 1
return result
if __name__ == '__main__':
num_keys = int(input())
input_keys = list(map(int, input().split()))
assert len(input_keys) == num_keys
num_queries = int(input())
input_queries = list(map(int, input().split()))
assert len(input_queries) == num_queries
results = []
for q in input_queries:
results.append(binary_search_first_occurrence(input_keys, q))
print(' '.join(map(str, results)))
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
4-3: Majority Element
n = int(input())
seq = [int(i) for i in input().split()]
def divide_func(seq, l, r):
if l+1==r:
return seq[l]
elif l+2==r:
return seq[l]
m = (l+r)//2
left = divide_func(seq, l, m)
right = divide_func(seq, m, r)
c1, c2 = 0, 0
for i in seq[l:r]:
if i == left:
c1+=1
elif i == right:
c2+=1
if c1>(r-l)//2 and left != -1:
return left
elif c2>(r-l)//2 and right != -1:
return right
else:
return -1
print(int(divide_func(seq, 0, n) != -1))
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
4-4: Improving QuickSort
from random import randint
def partition3(array, left, right):
pivot = array[left]
lt = left
gt = right
i = left
while i <= gt:
if array[i] < pivot:
array[lt], array[i] = array[i], array[lt]
lt += 1
i += 1
elif array[i] > pivot:
array[gt], array[i] = array[i], array[gt]
gt -= 1
else:
i += 1
return lt, gt
def randomized_quick_sort(array, left, right):
if left >= right:
return
k = randint(left, right)
array[left], array[k] = array[k], array[left]
m1, m2 = partition3(array, left, right)
randomized_quick_sort(array, left, m1 - 1)
randomized_quick_sort(array, m2 + 1, right)
if __name__ == '__main__':
input_n = int(input())
elements = list(map(int, input().split()))
assert len(elements) == input_n
randomized_quick_sort(elements, 0, len(elements) - 1)
print(*elements)
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
4-5: Inversions
def merge(left, right):
i, j, inversion_counter = 0, 0, 0
final = list()
while i < len(left) and j< len(right):
if left[i] <= right[j]:
final.append(left[i])
i += 1
else:
final.append(right[j])
inversion_counter += len(left) - i
j += 1
final += left[i:]
final += right[j:]
return final, inversion_counter
def mergesort(arr):
global tot_count
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
sorted_arr, temp = merge(left, right)
tot_count += temp
return sorted_arr
tot_count = 0
n = int(input())
seq = [int(i) for i in input().split()]
mergesort(seq)
print(tot_count)
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
4-6: Organizing a Lottery
master_list = list()
s, p = [int(i) for i in input().split()]
for i in range(s):
a, b = [int(i) for i in input().split()]
master_list.append((a,'l'))
master_list.append((b,'r'))
points = input().split()
for i in points:
master_list.append((int(i),'p'))
master_list.sort()
segment_count = 0
point_segment_map = dict()
for i in master_list:
if i[1] == 'l': segment_count += 1
elif i[1] == 'r': segment_count -= 1
else:
point_segment_map[i[0]] = segment_count
temp = ''
for i in points:
temp += str(point_segment_map[int(i)]) + ' '
print(temp[:-1])
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
4-7:Closest Points
import math
def dist(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def closest_split_pair(p_x, p_y, delta, best_pair):
ln_x = len(p_x)
mx_x = p_x[ln_x // 2][0]
s_y = [x for x in p_y if mx_x - delta <= x[0] <= mx_x + delta]
best = delta
ln_y = len(s_y)
for i in range(ln_y - 1):
for j in range(i+1, min(i + 5, ln_y)):
p, q = s_y[i], s_y[j]
dst = dist(p, q)
if dst < best:
best_pair = p, q
best = dst
return best_pair[0], best_pair[1], best
def brute(ax):
mi = dist(ax[0], ax[1])
p1 = ax[0]
p2 = ax[1]
ln_ax = len(ax)
if ln_ax == 2:
return p1, p2, mi
for i in range(ln_ax-1):
for j in range(i + 1, ln_ax):
if i != 0 and j != 1:
d = dist(ax[i], ax[j])
if d < mi:
mi = d
p1, p2 = ax[i], ax[j]
return p1, p2, mi
def closest_pair(ax, ay):
ln_ax = len(ax)
if ln_ax <= 3:
return brute(ax)
mid = ln_ax // 2
Qx = ax[:mid]
Rx = ax[mid:]
midpoint = ax[mid][0]
Qy = list()
Ry = list()
for x in ay:
if x[0] < midpoint:
Qy.append(x)
else:
Ry.append(x)
(p1, q1, mi1) = closest_pair(Qx, Qy)
(p2, q2, mi2) = closest_pair(Rx, Ry)
if mi1 <= mi2:
d = mi1
mn = (p1, q1)
else:
d = mi2
mn = (p2, q2)
(p3, q3, mi3) = closest_split_pair(ax, ay, d, mn)
if d <= mi3:
return mn[0], mn[1], d
else:
return p3, q3, mi3
def solution(a):
ax = sorted(a, key=lambda x: x[0])
ay = sorted(a, key=lambda x: (x[1], x[0]))
p1, p2, mi = closest_pair(ax, ay)
return mi
points = list()
n = int(input())
for i in range(n):
points.append([int(i) for i in input().split()])
print(solution(points))
These are Algorithmic Toolbox Week 4 Programming Assignment Coursera Answers
More Weeks of the course: Click Here
More Coursera courses: https://progiez.com/coursera
