Iterators - Allowing iteration over data structures (in java)
Posted on September 10, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves.
Here’s where java gives us the power called iterators which allows us to iterate over data structure.
Design Challenge
Consider the stack data structure and we want to support iteration over it on client side.
[Read More]Evaluating postfix expression using stack
Posted on September 10, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
We have seen the conversion of infix to postfix expression here. Now lets see how to evaluate it.
Algorithm
Scan input expression from left to right If scanned input is an operand, push it into the stack If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack. Repeat above two steps till all the characters are scanned.
[Read More]Array Implementation of Heap
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The parent function seems to be a bit in-correct. …
Anonymous - Apr 3, 2014
The parent function seems to be a bit in-correct. It should return i/2 if i is even.
parent(i)
{
if(i is even)
return i/2;
else
return floor(i/2);
}
Thanks mate for the correction. I have corrected it.
Array Implementation of Heap
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
We have discussed a heap as binary tree. Normal implementation of tree is via pointer, but in heap it is much more efficient to use arrays.
So, suppose we have following heap (having 9 elements) :
Now, we need array of 9 elements.
Now, we see the heap having 3 levels, level 0 as root, and level 3 which is partially filled.
Now, we start putting the elements one by one.
[Read More]Cuts of Graphs
Posted on August 22, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A cut of a graph (V, E) is a partition of a graph into two non-empty sets A and B. Each set contains only the vertices that connect one vertex in the set to another in the set. Meanwhile, there are also edges connecting the vertices from set A to set B and vice versa. For eg.
Similarly we have directed graph. Edges, that cross from A, to B are called are crossing edges.
[Read More]Data Type in Data Structure
Posted on August 11, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Before discussing data type in data structure, i am going to describe data, basis of categorization of these data, and advanced categories of data. DATA :- Data can be defined as a value or set of values. These values may represent some observations from an experiment, some figures collected during some surveys, marks obtained by a student in an examination, etc.
DATA ITEM :- A data item refers to a single unit of values.
[Read More]Hash Tables
Posted on August 10, 2013
(Last modified on August 7, 2020)
| 11 minutes
| Kinshuk Chandra
A hash table is primarily used to keep track of an evolving set of stuff by using a key. It is good for inserting, deleting, and lookups. It is also sometimes referred to as a “dictionary.”
They are similar to array in a way, that array gives information at the index very fast, if you know the index. Suppose, your friend names are integer, and you save the number in the array.
[Read More]Closest Pair Algorithm
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Here we will discuss about the closest pair algorithm.
Input : A set p = { p1,p2, … pn} of n points in the plane (R2)
Notation d(pi , pj) = Euclidean distance.
d = x
Assumption - All points have distinct x-coordinates distinct y-coordinates.
Brute force method
Say you are given a set of points in the plane and you want to find the two points closest to one another.
[Read More]Randomized Selection : Selecting the i'th smallest element
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Input - array A with n distinct numbers and a number i ∈ {1,2,…,n}
Output : ith order statistic i.e. ith smallest element of the input array
O(n log n) algorithm
Apply mergesort/quicksort Return the ith element of sorted array So, we used reduction via taking the help of sorting algorithm. So this was the naive way as we would be to say, “Hey let’s sort it and then we can just pick out the ith one!
[Read More]Meaning behind Master Method
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
After establishing what the running time of an algorithm based on three variables a, b, d, we might be wondering what is the meaning behind this method. Where do these logs and exponents come from?
If we look at the amount of work done at a single level of the recursion tree, we get that it is,
where aj is the number of level-j subproblems and the rest is the amount of work per level-j subproblem.
[Read More]