Week 11 Answers | An Introduction To Programming Through C++

Q1. What’s printed by the following code fragment?

set<int> s;
s.insert(100);
s.insert(25);
for(auto e : s) cout << e;

Answer:- 25100

Q2. What is printed by the following code

map < int,int> m;
m[50] = 24;
m[3] = 77;
for (auto e : m) cout << e.first << e.second;

Answer: 3775024

Q3. Suppose during a certain execution, 5 reallocations happened due to push backs on a certain vector. What is the minimum number of elements that the vector must have at the end of the execution?

Answer: 65

Q4. How many copying operations (overhead) must have happened during the execution?

Answer: 124

Q5. Suppose at a certain time during execution a vector has 100 elements (i.e. there have been 100 pushbacks). How many more push backs can there be without causing a reallocation?

Answer: 28

Q6. Answer T if you think the following statement is true and F if false:
The total number of copying operations performed as a part of reallocation is less than twice the number of elements in the vector (i.e. the number of elements pushed back).

Answer: T

Q7. Answer T if you think the following statement is true and F if false:
The amount of memory allocated to a vector that is not in use to store elements is less than the amount of memory that is being used to store elements, i.e. the memory in use is more than the memory not in use.

Answer: F

Consider the following code fragment.

map < string, set < string>> friends;
friends[“Dharmendra”].insert(“Amitabh”);
friends[“Dharmendra”].insert(“Vinod”);
cout << friends[“Dharmendra”].count(“Amitabh”) << endl;
cout << friends[“Dharmendra”].size() << endl;

Q8. What number is printed first?

Answer: 1

Q9. What number is printed second?

See also  An Introduction to Programming Through C++ Week 7 Answers

Answer: 2

Q10. I have information about which cities are in which countries. Using this information I want to write a program that answer questions of the form: (a) Is a city X in country Y. (b) Which cities are in country Y. What data structure is most convenient for representing the required information?

  • A map mapping each country to a vector containing cities in that country. 
  • A map mapping each country to a set containing cities in that country. 
  • A map mapping each city to the country in which it is present.

Answer: (B) A map mapping each country to a set containing cities in that country. 

Programming Assignment Answers:-

Q1. In processing documents, we often build something called an index, or an inverted index. This is simply a set of pairs (word, occurrences)where word is a word occurring in the document, and occurrences is a sequence of integers giving the positions (in increasing order) at which theword occurs. You are to write a program which takes a document as input and prints the index for it, with the words in ascending order (lexicographically).

Code:-

  int main()
 {
 string s;
 int i =0;
 bool end=false;
 map < string,vector < int>> word;
 while(!end)
 {
 cin>>s;
 if(s[s.size()-1]=='.')
 {
 s.resize(s.size() - 1);
 end=true;
 }

 word[s].push_back(i++);
 }
 for (auto it:word)
 {
 cout << it.first;
 for(auto index:it.second)
 cout << ' ' << index;
 cout << endl;
 }
 return 0;
 }

Q2. In the lectures we discussed a way to store a fare table: a fare table gives the fare between two cities, and is stored in the following data structure:

Code:-

map < string, map < string,double>> faretable;
int findfare(string c1,string c2)
{
  map < string, map < string,double> >::iterator itr;
  map < string,double>::iterator ptr;
  for(itr=faretable.begin(); itr!=faretable.end(); itr++)
  {
    for(ptr=itr->second.begin(); ptr!=itr->second.end();ptr++)
    {
      if((itr->first==c1 && ptr->first==c2)||(itr->first==c2 && ptr->first==c1))
      {
        return ptr->second;
      }
    }
  }
  return 0;
}
int main()
{
  string c1,c2,c,s;
  double f;
  bool end=false;
  int flag;

  map < string, map < string,double> >::iterator itr,itr1;
  map < string,double>::iterator ptr,ptr1;
  while(!end)
  {
    cin>>s;
    if(s=="Insert")
    {
      cin>>c1>>c2>>f;
      faretable[c1][c2]=f;
    }
    else if(s=="Fare")
    {
      cin>>c1>>c2;
      flag=findfare(c1,c2);
      if(flag==0)
        cout << "unknown" << endl;
      else
        cout << flag << endl;
    }
    else if(s=="Onechange")
    {
      cin>>c1>>c2;
      flag=findfare(c1,c2);
      if(flag!=0)
        cout << flag << endl;
        else
        {
          for(itr=faretable.begin();itr!=faretable.end(); itr++)
          {
            for(ptr=itr->second.begin(); ptr!=itr->second.end(); ptr++)
            {
              if(c1==itr->first)
              {
                c=ptr->first;
                flag=findfare(c,c2);
                if(flag==0)
                  continue;
                else
                  goto L;
              }
            }
          }
        }
        L:if(flag==0)
            cout << "impossible"<<endl;
          else
            cout << (flag+ptr->second) << endl;
    }
    else
      end=true;
  }
  return 0;
}

Similar: