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