Count Negative Numbers | 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 ” CountNegativeNumbers
Count Negative Numbers
When working with sorted data, we can often take advantage of the fact that it’s sorted to traverse the data more e”ciently. This is helpful in many, many situations.
Write a function
count_negative(L)
that consumes a sorted list of integers, and returns the counts of the negative and non-negative elements in a two-element array list. The input list may be empty, but if it contains any elements, they will be listed in sorted order. The output list should consist of two elements, where the #rst element is the count of the number of negative elements, and the second element is the count of the non-negative elements. You need to return the results in 𝑂 (log 𝑛) time, which is better performance than just iterating through the list!
Samples:
1 of 4 3/30/21, 12:16 AM
Count Negative Numbers | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
count_negative([-112, -43, -6, -5, -4, -3, -2, -1]) => [8, 0]
count_negative([-5, -3, -2, -1, 0, 2, 4, 6, 5476]) => [4, 5]
No submissions found
1 def count_negative(L): 2 ##YOUR CODE GOES HERE 3 pass
2 of 4 3/30/21, 12:16 AM
Count Negative Numbers | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
Code Output
Run Code Save Code
Discussion
Topic: Module 8 / Count Negative Numbers
Show all posts
Reset Code
Show History Visualize Submit Code
View Submissions
Hide Discussion
Add a Post
by recent activity
# List slicing
Hi I just want to make sure my code is indeed running in logn time. I know in module 7 it showed: L[a:b] is O(b−a…
# O(log n) is the must or suggestion?
Can I submit a code with O(n)? I know log n is more e”cient but I cannot think of the code using log n.
6 3
3 of 4 3/30/21, 12:16 AM
Count Negative Numbers | Assignment 8 | CS 116 Courseware | UW Online https://online.cs.uwaterloo.ca/courses/course-v1:UW+CS116+2021_01/courseware/a2584c108…
# Do we need to consider empty lists?
Just want to make sure that the empty list will return [0,0]
2 3
2
3
2
4
2 2 2 2
# Order of sorting
The question mentioned that the input list is always sorted, can we assume the list is always nondecreasing? Lik…
# O(log n)
Is (log n) more e”cient than O(n)? For this question are we expected to not go through the entire list?
# question
does O(log n) indicate that the function should have recursive calls?
# Sorted List
Since it doesn’t specify, can L be sorted in decreasing order or increasing order?
# Di%erence between list and array?
Throughout this course, we used lists to de#ne lists. In this question, we are asked to create a 2 element array. I …
# Negative Numbers
Is 0 considered a negative number?
# Empty List case
If an empty list is inputted, the function would then return [0,0], have I understood the instructions correctly?
# Testing
can we use the range function to create tests or does that have any impact on anything
# Will the list contains duplicated value?
I wonder if it is possible for the given list to contain duplicated values like two zeros?
4 of 4 3/30/21, 12:16 AM