Week 9

Trees

Trees are a data structure with a hierarchy. A tree node has some number of children but only one parent. The root of a tree has no parent. The leaves of a tree have no children. A tree where each node has at most two children is a Binary Tree. If the children are ordered, it is a Binary Search Tree.

Tree code from The Practice of Programming, Kernighan & Pike
tree.c 

1:	 typedef struct Nameval Nameval;
2:	 struct Nameval {
3:	   char *name;
4:	   Nameval *left;
5:	   Nameval *right;
6:	 };
7:	 
8:	 Nameval *insert(Nameval *treep, Nameval *newp) {
9:	   int cmp;
10:	   if (treep == NULL) {
11:	     return newp;
12:	   }
13:	   cmp = strcmp(newp->name, treep->name);
14:	   if (cmp == 0){
15:	     printf("insert: duplicate entry %s ignored", newp->name);
16:	   }else if (cmp < 0) {
17:	     treep->left = insert(treep->left, newp);
18:	   } else {
19:	     treep->right = insert(treep->right, newp);
20:	   }
21:	   return treep;
22:	 }
23:	 
24:	 Nameval *lookup(Nameval *treep, char *name) {
25:	   int cmp;
26:	   if (treep == NULL) 
27:	     return NULL;
28:	   cmp = strcmp(name, treep->name);
29:	   if (cmp == 0) {
30:	     return treep;
31:	   } else if (cmp < 0) {
32:	     return lookup(treep->left, name);
33:	   } else {
34:	     return lookup(treep->right, name);
35:	   }
36:	 }
37:	 
38:	 void printInOrder(Nameval *treep) {
39:	   if (treep == NULL) {
40:	     return;
41:	   }
42:	   printInOrder(treep->left);
43:	   printf("%s\n", treep->name);
44:	   printInOrder(treep->right);
45:	 }
  1. Find the examples of recursion in the tree code.
  2. What does the tree look like after inserting "red", "green", "white", "snow", "tree", "santa", "elf"?
  3. What happens if we insert items into the tree in a sorted order?
  4. How tall does the tree grow after inserting 7 items?

Sorting

Mergesort

Mergesort from Introduction to Algorithms, Cormen et al.
mergesort.c 
1:	 #include <limits.h>
2:	 void mergesort (int v[], int p, int r);
3:	 void merge (int v[], int p, int q, int r);
4:	 
5:	 void mergesort (int v[], int p, int r) {
6:	   int q;
7:	   if (p < r) {
8:	     q = (p+r)/2;
9:	     mergesort(v, p, q);
10:	     mergesort(v, q+1, r);
11:	     merge(v, p, q, r);
12:	   }
13:	 }
14:	 
15:	 void merge (int v[], int p, int q, int r) {
16:	   int i,j,k;
17:	   int left_length = q - p + 1;
18:	   int right_length = r - q;
19:	   int* left_array = (int*)malloc(sizeof(int)*(left_length+1));
20:	   int* right_array = (int*)malloc(sizeof(int)*(right_length+1));
21:	   
22:	   /* create temporary arrays */
23:	   for (i=0; i<left_length; i++) {
24:	     left_array[i] = v[p+i];
25:	   }
26:	   left_array[left_length] = INT_MAX;
27:	 
28:	   for (j=0; j<right_length; j++) {
29:	     right_array[j] = v[q+j+1];
30:	   }
31:	   right_array[right_length] = INT_MAX;
32:	 
33:	   i = j = 0;
34:	 
35:	   /* merge */
36:	   for (k = p; k<= r; k++) {
37:	     if (left_array[i] <= right_array[j]) {
38:	       v[k] = left_array[i];
39:	       i++;
40:	     } else {
41:	       v[k] = right_array[j];
42:	       j++;
43:	     }
44:	   }
45:	 }

Quicksort

Quicksort from The Practice of Programming, Kernighan & Pike
quicksort.c 
1:	  /* quicksort: sort v[0]..v[n-1] into increasing order */
2:	  void quicksort(int v[], int n)
3:	  {
4:	     int i, last;
5:	 
6:	     if (n <= 1) /* nothing to do */
7:	         return;
8:	     swap(v, 0, rand() % n);    /* move pivot elem to v[0] */
9:	     last = 0;
10:	     for (i = 1; i < n; i++)    /* partition */
11:	         if (v[i] < v[0])
12:	             swap(v, ++last, i);
13:	     swap(v, 0, last);          /* restore pivot */
14:	     quicksort(v, last);        /* recursively sort */
15:	     quicksort(v+last+1, n-last-1);    /* each part */
16:	  }
17:	 
18:	  /* swap:  interchange v[i] and v[j] */
19:	   void swap (int v[], int i, int j)
20:	  {
21:	     int temp;
22:	 
23:	     temp = v[i];
24:	     v[i] = v[j];
25:	     v[k] = temp;
26:	  }
  1. Pick 5 numbers. Write out the array being passed in to each call of mergesort and quicksort.
  2. How are mergesort and quicksort the same? How are they different?

Programming Assignment 4

Netlist files go through a stage called "place and route" to generate the layout files. The components are given locations on a board and the nets of the pins are wired together.

Terminology

Hints