Week 05 Tutorial Answers

Balanced Trees, Graph Basics

Balancing Trees

Show how the following tree would change if we do a right rotation on the node containing 10 followed by a left rotation on the node containing 6.

Answer:

After right rotation on node containing 10:

After left rotation on node containing 6:
Show the result of performing the insert-at-root operation with the value 7 in this binary search tree:

Answer:

AVL Trees

AVL trees use the following node definition:

struct node {
    int data;
    int height;
    struct node *left;
    struct node *right;
};

You may find these resources on AVL trees useful:

AVL tree visualization
VisuAlgo's AVL tree visualizer (click on AVL tree)

For the following AVL tree, annotate each node with the height of its subtree.

Now starting from the initial tree each time, insert the following integers:
```
0  2  10  17
```
Answer:
Tree annotated with heights:
1. After inserting 0, the node containing 3 becomes unbalanced:
  
  After rebalancing:
2. After inserting 2, the node containing 3 becomes unbalanced:
  
  After rebalancing:
3. After inserting 10, the node containing 6 becomes unbalanced:
  
  After rebalancing:
4. After inserting 17, the node containing 6 becomes unbalanced:
  
  After rebalancing:
Show how an AVL tree would be constructed if the following values were inserted into an initially empty tree in the order given:
```
12  10  8  6  4  2
```
Answer:

The following diagram shows how the tree grows:
Using an AVL tree, design an algorithm to determine if an array contains two elements that sum to a given value.
1. Write the algorithm in pseudocode.
2. Analyse the time complexity of your algorithm.
Answer:
1. One possible solution inserts all array elements into an AVL tree, and then for each element A[i], checks if (v - A[i]) is in the tree. However some extra care is needed to make sure we don't add an element A[i] to itself to get v.
```
hasTwoSum(A, v):
	Input:  array A[0..n - 1] of integers
	        integer v
	Output: true if A contains two elements that sum to v, false otherwise

	if v is even and v/2 occurs more than once in A then
		return true
	end if

	t = new AVL tree
	for i = 0 up to n - 1 do
		if 2 x A[i] =/= v then
			insert A[i] into t
		end if
	end for
	
	for i = 0 up to n - 1 do
		if (v - A[i]) is in t then
			return true
		end if
	end for
	
	return false
```
  Here is a cleaner solution:
```
hasTwoSum(A, v):
	Input:  array A[0..n - 1] of integers
	        integer v
	Output: true if A contains two elements that sum to v, false otherwise

	t = new AVL tree
	
	for i = 0 up to n - 1 do
		if (v - A[i]) is in t then
			return true
		end if
		insert A[i] into t
	end for
	
	return false
```
2. First solution: The first if statement runs in \( O(n) \) time, since counting the number of occurrences of a value in an array is \( O(n) \). The first for loop inserts at most \( n \) values into an AVL tree, and since AVL tree insertion is \( O(\log n) \), this loop runs in \( O(n \log n) \) time. The second for loop performs at most \( n \) searches in the AVL tree, and since searching in an AVL tree is \( O(\log n) \), this loop also runs in \( O(n \log n) \) time. Thus the time complexity of the algorithm is \( O(n) + O(n \log n) + O(n \log n) = O(n \log n) \). Notice how this algorithm is more efficient than the algorithm we developed in Week 3.
  
  Second solution: The for loop performs at most \( n \) searches and \( n \) insertions in the AVL tree, and since searching and inserting in an AVL tree are both \( O(\log n) \), the loop runs in \( O(n \log n) \) time. Thus, the time complexity of the algorithm is \( O(n \log n) \).

Graph Representation

Consider the following graph

The edges are labelled simply for convenience in describing graph properties.
1. How many edges does it have?
2. How many cycles are there in the graph?
3. How many cliques are there in the graph?
4. What is the degree of each vertex?
5. How many edges in the longest path from 5 to 8?
  (without traversing any edge more than once)
