Solved

Help on Question

Posted on 2006-11-23
4
254 Views
Last Modified: 2010-04-16
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
Comment
Question by:Max_AJApplegarth
  • 2
4 Comments
 
LVL 1

Accepted Solution

by:
gdepeute earned 300 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

by:HonorGod
HonorGod earned 200 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

by:Arthur_Wood
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

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

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
scoresAverage challenge 8 76
sumHeights2  challenge 7 78
wordmultiple challenge 12 92
Help to convert powershell script into a gui 9 76
Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
A short article about problems I had with the new location API and permissions in Marshmallow
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now