Algorithms代考 Exam Algorithms and Data Structures

Exam Algorithms and Data Structures

Algorithms代考 1.10 points TEXT This exercise is about stacks. Write down nine operations which can be executed on an empty stack in this…

1. Linear Data Structures Algorithms代考

1.10 points TEXT This exercise is about stacks. Write down nine operations which can be executed on an empty stack in this order, one operation per line. After each operation, but in the same line, write down the contents of the stack after the operation, with the bottom element fifirst.

In addition, ensure the following:

• At some point during your sequence of operations the stack should contain at least three items.
• After the ninth and last operation the stack should contain at most two items.
• Use random and difffferent numbers from 0 to 100 as items.

2.10 points TEXT Consider the following defifinition of the type Queue:

typedef struct Queue {

int *array;

int back;

int front;

int size;

} Queue;

If a Queue is not empty, then the front is the array position of the oldest item. Consider the following implementation of the operation dequeue:

1 int dequeue(Queue *qp) {

2 if (isEmptyQueue(*qp)) {

3 queueEmptyError();

4 }

5 qp->front = (qp->front + 1) % qp->size;

6 return qp->array[qp->front - 1];

7 }

What is wrong with this implementation? Explain your answer and make suggestions how the function should be changed. Algorithms代考

3. 10 points TEXT Consider the following grammar.

<id> ::= <letter> { <posdigit> } [ ’*’ ]

<label> ::= <letter> { <num> }

<num> ::= <posdigit> { <digit> }

<digit> ::= ’0’ | <posdigit>

<posdigit> ::= ’1’ | ’2’ | ’3’ | ’4’

<letter> ::= ’a’ | ’b’ | ’c’

(a) Write down two expressions which can be produced by <id> but not by <label>.

(b) Write down two expressions which can be produced by <label> but not by <id>.

(c) Write down one expression which can be produced both by <id> and by <label>.

2.Trees Algorithms代考

1. 5 points PDF Draw a heap which contains all digits of your student number as elements. For example, if your student number would be 3214123 then the heap should contain seven nodes with the elements 3, 2, 1, 4, 1, 2 and 3.

Next to the drawing, also write down the array representation of the heap.

2. 10 points PDF Draw two search trees which contain the elements 9, 42, 50, 51, 57, 64 and your age in years. One of the trees should have at most two leaves and the other one should have at least three leaves.
3. 10 points CODE This problem is about binary trees. Their defifinition in C is as follows.

typedef struct TreeNode *Tree;

struct TreeNode {

int item;

Tree leftChild, rightChild;

};

Defifine an effiffifficient C function with prototype Tree singleBranch(Tree tr) that at each node with two children removes the right child and its descendants. That is, the resulting tree should consist of a single branch.

Make sure that no memory leaks occur.

You may call freeTree(Tree t) from the solution of Exercise 2.3 in the lecture notes.

4. 10 points CODE This question is about binary trees as described in the previous question. Defifine an effiffifficient C function with prototype int childProduct(Tree tr) which returns the product of the number of left children and the number of right children. You may defifine additional helper functions to be called from childProduct.

For example, given the tree below the function childProduct should return 6.

5. 10 points PDF This question is about tries and has three parts; each part relies on its successor. You are given the following dictionary: {am, are, be, been, could, had, has, have}. First, add your fifirst name and your last name to the dictionary, using lower case letters. (If you have multiple fifirst or last names, choose one of each. Also, leave out any prefifixes such as “van” or “de”). Use the resulting dictionary for this whole exercise.

Now, make the following three drawings. For each step, brieflfly explain any additional assumptions or decisions you made. If you decide to use a stop character to mark the end of words, please use the $ symbol.

(a) Draw a standard trie T for the dictionary including the words above and your fifirst and last name.

(b) Draw a compressed trie T’ based on the standard trie T, from part a.

(c) Draw a compact trie T” based on the compressed trie T’, from part b.

Please upload your answers for (a), (b) and (c) together as one single PDF fifile.Algorithms and Data Structures page 5 of 7 9 April 2020

3.Graphs Algorithms代考

1. 5 points PDF Draw a connected undirected graph with 5 nodes and 8 edges which has an Euler cycle. Number the nodes and write down an Euler cycle of this graph.
2. 5 points TEXT Suppose we apply BFS and DFS to the same simple connected graph. What do we know about the height of the two resulting spanning trees? Explain and justify your answer!
3. 15 points PDF This exercise is about simple connected graphs (undirected and without weights). Suppose for each graph G = (V, E) we also have a function f : E → {red, black} which assigns to each edge in G one of two labels.

(a) Defifine an algorithm AlternatingDistance(G, f, v, w) in pseudocode that returns the length of a shortest path from v to w in G such that the edges along the path have alternating labels. If there is no path with alternating labels from v to w, the algorithm should return NoPath.

For example, given the graph below and v = 1 and w = 5 the algorithm should return 3 and not 2 because (1,3,4,5) is a shortest path with alternating labels, whereas (1,2,5) does not have alternating labels.

(b) What is the time complexity of your algorithm in terms of the number of nodes n and the number of edges e? Explain your answer.