JAVA Tutorials by Google Students’ Club (GSC)

164 registrations and an amazing feedback, summarizes it all.

GSC aims at pooling up resources we have here with us and disseminate knowledge across the student community in all possible ways that would lead to overall upliftment in technical culture at DA. So, when we get to know about existing problems in understanding JAVA especially amongst the freshers we designed this two-day event where we tried to start from the basics and cover the very essence of JAVA. We had a proper team structure, eight GSCians, four speakers and four volunteers. We dispersed the volunteers across the crowd to handle the doubts locally throughout the session.

So we began the session addressing the basic questions as to what is OOPS? Why OOPS? How can I conceptualize OOPS? Once done with that, all of us coded a basic class and tried calling any one of the methods from an object created of the class to get a feel of it, all this was done under the presumption that even a beginner who has no prior knowledge of JAVA can start NOW. Even those who had done it previously but just doing it religiously without questioning the basic facts like what’s the significance of  particular keyword in a function signature were made to focus their thoughts on it a little.

Then came the syntactical part of the language where we covered concepts like access modifiers, non-access modifiers, ‘this’ keyword etc. Then we switched back to the OOPS concepts of inheritance and polymorphism. This was day one. The crowd applauded and left happily with students giving a feedback in person and a request on conducting more of such sessions. It was a day full of contentment for GSC.

The second session brought along  most of the faces from the previous day. We had on our cards topics namely constructors, abstract classes, interfaces, operator precedence, exception handling  and array list. The mob was much more motivated to learn concepts this day. People tried out examples, basic examples and got an insight into how JAVA works.

If I ask you to imagine the prevalent scenario in this CEP room while this session in going on and you imagine of one speaker uttering in a monotone being on podium and students looking towards him in a perplexed gaze, you would be completely wrong! The room was not at all static , it was dynamic, queries popping up from all across, students discussing amongst themselves on brilliant questions that come up only when a person puts in adequate amount of thought to the content. There was no formal ending of this session, people went on discussing, we remember clarifying doubts till late, after all. this entropy was all we were aiming at. And then the feedbacks that stirred us all in delight. One of the feedbacks we received online:

I felt the workshop was very good. You started from the very basics, which was the whole point. So kudos…Thanks. Looking forward to the next session.

If you have any suggestion or request for any sort of technical session, you can always drop a mail at gscdaiict@daiict.ac.in or reach out to any of the GSC member in person. Also, for the students around who are eager to learn about JAVA, we have our resources up here, you can always refer to them and mail us your queries , we would be happy to answer!

Also, folks out there who are really interested in Android Programming and would like to network with DAIICT-ians who follow the same interest are most welcome to join the online G+ community Android Class

Lastly, thanks to the Programming Club for letting us reach all of you!

Adieu!

Stay Connected! Stay Updated!

Google Students’ Club

Lazy Propagation in Segment Trees

This is in continuation with my previous blog on segment trees. As we have seen segment trees can be a very powerful DS for solving problems of range min,max,sum etc. But when the updates come very frequently or in large range like almost the entire array, then the update function would end up with O(n) ,so to overcome this problem, we update only when it’s required which is also called Lazy Propagation.

Here the building tree will remain the same, but we will also declare other array that contains info. whether to update the particular node or not. We will update the node only when it is queried or updated once more.

So the new query method is

