updated 14 April 1999

Subject: Programming Assignment 1:

Good morning Mr. Stachour. I have been looking at the first programing
assignment and I have a few questions about it.
1) Should the searches be limited to the items known to be in the list? This
would apply to both the binary and sequential search.
==> The text indicates that the usual style is both present and absent
    items, unless indicated otherwise.
2) If we are to search for items known to be outside the list, should there be
a set number of these types of searches or should we let this occur randomly?
==> You need to decide what is best here.
3) Should the list be restricted to have only one occurance of a given
number/element? If not should the search terminate when the first occurance is
found?
==>  The text indicates that multiple items with the same key can happen.
     Your program needs to account for that possibility.

Subject: Random Number Generator for Assignment 1

     Question 1 - The handout says to "start by generating
 a set of random numbers and storing them in an array".
  Should this be a part of the code that is to be turned 
in?  The reason I am asking this is, in class on Tuesday, 
January 19, 1999 you stated that, "the data should 
be same for every test that is performed".  If this 
is true, having a random number generator in the code 
will generate new numbers every time the program is 
run.  I guess that right now I am a little confused. 
 If you could give me a little more information on 
what it is that your looking for, it would be greatly appreciated.
==>  Most random number generators work from a "seed".
     As long as they start everytime with the same seed,
     they will generate the same sequence of numbers.
     Most random number generators have some means to set the seed.
     For example, the ones in Ada in section A.5.2 has a procedure
     Reset taking two parameters:
       Gen :  [the generator which saves the state]
       Iniatiator: [ an integer to set the new state]
     So, if you Reset the generator with the sanem integer, say 10241,
     in your program *before* you use it, it will generate the same
     sequence every time.   I hope this is helpful.  
==>  By "the same every time", I was referring to the fact that
     your searching programs need to search the same list of numbers
     for the same targets.  If you seached using different lists, or
     different targets, then the data you got would probably not be
     directly comparable.  OK?
==>  The code that generates the random numbers and stores them
     in an array may be part of your program, but it does not have
     to be that way.  You might genrate the numbers one-time, write
     them into a file, and always read from the file.  If you take
     the approach, you (obviously) need to turn in the file also,
     otherwise your program would not be runnable by me.

Subject: ada95 installation

I tried to install ada95 on my PC which runs the Windows 95 operating 
system.  The install appears to work but only takes about 20 seconds.  I 
used the instructions shown on the green sheet handout named "Ada compiler 
installation instructions".  After the install, I see a directory "usr" 
with a few files and a bin subfolder containing cygwin.dll, gdb.exe, 
tcl76.dll and tk42.dll.  I do not see any program listed in my start 
programs menu for GNAT IDE .  Any idea what I am doing wrong?
==>  Are you sure that you are using the right name?  From what you
     indicate, it seems like you installed gdb (the debugger) instead
     of gnat/gcc (the compiler).  Please check the sheet.  Perhaps
     the name is wrong there.


I installed using the GNAT-3.10P1-nt.exe and everything looks good now. 
 The instructions show the file as GNAT-3.10P-nt without the "1" in the 
name.  You were correct that my first try used gdb-3.10P-nt which I assume 
is the debugger.  The instruction sheet shows the debugger as gdb_3-10.exe.
==> Thanks for finding the typo in the instructions.

Subject: Written Assignment 1

How much detail do you want in the writeup?
==> Enough to convince me that you did the assignment, like
    the tracking of the search.  You can draw pictures, write text,
    give formulas, whatever does the needed enderstanding.

Subject: Written Assignment 2, Ex 7.5, E2

> Question E.2 asks to solve in terms of the formula.  I 
> managed to derive the right answer, but I do not know 
> how to get the answer by solving in terms of the 
> formula.  I have read the section in the book about 3 
> times.  If you could give me a little direction it
> would be greatly appreciated.
One way is to use the formula to build a table:

      Sequential    Binary
N      [Formula]    [Formula]

1
2
3
4
5
etc

And in the table you put the values for the number of comparisions.

Subject: Translating Pascal to Ada.
I already know Pascal.  Can you give me hints about the differences
between the two languages?
==> I've put a file pas2ada.txt in this directory.  It gives some of
    the simple syntactic differences between the languages.
    This, together with the tuturial about Ada, should allow you
    to understand the "easy differences".  The power of Ada, such as
    ranges, concurrency, exceptions, time, packages, generics, comes
    with use.   Look at the examples in the expamples directory, and
    let me know of you have specific questions.
Subject: InsertList
I'm trying to compile the material from the textbook, and the
compiler compains that InsertList is an unknown identifier.
What goes?
==>  This is from the list package that you did last term.
     If you didn't do it, it is in the book.
     You need a command of the form "uses ListADT, Timer"
     if those are the two units you are trying to reuse.
     See the directory "c:\tp\*.tpu" for the units already there.
Subject: pascal units would not compile
I'm trying to compile in the units, but the pascal compiler can't find them.
What do I do next?
==>  Ensure that for the turbo Pascal in the lab, that the units area
     is set to "disk", and the directories have "a:\" for all 4 items.
     This will ensure that your units are found.
     Note: This problem regularly occurs in languages where the libary
     facilities are not built into the language.  You are not the first,
     nor will you be the last, to have this situation.  If you are in
     a language, e.g., Ada, where the libraries are part of the language,
     then you would find everything both on compile and link
