Design and analysis of algorithms Assignment Week 6
Contents
Design and analysis of algorithms Assignment Week 6
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. 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.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-2018). 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:-
- 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 6 Answers:-
Week 6 Programming Assignment: Siruseri Sports Stadium
The bustling town of Siruseri has just one sports stadium. There are a number of schools, colleges, sports associations, etc. that use this stadium as the venue for their sports events.
Anyone interested in using the stadium has to apply to the Manager of the stadium indicating both the starting date (a positive integer S) and the length of the sporting event in days (a positive integer D) they plan to organize. Since these requests could overlap it may not be possible to satisfy everyone.
It is the job of the Manager to decide who gets to use the stadium and who does not.
The Manager would like to keep as many organizations happy as possible and hence would like to allocate the stadium. By that maximum number of events are held.
He would allot the stadium to events 1, 4, and 3. Event 1 begins on day 2 and ends on day 6, event 4 begins on day 9 and ends on day 11 and event 3 begins on day 15 and ends on day 20. You can verify that it is not possible to schedule all the 4 events (since events 2 and 3 overlap and only one of them can get to use the stadium).
Your task is to help the manager find the best possible allotment (i.e., the maximum number of events that can use the stadium).
Answers/Code:-
#include<bits/stdc++.h>
using namespace std;
int main(){
long n;
cin>>n;
vector<pair<int,int>> v(n);
for (int i=0;i<n;i++){
cin>>v[i].second>>v[i].first;
v[i].first += v[i].second;
}
sort(v.begin(),v.end());
int cnt = 1;
auto comp = v[0];
for (int i=1;i<n;i++){
if(v[i].second >= comp.first + 1){
comp = v[i];
cnt++;
}
}
cout<<cnt<<"\n";
return 0;
}Also Check other Quizes:-
NPTEL Programming In Java Assignment week 9 Sep-2020
Amazon Fashion Quiz Answers & Win ₹1000
NPTEL » Programming In Java Assignment week 8 Sep-2020
Amazon Great Indian Festival Quiz Answers: Win Rs. 50,000
Win Flipkart Plus Membership – 3 Months
