Programming, DS, And Algo Using Python This course is an introduction to programming and problem-solving in Python. It does not assume any prior knowledge of programming. Using some motivating examples, the course quickly builds up basic concepts such as conditionals, loops, functions, lists, strings, and tuples. It goes on to cover searching and sorting algorithms, dynamic programming, and backtracking, as well as topics such as exception handling and using files. As far as data structures are concerned.
Programming, Data Structures And Algorithms Using Python is a MOOC based course that is 8 weeks in duration and can fulfill the criteria of 4 credits in a year. You can visit the NPTEL SWAYAM platform and register yourself for the course. This course is brought to you by Madhavan Mukund studied at IIT Bombay (BTech) and Aarhus University (Ph.D.). He has been a faculty member at Chennai Mathematical Institute since 1992, where he is presently Professor and Dean of Studies. His main research area is formal verification. He has active research collaborations within and outside India and serves on international conference program committees and editorial boards of journals.
Who Can Join: Any discipline PREREQUISITES: Minimum: School level mathematics.
INDUSTRY SUPPORT: This course should be of value to any company requiring programming skills.
CRITERIA TO GET A CERTIFICATE
Average assignment score = 25% of the average of the best 6 assignments out of the total 8 assignments.
Exam score = 75% of the proctored certification exam score out of 100
Final score = Average assignment score + Exam score
Students will be eligible for CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If any of the 2 criteria are not met, the student will not get the certificate even if the Final score >= 40/100.
Programming, Data Structures And Algorithms Programming Assignment Week 8 Answers:-
Contents
Q1.
Dividing Sequences
(IARCS OPC Archive, K Narayan Kumar, CMI)
This problem is about sequences of positive integers a1,a2,…,aN. A subsequence of a sequence is anything obtained by dropping some of the elements. For example, 3,7,11,3 is a subsequence of 6,3,11,5,7,4,3,11,5,3 , but 3,3,7 is not a subsequence of 6,3,11,5,7,4,3,11,5,3 . A fully dividing sequence is a sequence a1,a2,…,aN where ai divides aj whenever i < j. For example, 3,15,60,720 is a fully dividing sequence.
Given a sequence of integers your aim is to find the length of the longest fully dividing subsequence of this sequence. Consider the sequence 2,3,7,8,14,39,145,76,320 It has a fully dividing sequence of length 3, namely 2,8,320, but none of length 4 or greater. Consider the sequence 2,11,16,12,36,60,71,17,29,144,288,129,432,993 .
It has two fully dividing subsequences of length 5,
- 2,11,16,12,36,60,71,17,29,144,288,129,432,993 and
- 2,11,16,12,36,60,71,17,29,144,288,129,432,993
Code:-
def lds(arr, n):
lds =[0 for i in range(n)]
lds[0] = 1
for i in range(n):
lds[i] = 1
for j in range(i):
if (lds[j] !=0 and arr[i] % arr[j] == 0):
lds[i] = max(lds[i], lds[j] + 1)
return max(lds)
arr=[]
n=int(input())
arr.append (n)
for i in range(n):
arr.append(int(input()))
print(lds(arr, len(arr)))Programming, Data Structures And Algorithms ONLINE PROGRAMMING TEST 8PM TO 11 PM:-
Q1. Here is an function to return the minimum value in a list. There is an error in this function. Provide an input list for which minbad produces an incorrect output.
def minbad(l):
mymin = l[-len(l)]
for i in range(-len(l),-1):
if l[i] < mymin:
mymin = l[i]
return(mymin)ANSWER:-
[55,5,0]Q2. 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) ANSWER:-
[(12,15),(5,9,),(8,3),(77,15)]Q3. Here is a function to compute the third largest value in a list of distinct integers. All the integers are guaranteed to be positive. You have to fill in the missing lines. You can assume that there are at least three numbers in the list.
def thirdmax(l):
(mymax,mysecondmax,mythirdmax) = (0,0,0)
for i in range(len(l)):
# Your code below this line
# Your code above this line
return(mythirdmax)Answer:-
pass
for i in range(2):
l.remove(max(l))
mythirdmax = max(l)Q4. Recall that the positions in a list of length n are 0,1,…,n-1. We want to write a function mod3pos(l) that returns the elements at all positions in l that are divisible by 3. In other words, the function should return the list [l[0],l[3],…]. For instance mod3pos([]) == [], mod3pos([7]) == [7], mod3pos([8,11,8,11]) == [8,11] and mod3pos([19,3,44,44,3,19,17,23]) == [19,44,17]. A recursive definition of mod3pos is given below. You have to fill in the missing argument for the recursive call.
def mod3pos(l):
if len(l) == 0:
return([])
else:
return(...)Answer:-
[l[0]]+mod3pos(l[3:])Q5. A positive integer is said to be square free, if it is not divisible by any square integer strictly greater than 1. For instance, 5, 10 and 21 are square free, while 4 and 48 are not, since 4 is divisible by 22 and 48 is divisible by 42.
Write a Python function squarefree(n) that takes a positive integer argument and returns True if the integer is square free, and False otherwise.
Answer:-
from math import sqrt
def squarefree(n):
if n % 2 == 0:
n = n / 2
if n % 2 == 0:
return False
for i in range(3, int(sqrt(n) + 1)):
if n % i == 0:
n = n / i
if n % i == 0:
return False
return TrueQ6. Write a Python function disjointlist(l1,l2) that takes two lists as arguments and returns True if the two lists are disjoint, otherwise returns False.
Two lists are said to be disjoint if there is no element that common to both the lists. For instance, [2,2,3,4,5] and [6,8,8,1] are disjoint, while [1,2,3,4] and [2,2] are not.
Answer:-
def disjointlist(l1,l2) :
s1 = set(l1)
s2 = set(l2)
intersection = s1 & s2
return (len(intersection)==0)Q7. Write a Python program that reads input from the keyboard (standard input). The input will consist of an even number of lines of text. The input will be terminated by a blank line. Suppose there are 2n lines of input. Your program should print out the last n lines of the input, i.e., the second half of the input, followed by the first n lines, i.e., the first half of the input.
For instance, if the input is the following:
our dear friend,
let's eatAnswer:-
p=[]
while True:
s=input()
if s=="":
break
else:
p.append(s)
for i in range(len(p)//2,len(p)):
print(p[i])
for i in range(len(p)//2):
print(p[i])Q8. Write a Python function maxdifference(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),(‘Kohli’,66),(‘Ashwin’,90)] represents three scores of 73, 66 and 7 for Kohli, two scores of 33 and 90 for Ashwin and one score of 122 for Pujara. Your function should compute the difference between the maximum and minimum score for each player and return the list of players for whom this difference is maximum. The list should be sorted in ascending order by the name of the player.
Answer:-
def maxdifference(l):
d={}
for i in range(len(l)):
(name,scores )=l[i]
try:
d[name].append(scores )
except KeyError:
d[name]={}
d[name]=[scores ]
res=[]
maaa=0
for i in d.keys():
ma=max(d[i])
mi=min(d[i])
mx=ma-mi
if maaa<mx:
maaa=mx
for i in d.keys():
ma=max(d[i])
mi=min(d[i])
mx=ma-mi
if mx==maaa:
res.append(i)
res.sort()
return(res)Programming, Data Structures And Algorithms ONLINE PROGRAMMING TEST:-
Q1. Here is an function to return the maximum value in a list. There is an error in this function. Provide an input list for which maxbad produces an incorrect output.
def maxbad(l):
mymax = l[-1]
for i in range(-1,-len(l),-1):
if l[i] > mymax:
mymax = l[i]
return(mymax)Answer:-
[-2,-3,-4]Q2. Here is an implementation of quicksort, which splits the input list according the pivot value, sorts each part and arranges the sorted parts with the pivot in between to give the final sorted sequence. There is a small error in the implementation. Provide an input list for which this version of quicksort produces an incorrect output.
Code:-
def quicksortbad(l):
if len(l) < 2:
return(l)
else:
pivot = l[0]
smaller = [l[j] for j in range(1,len(l)) if l[j] < pivot]
bigger = [l[j] for j in range(1,len(l)) if l[j] > pivot]
rearrange = quicksortbad(smaller) + [pivot] + quicksortbad(bigger)
return(rearrange)Answer:-
[11,22,33,40,40]Q3. The median of three numbers x,y,z is the second number in the sequence when the three numbers are sorted in ascending or descending order. Here is a function to compute the median of three input integers. You have to fill in the missing lines.
def median3(x,y,z):
if x <= y:
if x >= z:
mymedian = x
# Your code below this line
# Your code above this line
return(mymedian)Answer:-
elif y <= z:
mymedian = y
else:
mymedian = z
else:
if x < z:
mymedian = x
elif y > z:
mymedian = y
else:
mymedian = zProgramming, Data Structures And Algorithms ONLINE PROGRAMMING TEST:-
Q4. A list is a decreasing if each element is strictly smaller than the preceding one. For instance [], [7], [11,8] and [89,63,44,19,3] are decreasing, while [3,18,4] and [23,14,14,3] are not. Here is a recursive function to check if a list is decreasing. You have to fill in the missing argument for the recursive call.
def decreasing(l):
if l==[] or len(l) == 1:
return(True)
else:
return(...)Answer:-
decreasing(l[1:]) if l[0] > l[1] else FalseQ5. A positive integer n is a sum of three cubes if n = i3 + j3 + k3 for integers i,j,k such that i ≥ 1, j ≥ 1 and k ≥ 1. For instance, 10 is a sum of three cubes because 10 = 13 + 13 + 23, and so is 36 (13 + 23 + 33). On the other hand, 4 and 11 are not sums of three cubes.
Write a Python function sum3cubes(n) that takes a positive integer argument and returns True if the integer is a sum of three cubes, and False otherwise.
Code:-
def sum3cubes(n):
sum=0
for i in range(1,n):
for j in range(1,n):
for k in range(1,n):
if (i*i*i+j*j*j+k*k*k) == n:
sum+=1
if sum>=1:
return True
else:
return FalseQ6. Write a Python function uncommon(l1,l2) that takes two lists sorted in ascending order as arguments and returns the list of all elements that appear in exactly one of the two lists. The list returned should be in ascending order. All such elements should be listed only once, even if they appear multiple times in l1 or l2.
Thus, uncommon([2,2,4],[1,3,3,4,5]) should return [1,2,3,5] while uncommon([1,2,3],[1,1,2,3,3]) should return [].
Code:-
def uncommon(l1,l2) :
s1 = set(l1)
s2 = set(l2)
union = s1|s2
intersection = s1 & s2
ans = list(union - intersection)
ans.sort()
return ansQ7. Write a Python program that reads input from the keyboard (standard input). The input will be terminated by a blank line. The lines are numbered 0,1,2,… Your program should print out the even numbered lines followed by the odd numbered lines. In other words, first print lines 0,2,4,… then lines 1,3,5,…
Line zero
Line one
Line two
Line three
Line fourAnswer:-
x = input()
c = 0
even = []
odd = []
while len(x) > 0 :
if c%2 == 0 :
even.append(x)
else :
odd.append(x)
x = input()
c+=1
for eve in even :
print(eve)
for od in odd :
print(od)Q8. Write a Python function aboveaverage(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 list of players whose individual average score is greater than or equal to the overall average score.
Code:-
def aboveaverage(l):
d = {}
for i in l:
name, score = i
if name in d:
tot_score, num = d[name]
d[name] = (tot_score+score, num+1)
else:
d[name] = (score, 1)
max= -1
for k in d:
tot_score, num = d[k]
ave = tot_score/num
if(max < ave):
max = ave
l = []
for k in d:
tot_score, num = d[k]
ave = tot_score/num
if(max == ave):
l.append(k)
l.sort()
return lProgramming, Data Structures And Algorithms Quiz Assignment Week 6 Answers:-
Q1. Suppose u and v both denote sets in Python. Under what condition can we guarantee that u-(u-v) == v?
Answer:- C – The set v should be a subset of the set u
Q2. Suppose u and v both denote sets in Python. Under what condition can we guarantee that u|v == u^v?
Answer:- A – The sets u and v should be disjoint.
Q3. Which of the following does not correspond to a max-heap on the list of values [19, 28, 29, 31, 31, 45, 55, 72, 83, 97]?
Answer:- B – [97, 55, 83, 29, 45, 72, 31, 19, 31, 28]
Q4. Consider the max-heap [96, 96, 55, 74, 37, 42, 29, 18, 31, 19]. Suppose we apply the operation delete_max() twice to this max-heap. The resulting max-heap is:
Answer:- D – [74, 37, 55, 31, 19, 42, 29, 18]
Programming, Data Structures And Algorithms Programming Assignment Week 5 Answers:-
Q1. Here are some basic facts about tennis scoring: A tennis match is made up of sets. A set is made up of games.
To win a set, a player has to win 6 games with a difference of 2 games. At 6-6, there is often a special tie-breaker. In some cases, players go on playing till one of them wins the set with a difference of two games.
Tennis matches can be either 3 sets or 5 sets. The player who wins a majority of sets wins the match (i.e., 2 out 3 sets or 3 out of 5 sets) The score of a match lists out the games in each set, with the overall winner’s score reported first for each set. Thus, if the score is 6-3, 5-7, 7-6 it means that the first player won the first set by 6 games to 3, lost the second one 5 games to 7 and won the third one 7 games to 6 (and hence won the overall match as well by 2 sets to 1).
You will read input from the keyboard (standard input) containing the results of several tennis matches. Each match’s score is recorded on a separate line with the following format:
Winner:Loser:Set-1-score,…,Set-k-score, where 2 ≤ k ≤ 5
Code:-
stats = dict()
LINE= input()
while LINE:
(wsets,lsets,wgames,lgames) = (0,0,0,0)
(WINNER ,LOSER ,setscores) = LINE.strip().split(':',2)
sets = setscores.split(',')
for set in sets:
(winstr,losestr) = set.split('-')
win = int(winstr)
lose = int(losestr)
wgames = wgames +win
lgames = lgames+ lose
if win > lose:
wsets = wsets+1
else:
lsets=lsets+1
for player in [WINNER ,LOSER ]:
try:
stats[player]
except KeyError:
stats[player]=[0,0,0,0,0,0]
if wsets >=3:
stats[WINNER ][0]=stats[WINNER ][0]+1
else:
stats[WINNER ][1]=stats[WINNER ][1]+1
stats[WINNER ][2]=stats[WINNER ][2]+ wsets
stats[WINNER ][3]=stats[WINNER ][3]+wgames
stats[WINNER ][4]=stats[WINNER ][4]-lsets
stats[WINNER ][5]=stats[WINNER ][5] - lgames
stats[LOSER ][2] = stats[LOSER ][2] + lsets
stats[LOSER ][3] = stats[LOSER ][3] + lgames
stats[LOSER ][4] = stats[LOSER ][4] - wsets
stats[LOSER ][5] = stats[LOSER ][5] - wgames
LINE = input()
statlist = [(stat[0],stat[1],stat[2],stat[3],stat[4],stat[5],name) for name in
stats.keys() for stat in [stats[name]]]
statlist.sort(reverse = True)
for e in statlist:
print(e[6],e[0],e[1],e[2],e[3],-e[4],-e[5])Programming, Data Structures And Algorithms Programming Assignment Week 4 Answers:-
1. We have a list of annual rainfall recordings of cities. Each element in the list is of the form (c,r) where c is the city and r is the annual rainfall for a particular year. The list may have multiple entries for the same city, corresponding to rainfall recordings in different years.
Write a Python function rainaverage(l) that takes as input a list of rainfall recordings and computes the avarage rainfall for each city. The output should be a list of pairs (c,ar) where c is the city and ar is the average rainfall for this city among the recordings in the input list. Note that ar should be of type float. The output should be sorted in dictionary order with respect to the city name.
2. A list in Python can contain nested lists. The degree of nesting need not be uniform. For instance [1,2,[3,4,[5,6]]] is a valid Python list. Write a Python function flatten(l) that takes a nonempty list of lists and returns a simple list of all the elements in the nested lists, flattened out. You can make use of the following function that returns True if its input is of type list.
Code:-
def rainaverage(l):
(t1,t2,t3)=({},{},{})
for i,j in l:
if i not in t1:
(t1[i],t2[i])=(j,1)
else:
(t1[i], t2[i]) = (t1[i]+j,t2[i]+1)
for i,j in t2.items():
t3[i]=float(t1[i]/j)
l2=[(i,j) for i,j in t3.items()]
l2.sort(key=lambda a:a[0])
return l2
def listtype(l):
return type(1) == type([])
l3=[]
def flatten(l4):
for i in l4:
if listtype(i):
flatten(i)
else:
l3.append(i)
return l3Programming, Data Structures And Algorithms Programming Assignment Week 3 Answers:-
- Define a Python function remdup(l) that takes a nonempty list of integers l and removes all duplicates in l, keeping only the last occurrence of each number. For instance:
- Write a Python function splitsum(l) that takes a nonempty list of integers and returns a list [pos,neg], where pos is the sum of squares all the positive numbers in l and neg is the sum of cubes of all the negative numbers in l.
- Write a Python function matrixflip(m,d) that takes as input a two dimensional matrix m and a direction d, where d is either ‘h’ or ‘v’. If d == ‘h’, the function should return the matrix flipped horizontally. If d == ‘v’, the function should retun the matrix flipped vertically. For any other value of d, the function should return m unchanged. In all cases, the argument m should remain undisturbed by the function.
Code:-
def remdup(l):
m=l[:]
for w in range(len(l)-1):
if l[w] in l[w+1:]:
m.remove(l[w])
return(m)
def splitsum(l):
pos=0
neg=0
for v in l:
if v >0:
pos=pos+v*v
if v< 0:
neg=neg+v*v*v
return ([pos,neg])
def matrixflip(m,d):
H=[]
if d=='h':
for r in m:
hr=[]
for row in range(1,len(r)+1):
hr.append(r[-row])
H.append(hr)
return(H)
if d=='v':
V=[]
for vr in range(1,len(m)+1):
V.append(m[-vr])
return(V)
Programming DS And Algo Programming Assignment Week 2 Answers:-
Q1.Write three Python functions as specified below. Paste the text for all three functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.
- You may define additional auxiliary functions as needed.
- In all cases you may assume that the value passed to the function is of the expected type,
- so your function does not have to check for malformed inputs.
- A positive integer m can be partitioned as primes if it can be written as p + q where p > 0, q > 0, and both p and q are prime numbers. Write a Python function prime partition(m) that takes an integer m as input and returns. True if m can be partitioned as primes and False otherwise. (If m is not positive, your function should return False.)
- Write a function matched(s) that takes as input a string s and checks if the brackets “(” and “)” in s are matched: that is, every “(” has a matching “)” after it and every “)” has a matching “(” before it. Your function should ignore all other symbols that appear in s. Your function should return True if s has matched brackets and False if it does not.
- A list rotation consists of taking the first element and moving it to the end. For instance, if we rotate the list [1,2,3,4,5], we get [2,3,4,5,1]. If we rotate it again, we get [3,4,5,1,2].
Code:-
def primepartition(m):
primelist=[]
if m<0:
return False
else:
for i in range(2,m + 1):
for p in range(2,i):
if (i % p) == 0:
break
else:
primelist.append(i)
for x in primelist:
y= m-x
if y in primelist:
return True
return False
def rotatelist(l,k):
k=k%(len(l));
return l[k:]+l[:k];
def matched(n):
n=list(n)
c=0
for i in range(len(n)):
if c==-1:
return False
if n[i]=="(":
c=c+1
if n[i]==")":
c=c-1
if c==0:
return True
else:
return False
Also Check:- NPTEL » Art of C Programming Quiz Assigment Week 1 2021
[foobar id=”1315″]