UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

  • Index
  • » Java
  • » Urgent Help needed please

#1 2004-04-03 07:35 PM

Liberated Soul
Guest

Re: Urgent Help needed please

I would greatly appreciate if anyone can answer me any or all of these questions listed below. Id be very thankful, i really need it urgently :)
Thank you


Question 1) what does it accomplish

public void foo (stack s1, stack s2, int num, int x){
s2.clear();
for (int i = 0; i < num - 1; i++)
s2.push(s1.pop()))
int temp = s1.pop();
s1.push(x);
while (!(s2.empty()))
s1.push(s2.pop());
}

Question 2) assume the following elemets are insterted into stack s in the order 2,
4, 6, 8 and also assume the following elements are insterted

into queue q in this order 1, 3, 5, 7. Show the contents of the stack s
and queue q after the following code segment executes

while (!q.isempty()){
temp = q.remove();
s.push(temp);
}
while (!s.isempty()) {
temp = s.pop();
q.insert(temp);
}

Question 3)Given a reference list to a linear linked list and three reference variables p, q and r, determing what the following
aloritham accomplishes

p = list
q = null
while p != null
r=q
q=p
p=p.getNext()
q.setNext(r)
list = q




Question 4)Assume a reference list to the fist node in a non empty linear linked
list, write a pseudo code alogrith which outputs the value of the largest node in the list.

#2 2004-04-03 09:23 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,833
Website

Re: Urgent Help needed please

And, how much are you willing to pay us to do your homework
for you, exactly? ;-)

Offline

#3 2004-04-05 07:18 PM

HectorLasso
Administrator
From: Colombia
Registered: 2002-06-12
Posts: 353

Re: Urgent Help needed please

I don't like people that don't do their homework...

But just to prove I'm a nice guy, I'll try to help you UNDERSTAND how to solve these problems... My idea is not to give you the answer, but to guide you to come to your own conclussions. So I may introduce a couple of mistakes here, and I hope you get them and sort them out.

The method I use for solving the first problem uses simple math concepts, like sets and series. This is not a complete math proof or something, is just some way of presenting the information clearly, and using the properties of sets and series (stacks can be thought as series)

public void foo (stack s1, stack s2, int num, int x){ 
   s2.clear(); 
   for (int i = 0; i < num - 1; i++) 
      s2.push(s1.pop())) 
   int temp = s1.pop(); 
   s1.push(x); 
   while (!(s2.empty())) 
      s1.push(s2.pop()); 
}

I assume you know how a stack works, however, I'll try to put the rules clear.

I'll use the following syntax. I'll write a stack as a set.

i.e. Stack = { 1, 2, 3, 4, ..., x } means that Stack has the elements 1,2,3,4,...,x (they don't need to be ordered)

The first element in this set (1) is the head, and the last one (x) is the tail... I will always push() into the tail and pop() from the tail thus making it easier to write as a SET...

So, if you have S = {a}, and PUSH(b) into S, the result will be: S = {a,b}
after PUSH(c) and PUSH(e) into S, you will have: S = {a,b,c,e}
if you POP() from S, you will get e, and S={a,b,c}

As we will work with an unspecified number of elements, I will label the elements differently:

S = { e1, e2, e3, e4, ... , en }
The number or letter to the right of "e" is the subscript - I couldn't write a subscript here, and it means the en is the n-th element of the set

NOTE: In fact, the stack is more like a series. In sets the order of the elements is irrelevant, while in series the order is relevant, and they use the subscript notation to refer to the i-th element of the series

Ok, the let's suppose s1 and s2 are stacks. And we have the push, pop and clear operations, and another operation used to verify that it is empty, implemented as java objects they'd be methods of the object.

s1 = { e1, e2, e3, ... , en } , i.e. stack s1 has n elements now, and the last pushed was "en"
s2 = { x1, x2, ... , xm }, i.e. stack s2 has m elements at this moment and the last one is xm... As you'll see, we don't care about s2 contents.

Now let's review your code again, the function foo() receives two stacks (s1 and s2), one integer value num, and another integer value x.

s2.clear(); 
   for (int i = 0; i < num - 1; i++) 
      s2.push(s1.pop()))

First it clears stack s2 (meaning, remove all elements from s2), so now s2 has 0 elements, i.e. s2 = {} = EMPTY

After that, the function goes into a loop that is repeated from 0 to (num-1), that is "num" times...

What does it do?

s2.push(s1.pop()) ;

