Design and analysis of Algorithms 2021 – An algorithm is the best way to represent the solution of a particular problem in a very simple and efficient way. If we have an algorithm for a specific problem, then we can implement it in any programming language, meaning that the algorithm is independent of any programming language.
Design and analysis of Algorithms is a MOOC based course that is 12 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 (PhD). 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 programme committees and editorial boards of journals.
Who Can Join: Any discipline Students in BE/BTech Computer Science, 2nd/3rd year. 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.
CRITERIA TO GET A CERTIFICATE
Average assignment score = 25% of the average of the best 6 assignments out of the total 8 assignments given in the course.
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.
Design And Analysis Programming Assignment Thirsty Tourists Week 7 Answers:-
Contents
Thirsty Tourists
A large group of tourists set out on a long journey that will take them back and forth across the country. They planned the trip for June to beat the summer heat but the delay in the onset of the monsoon has meant that their journey is extremely hot and uncomfortable. Moreover, the price of mineral water has skyrocketed because of the acute shortage of water.
Totally, the tourists consume a litre of water every hour. Between them, they have enough muscle power to carry C litres of water. Thanks to the miracle of mobile telephones, they have found out the price of water at various shops along the route they are going to travel. Being both thrifty and thirsty, they would like to minimize the amount they spend on water by scheduling their water purchases optimally. They have to ensure that they never run out of water between shops. It is permissible, however, to arrive at a shop with no stored water. They begin their journey without any water. There is a shop at the starting point where they can buy water.
You are given the number of hours that they have to travel totally. You are also provided with the locations, in terms of hours of travel, of the different shops that sell water along their route, as well as the price of a litre of water at each of these shops, in paise. Your task is to find the minimum amount that they need to spend on water to arrive at their destination without dying of dehydration. You are guaranteed that the input values always admit at least one feasible solution.
Code:- In C++
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define inf 1e18
int dp[5001][10001];
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int h, n, c;
cin >> h >> n >> c;
vector<int> dist(n), cost(n);
for(int i = 0; i < n; ++i) {
cin >> dist[i] >> cost[i];
}
// dp[i][j] = define as the cost if they are at
// the ith shop with rem j litre of water.
// Transition
// So at the ith shop The extra j can be from :
// Case 1 : from any of the shop {0, 1, 2, ... i - 1}
// Case 2 : If not possible to carry j from any of the {0, 1 ... n - 1} then fill j in the current shop
// Case 3 : Or What if instead like case 2 where we are filling
// full j litre on the cost of ith shop only
// we try to make some litre carried from previous + current
// kind of eqn. cost = some_prev_shop * (c - rem) + cur_shop * rem
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= c; ++j) {
dp[i][j] = inf;
}
}
for(int j = 0; j <= c; ++j) {
dp[0][j] = j * cost[0];
}
for(int i = 1; i < n; ++i) {
for(int j = 0; j <= c; ++j) {
if(j + dist[i] - dist[i - 1] <= c) {
dp[i][j] = min(dp[i - 1][j + (dist[i] - dist[i - 1])], dp[i - 1][dist[i] - dist[i - 1]] + j * cost[i]); // Case 1 & case 2
}
else {
dp[i][j] = min(dp[i][j], dp[i - 1][dist[i] - dist[i - 1]] + j * cost[i]); // Case 2
}
if(j > 0) {
dp[i][j] = min(dp[i][j], dp[i][j - 1] + cost[i]); // Case 3
}
}
}
cout << dp[n - 1][h - dist[n - 1]] << '\n';
}Design And Analysis Programming Assignment Week 6 Answers:-
Week 6 Programming Assignment: Milk Delivery
Milk Delivery
A private dairy has n milk delivery vans. The company has mapped out n delivery routes. Each route has to be served once in the morning and once in the evening. Each van covers one morning route and one evening route, but these may be different routes. The route has fixed delivery volumes in the morning and evening, possibly different.
The dairy’s license limits the number of packets a van can deliver to p packets per day. If a van delivers more than p packets, the company has to pay a fine of f per additional packet.
Given the delivery volumes of the morning and evening routes, your task is to find the minimum fine the company has to pay if it optimally allocates morning and evening routes to each delivery van.
For instance, suppose there are 3 routes, the packet limit per day is 24, the fine per additional packet is 4, the morning volumes for the three routes are [10,17,12] and the evening volumes for the three routes are [11,9,24]. Then, the minimum fine to be paid is 48. This can be achieved by pairing the routes as follows: (10,24), (17,9), (12,11).
JOIN US ON TELEGRAM FOR UPCOMING WEEK ASSIGNMENT SOLUTIONS
Solution hint
Minimize the average morning plus evening volume by pairing up small volumes with large volumes.
Code:- code is in c++
//THANKS TO AAFAQUE
#include<iostream>
using namespace std;
int main()
{
int n, p, f, *m, *e, i, j, s = 0;
cin >> n >> p >> f;
m = (int *)malloc(n*sizeof(int));
e = (int *)malloc(n*sizeof(int));
for(i = 0;i < n;i++)
cin >> m[i];
for(i = 0;i < n;i++)
cin >> e[i];
for(i = 0;i < n - 1;i++)
{
for(j = 0;j < n - i - 1;j++)
{
if(m[j] > m[j + 1])
{
int t = m[j];
m[j] = m[j + 1];
m[j + 1] = t;
}
}
}
for(i = 0;i < n - 1;i++)
{
for(j = 0;j < n - i - 1;j++)
{
if(e[j] < e[j + 1])
{
int t = e[j];
e[j] = e[j + 1];
e[j + 1] = t;
}
}
}
for(i = 0;i < n;i++)
{
if(m[i] + e[i] > p)
s = s + (m[i] + e[i] - p)*f;
}
cout << s << endl;
}
Design And Analysis Assignment Week 4 Answers:-
Week 4 Programming Assignment: Number Triples
Number Triples
(IARCS OPC Archive, K Narayan Kumar, CMI)
In this problem you will be given a sequence of triples of positive integers. For example:
1 2 5 5 2 6 1 3 8 8 1 11 1 1 6 10 1 6 11 3 6 10 4 8 10 1 11 Given a pair of numbers A and B, a chain connecting A and B is a sequence of triples A0 W0 A1, A1 W1 A2, A2 W2 A3, ... Ak-2 Wk-2 Ak-1, Ak-1 Wk-1 Ak such that A0 = A Ak = B For each i, 0 ≤ i < k, either the triple Ai Wi Ai+1 or the triple Ai+1 Wi Ai is in the given set of triples. The value of such a chain is the sum of the Wis in the chain. For example, here is a chain connecting 1 and 11 using the triples listed above:
Code:- Code in C programming language
#include <stdio.h>
int main() {
int M, A, B, i, j, v1, v2, len_graph, curr_vertex;
long int weight_sum = 0, weight, min_dist;
scanf ("%d %d %d", &M, &A, &B);
int visited[1001];
long int adj_matrix[1001][1001] = {0};
int max = -1;
for (i = 0; i < M; i++) {
scanf ("%d %ld %d", &v1, &weight, &v2);
adj_matrix[v1 - 1][v2 - 1] = weight;
adj_matrix[v2 - 1][v1 - 1] = weight;
weight_sum += weight;
visited[v1 - 1] = visited[v2 - 1] = 0;
if (max < v1) max = v1;
if (max < v2) max = v2;
}
len_graph = max;
long int distance[1001];
for (i = 0; i < len_graph; i ++) {
distance[i] = weight_sum + 1;
}
distance[A - 1] = 0;
for (i = 0; i < len_graph; i++) {
min_dist = weight_sum;
for (j = 0; j < len_graph; j++) {
if (visited[j] == 0 && distance[j] < min_dist) {
min_dist = distance[j];
curr_vertex = j;
}
}
visited[curr_vertex] = 1;
for (j = 0; j < len_graph; j ++) {
if (j == curr_vertex) {continue;}
if (adj_matrix[curr_vertex][j] != 0 && distance[j] > distance[curr_vertex] + adj_matrix[curr_vertex][j]) {
distance[j] = distance[curr_vertex] + adj_matrix[curr_vertex][j];
}
}
}
for (i = 0; i < len_graph; i ++) {
}
if (visited[B - 1] == 1) {
printf("YES\n");
printf("%ld\n", distance[B - 1]);
}
else {
printf("NO\n");
}
return 0;
}Design And Analysis Assignment Week 3 Answers:-
Week 3 Programming Assignment: Prisoner Escape
Prisoner Escape
(Baltic Olympiad in Informatics, 2009)
A group of war prisoners are trying to escape from prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as B, see picture below) and the prison (marked as A) are separated by a canyon which is also guarded by soldiers. These soldiers sit in their pickets and rarely walk; the range of view of each soldier is limited to exactly 100 meters. Thus, depending on the locations of soldiers, it may be possible to pass the canyon safely, keeping the distance to the closest soldier strictly larger than 100 meters at any moment.
You are to write a program which, given the width and the length of the canyon and the coordinates of every soldier in the canyon, and assuming that soldiers do not change their locations, determines whether prisoners can pass the canyon unnoticed.
Solution Hint
Add an edge between two vertices if and only if the range of view of the corresponding soldiers overlaps. Add two additional vertices s and t, representing the northern and southern side of the canyon, respectively. Connect s and t to those vertices representing soldiers who range of view includes the respective side of the canyon. Use depth-first-search or breadth-first-search to check whether there is a path between s and t in G.
Code:- Code in C++
#include <iostream>
#include <set>
#include <deque>
#include <list>
#include <utility>
using namespace std;
#define sq(x) ((x)*(x))
struct pt:pair<int,int>
{
int i;
pt(int x=0,int y=0):pair<int,int>(x,y),i(-1) { }
};
int main()
{
int L,W,n,r=100,d=2*r;
cin>>L>>W>>n;
set<pt> points;
typedef set<pt>::iterator iter;
pt P;
list<int> G[n+2];
//Prepare Graph with intelligence {using lgn based set}
for(int i=1; i<=n; i++)
{
cin>>P.first>>P.second;
P.i=i;
pt Q(P.first-d,P.second-d),R(P.first+d,P.second+d);
iter l=points.lower_bound(Q),u=points.upper_bound(R);
for(iter j=l; j!=u; ++j) // only those circles which can overl
if(sq(P.first-j->first)+sq(P.second-j->second) <= sq(d))
G[i].push_back(j->i), G[j->i].push_back(i);
if(P.second - r <= 0) // if P is touching y=0
G[i].push_back(0), G[0].push_back(i);
if(P.second + r >= W) // if P is touching y=W
G[i].push_back(n+1), G[n+1].push_back(i);
points.insert(P);
}
//Do DFS/BFS to track
int visited[n+2];
for(int i=0;i<n+2;i++)
visited[i]=0;
deque<int> q;
q.push_back(0); // the y=0 line
while(!q.empty())
{
int v=q.front();
q.pop_front();
if(visited[v])
continue;
visited[v]=1;
if(v==n+1) //the y=L line
{
cout<<1<<"\n"; //there is an path from y=0 to y=L
return 0;
}
for(list<int>::iterator i=G[v].begin(); i != G[v].end(); ++i)
q.push_back(*i);
}
cout<<0<<"\n";
return 0;
}
Design And Analysis Assignment Week 2 Answers:-
Q1. The Siruseri Singing Championship
The Siruseri Singing Championship is going to start, and Lavanya wants to figure out the outcome before the tournament even begins! Looking at past tournaments, she realizes that the judges care only about the pitches that the singers can sing in, and so she devises a method through which she can accurately predict the outcome of a match between any two singers.
She represents various pitches as integers and has assigned a lower limit and an upper limit for each singer, which corresponds to their vocal range. For any singer, the lower limit will always be less than the upper limit. If a singer has lower limit L and upper limit U (L < U), it means that this particular singer can sing in all the pitches between L and U, that is they can sing in the pitches {L, L+1, L+2, …, U}.
The lower bounds and upper bounds of all the singers are distinct. When two singers Si and Sj with bounds (Li, Ui) and (Lj, Uj) compete against each other, Si wins if they can sing in every pitch that Sj can sing in, and some more pitches.
Similarly, Sj wins if they can sing in every pitch that Si can sing in, and some more pitches. In this problem, you can assume that no match ends in a draw.
N singers are competing in the tournament. Each singer competes in N-1 matches, one match against each of the other singers. The winner of a match scores 2 points, and the loser gets no points. But in case of a draw, both the singers get 1 point each.
NOTE CODE IS IN C LANGUAGE:-
#include<stdio.h>
int main()
{ int N;
scanf("%d",&N);
int L[N],U[N],i,A[N],j;
int R[N];
for(i=0;i<N;i++)
{
scanf("%d%d",&L[i],&U[i]);
A[i]=U[i]-L[i];
}
for(i=0;i<N;i++)
{ R[i]=0;
for(j=0;j<N;j++)
{
if(A[i]>A[j])
{
R[i]=R[i]+2;
}
else
{
R[i]=R[i]+0;
}
}
}
for(i=0;i<N;i++)
{
printf("%d ",R[i]);
}
}Also check DAA quiz Assignment:- NPTEL » Design and analysis of Algorithms Assignment 2021
