Week 02 Tutorial Questions

Analysis of Algorithms, ADTs, Binary Search Trees

Analysis of Algorithms

Design an algorithm to determine if a string of length \( n \) is a palindrome - that is, it reads the same backwards as forwards. For example, "racecar" is a palindrome, while "reviewer" is not.
1. Write the algorithm in pseudocode.
2. Analyse the worst-case time complexity of your algorithm.
3. Implement your algorithm in C. Your program should accept a single command line argument, and check whether it is a palindrome. Examples of the program executing are:
```
./palindrome racecar
yes
./palindrome reviewer
no
```
  Hint: You may use the standard library function strlen(3), which has prototype size_t strlen(char *), is defined in <string.h>, and which computes the length of a string (without counting its terminating '\0' character).
Using only techniques that you have learned so far, 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 worst-case time complexity of your algorithm.
3. Implement your algorithm as a function in C. The algorithm should accept an array and a value as input and return true or false.

ADTs

Consider the following Set ADT interface:
```
// Creates a new empty set
Set SetNew(void);

// Frees memory allocated to the set
void SetFree(Set s);

// Inserts an element into the set
void SetInsert(Set s, int elem);

// Deletes an element from the set
void SetDelete(Set s, int elem);

// Returns true if the given element is in the set, and false otherwise
bool SetContains(Set s, int elem);

// Returns the number of elements in the set
int SetSize(Set s);
```
Use the Set ADT to implement the following functions:
1. ```
int numOddOccurrences(int arr[], int size);
```
  This function takes an array of integers and its size, and returns the number of integers that occur an odd number of times.
  
  For example, if given the array [4, 3, 4, 8, 8, 4], the function should return 2, because there are two elements that appear an odd number of times: 3 (occurs 1 time) and 4 (occurs 3 times).
2. ```
int numSingleOccurrences(int arr[], int size);
```
  This function takes an array of integers and its size, and returns the number of integers that occur exactly once.
  
  For example, if given the array [4, 3, 4, 8, 7, 4], the function should return 3, because there are three elements that occur exactly once: 3, 8 and 7.

A classic problem in computer science is the problem of implementing a queue using two stacks. Consider the following stack ADT interface:

// Creates a new empty stack
Stack StackNew(void);

// Pushes an item onto the stack
void StackPush(Stack s, int item);

// Pops an item from the stack and returns it
// Assumes that the stack is not empty
int StackPop(Stack s);

// Returns the number of items on the stack
int StackSize(Stack s);

Use the stack ADT interface to complete the implementation of the queue ADT below:

struct queue {
	Stack s1;
	Stack s2;
};

Queue QueueNew(void) {
	Queue q = malloc(sizeof(struct queue));
	q->s1 = StackNew();
	q->s2 = StackNew();
	return q;
}

void QueueEnqueue(Queue q, int item) {
	// TODO
}

int QueueDequeue(Queue q) {
	// TODO
}

Binary Search Trees

For the questions below, use the following data type:

struct node {
	int value;
	struct node *left;
	struct node *right;
};

(Binary Search Trees)

For each of the sequences below
- start from an initially empty binary search tree
- show the tree resulting from inserting values in the order given
1. 4 6 5 2 1 3 7
2. 5 2 3 4 6 1 7
3. 7 6 5 4 3 2 1
Assume new values are always inserted as new leaf nodes.
(Binary Search Trees)

Consider the following tree and its values displayed in different output orderings:

What kind of trees have the property that their in-order traversal is the same as their pre-order traversal?

Are there any kinds of trees for which all output orders will be the same?
(Binary Search Trees)

Implement the following function that counts the number of odd values in a tree. Use the following function interface:
```
int bstCountOdds(struct node *t) { ... }
```
(Binary Search Trees)

Implement the following function to count number of internal nodes in a given tree. An internal node is a node with at least one child node. Use the following function interface:
```
int bstCountInternal(struct node *t) { ... }
```
(Binary Search Trees)

Implement the following function that returns the level of the node containing a given key if such a node exists, otherwise the function returns -1 (when a given key is not in the binary search tree). The level of the root node is zero. Use the following function interface:
```
int bstNodeLevel(struct node *t, int key) { ... }
```
(Binary Search Trees)

Implement the following function that counts the number of values that are greater than a given value. This function should avoid visiting nodes that it doesn't have to visit. Use the following function interface:
```
int bstCountGreater(struct node *t, int val) { ... }
```