Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007
CoWeb Assignment 1
CoWeb Assignment 2
CoWeb Assignment 3
"Nil illegitimum carborundum."
CoWeb Assignment 1:
Implement a method in Squeak that will give you the nth Fibonacci number. For both 0 and 1, the Fibonacci number equals 1. From then on, the next in the series is simply the sum of the previous two in the series (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc.). Return an error when applicable. Your code should be based on good OO-style and be an efficient algorithm.
There are two basic methods of implementing the Fibonnaci Sequence: iteration and recursion. First, the long way, iteration:
"This method calcutes the nth Fibonacci's number using iteration."
| a b c |
(num < 0) ifTrue: [^self error: 'Non-negative integers only.'].
(num < 2) ifTrue: [^1].
a _ 1.
b _ 1.
2 to: num do: [:i |
c _ a + b.
a _ b.
b _ c.].
Pretty straight forward, slower than the other method though, recursion:
"This method calcutes the nth Fibonacci's number using recursion."
(num < 0) ifTrue: [^self error: 'Non-negative integers only.'].
(num < 2) ifTrue: [^1]
ifFalse: [^(self fibRecursion: (num - 1)) + (self fibRecursion: (num - 2))].
The following code solves the rainfall problem, which you may have seen in previous CS classes. For each line, describe what the Smalltalk code does. Be as specific as possible. In particular, what is data at the various points in the code?
| data onlyPositiveNumbers |
The two temporary variables, data and onlyPositiveNumbers are declared (but not initialized) in this line.
data := OrderedCollection withAll: #(1 2 3 -4 -5 'error' 6 -7 999 2).
Initializes the variable data as an OrderedCollection with the values given within the parentheses.
Note: the value 'error' is a string, unlike the rest of the values, which are numbers.
onlyPositiveNumbers := [:i | (i isKindOf: Number) and: [i positive]].
Initializes the variable onlyPositiveNumbers as a block (of code).
This paticular block tests the class and values of whatever it is used on.
data := data select: onlyPositiveNumbers.
Reassigns data to the values within itself that satisfy the block onlyPositiveNumbers.
Strangely enough, these values are the entries with data that are numbers greater than zero.
The variable data is now composed of 1, 2, 3, 6, 999, 2.
data := data copyUpTo: 999. "not including"
Reassigns data to a non-inclusive copy of data, stopping at the value 999.
The variable data is now composed of 1, 2, 3, 6.
Note: the code "not including" doesn't do anything, this is a comment.
Transcript show: data average
Calculates the average of the entries in data and prints it to the Transcript.
The sum of the entries is 12, and the displayed average is 3.
CoWeb Assignment 2:
Monticello: How do we use Monticello to manage group code?
Monticello is a built in component of Squeak that allows you to easily acess a repository. This guide will guide you through using Monticello one step at a time, including creating a repository.
Step 1: Creating a repository...
Monticello does not support the creation of a repository, that must be done on your own. The Monticello browser supports 4 primary types of repositories:
Note that Squeak supports 4 other repository types. However, one of the listed four will probably be the most convenient to use. In this walk-through, we will be using an HTTP repository. While you could set up your own site if you wanted, there is a very easy to use site already dedicated to this purpose.
Visit this site and create a user-name and a project: http://www.squeaksource.com
Step 2: Adding the repository to the Monticello browser...
After having created your repository, open the Monticello browser by red-clicking (that's a left-click for most of you) in the world and going to the open option. A little over half-way down, you should see the listing: Monticello Browser.
Now click the +Repository button (circled in red) on the top of the browser window and choose the HTTP option from the pop-up window. You should see this:
In the prompt, enter in the information for the location and username/password of the repository you created. You should now see a listing for it in the browser window.
Step 3: Adding a package to the repository...
Now, click the +Package button on the left and enter the name of the package you wish to work on with other team members. The package name shold now appear in the left window. Now select both the package name (on the left) and the repository name (on the right) and click the Save button. This adds the package to the repository where it can be downloaded by yourself and other people. This is also the button you use to commit your changes.
Step 4:Loading a package from the repository...
Select the desired repository and click the Open button on the right. This brings up a new window with all the packages inside the repository. You can see all the revisions and thier comments to each package by selecting them. Select the package and version you wish to load in, and click the Load button. Should you hapen to break your project and not be able to fix it, not an all together unlikely occurence, repeat these steps to replace your current code with the working code from the repository.
Step 5: Merging changes and submitting...
If you're an adventurous type person (like me), or if you just plain don't like your group members, you can skip to the next paragrpah. For those of you left: after you've finished whatever it is you wanted to do, go back to the Monticello browser and open the repository again. Select the package you've been working on and find the latest version of it. Sometimes the numbering can get messed up within the file names, so it's best to right click in the right window and select unchanged. This reorganizes the versions to match their order in the repository regardless of file name. For most systems, this puts the version in chronological order. Now, find and click the merge button and Squeak will bring up a window detailing all the changes it's about to load in. Take a careful look at these and ensure that they don't correspond to any of the methods you've been working in before continuing the merge.
If you've just skipped the last paragraph, I congratulate you and wish you a merry time among your soon to be angry group members. Go to the Monticello main browser window and select the package you wish to commit (it's marked by an asterisk). Now highlight the repository on the right and click the Save button. This brings up a window where you can enter a comment. Keep in mind that these comments are actually viewable, unlike the ones no one can ever find in regualr old CVS. It is also worth noting (for those of you who skipped the last paragraph) that is possible to change the filename in the upperwindow to include someone else's initials, or, for the truly sadistic, the version number as well.
CoWeb Assignment 3:
(Part A) What are the advantages and disadvantages to using garbage collection?
(Part B) Explain how reference counting works. Include an example.
- The primary function and largest advantage associated with garbage collection is that the collector frees the programmer from having to worry about deallocating memory space. Anyone who's worked with a language that requires the programmer to do his own memory managment, such as C, can attest that keeping track of this yourself takes up a significant amount of work which could be better spent on other tasks. As a by product of doing the work for the programmer, the garbage collector also helps prevent numerous runtime errors. Attempting to access memory that has already been deallocated is bad, and is something that a garbage collector prevents from occuring. Garbage collection also prevents memory leaks. One of the biggest drawbacks to garbage collection is the extra processor use required. Also, a garbage collector is not as effiecient as a proper, well set-up program that has its own deallocation included.
(Part C) Explain how mark and sweep works. Include an example.
- Reference counting is a very simplistic adaptation on memory managment. Each time a reference (or pointer) is made to a block of memory, a counter for that block is incremented. Similarly, the counter is decremented when the pointer is overwritten or lost. If, at any point, the counter reaches zero after being updated, the memory block is deallocated. While simple, this method is a bit inefficient since it requires the counter calues to be updated quite often. On a lesser scale, it also requires a bit more memory space for each block to store the counter itself.
- Example: Goldbomber is a character created at the begining of a round of Super Bomberman 2 (Count: 1). At the initialization of the round, he is added to the collection of players in the round (Count: 2). The initialization method ends and the game begins. The temp variable Goldbomber in the initialization function is lost (Count: 1). The game commences and lots of stuff gets blown up. At some point later, Goldbomber is attempting to kill Redbomber when Bluebomber deftly ninjas in and drops a bomb in Goldbombers only escape route. An interminable four seconds or so later, the kill method is called on Goldbomber and he is removed from the round's player collection (Count: 0). Goldbomber, now having a reference count of zero, is deallocated. Bluebomber runs off in victory to collect Goldbomber's dropped power-ups and Redbomber lives to fight another day.
(Part D) What problems of garbage collection do generational scavenging and “stop and copy” address? How do they address them?
- Mark and sweep is a method for scheduling deletion within a garbage collector. A small amount of bits (usually no more than a couple) are added to each block of memory specifying its current state. This allows the garbage collector to mark a block for later deletion. When the garbage collector does need to deallocate space, it simply goes back and deallocates anything marked. This method allows for either moving or non-moving collection strategies to be used at a later time.
- Example: Let's say a block of memory named Bobchu is referenced at some point during the program. After a couple million instructions, the program no longer has any references to Bobchu. Bobchu, now in exile and on the run, is caught by the garbage collector and branded a marked man. His bits are now set to reflect his condemned status. At some arbitrary time in the future, the garbage collector decides its time to go back and sweep away all the refuse. The collector goes through and deallocates all the marked blocks of memory. At this point, Bobchu still technically exists, but the computer has forgotten him and no one will ever visit him again. He will be overwritten and lost forever the next time his memory address is needed.
- Generational scavenging takes advantage of the infant mortality theory to cut down on the amount of processing power used by the collector. This theory is the observation that the most recently allocated clocks of memory are also the ones most likely to quickly lose all references pointing to it. The garbage collector divides memory into generations. Each new block is written into the newest generation of memory which is checked whenever the collector runs. When a generation is full, all the generations are aged and a new youngest generation is created. This allows the collector to watch those blocks of memory most likely to become unreachable while saving overall processing time. Should older generations begin to lose references and memory becomes low, a full mark and sweep collection is required.
- Stop and copy is garbage collection process by which all program execution is paused and the collector runs. This prevents any blocks losing references or being created while the collector runs. While the halt does simplify garbage collection, it's rare that this simplicity outweighs having the entire program stop for a time.
History of Object-Oriented Programming:
Pick two of the following four people and briefly describe one of their main contributions to object-oriented programming and design: Kent Beck, Ward Cunningham, Alan Kay, and Ivan Sutherland. (Note: Do not describe more than two.)
Ward Cunningham invented the first wiki, WikiWikiWeb. In addition, he also worked with Kent Beck to come up with the first CRC cards. He was also a pioneer in design patterns and Extreme Programming. The wiki is a website that is both viewable and editable within an internet browser. This site is a type of wiki. Another example of a wiki is http://www.wikipedia.org.
Ivan Edward Sutherland's most noticable achievment is the invention of Sketchpad. It changed the way people interacted with computers, and basically kicked off the ideas of computer-aided-drafting (CAD) and computer graphics. Sketchpad was essentiall ythe first GUI and it led to the beginnings of object-oriented programming.
Links to this Page