Remove Duplicates | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
!
A new course announcement has been posted. Click here to view the new announcement.
Module 8: Searching and Sorting
Course ” Algorithms ” Assignment8 ” RemoveDuplicates
Remove Duplicates
Write a function
remove_duplicates(L)
that consumes a list L of natural numbers and uses a modi”cation of our binary searching algorithm to
replace all elements that appear more than once with -1. Your code must run in 𝑂 (𝑛 log 𝑛) time. Sample:
and L is mutated to [-1,1,2,-1,-1,4,5,-1,182202]
L = [6,1,2,3,3,4,5,6,182202]
remove_duplicates(L) => None
1 of 4 3/30/21, 12:16 AM
Remove Duplicates | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
Loading last submission entry…
1 def remove_duplicates(L): 2 ##YOUR CODE GOES HERE 3 pass
Code Output
2 of 4 3/30/21, 12:16 AM
Remove Duplicates | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
Run Code Save Code
Discussion
Topic: Module 8 / Remove Duplicates
Show all posts
Reset Code
Show History Visualize Submit Code
View Submissions
Hide Discussion
Add a Post
by recent activity
# Con”rmation
in is O(n), right?? like 3 in [1,2,3]
2 4
2 2
# Application of Binary search
I want to sort the list, mutate it , then arrange it back to its original order. which is O(nlogn)+O(n)+O(nlogn)=O(nl…
#L
can L be empty list?
# Question 2
3 of 4 3/30/21, 12:16 AM
Remove Duplicates | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
The code output shown on EdX is not the same as the result of submission on Markus, how is it possible? On Ed…
# Using binary search
Do I have to use the binary searching algorithm strictly when we are muting the elements to -1, or as long as I us…
2
3
2
2
2
2
2
2
# Runtime
Hi, if my code could be tested by Markus, does it mean my runtime is correct?
# Runtime on sorted/sort
I already went through section 8.6 but I just wanted to con”rm this statement: **Both sort and sorted *always* …
# Modi”cation of binary searching algorithm
When saying that we should use a Modi”cation of binary searching algorithm, does that mean we have to alway…
# Question 2
Can the list be empty?
# Binary Search and Sorted Lists
Hi, I got confused with the (modi”cation of our binary searching algorithm). doesn’t binary search take advantag…
# Multiple Questions
1. For every n in L if we run a function with tightest bound O(log n), the run time would be O(n) x O(logn) = O(nlo…
# In our purpose statement do we need to mention the code runtime and that it uses a modi”cation of binary search algorithm?
Thanks in advance!
Load more
4 of 4 3/30/21, 12:16 AM