Answer:
1. 11 edges (labelled a..k)
2. 6 cyles: 0-1-7-8-0, 1-2-7-1, 2-3-7-2, 0-1-2-7-8-0, 0-1-2-3-7-8-0, 1-2-3-7-1
3. 2 cliques: {1, 2, 7}, {2, 3, 7} (clique = complete subgraph with at least 3 nodes)
4. d(0) = 2, d(1) = 3, d(2) = 3, d(3) = 3, d(4) = 2, d(5) = 1, d(6) = 1, d(7) = 5, d(8) = 2
5. 7 edges, path is 5-4-3-2-7-1-0-8 or 5-4-3-7-2-1-0-8
For each of the following graphs:

Show the concrete data structures if the graph was implemented via:
1. adjacency matrix representation (assume a full \( V \times V \) matrix)
2. adjacency list representation (if non-directional, include both \( (v, w) \) and \( (w, v) \))
Answer:
How is the adjacency matrix for a directed graph different to that for an undirected graph?

Answer:

The adjacency matrix for an undirected graph is symmetric and has zeroes on the leading diagonal (no self-edges). The adjacency matrix for a directed graph is typically not symmetric and can have non-zero values on the leading diagonal (self-edges are allowed).
Facebook could be considered as a giant "social graph"
1. What are the vertices?
2. What are the edges?
3. Are edges directional?
4. What does the degree of each vertex represent?
5. What kind of graph algorithm could suggest potential friends?
Answer:
1. Vertices are people (Facebook users)
2. Edges are "friend" relationships
3. No - if you are someone's friend, they are also your friend
4. The degree of a vertex is the number of friends that the person represented by the vertex has
5. Breadth-first search - find your immediate friends, then consider their friends, and so on

A Tutor's Worst Nightmare

The following piece of code has several style issues. Identify and fix them.

Click here to download the file and a Makefile for compiling it.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

void freeList(struct Node *head) {
	if (head == NULL) {
	return;
	}
	// Frees the list by iterating through the list, using a temporary element and freeing the elements by using free (hopefully this comment is useful and helps out)
	struct Node *Temp = head;
	while (head != NULL) {
	    Temp = head;
	    head = head->next;
	    free(Temp);
	}
}
void print_list(struct Node *node) {
    while (node->next != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("%d\n", node->data);
    return;
}
struct Node *add(struct Node *a, int data) {
    // malloc the node
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    // set the node's data field
    newNode->data = data;
    // set the node's next field to NULL
    newNode->next = NULL;
	if (a == NULL) {
		a = newNode;
	} else {
        struct Node *lastNode = a;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }
        lastNode->next = newNode;
	}
	return a;
}
int main() {
	struct Node *head = NULL;
	head = add(head, 1);
	head = add(head, 2);
	head = add(head, 3);
	head = add(head, 4);
	print_list(head);
	freeList(head);
	return 0;
}

Answer:

This is a list of most of the style issues in the code:

Inconsistent indentation
- The return statement in freeList is not indented
- Both tabs and spaces used for indentation
Lack of vertical whitespace
- There is no whitespace between functions
- There is no whitespace between different logical parts of a function, e.g., the add function
Incorrect function order
- Helper functions should be placed under the functions that use them, in the order that they are used.
- In the program, we can see that the main function uses add(), then print_list(), then freeList(), so the main function should appear first, followed by add(), print_list() and then freeList().
Poor commenting
- Each function should have a comment above it describing its purpose
- Comments should be used to provide explanation and commentary, not to restate the code
Inconsistent naming style
- A consistent naming style should be used for variable and function names. The allowed styles are camelCase and snake_case, and only one should be used across the entire program.
Poor variable/function names
- add is too short of a variable name and doesn't adequately describe the function. A better name would be appendList.
- a is not a meaningful variable name. A better name might be list or listHead.
Unnecessary type casts
- Type casts are not necessary when using malloc.