Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Help on Question

Posted on 2006-11-23
Medium Priority
266 Views
Hi,

I have the following question to answer but my text books are not breaking it down enough for me to understand, could anyone please let me know in more simple terms how to work it all out. I will supply the whole question so that you know what is being asked.
________________________________________________________________________
a specification of a function LASTAT is given below. In this, we number positions in the stack s from the top, so that the top item is at position 1, the item below this is at position 2, and so on. So for example, if s is the stack [5,4,3,4,33,22,11] then the item 11 is at position 1, the item 22 is at position 2 and so on.

In the specification below, the term 'last' is used  to refer to the occurence of num in s whose position os largest when numbered in this was

function LASTAT (s in Stack of Int, num in Int) return in Int
pre  true
post The returned value gives the position of the last occurence of num in s. If s is empty, or contains no copies of num, then the returned value is 0.

the questions are as follows

code in XImp is intended to implement LASTAT

function LASTAT(s,num)
{  /* XImp*/
var pos in Int
Var ret in Int
Var temp in Stack of Int
temp <-- s
for (pos <-- 0 to 4)
{
if (PEEK(temp) == num) then
{ ret <-- pos}
temp <-- POP(temp)
}
return ret
}

Q1.  If the stack s is [3,1,3,4,5] and num is 3, give a trace table giving the values of the variables pos, int, temp before and after the loop is entered, and after each execution of thebody of the loop

Q2. The trace in Q1 should show that XImp is not a correct implementation of LASTAT. Explain why the trace shows the implementation to be incorrect.

Q3.  Explain how XIMP might be modified to make it correct. show the changes that need to be made
____________________________________________________________________
As i said before I need some idiot notes as to how to answer this question, and i am not asking anyone to give me the answers unless they want to, but any help or information you can give will be grately recieved as I am desperate to understand this.

0
Question by:Max_AJApplegarth
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 2

LVL 1

Accepted Solution

gdepeute earned 1200 total points
ID: 18001849
Won't give you the answer indeed ... however, here is a pointer : LASTAT might not be working according to specification

You say : s is the stack [5,4,3,4,33,22,11] then the item 11 is at position 1 (remember... position ONE)
What happens when you run LASTAT(s, 11) ?
Since there is only one number 11 in the stack, it should return 1, not ? (like you said before)

When you run it through the code and build a trace table, you will see that LASTAT(s, 11) != 1 (although we were clearly expecting 1)

Point it, take a look at the how the stack is indexed (from the specification and the how the code behaves).
Probably you will see a mismatch (unless you gave us some incorrect information)

-- Geert

0

LVL 41

Assisted Solution

HonorGod earned 800 total points
ID: 18002788
One thing that might help is to redraw your stack, and add the position, or index associated with each value.
For example, instead of using a horizontal representation, change it to vertical:

7 :  5
6 :  4
5 :  3
4 :  4
3 : 33
2 : 22
1 : 11

The way stacks were explained to me (a long time ago, in a galaxy far far away), was that they act like a plate dispenser at the cafeteria.  A bunch of clean plates are "pushed" onto the stack, and then are available to be "popped", one at a time, for each customer.

Using this illustration, your stack (above), contains seven items (values).

As suggested by Geert, take the code, and "play computer".  For each variable that is declared, draw a box to hold it value, and write the variable name by the box.  For each statement in your routine, make the appropriate changes to your variable values, and see how these values change as the instructions are executed.
0

LVL 44

Expert Comment

ID: 18003109
big hint:  what is that significance of the HARD-CODED number 4 in this line of the prposed implementation:

for (pos <-- 0 to 4)

AW
0

LVL 41

Expert Comment

ID: 18159519
Thanks for the 'A', hopefully things are working out well for you. Good luck
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This is about my first experience with programming Arduino.
If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
Introduction to Processes
###### Suggested Courses
Course of the Month6 days, 13 hours left to enroll