SE250:lab-6:klod004

Lab 6

This lab was rather hard for me to do, as we have not have been coding in c for quite a while now. But anyways, I finally got around to actually running the tasks after an hour. So I had some teething problems in the beginning of the lab, as I was confused whether to write a main file or to just include it in the file provided.

Task 1

After an hour of looking at the code and trying to write a program file, one of my mates told me what to do, and I started writing a main file in the file provided. I also didn't know that we had to use the randomtree function provided, so I wasted a bit of time there. But after an hour, I finally got all that working. My results were with:

Number of Nodes              Height
10                           4
20                           6
30                           7
40                           10
50                           12
60                           11
70                           12
80                           13
90                           13
100                          16
500                          18

I got some pretty interesting results as you can see with 60 nodes, I had height of 11 and with 50 nodes, I had height of 12. But as told in lectures, we had to do a lot of trials. Which I didnt. But anyways, that is the distribution for the random trees. I would have drawn a graph, but I had some troubles putting it on the wiki, so didnt try too hard.

Task 2

The minimum and maximum functions were pretty hard to implement, considering the fact that Mark told us how to do it in lectures. But the code to do this was:

Node* minimum( Node* node ) {
  /* TODO */
	while(node->left!=empty){
		node = node->left;
	}
	return node;
} 

Node* maximum( Node* node ) {
  /* TODO */
	while(node->right!=empty){
		node = node->right;
	}
	return node;
}

I used the same tree as Mark gave in lectures, the input file was: 4,6,5,7,2,1,3 So the min and max function did do the work that it was supposed to do.

Task 3

The lookup function was rather harder to implement. I had lots of trouble with the logic that even the tutorer was struggling with my code and could not help me to find the problem with the code. The logic seemed right, but there was still some errors in there. Here's the code:

Node* lookup( int key, Node* node ) {
  /* TODO */
	int isFound = 0;
	while(!isFound){
	        if(node->key == key){
			isFound = 1;
			return node;
		}else if(node->left == key){
			isFound = 1;
			return node->left;
		}else if(node->right == key){
			isFound = 1;
			return node->right;
		}
	}
}

This code doesnt really work, but as I said, I cannot really find an error with it. The logic seems to be right which even the tutorer said was right. So if anyone find the problem, let me know.

Conclusion

This is as far as I got in the lab, it took me ages to get the first task figured, but then I progressed well. I guess I got so overloaded with Java, that it messed up my C and even Mark was like, that is Java notation. But anyways, I would have done the other tasks, but had was busy doing Java like everyone, and after Java was completed, my laptop crashed. So couldnt get around to completing all the tasks. Overall, I guess this was an excellent lab. I only had problems with syntax and getting used to the code and running it and all. I guess we should get a bit more practice on making small programs on C earlier on in the course, and have one program that we can use. As people have problems with EMACS and Visual aint the best all the time.

But as for the lab is concerned, I did notice as the number of nodes increases, the time taken to make the tree is so much, that I can actually go to the guys room and be back to see the tree still forming. That maybe exaggerrating a bit, but it takes a bit of time. Whereas for hash tables, it didnt take that long all the time. And we were dealing with 10000+ there. Also noticed was that the functions, once you get your head around the code syntax and all, it rather easy to understand, use and manage.