Well, it pushes into s2, whatever value is the last one on the s1 stack. Returning to our status of s1 and s2, s1 = { e1 ... en }, s2 = {}. After the first operation the status for both will be:
s1 = { e1, e2, e3, ... , en-2, en-1 } (remember that en-1 means the (n-1)th element e)
s2 = { en }

Why? If you don't see it clearly, then let's break this operation into its parts: the s1.pop() removes the last element in the stack ("en"), and returns it. The s2.push() pushes the element you give to it, which in this case is s1.pop() which is "en"...

If you repeat the operation (remember this operation is in a loop), the outome after the second iteration is:
s1 = { e1, e2, e3, ... , en-2 }
s2 = { en, en-1 }

And so on...

After num iterations we will have:

s1 = { e1, e2, e3, ... , en-num } (remember that en-num means the (n-num)th element e)
s2 = { en, ..., en-(num-1) }
how many elements does s2 stack have?  n - (n-(num-1)) + 1 = n - n + num -1 +1= num elements. This will help you visualize what the function has done up until now...

(If you have iterated num times, and each time you have pushed an element into s2, and you have popped an element from s1, then logically you will have "num" elements in s2, and "n-num" elements in s1, being n the number elements in s1 before the loop)

What has happened up to this moment??? Well, you can clearly see that this part of the function breaks s1 into two parts if you count the elements from the last one, from the last element until the "num"th element (s2), and from the "num+1"-th element until the first (s1).

int temp = s1.pop(); 
   s1.push(x);


What do you think these two lines do???

Well, they extract the last element of s1 and pushes a new element, the integer x into the s1 stack.

Thus practically this part replaces the en-num element in the stack with x. The "n-num"-th element of the stack is the "num+1"-th element in the stack if we count from the tail towards the head

The two remaining lines take care of "undoing" what the first loop did... but first let's see at the current stacks contents:

s1 = { e1, e2, ... , en-(num+1), x }
s2 = { en, en-1, ... , en-(num-1) }

while (!(s2.empty())) 
      s1.push(s2.pop());


This is just a loop that will execute as long as s2 has elements... and because each iteration does a pop on s2, (thus removing an element from s2), it will execute for the number of elements that are in s2, which has NUM elements...

The iterated line just pushes into s1 whatever it pops from s2... thus putting back s1 as it was originally. Let's check it:

After the first iteration, s1 and s2 will be:
s1 = { e1, e2, ... , en-(num+1), x , en-(num-1) }
s2 = { en, en-1, ... , en-(num-2) }
After the second iteration they will be:
s1 = { e1, e2, ... , en-(num+1), x , en-(num-1), en-(num-2) }
s2 = { en, en-1, ... , en-(num-3) }
And so on, until...
s1 = { e1, e2, ..., en-(num+1), x, en-(num-1), ..., en }
s2 = { }

So, we can conclude that this function takes a stack s1, and replaces its "num+1"-th element (counting starting from the last element in the stack) with the x value provided. The s2 stack provided to the function is used as temporary storage for this operation, and UNFORTUNATELY, is cleared after the operation so the information it might have had is lost...

Sow questions for you:
1) What happens if num is greater than the number of elements in s1 (it depends on the implementation of pop() )
2) Can you make a small adjustment to the function so that after returning it has achieved the same result on s1, HOWEVER, s2 contains the same elements it had before calling foo() ?


Now, regarding the other questions:
Question 2)
Which one is the correct answer?

    * 1,3,5,7,2,4,6,8
    * 7,5,3,1,2,4,6,8
    * 1,5,6,7,8,6,4,2
    * 7,5,3,1,8,6,4,2
    * 1,2,3,4,5,6,7,8


From the list above, which one is the stack after the first loop?

Question 3)Given a reference list to a linear linked list and three reference variables p, q and r, determing what the following
aloritham accomplishes

p = list
q = null
while p != null
r=q
q=p
p=p.getNext()
q.setNext(r)
list = q


Should be written:

p = list 
q = null 
while p != null  {
   r=q 
   q=p 
   p=p.getNext() 
   q.setNext(r) 
}
list = q


Or in the pseudo-code way to make clear that the loop executes those steps...

This algorithm clearly modifies the order of the list elements... HINT: Just think of the locations of p, q and r when traversing the list. Do you see that p is one step (node) ahead of q, and r is one step behind of q? What does setNext() tells you???

Question 4 is too easy to even discuss it here. It's already written in Question 3, and all you have to do is check the values (and not use q, or r)

I hope all this time I have dedicated here can really help you understand what you are studying. This part is not so difficult, and you'll really need it in the future.

Offline

  • Index
  • » Java
  • » Urgent Help needed please

Board footer

Powered by FluxBB