now coming to a bit more useful topics in linked lists. often, we require that our lists be sorted at all times. even the items we insert into the linked lists be places at the correct place. so let's look at the insert function.
struct node
{
int data;
node* next;
};
now the possibilities are:
1. list is currently empty
2. the item (head->data) at first place is bigger than item to be inserted
3. the new item needs to placed "somewhere" in between
4. the new item needs to placed at the end.
now look at the following code:
node *temp;
temp->data=item;
temp->next=head;
head=temp;
if the head is NULL OR head->data is more than item, the above code works. otherwise, we go to the node (current), BEFORE which, the new node should be inserted. we also heep a track of the node before that (last) so that we can insert the new node (temp) between last and current.
node *current=head,*last;
while(current!=NULL && current->data< item)
{
last=current;
current=current->next;
}
node *temp;
temp->data=item;
last->next=temp;
temp->next=current;
---------------------------------
deletion function - similar to the insertion function, cases are:
1. either list is empty (do nothing)
2. item to delete is at head (just shift head to the next node)
3. item to delete is in the middle or at the end. (link the item before the concerned item to the item next to the concerned item\)
if(head->data==item)
head=head->next;
else
{
node *current=head,*last;
while(current!=NULL && current->data!=item)
{
last=current;
current=current->next;
}
if(current!=NULL)
last->next=current->next;
//if we reach the end of list, the item is not found
}
Tuesday, February 3, 2009
Monday, February 2, 2009
alu matar (gunjan's fav) recipe
hey,
here's the alu matar recipe (potatoes with green peas).
ingredients:
potatoes - 3, diced
peas - 300-400 grams (really depends on how much you like them)
onion - 2 medium - chopped fine
tomatoes - 2, big, ripe, diced
bay leaves - 3
chilli powder - 1 teaspoon
turmeric power - 1/2 teaspoon
coriander powder - 2 heaped teaspoon
garam masala powder - 1/2 teaspoon
mustard seeds - 1/2 teaspoon
cumin seeds - 1/2 teaspoon
ginger paste 1 heaped teaspoon
garlic paste 1 heaped teaspoon
oil - 50ml
salt to taste
heat oil and when it's hot enough, add the mustard, cumin seeds and bay leaves. after 10 seconds or so (or before the cumin and mustard seeds start burning), add the onion and cook for 5 mins on high heat, stirring occasionally. add the ginger garlic paste and cook for 3 more minutes stirring occasionally.
put the four powders in a bowl, add 100 ml of water and mix thoroughly, add this to the onions cooking at high heat. keep stirring so that it doesn't stick to the base (if it sticks, add some water slowly). after about 30 seconds, add the diced potato, stir and cook for 2 mins. add the diced tomatoes and cook for another minute. add a litre of water and turn up the heat. when the boil comes, add salt, reduce heat to 4 o'clock position and cook for 20 minutes. add peas, cook for 3 more minutes. garnish with coriander leaves and ta-da!
here's the alu matar recipe (potatoes with green peas).
ingredients:
potatoes - 3, diced
peas - 300-400 grams (really depends on how much you like them)
onion - 2 medium - chopped fine
tomatoes - 2, big, ripe, diced
bay leaves - 3
chilli powder - 1 teaspoon
turmeric power - 1/2 teaspoon
coriander powder - 2 heaped teaspoon
garam masala powder - 1/2 teaspoon
mustard seeds - 1/2 teaspoon
cumin seeds - 1/2 teaspoon
ginger paste 1 heaped teaspoon
garlic paste 1 heaped teaspoon
oil - 50ml
salt to taste
heat oil and when it's hot enough, add the mustard, cumin seeds and bay leaves. after 10 seconds or so (or before the cumin and mustard seeds start burning), add the onion and cook for 5 mins on high heat, stirring occasionally. add the ginger garlic paste and cook for 3 more minutes stirring occasionally.
put the four powders in a bowl, add 100 ml of water and mix thoroughly, add this to the onions cooking at high heat. keep stirring so that it doesn't stick to the base (if it sticks, add some water slowly). after about 30 seconds, add the diced potato, stir and cook for 2 mins. add the diced tomatoes and cook for another minute. add a litre of water and turn up the heat. when the boil comes, add salt, reduce heat to 4 o'clock position and cook for 20 minutes. add peas, cook for 3 more minutes. garnish with coriander leaves and ta-da!
tutorial 1 for pointers
hey C++ nerds and geeks!
we will be tackling pointers, the most evil of the eviloparisuis brothers, the curse of the black dragon, the swallower of black holes.
int x=5;
what does the above innocent, sweet and simple statement mean?!?
that x is an integer, which tells the computer to reserve 4 bytes and the starting address of those 4 bytes (i.e. the first byte is referred by &x). when we output x, we are actually outputting value at address &x. we will come back to this later. but, right now, let's get started with pointers.
int *p
you read this statement as "integer pointer p" or simply "p points to an integer"
this statement means that "p contains starting address of some integer"
we can output value of "that" integer that p points to with "*p" (read as pointer p)
now why is it important for a pointer to be associated with a data type such as integer?
because when we output *p, 4 bytes from starting address (p) are fetched, encoded as an integer and displayed. hence we cannot copy an integer pointer to a double pointer and so on.
pass 1:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
p=&x; //means that p contains address of x, which means p=0x112233
cout<<*p< 5
*p=20; //modify value at address 0x112233 to 20
cout<< x<outputs 20
------------------------------------
pass 2:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
*p=x; //modify value at "that" address to 5
cout<<*p<< endl; address =""> 5
*p=20; //modify value at "that" address to 20
cout<< x<< endl; //still outputs 5
------------------------------------
the above two versions had just one statement different
p=&x versus *p=x
p=&x means that p stores address of x, and therefore x changes if *p is modified and *p changes if x is modified. This is called "tight coupling"
*p=x refers to a one time copy. value at address stored in p takes the value of x but p DOES NOT point to x actually. Thus *p DOES NOT change if x changes and vice versa. This is called "loose coupling"
-----------------------------------
int x=10,y=20;
int *p,*q;
p=&x;
q=&y;
q=p;
x++;
cout<< *q<< " ";
*p=y;
cout<< *q<< endl;
what's the output of the above code?
a) 10 20
b) 11 11
c) 20 20
d) 11 20
e) 10 11
you got it right if you answered 'd'. you see, q=p means q now contains whatever address p contains, which is the address of x. hence both p.q point to x. when x increases to 11 (using x++)
*p and *q output 11. then *p=y means *p which is value at address inside p (which is the address of x) becomes y. Thus x becomes y (20). Thus *q (q still points to x) outputs 20.
we will be tackling pointers, the most evil of the eviloparisuis brothers, the curse of the black dragon, the swallower of black holes.
int x=5;
what does the above innocent, sweet and simple statement mean?!?
that x is an integer, which tells the computer to reserve 4 bytes and the starting address of those 4 bytes (i.e. the first byte is referred by &x). when we output x, we are actually outputting value at address &x. we will come back to this later. but, right now, let's get started with pointers.
int *p
you read this statement as "integer pointer p" or simply "p points to an integer"
this statement means that "p contains starting address of some integer"
we can output value of "that" integer that p points to with "*p" (read as pointer p)
now why is it important for a pointer to be associated with a data type such as integer?
because when we output *p, 4 bytes from starting address (p) are fetched, encoded as an integer and displayed. hence we cannot copy an integer pointer to a double pointer and so on.
pass 1:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
p=&x; //means that p contains address of x, which means p=0x112233
cout<<*p<
*p=20; //modify value at address 0x112233 to 20
cout<< x<
------------------------------------
pass 2:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
*p=x; //modify value at "that" address to 5
cout<<*p<< endl; address =""> 5
*p=20; //modify value at "that" address to 20
cout<< x<< endl; //still outputs 5
------------------------------------
the above two versions had just one statement different
p=&x versus *p=x
p=&x means that p stores address of x, and therefore x changes if *p is modified and *p changes if x is modified. This is called "tight coupling"
*p=x refers to a one time copy. value at address stored in p takes the value of x but p DOES NOT point to x actually. Thus *p DOES NOT change if x changes and vice versa. This is called "loose coupling"
-----------------------------------
int x=10,y=20;
int *p,*q;
p=&x;
q=&y;
q=p;
x++;
cout<< *q<< " ";
*p=y;
cout<< *q<< endl;
what's the output of the above code?
a) 10 20
b) 11 11
c) 20 20
d) 11 20
e) 10 11
you got it right if you answered 'd'. you see, q=p means q now contains whatever address p contains, which is the address of x. hence both p.q point to x. when x increases to 11 (using x++)
*p and *q output 11. then *p=y means *p which is value at address inside p (which is the address of x) becomes y. Thus x becomes y (20). Thus *q (q still points to x) outputs 20.
tutorial on linked list
a lot of students studying advanced C++ have some trouble understanding the concept of linked list. this is either due to lack of imagination, or lack of understanding of fundamental operations. but essentially, the problem arises due to students studying basic C++ tend to memorize topics rather than trying to build a deep understanding of the same.
you wouldn't think of memorizing addition, would you? addition is a primitive operation that everyone understands to the bone. a+b refers to the outcome of someone giving you 'b' dollars when you already have 'a' dollars in your purse, or vice versa (i think that concepts are much clearer when money is involved :D). the "vice versa" becomes really important since a+b=b+a which is the commutative property. similarily, it doesn't matter in which order you get the money (a+b)+c = a+(b+c). this is the associative property.
You can view this as ID of students standing in a queue. The person at the front of the queue has ID 8, the next one 3 and so on. It is useful to divide each item (from now on referred to as "node") as containing two parts:
Thus we come to our first C++ definition, that of a node. A node is an abstract data type containing value and address of next node. From the discussion on pointers, what contains address of a node -- pointer to a node :) So,
please be clear that the node DOES NOT contain another node, it simply contains address of another node.
Sorry, the above image is a bit too small, but if you click on it, it will open in a new window/tab and is viewable.
I can also move the "head" around so that the first item changes. This happens when the first person in the queue (head) is served and now is no longer a part of the queue. Look at the following statement:
head=head->next;
the right hand side of this statement (head->next) contains address of temp (87)
so it simplifies to head=87
thus head now contains address 87 rather than the old address 84.
thus head now points to the second node.
thus the second node now becomes the first node :)
what happens to the old first node?!?!?! it is still in the memory. so it you want to remove it from memory, you use:
node* old=head //old points to same location as head (84)
head=head->next;
delete old //delete node contained at address inside old (84)
------------------------------------
Now let us look at some more useful operations on lists.
Operation 1: To check if list is empty or not?
The list is empty if head contains no address. That is, head is NULL. Which also tells us that when we create a list, we should assign NULL to head. Hence, the correct way to initialize a list is:
node* head=NULL;
bool isEmpty(node* head)
{
if(head==NULL)
return true;
else
return false;
}
---------------------------------------
Assuming that the list is containing a set of items where order isn't important. We pass the node pointer by reference (that is the actual head is modified rather than a duplicate copy of head being passed to the function).
We first create a node by reserving memory space.
We contain address of old head in node temp.
We move head so that head now contains address of temp.
void insert(node* &head, int item)
{
node* temp=new node;
temp->data=item;
temp->next=head;
head=temp;
}
Even if head was NULL (inserting item into an empty list), the statement temp->next=head means that temp->next contains NULL which is also correct :)
-----------------------------------
Operation 3: Deleting item from front of list:
void delete(node* &head)
{
if(head!=NULL)
{
node* temp=head;
head=head->next;
delete temp;
}
//if head is already NULL, it means nothing remaining to delete
}
-------------------------------
Operation 4: Traverse through the list (go through the list for some xyz purpose)
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
while(head)
{
cout<data<<" ";
head=head->next; //please remember the actual head is not modified since a duplicate
//pointer in memory is there, that contains same address as head
}
}
For those of you, who still are freaked out by me modifying "head" in the function, use the following function varient:
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
node* current=head;
while(current)
{
cout<data<<" ";
current=current->next;
}
}
------------------
Tutorial part 2 coming soon to a cinema near you!
cheers
gaurav
you wouldn't think of memorizing addition, would you? addition is a primitive operation that everyone understands to the bone. a+b refers to the outcome of someone giving you 'b' dollars when you already have 'a' dollars in your purse, or vice versa (i think that concepts are much clearer when money is involved :D). the "vice versa" becomes really important since a+b=b+a which is the commutative property. similarily, it doesn't matter in which order you get the money (a+b)+c = a+(b+c). this is the associative property.
anyways, so much so for kindergarten math. coming to linked lists now. before understanding linked lists, it is necessary to understand pointers. so please refer to my post on pointers if you think that pointers are nasty things planted on earth by the evil cybermen from outer universe. (i'm watching too much dr. who nowadays!)
(once you are happy with pointers, proceed)
a linked list is a linked collection of items of the same type such that first value knows where is the second value stored, the second value knows about the third value and so on. for example, a list of students can be encoded as a linked list (LL). If I want to display the list of students, I need to start from somewhere. Thus, the location of the first student, (to whom no one points - so sad) is important and should be stored somewhere. If the location of the first student is lost, then that of the second student is also lost (since the first student has that info) and so on.
A simple list looks like the following figure. It simply contains a set of integers, not stored in sorted order.
You can view this as ID of students standing in a queue. The person at the front of the queue has ID 8, the next one 3 and so on. It is useful to divide each item (from now on referred to as "node") as containing two parts: 1. data
2. link to next node
Thus we come to our first C++ definition, that of a node. A node is an abstract data type containing value and address of next node. From the discussion on pointers, what contains address of a node -- pointer to a node :) So,struct node
{
int data; //this can be int, double, even another structure object
node* next;
};
node* next;
};
please be clear that the node DOES NOT contain another node, it simply contains address of another node.Since it's important to have address of the first node somewhere, we call it "head", or "first", or "top" or "front" depending on the situation. I call it head over here. This is implemented as:
node* head;
head = new node;//allocate memory for a node and store it's location in head
head->data=8 //data part of node to which head points becomes 8
head->next=NULL //right now, head does not contain any address, thus it's the only node
If you want to add another node
node* temp=new node;
temp->data=3;
temp->next=NULL;
head->next=temp;
Sorry, the above image is a bit too small, but if you click on it, it will open in a new window/tab and is viewable.
I can also move the "head" around so that the first item changes. This happens when the first person in the queue (head) is served and now is no longer a part of the queue. Look at the following statement:
head=head->next;
the right hand side of this statement (head->next) contains address of temp (87)
so it simplifies to head=87
thus head now contains address 87 rather than the old address 84.
thus head now points to the second node.
thus the second node now becomes the first node :)
what happens to the old first node?!?!?! it is still in the memory. so it you want to remove it from memory, you use:node* old=head //old points to same location as head (84)
head=head->next;
delete old //delete node contained at address inside old (84)
------------------------------------
Now let us look at some more useful operations on lists.
Operation 1: To check if list is empty or not?
The list is empty if head contains no address. That is, head is NULL. Which also tells us that when we create a list, we should assign NULL to head. Hence, the correct way to initialize a list is:
node* head=NULL;
bool isEmpty(node* head)
{
if(head==NULL)
return true;
else
return false;
}
---------------------------------------
Operation 2: To insert an item at the front of the list
Assuming that the list is containing a set of items where order isn't important. We pass the node pointer by reference (that is the actual head is modified rather than a duplicate copy of head being passed to the function).
We first create a node by reserving memory space.
We contain address of old head in node temp.
We move head so that head now contains address of temp.
void insert(node* &head, int item)
{
node* temp=new node;
temp->data=item;
temp->next=head;
head=temp;
}
Even if head was NULL (inserting item into an empty list), the statement temp->next=head means that temp->next contains NULL which is also correct :)
-----------------------------------
Operation 3: Deleting item from front of list:
void delete(node* &head)
{
if(head!=NULL)
{
node* temp=head;
head=head->next;
delete temp;
}
//if head is already NULL, it means nothing remaining to delete
}
-------------------------------
Operation 4: Traverse through the list (go through the list for some xyz purpose)
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
while(head)
{
cout<
head=head->next; //please remember the actual head is not modified since a duplicate
//pointer in memory is there, that contains same address as head
}
}
For those of you, who still are freaked out by me modifying "head" in the function, use the following function varient:
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
node* current=head;
while(current)
{
cout<
current=current->next;
}
}
------------------
Tutorial part 2 coming soon to a cinema near you!
cheers
gaurav
Wednesday, January 28, 2009
recipe for marathi kadi / marathi kadhi
my wife, gunjan, is extremely fond of marathi or maharashtrian kadi. The recipe is quite simple. Here it goes:
Ingredients
Yoghurt - one bowl
Gramflour - one heaped tablespoon
salt - to taste
sugar - 1 heaped tablespoon
green chilli - 3/4
ginger 1 finger sized (my finger :D)
mustard seeds 1/2 teaspoon
curry leaves about 15-20
oil 3 tablespoon
water 1.5ltr
crush the ginger and chilli
mix the yoghurt and gramflour and whisk together gently (you don't want butter to come out of the yoghurt now, do you!?) till no lumps, to which add sugar, salt, and water. mix well till uniform and add crushed ginger and chilli.
heat oil on high in a deap saucepan and add mustard seeds and curry leaves. after 5-10 seconds, add the yoghurt mix and keep stirring till the boil comes. boil for another 5 mins on high heat, stirring regularly, and then turn heat to mid (4 to 5 o'clock) and stir intermittently for 20 mins. Done :)
Hope you enjoy this :p
cheers
gaurav
Ingredients
Yoghurt - one bowl
Gramflour - one heaped tablespoon
salt - to taste
sugar - 1 heaped tablespoon
green chilli - 3/4
ginger 1 finger sized (my finger :D)
mustard seeds 1/2 teaspoon
curry leaves about 15-20
oil 3 tablespoon
water 1.5ltr
crush the ginger and chilli
mix the yoghurt and gramflour and whisk together gently (you don't want butter to come out of the yoghurt now, do you!?) till no lumps, to which add sugar, salt, and water. mix well till uniform and add crushed ginger and chilli.
heat oil on high in a deap saucepan and add mustard seeds and curry leaves. after 5-10 seconds, add the yoghurt mix and keep stirring till the boil comes. boil for another 5 mins on high heat, stirring regularly, and then turn heat to mid (4 to 5 o'clock) and stir intermittently for 20 mins. Done :)
Hope you enjoy this :p
cheers
gaurav
ACS
I, not-so-recently, applied for skills assessment (essentially that an approval of the fact that i am skilled enough to work in the IT industry) with ACS - Australian Computing Society. The application was lodged on 1st Dec and as of today, not even an officer has been assigned my case. A computing organization, that evaluates your credentials, taking two months (and counting) to assign the case to a person - makes you think, doesn't it :D
Sunday, January 18, 2009
the ABSOLUTE easiest recipe
hi all,
this is a simpler form of the khichdi recipe I posted a couple of weeks back. it's a shove-everything-in-and-just-don't-forget-about-it kind of recipe.
ingredients:
1 bowl low starch rice (preferably basmati)
1 bowl split green moong daal (lentil)
1 big potato - diced (on the bigger side)
1 carrot - diced
4 bowls of water
1/2 teaspoon chilli powder
1/2 teaspoon turmeric powder
1/2 teaspoon cumin powder
4-5 whole dried chillies/ fresh chilli padi (if you like it hot!)
salt to taste
wash the rice and lentil together and get any excess starch off them. mix ALL the ingredients together, cover and cook on high heat for 7 mins, stir, then on 3 o'clock (low heat) for 20 mins.
DONE !!!!
cheers
gaurav
this is a simpler form of the khichdi recipe I posted a couple of weeks back. it's a shove-everything-in-and-just-don't-forget-about-it kind of recipe.
ingredients:
1 bowl low starch rice (preferably basmati)
1 bowl split green moong daal (lentil)
1 big potato - diced (on the bigger side)
1 carrot - diced
4 bowls of water
1/2 teaspoon chilli powder
1/2 teaspoon turmeric powder
1/2 teaspoon cumin powder
4-5 whole dried chillies/ fresh chilli padi (if you like it hot!)
salt to taste
wash the rice and lentil together and get any excess starch off them. mix ALL the ingredients together, cover and cook on high heat for 7 mins, stir, then on 3 o'clock (low heat) for 20 mins.
DONE !!!!
cheers
gaurav
Subscribe to:
Posts (Atom)