Design and analysis of algorithms Assignment Week 7
This course will cover basic concepts in the design and analysis of algorithms.
- Asymptotic complexity, O() notation
- Sorting and search
- Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees
- Design techniques: divide and conquer, greedy, dynamic programming
- Data structures: heaps, union of disjoint sets, search trees
- Intractability
About Instructor– Madhavan Mukund studied at IIT Bombay (BTech) and Aarhus University (Ph.D.). Prof. Madhavan Mukund has been a faculty member at Chennai Mathematical Institute(CMI) since 1992, where he is presently Professor and Dean of Studies. His main research area is formal verification. Madhavan holds active research collaborations within and outside India and serves on international conference program committees and editorial boards of journals.
Madhavan also served as President of both the Indian Association for Research in Computing Science (IARCS) (2011-2017) and the ACM India Council (2016-2019). He has been the National Coordinator of the Indian Computing Olympiad since 2002. He served as the Executive Director of the International Olympiad in Informatics from 2011-2014.
Design and analysis of algorithms 2020 Details:-
Contents
- Who Can Join: Students in BE/BTech Computer Science, 2nd/3rd year.
- Requirements/Prerequisites: Exposure to introductory courses on programming and data structures.
- INDUSTRY SUPPORT: This course should be of value to any company working in the area of software services and products.
Design and analysis of algorithms Assignment Week 7 Answers:-
Week 7 Programming Assignment: IOI Training Camp 20xx
We are well into the 21st century and school children are taught dynamic programming in class 4. The IOI training camp has degenerated into an endless sequence of tests, with negative marking. At the end of the camp, each student is evaluated based on the sum of the best contiguous segment (i.e., no gaps) of marks in the overall sequence of tests.
Students, however, have not changed much over the years and they have asked for some relaxation in the evaluation procedure. As a concession, the camp coordinators have agreed that students are allowed to drop up to a certain number of tests when calculating their best segment.
For instance, suppose that Lavanya is a student at the training camp and there have been ten tests, in which her marks are as follows.
In this case, without being allowed to drop any tests, the best segment is tested 5–7, which yields a total of 15 marks. If Lavanya is allowed to drop up to 2 tests in a segment, the best segment is tested 1–7, which yields a total of 24 marks after dropping tests 2 and 4.
If she is allowed to drop up to 6 tests in a segment, the best total is obtained by taking the entire list and dropping the 5 negative entries to get a total of 33.
You will be given a sequence of N test marks and a number K. You have to compute the sum of the best segment in the sequence when up to K marks may be dropped from the segment.
Solution hint
For 1 ≤ i ≤ N, 1 ≤ j ≤ K, let Best[i][j] denote the maximum segeent ending at position i with at most j marks dropped. Best[i][0] is the classical maximum subsegment or maximum subarray problem. For j ≥ 1; inductively compute Best[i][j] from Best[i][j-1].
Input format
The first line of input contains two integers N and K,
Constraints
You may assume that 1 ≤ N ≤ 104 and 0 ≤ K ≤ 102. The marks for each test lie in the range [-104 … 104]. In 40% of the cases you may assume N ≤ 250.
Answers/Code:-
n,k = map(int,input().split())
l = []
l.append(0)
for i in range(n):
x = int(input())
l.append(x)
best = [[0 for z in range(k+1)] for zz in range(n+1)]
for i in range(1, n+1):
best[i][0] = max(best[i-1][0]+l[i], l[i])
for j in range(1, min(i+1, k+1)):
best[i][j] = max(best[i-1][j]+l[i], best[i-1][j-1])
ans = 0
for i in range(1, n+1):
ans = max(ans, best[i][k])
print(ans)Also Check other Quizes:-
Amazon Fashion Quiz Answers & Win ₹1000
NPTEL » Programming In Java Assignment week 6 Sep-2020
Amazon Great Indian Festival Quiz Answers: Win Rs. 50,000
NPTEL » Programming In Java Assignment week 8 Sep-2020