private int getSum(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
    {
         if(updates[current]>0) //If the current node needs to be updated, first update it
        {
                treeNode[current] += updates[current]*(endIndex - startIndex + 1) ;
                if(startIndex != endIndex) //Also set its children for update
                {
                        updates[getLeftChild(current)] += updates[current] ;
                        updates[getRightChild(current)] += updates[current] ;
                }
                updates[current] = 0 ;
        }
        if (queryStart <= startIndex && queryEnd >= endIndex ) //If it is leaf node
        {
            return treeNode[current];
        }
        if (endIndex < queryStart || startIndex > queryEnd) //out of range
        {
            return 0;
        }
        int mid = (startIndex + (endIndex - startIndex) / 2);
        return  getSum(startIndex, mid, queryStart, queryEnd, getLeftChild(current)) 
                 + getSum( mid + 1, endIndex, queryStart, queryEnd, getRightChild(current)); //return the result
    }
 
    public int query(int queryStart, int queryEnd)
    {
        if(queryStart < 0 || queryEnd > treeNode.length)  //query is out of range
        {
            return -1;
        }
        return getSum(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
    }
 

Here the updates[] I am referring to is the array that contains amount by which that particular node needs to be updated.
Also the now since we are doing lazy propagation,I will call update method on a range of elements to exploit its full use.The new update method is

private void updateTree(int startIndex, int endIndex, int updateStart,int updateEnd, int update, int current)
    {
        if(updates[current]>0) //If current node needs to be updated,update it first
        {
                treeNode[current] += updates[current]*(endIndex - startIndex + 1) ;
                if(startIndex != endIndex)
                {
                        updates[getLeftChild(current)] += updates[current] ; //Also set update for its children
                        updates[getRightChild(current)] += updates[current] ;
                }
                updates[current] = 0 ;
        }
        if ( updateStart < startIndex || updateEnd > endIndex) //out of range
        {
            return;
        }
 
        if(startIndex >= updateStart && endIndex <= updateEnd)// Node in range totally
        {
                treeNode[current] += update*(endIndex-startIndex  + 1) ;  //update the current node
                if(startIndex != endIndex)
                {
                        updates[getLeftChild(current)] += update ;  //set update for its children
                        updates[getRightChild(current)] += update ;
                }
                return ;
        }
        int mid = (startIndex + (endIndex - startIndex) / 2); //If its not totally in range
        updateTree(startIndex, mid, updateStart,updateEnd, update, getLeftChild(current)); //Call recusively on its children
        updateTree(mid+1, endIndex, updateStart,updateEnd, update, getRightChild(current));
        treeNode[current] = treeNode[getLeftChild(current)] + treeNode[getLeftChild(current)] ; //Also update current node accordingly
       
    }
 
    public void update(int update, int updateStart,int updateEnd, int[] elements)
    {
        int updatediff = update - elements[updateStart]  ; 
        for(int i=updateStart;i<updateEnd;i++)
        elements[i] = update; //update the element array
        updateTree(STARTINDEX, ENDINDEX, updateStart,updateEnd, updatediff, ROOT); // call the update method
    }

As you can see through lazy propagation it update a node only when a query/update is called on that node.So it will only update the required node at once keep the rest of the nodes for updating next time.In this way the update order reduces to O(1) which can be very helpful when a large no of updates are fired before having any query.

Feel free to type in any suggestions/corrections in comments

Keep Learning!

Parth Panchal

Segment Trees

As some of you might be knowing, Segment Trees are special type of data structure for query and updating of intervals of array in logarithmic time.Basically segment trees store data of specific intervals of array in tree form. The root contains the whole array, it’s left child contain data of start index to middle index and right child contain data of middle index +1 to end index and so on. So the leaf nodes contain data of specific element of array.

Now the data of element I have been mentioning can be anything like the sum of elements or the max element or the min element etc. I have written the code in java for data containing sum of elements. A segment tree for an array of n elements uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of queried intervals.

The segment tree is stored in a form of heap so left child of node i is 2*i and right child of node i is 2*i+1. To build the segment tree for sum of particular range problem, I have recursively called the method for child nodes. The moment it is the leaf node, it will be the base case of the recursion so the parent will get the value of sum of its childrens values. In this way the whole tree will be created from bottom up.


private int[] treeNode;
private int maxsize;
private int height;

private final int STARTINDEX = 0;
private final int ENDINDEX;
private final int ROOT = 0;

public SegmentTree(int elements[])
{
  height = (int)(Math.ceil(Math.log(elements.length) / Math.log(2))); //height of segment tree is O(log(n))
  maxsize = 2 * (int) Math.pow(2, height) - 1;  //setting maxsize
  treeNode = new int[maxsize];
  ENDINDEX = elements.length - 1; //setting global variable to size of array given
  constructSegmentTree(elements, STARTINDEX, ENDINDEX, ROOT);  // calling method to construct tree from the array
}

private int getLeftChild(int pos){
   return 2 * pos + 1;
}

private int rightchild(int pos){
   return 2 * pos + 2;
}

private int constructSegmentTree(int[] elements, int startIndex, int endIndex, int current)
{
if (startIndex == endIndex) //base case or leaf node
{
   treeNode[current] = elements[startIndex];
   return treeNode[current];
}
int mid = (startIndex + (endIndex - startIndex) / 2);
treeNode[current] = constructSegmentTree(elements, startIndex, mid, getLeftChild(current))
+ constructSegmentTree(elements, mid + 1, endIndex, rightchild(current));
return treeNode[current];  // calling it recusively and setting the current node's value to sum of its children
}

Here’s the method to get result of query.

private int getSum(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
{
if (queryStart &lt;= startIndex &amp;&amp; queryEnd &gt;= endIndex )  // base case
   return treeNode[current];

if (endIndex &lt; queryStart || startIndex &gt; queryEnd)  // current node is out of range
   return 0;

int mid = (startIndex + (endIndex - startIndex) / 2);
return getSum(startIndex, mid, queryStart, queryEnd, getLeftChild(current))
+ getSum( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));  //recursively calling the query method and getting the result
}

public int query(int queryStart, int queryEnd)
{
if(queryStart &lt; 0 || queryEnd &gt; treeNode.length)  // if the query is out of range
  return -1;

return getSum(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
}

Here’s the code for updating the tree

private void updateTree(int startIndex, int endIndex, int updatePos, int update, int current)
{
if ( updatePos &lt; startIndex || updatePos &gt; endIndex) //update pos out of range
   return;
treeNode[current] = treeNode[current] + update;  // if current node comes under the range to update, update it first and then call the method on its children
if (startIndex != endIndex)
{
  int mid = (startIndex + (endIndex - startIndex) / 2);
  updateTree(startIndex, mid, updatePos, update, getLeftChild(current));
  updateTree(mid+1, endIndex, updatePos, update, rightchild(current));
}
}

public void update(int update, int updatePos, int[] elements)  // This method first calculates the diff to be added in each of the required nodes and then calls the method on the root of the tree
{
   int updatediff = update - elements[updatePos] ;
   elements[updatePos] = update;  //the elements of the array are updated first
   updateTree(STARTINDEX, ENDINDEX, updatePos, updatediff, ROOT);  
}

This is the test run

 public static void main(String args[])
	    {
	        int[] elements = {1,2,3,4,5,6,7,8,9};
	        SegmentTree segmentTree = new SegmentTree(elements); //creating the segment tree
	        int sum = segmentTree.query(1, 4);  //querying for sum of elements in range 1-4
	 
	        System.out.println("the sum is " + sum);
	        segmentTree.update(3, 1,elements); // updating the tree
	        sum = segmentTree.query(1, 4); //getting the updated result
	        System.out.println("the sum is " + sum);	
	    }  	

And the output is

the sum is 14
the sum is 15

Segment tree stores cumulative values of all intervals of the array and each interval can be accessed in logarithmic time, segment tree can be very helpful for problems like range min or max or range sum which have large amount of queries.
Also if there is large amount of updates given in the problem the segment tree may not survive, for that lazy propagation comes in handy which I will discuss in my next blog.
Here is the link to 60 problems relating to segment trees,try them to get a hold of the topic
problems on segment trees

By the way,this is my first blog so feel free to write any suggestions in comments.

Keep learning!

Parth Panchal

Fast Input in Java-2

In the previous Blog, we talked about Buffered Reader for Fast I/O.

Some of you are wondering if there is a fast alternative to the BufferedReader. The following class is an alternative to the BufferedReader


static class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

You can use this class as mentioned in Fast Input in Java.

Fast Input in Java

In many questions of contest, we have to read very large Input. The Scanner class is slow and may cause a time limit exceeded. We can read the input faster with the BufferedReader and BufferedInputStream. but the only bad thing is that you have to worry about the input format means BufferedReader can read only one character or one line. So we have to read Line and split that line by delimiter and convert each resulted string to integer or long or double. Instead of using string.split(” “), we can use StringTokenizer which is faster than earlier one.

All this things  become very complex and take very much time. Time is very important especially when you are participating in  short contest. So instead of writing all this things every time we can make Reusable code.


import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class MyScanner {
   BufferedReader br;
   StringTokenizer st;
 
   public MyScanner() {
      br = new BufferedReader(new InputStreamReader(System.in));
   }
 
   String next() {
      while (st == null || !st.hasMoreElements()) {
         try {
            st = new StringTokenizer(br.readLine());
         } catch (IOException e) {
            e.printStackTrace();
         }
      }
      return st.nextToken();
   }
 
   int nextInt() {
      return Integer.parseInt(next());
   }
 
   long nextLong() {
      return Long.parseLong(next());
   }
 
   double nextDouble() {
      return Double.parseDouble(next());
   }
 
   String nextLine(){
      String str = "";
      try {
         str = br.readLine();
      } catch (IOException e) {
         e.printStackTrace();
      }
      return str;
   }

}

How to use it?

Copy MyScanner class in your code. and you can use it by making object of it. It is same as Scanner.

class YourClassName
{
    public static void main(String[] args)
    {
        MyScanner s=new MyScanner();

        int t=s.nextInt(); // read an Interger
        System.out.println(t);

        long l=s.nextLong(); // read a Long
        System.out.println(l);

        String word=s.next(); // read a word
        System.out.println(word);

        String str=s.nextLine(); // read whole line
        System.out.println(str);
    }
}