wcalgo4log.txt

<ashwin> : Hello
<vilas_m> : Hi! We ll start when everybody joins. 
<vilas_m> : So i guess we ll start.
<vilas_m> : Today we will cover STL containers and if time permits, get started with a bit of number theory required for competitive coding
<vilas_m> : Can someone point out what is a container, first of all?
<vilas_m> : Ok, so in simple terms, something which can hold data is called a container
<vilas_m> : First we shall deal with vectors
<vilas_m> : Vectors are very similar to arrays, except that they can change their size at any time. 
<vilas_m> : To use them, insert #include<vector> in your code 
<vilas_m> : Or if you're using bits/stdc++.h already, then thats fine too
<vilas_m> : We define a vector like this: vector<vector_type> var_name; 
<vilas_m> : So if we want a vector named 'v' with integer elements, we write vector<int> v; 
<vilas_m> : Inserting an element: to insert an element (say 'x') into the vector, we write v.push_back(x)
<vilas_m> : This writes the element 'x' at the end of the vector
<vilas_m> : How do we know the size of a vector? 
<vilas_m> : We use the function size(). So if we want to know the size of the vector v, we can write int count = v.size()
<vilas_m> : Be careful not to write statements like vector<int> v[10] when you need a vector of size 10. 
<vilas_m> : The above statement actually initialises 10 seperate vectors instead of a single vector of size 10. 
<vilas_m> : To change the size of a vector, we can use the resize() function.
<vilas_m> : So to declare a vector of size 10, we can write 2 statements: vector<int> v; v.resize(10);
<Pratik> : What will be the names of those 10 vectors? All v?
<vilas_m> : Yea. Sort of. The different vectors can be accessed by using the vector index. So for the 1st vector, we write v[0] 
<vilas_m> : Something similar to 2D arrays 
<Pratik> : All right
<vilas_m> : The size of a vector can be changed at any time using the resize function.
<vilas_m> : Note that you do not need to use the resize function at all.
<vilas_m> :  When you use the push_back()/insert() function, the vector automatically increases the size of the vector as and when it is required.
<vilas_m> : Accessing elements in a vector works in the same way as arrays.
<vilas_m> : To access say the 10th element of a vector, we can just write v[9] 
<vilas_m> : Does anyone know what are iterators? 
<Sai_> : Difference between push_back() and insert()?
<vilas_m> : Come on guys :P Guess something atleast
<vilas_m> : @Sai, i will come to insert() function soon
<Sai_> : okk
<vilas_m> : So basically iterators help you in traversing a given container (in this case, a vector)
<Pratik> : Iterators are the variables we use to run through an array or vector?
<vilas_m> : Yes! @Pratik :) 
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :Yeah that
<vilas_m> : We can declare an iterator for any container as follows: 
<vilas_m> : container_type :: iterator i;
<vilas_m> : So for vector, we can write vector<int>::iterator i 
<vilas_m> : There are default iterators in vectors which return the address of the starting element (v.begin()) and end of the vector ( v.end() )
<vilas_m> : Note that v.end() does not give the address of the last element present in the vector.
<vilas_m> : It returns the address past the last element.
<vilas_m> : So if we want the last element in the vector, we can use the address (v.end() - 1)
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :Can we not use: for(int i = v[0]; i < v[n]; i++); What is the advantage of iterators over this?
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :i mean 0 -> n
<vilas_m> : What if the size of the vector is unknown? We need to write an additional statement there. And itertors give the address of a particular element in a vector
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :Oh Okay!
<vilas_m> : So lets say you have a particular address of an element in the vector. Instead of traversing the whole vector to find it's index, we can directly access that element with the iterator 
<vilas_m> : If we want to print all elements in a vector, we can write
<vilas_m> : vector<int> :: iterator i; 
<vilas_m> : for( i = v.begin() ; i! = v.end(); i++) { printf("%d", *i); // or cout<<*i; } 
<ashwin> : so iterator is a pointer
<vilas_m> : @Sai, Can you write a statement that sorts a given vector? (Use the STL function discussed in the last session)
<vilas_m> : Yes, Ashwin
<Sai_> : Yes
<Sai_> : sort(v.begin(), v.end()-1)
<Sai_> : I dont remember the symtax properly 
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :int count = v.size();
<Sai_> : syntax*
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :sort(v, v+count) ?
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :Would that work?
<vilas_m> : great @Sai! A slight correction though. sort(v.begin(), v.end()) without the -1.  
<Sai_> : Oh ok
<vilas_m> : Yes tushaar, you can also write sort(v.begin(), v.begin() + count) 
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :Thanks
<vilas_m> : We also have a function called insert to insert at any given position in a vector
<vilas_m> : Let's say the vector v contains 1, 2, 4 and I want to insert data 3 at position 2 (ie after element 2) 
<vilas_m> : I can just write v.insert(v.begin() + 2, 3);
<vilas_m> : The vector now contains 1, 2, 3, 4
<vilas_m> : any doubts so far?
<Sai_> : No
<Pratik> : NO
<ashwin> : nope
<tushaar_> : 204:5082:572:c9b0:2409:a61b:9620 PRIVMSG #wcalgo4 :None
<vilas_m> : Make sure you do not make the mistake anywhere while using the sort() function. If the array A has N elements from index 0 to N-1, we write sort(A, A+N) and not sort(A, A+N-1)   
<vilas_m> : Next we come to pairs. 
<vilas_m> : Pairs are basically a pair of 2 (not neccessarily of the same type) elements.
<vilas_m> : Say we need to pair 2 elements, one integer and one character. 
<vilas_m> : We can write pair<int, char> p; 
<vilas_m> : To access the 1st element, i.e the integer, we can write p.first and to access the character, we write p.second
<vilas_m> : We can initialise the values in 2 ways: 
<vilas_m> : 1) pair<int, char> p(2, 'A');
<vilas_m> : 2) pair<int, char> p; p.first = 1; p.second = 'A';
<vilas_m> : If you are familiar with C++ classes, then maybe you can note here that the 1st element uses the default constructor.  
<vilas_m> : 1st method*
<vilas_m> : @shamitha, Can you write a statement that declares a vector whose type is a pair of 2 integers?
<shamitha> : vector<pair<int,int>> v;
<vilas_m> : Right! :) 
<vilas_m> : Now we also have a make_pair function to make a pair out of 2 available variables.
<vilas_m> : Say we have int x = 20, y = 30; 
<vilas_m> : We can make a pair out of x and y as follows:
<vilas_m> : pair<int, int> p; p = make_pair(x, y);
<vilas_m> : Next, we come to strings.
<vilas_m> : So instead of using an array of characters, we can the default string containers 
<vilas_m> : To declare a string we write string s; 
<vilas_m> : For length of a string: s.length()
<vilas_m> : To say get a substring from a given string, we use the substr() function. 
<vilas_m> : Say string s = "Webclub";
<vilas_m> : Then we write string s1 = s.substr(0, 3), s2 = s.substr(3, 7);
<vilas_m> : s1 will now contain "Web" and s2 will contain "club"
<vilas_m> : There are lot of functions that perform string manipulations in the header file string.h which you might have learnt last year. So let's skip it for now. 
<vilas_m> : Any doubts so far?
<Sai_> : Nope
<Pratik> : No
<ashwin> : cool
<vilas_m> : Next comes Maps. Maps basically maps data with our desired key values.
<vilas_m> : For example, in arrays, we used A[1] to access the element with index 1. 1 is the key value here
<vilas_m> : What if we dont want the key value to be integers?
<vilas_m> : Say we want to map names to roll no's
<vilas_m> : We will see an example. 
<vilas_m> : map<string, int> m; 
<vilas_m> : m["Tushaar"] = 20;
<vilas_m> : m["Saikiran"] = 23; 
<vilas_m> : So basically we can map any data type to any other data type. 
<vilas_m> : The elements in maps are stored in the sorted order of their key value. 
<vilas_m> : Just like how index 0 is stored before index 1 in arrays, Saikiran's Roll No. will be stored before Tushaar's. (As S<T)
<vilas_m> : Like vectors, the default iterators begin() and end() are applicable here as well.
<vilas_m> : To traverse all elements in a map we can write
<vilas_m> : for(map<string,int> :: iterator it= m.begin(); it!=m.end(); it++)
<vilas_m> :  { cout<<(*it).first << (*it).second; }
<vilas_m> : (*it).first and second corresponds to the key value and data respectively
<vilas_m> : Note that instead of using the dot operator in (*it).first, we can also write it->first i.e the arrow operator for pointers
<vilas_m> : @Pratik, Can you tell a method to store names and marks in several subjects of many students?
<Pratik> : We can use a vector of maps or a vector of pairs
<vilas_m> : Yup! So @Tushaar, can you declare a container that does the job? 
<vilas_m> : Write the statement
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :vector<map<string, int>> v
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :vector<pair<int, int>> v
<vilas_m> : A slightly better method would be declaring a map of string, vector<int>. i.e, map< string, vector<int> >
<vilas_m> : Now we come to sets
<vilas_m> : Like the sets we have in maths, we cannot have duplicate elements in a set.
<vilas_m> : The elements in a set cannot be accessed by a particular index (As they are always stored in a sorted order).
<vilas_m> : We can declare a set by writing set<data_type> s; 
<vilas_m> : And inserting data 'x' into a set: s.insert(x); 
<vilas_m> : Other syntax like begin(), end(), size() etc are similar to the other containers.
<vilas_m> : So let's solve a basic question.
<vilas_m> : Given a list of N elements, count the number of distinct elements in the list. 
<vilas_m> : Can someone come up with an approach? ;) 
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :Insert all elements into a set container and find its size
<Sai_> : We can use Maps
<vilas_m> : Yes! :) 
<vilas_m> : @Sai, Yup! :D Can you explain how? 
<Sai_> : Let say array A has the elements, 
<Sai_> : And m is a map
<Sai_> : We can iterate m[A[i]]=1
<Sai_> : or some constant
<Sai_> : ans calculate size of the map
<Sai_> : and*
<vilas_m> : Yea! :)  
<Sai_> : If it has 3 'ones', It will go to m[1] itself, everytime
<vilas_m> : So the map will map integers to integers.  
<vilas_m> : We are done with STL Containers. 
<vilas_m> : So, whenever you are coding online from now, try to use them to make your life simpler. 
<vilas_m> : We'll also share a few questions to be done as assignment on the group later on.
<vilas_m> : Now, before we conclude, we will see an efficient algorithm to find the GCD of 2 numbers.
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :Cool
<vilas_m> : Can anyone write a basic code to find the GCD of 2 numbers say a and b? 
<vilas_m> : ?
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :if(a == 0) then return b; else return gcd(b%a, a);
<vilas_m> : Haha, Ok so you wrote it using the euclid's algorithm :P I wanted a basic code. Anyway, 
<vilas_m> : So Euclid's algorithm says GCD of 2 numbers A and B, GCD(A,B) = GCD(B%A, A) 
<vilas_m> : We can use this recursively, like in the code written by Tushaar, to find GCD of any 2 numbers A and B in O(log(max(A,B))) time
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :How?
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :O(log(max(a,b))
<vilas_m> : The derivation is pretty tricky :P Even I am not so sure myself on how to put it in proper equations. 
<vilas_m> : But
<vilas_m> : We can think of it like this - Every time, we have B%A to be a number smaller than A (property of mod), it takes approximately log(A) time to reach 0.  
<vilas_m> : I'll look into it and get back to you 
<tushaar__> : 204:5082:572:3852:6045:4cc3:d823 PRIVMSG #wcalgo4 :Sure thanks
<vilas_m> : So with that, we conclude today's session. Next session will cover more aspects with respect to the number theory required for Competitive Coding.