Tues, 12 Nov 2019, 02:14 A couple of comments...

My students,

This will be a long email, but one I hope you will read in its entirety.

I understand that some of you are discouraged by your performance on the
program that was due last night.  Almost everyone turned in something, but
too many of you did not perform very well on it.  When I discussed the
situation with my TAs, they said most of you understand all the pieces but
you are hurting when it comes to putting the pieces together into a program.

The concept of linked lists and in particular putting all the pieces of a
program together to actually make it work are sufficiently important that
I am going to try to find some time after the second midterm to allow you
to take a second shot at the program.  I will start by having one of my
TAs do a review session where he will show you how to write the program.
Then I will give you some time (if you wish) to submit a second attempt at
PL3, with the understanding that if you do well on it, I will increase your
grade somewhat on PL3.  I will work out the details later.

Meanwhile a couple of things that are important.  First, no one writes a
serious program by just sitting down and cranking out instructions.  It takes
time to chew on the problem you are being asked to solve.  What is the input 
you are provided, what is the output desired?  What is the crux of the problem?
In the case of PL3, the crux was comparing the character string of a node
on one linked list with the character string of a node on the other linked
list.  If identical, remove the nodes from their respective lists, and insert
one of them on the third list.  What links need to be broken and what links
need to be established in order to remove the node from one list and put it on
another?  How do I systematically select nodes to be examined?  After all that
chewing on the problem, you are ready to throw away all your previous code
and start fresh on coming up with an algorithm to do the job.  Here is where
structured programming comes in.  First the initialization phase.  What all do
you need to solve this problem.  Pointers, of course.  A pointer to the first
node in each of the three lists (actually, in the case of the third list, a
pointer to its listhead since there are no nodes on the list yet) and a pointer
to the list heads of lists one and two that will needed to remove nodes from 
lists one and two.  Then you are ready to begin.  Iteration: you need to 
continue examining pairs of character strings until you are done.  What does
that mean?  Answer: you have two lists.  You will start with the first node
of the first list and compare the character string of that node with all the 
nodes of the second list until you have reached the end of that list.  Then 
you will move to the second node of the first list and compare its character 
string with all the nodes of the second list.  Then you will move to the third 
node and the fourth node until you have reached the end of the first list.  Each
time you find a match you remove that node from the two lists and add it to
the third list.  When you have finished comparing the last node of the first
list with all the nodes of the second list, you are done.

See if you can draw a flow chart using the three structured programming
constructs we studied in chapter six to exhibit what I have just described. 

The good news is that PL3 is the toughest programming lab in EE306.  You have
two more programs to write, and both you will find are easier to do than PL3.
So this is not the time to give up.

Second, some comments on today's lecture on Recursion.  I realize that you had
a lot coming at you at once today, and a lot of it was hard to grasp at first
gulp.  So, to relieve a little of the pressure, I want you to know that there
will be nothing on recursion on the exam next week.  However, recursion is too 
important a topic for me to NOT expose you to.  And too many instructors revel 
in its beauty and do not see the enormous degradation in its execution time.  
Given that we are operating at the level of the actual computer doing its actual
processing, I could not avoid trying to explain that degradation so you will
know that although recursion is a powerful expressive technique, it should not
be used unless you really need the expressive power of recursion to solve your
problem.  I have included in chapter 8 of the text book three problems.  The
first two (factorial and Fibonacci) are examples where recursion would result
in a disaster with respect to the time it takes to execute the programs. ...and
there are much simpler algorithms available to do the job without the enormous
penalty.  The third example, the MAZE, is an example of a problem where 
recursion can be used to great advantage since you can utilize its power by 
examining the problem from the top level and show how JSR to the MAZE from 
*inside* the MAZE subroutine can keep things well organized and allow you to 
manage the complexity without getting into what goes on inside each 
subsequent JSR call.

I realize that there was a lot there that was not easy for many of you to
grasp at its first look.  No matter.  You are aware of it.  You can look 
deeper when you have the time.  The three examples are laid out in detail
in Chapter 8 when you are ready to look at them.  And, I submit, you are
better prepared than you were before today in understanding that there is
a legitimate question each time you are presented with the choice of whether
to solve something recursively if you can, versus when some non-recursive
algorithm can be written when you do not need the expressive power of 
recursion.

Finally, I hope this very long email helps.  You have learned a lot in PL3
even if you did not get it to work, and you will have another chance to
demonstrate that.  You have a better sense of recursion than you had before
today.  And, most of all, this is not the time to give up.  You still have
two exams, two easier programs to write and a final exam to show that you 
should succeed in 306 and move on to 319K in January.

Good luck.


Yale Patt