CSE 2320 Section 002, Fall 2015

Exam 1

Time: 80 mins

Name: .

Student ID: .

Total exam points: 100.

Question / Points / Out of
1 / 16
2 / 13
3 / 18
4 / 20
5 / 20
6 / 5
7 / 8
Total / 100

If you have the smallest doubt about what a question asks of you, or whether or not you can use certain code, ASK US! (Even if you think that it is a really silly question).

All the answers need to be justified. No credit will be given if the answer is provided, but with no justification.

Question 1 (16 points) The Quick-Find algorithm is given below.

#include <stdio.h

#define N 8

main(){ // line

int i, p, q, t, id[N]; // 1

for (i = 0; i < N; i++) id[i] = i; // 2

while (scanf("%d %d", &p, &q) == 2) { // 3

if (id[p] == id[q]) { // 4

printf(" %d and %d were on the same set\n", p, q); // 5

continue; // 6

}

t = id[p]; // 7

for (i = 0; i < N; i++) // 8

if (id[i] == t) id[i] = id[q]; // 9

printf(" %d %d link led to set union\n", p, q); // 10

}

}

Show the graph and fill-out the values of the id array produced by the above program when the following pairs of edges are given in this order. The label at the top of the columns shows the index. Every row represents the state of the id array.

CIRCLE the changes produced in the id array due to processing the current pair.

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7
no pair yet
6 – 5 (first)
3 – 2
2 – 6
0 – 2
3 – 2
5 – 7 (last)

Draw the graph below. Make sure you show the direction of the arrows as it should be based on the given implementation (do not pick a direction of your choice).

REDRAW the graph after each pair. Each row below should show the redrawn graph.

Pair / Tree
6 – 5 (first)
3 – 2
2 – 6
0 – 2
3 – 2
5 – 7 (last)

Question 2 (13 points)

a)  (5 points) Is anything wrong with the following recursive definition?

g(0) = N

g(N) = g(N-1) + c

b)  (8 points) Assume that you expanded a recursion and got to the summation:

1 + 25 + 35 + … + N5

Can you solve this in terms of Θ, Ω or O ?

Question 3 (18 points) Let g(N) = g(N-1) + N/5, and g(0) = 1.

Expand the formula up to where there is no recursive term.

Give the expression for the i-th step.

How many steps does it take until there is no recursive term in the expansion?

Give the final expansion (with no recursive term) .

If you can rewrite the term above as a more concise expression, give that expression.

Find a function f(N) such that g(N) = Θ(f(N)). (Find the Θ for g(N) based on the above expression). Justify your answer. Note that your answer here must be in terms of N.

Question 4 (20 points) Write a function, int foo(list L), that takes as argument a list L of integers (the item is an integer). It should start from the first node and check the following property:

-  the first node can have any value (nothing to check)

-  every other node (starting from the first node) has an item that is twice the value of the current node.

The program should return 1 if the list has this property and 0 otherwise. The examples below will clarify the problem:

3 -> 7 -> 6 -> 0 -> 12 -> 11 -> 24 has the property: 3*2 = 6, 6*2 = 12, 12*2 = 24

5 -> 7 -> 10 -> 0 -> 20 -> 11 -> 40 has the property

5 -> 7 -> 6 -> 0 -> 12 -> 11 -> 24 does NOT have the property because 5 * 2 = 10, but the item in the second node from 5 is 6.

Assume that lists are implemented using the types and structs defined below. You should do the pointer manipulation (do not assume for example that there is a function that removes a node or one that inserts at a specific position).

typedef struct node * link;

typedef struct struct_list * list;

struct node {

int item;

link next;

};

struct struct_list {

link first; // Note that no length field is available

};

Question 5 (20 points) Assume that you have an implementation of a stack object and you need to simulate a FIFO (First-In-First-Out) queue, using the stack. For simplicity, we will not declare a queue_struct. We will use as the queue a stack object. Provide the implementation of the put_in_FIFO and get_from_FIFO functions (they must have the signature shown here) using the stack’s put and get functions.

void put_in_FIFO(stack my_queue, int data);

int get_from_FIFO(stack my_queue);

From the stack implementation, you only have access to the header file. In particular, you do not know the stack implementation and you do not have access to the stack_struct. You must access the stack only through the provided functions:

typedef struct stack_struct * stack;

stack newStack(int mx_sz);

void push(stack s, int data);

int push(stack s);

destroyStack(stack s);

The description and the code below are provided to help you understand the problem.

If a stack is accessed through the put_in_FIFO and get_from_FIFO only it should behave like a FIFO queue. For example the client code below would print: 4, 1, 9, 15, 7

int main() {

stack my_queue = newStack(100);

put_in_FIFO(my_queue, 4);

put_in_FIFO(my_queue, 1);

put_in_FIFO(my_queue, 9);

int data = get_from_FIFO(my_queue); // data will be 4

printf("%d, ", data); // prints 4

put_in_FIFO(my_queue, 15);

put_in_FIFO(my_queue, 7);

data = get_from_FIFO(my_queue);

printf("%d, ", data); // prints 1

data = get_from_FIFO(my_queue);

printf("%d, ", data); // prints 9

data = get_from_FIFO(my_queue);

printf("%d, ", data); // prints 15

data = get_from_FIFO(my_queue);

printf("%d ", data); // prints 7

}

(5 points) Give the complexity of your functions in terms of θ.

Question 6 (5 points) A letter means push and an asterisk means pop. Is there a way to insert asterisks in the sequence W O N D E R F U L so that the sequence of letters returned by the pop operations is: N D O R E W F U L

If it’s possible, give the sequence. If it’s not possible, say why.

Question 7 (8 points)

int foo(int * array, int N)

{

if (N == 0) return 0;

int result = 0;

int b, c;

for (b = 0; b < N/4; b++)

for (c = N; c > 1 ; c = c/2)

result = result + array[b] * array[c];

return result + foo(array, N-1);

}

Give the recursion formula (including the stopping term). You do NOT need to include constants that do not affect the recurrence.

8