Session 2 (8 PM - 10 PM) ONLINE Questions for Unprotected Exam (Programming, Datastructures and Algorithms using Python) (NPTEL 2022 - CS26)

 

Question 1

Here is an function to return the maximum value in a list of integers. There is an error in this function. Provide an input list for which maxbad produces an incorrect output.

def maxbad(l):
  mymax = 0
  for i in range(len(l)):
    if l[i] > mymax:
       mymax = l[i]
  return(mymax)

Open up the code submission box below and write your test case where you would normally paste your code.

Here is a function stablesortbad that takes a list of pairs of integers as input and sorts them by the second coordinate in each pair. A stable sort preserves the order of pairs that have an equal second coordinate. This is not a stable sort. Provide an input for which stablesortbad produces an output that is not stably sorted. Your input should be a list of pairs of integers of the form [(i1,j1),(i2,j2),...,(in,jn)].

def stablesortbad(l):
  for j in range(len(l)-1):
    for i in range(len(l)-1):
      if l[i][1] >= l[i+1][1]:
        (l[i],l[i+1]) =  (l[i+1],l[i])
  return(l)    

Open up the code submission box below and write your test case where you would normally paste your code. Your input should be a list of pairs of integers of the form [(i1,j1),(i2,j2),...,(in,jn)].

Question 3

Here is a function to compute the third smallest value in a list of distinct integers. All the integers are guaranteed to be below 1000000. You have to fill in the missing lines. You can assume that there are at least three numbers in the list.

def thirdmin(l):
  (mymin,mysecondmin,mythirdmin) = (1000000,1000000,1000000)
  for i in range(len(l)):
  # Your code below this line


  # Your code above this line
  return(mythirdmin)

Open up the code submission box below and fill in the gap in the code. Ensure that you maintain correct indentation.

Question 4

Recall that the positions in a list of length n are 0,1,…,n-1. We want to write a function oddpositions(l) that returns the elements at the odd positions in l. In other words, the function should return the list [l[1],l[3],...]. For instance oddpositions([]) == [], oddpositions([7]) == [], oddpositions([8,11,8]) == [11] and oddpositions([19,3,44,44,3,19]) == [3,44,19]. A recursive definition of oddpositions is given below. You have to fill in the missing argument for the recursive call.

def oddpositions(l):
  if len(l) <= 1:
    return([])
  else:
    return(...)

Open up the code submission box below and fill in the missing argument for the recursive call.

Question 5

A positive integer n is a sum of three squares if n = i2 + j2 + k2 for integers i,j,k such that i ≥ 1, j ≥ 1 and k ≥ 1. For instance, 29 is a sum of three squares because 10 = 22 + 32 + 42, and so is 6 (12 + 12 + 22). On the other hand, 16 and 20 are not sums of three squares.

Write a Python function sumof3squares(n) that takes a positive integer argument and returns True if the integer is a sum of three squares, and False otherwise.

Question 6

Write a Python function intersect(l1,l2) that takes two sorted lists as arguments and returns the list of all elements common to both l1 and l2 in the same order that they appear in the two lists. If the same element occurs more than once in both lists, it should appear in the output exactly once.

Thus, intersect([2,2,4],[1,2,2,3,4]) should return [2, 4] while intersect([1,2,3],[4,5,6]) should return [].

Question 7

Write a Python program that reads input from the keyboard (standard input). The input will consist of some number of lines of text. The input will be terminated by a blank line. The first line will consist of a single word to be interpreted as a pattern, after discarding the new line character. Your program should print the last line from the second line onward that contains an occurrence of the pattern. If no lines match the pattern, the program should print an empty line. You can assume that the input will have a non-empty pattern line. Recall that for a string s and a pattern p, s.find(p) returns the first position in s where p occurs, and returns -1 if p does not occur in s.

For instance, if the input is the following:

the
"Spot the mistake
in the following argument",
Jack challenged
1+(-1+1)+(-1+1)+... = (1+ -1)+(1+ -1)+...
so therefore,
1 = 0
??

then your program should print the following. Note that the pattern string the is matched by the word therefore.

Question 8

Write a Python function maxaverage(l) that takes a list of pairs of the form (name,score) as argument, where name is a string and score is an integer. Each pair is to be interpreted as the score of the named player. For instance, an input of the form [('Kohli',73),('Ashwin',33),('Kohli',7),('Pujara',122),('Ashwin',90)] represents two scores of 73 and 7 for Kohli, two scores of 33 and 90 for Ashwin and one score of 122 for Pujara. Your function should compute the players who have the highest average score (average = total across all scores for that player divided by number of entries) and return the list of names of these players as a list, sorted in alphabetical order. If there is a single player, the list will contain a single name.

For instance, maxaverage([('Kohli',73),('Ashwin',33),('Kohli',7),('Pujara',122),('Ashwin',90)]) should return ['Pujara'] because the average score of Kolhi is 40 (80 divided by 2), of Ashwin is 61.5 (123 divided by 2) and of Pujara is 122 (122 divided by 1), of which 122 is the highest.