Subject: Stack overflow when doing large recursive binary search
I got a stack overflow when I range the 10000 case in assignment 1.
You told us why, but I didn't get the var/val things.
Would you explain it again?
==>  Sure.  when one routine calls another, most compilers arrange
     to put the parameters on the stack.  If you put a big thing
     (like a 10000 element record of several words or more) on the
     stack each time you call, you can run out of stack space.
     Instead, you need to put a reference to the item there, which
     probably takes 1 word instead of 10000+.   
     In pascal, if you say "var" in a parameter defn, that means you
     want to udpate a variable, so it passes an address.  If you say
     nothing, it passes the values.
     In C, it always passes values. So in C, you need to describe that
     that variable definition is like
         contig_list_type *  clp
     instead of
         contig_list_type cl
     In Ada, you just write 
         cl : in contig_list_type
     and the compiler arranges to pass a read-only referenct automatically
     for you.

     The reality is that you need to consider not only the read/write/update
     behavious you want, but how the compiler pases it, in order to decide
     what to code.  Many pascal programmers always write "var" rather than
     analyze.  Many C programmers always pass pointers rather than analyze.

     But neither helps you to learn what really is needed for understanding.
     In this class, we will not be doing multi-level nested data structures,
     so you can usually get "the right answer" with var/address.
     But it's not good software engineering practice.
Subject: What to measure for assignement 2?
 If in the first assignment, we could use the comparison count as a
 timing method, what then should we use in the second assignment?  When
 comparing shell sort especially, the comparisons will be much higher
 than say the selection sort, but the actual moves may be much less.
 Depending on the size of the records being sorted, both of these factors
 will affect the time.  So we now have three variables.  I think it would
 be more conclusive to measure both moves and comparisons, rather than
 time, because both will have an effect on the time consumed depending on
 the implementation of the algorithms in real life. What do you think?
  ==> You are correct.  Here one really needs to measure both
       moves and comparisions.  I did indicate when talking about the
       assignment that such (moves & comparisions) would be needed thus
       two tables and  *not* to do clock-time / cpu-time for assignment 2.
Subject: my C program hangs before starting
When I try to declare my arrays with the full size needed by the
assignment, my program doesn't run.  When I do smaller arrays,
it works.  I've checked my parameter modes, and I am passing everything
by reference, so I'm not getting more things on the stack. 
I also tried several different memory models. lAny ideas?

==>  I suspect that your arrays are just "too big" to fit on the stack.
     If you chose the turbo C option to check for stack overflow,
     you will probably see a message about stack overflow.  To avoid
     this situation, you need to do move those large arrays off the stack.
     I suggest that you try:
       1) Declare them as static, thus moveing them from the stack.
       2) Declare the type in the record which is the element of the array 
          smaller, if that makes sense.
       3) Go to dynamic memory allocation using malloc.
       4) Write in a programming language, like Ada, that understands
          how to allocate package-level data so that the problem never
          happens.   :<)


Subject: word

    Well I am having a small problem with lab #3.  My 
program runs just fine when the data type is 'string'.
When I switch it to 'word' it compiles just fine, but
when I go to run the program it kicks back an error 
saying "ERROR 106: Invalid numeric fromat."  According
to the error message it says that the text file does not
conform to the proper format.  My dictionary file 
contains words in it, and the file I am checking is
words also.  So I am kind of confused on why I am 
getting this message.  Please help.

==>  In Pascal, "word" means a computer word, rather than
     a natural languge word. And words usually contain numbers,
     not characters.  What you need is a variable whose NAME
     is "word" and whose TYPE is "string".  However, since
     "word" is (I think) a reserved identifier in pascal, you
     probably can't use it as a name.  You probably want something
     such as:

   var
     Input_Word:      String;
     Dictionary_Word: String;

Subject: words

I want to be perfectly clear on the assignment.  I know that we have to catch
all the begins, ends, ifs, thens and etc, but what about the stuff in the
writelns?

You gave the example in class:

Begin
   A := lower + higher + 1;

and we are to get Begin, A, lower & higher and throw out the rest.

if we have a writeln statement do we get all of it or just the writeln?

writeln ('Are we suppose to get this?');

==>  Items in strings are not words.
     So all you need to get is the identifier/keyword "writeln"

Subject: Exactly what is the browse graphs assignment?

On the internet you need to go to www.seas.gwu.edu/student/jarc/idsv/.
Once at that URL, you need to:

  1. Login by entering your username. Please use the form msu-mn:YourName
  2. From the left-side pannel, select Graphs:Searches
  3. Read the data in the pannel about seraching graphs
  4. Select "Start Visualization" at the bottom right.
  5. This will bring up a visualization screen with a graph in it.
  6. Select either "Depth First" or "Bredth First" to watch a marked search.
  7. Then select the other one to watch the other style search.
  8. Then select "Make Graph" to make a different graph.
  9. Continue this pattern until you understand how the marking works.
  10. Then select "I'll try" from the right pannel.
  11. After the graph is drawn, select "Depth First" or "Bredth First" to do it yourself.
  12. Mark nodes one by one, watching the feedback you get inthe upper right corner.
  13. When you have done a bunch, select "Progress" from the loewr right corner.
  14. When progress indicates you have done enough, select "submit", and you are done.
  15. When progress indicates not enough done, close that window and continue the "make graph" traverse graph" pattern.
  16. If you'd like to see the code behind the traversals, click on the Ada code button.
  17. When you are ready to stop, select "Stop Visualization" from the main window at SEAS.