![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
My name is Yuji Shimojo and I'm 24. I'm from Okinawa, Japan and live there now. I have parents and an older brother.
This class is required to obtain my B.S. in Computer Science.
I'm currently in charge of data center sales and web direction at an IT company based in Okinawa. I'm aiming to enhance my sales engineer career.
Actually, I used to study in Information Engineering at University of the Ryukyus in Okinawa until 3 years ago, and there I've taken a class in data structures and algorithms. I took CMIS242 and CMSC335 in this Spring term. Through these classes, I learned ArrayList, LinkedList, Stack, Queue, HashMap in Java.
My hobby is to play a lots of sports.
I am using Eclipse Indigo on Mac OS X Snow Leopard (10.6). I really hope to enjoy learning in this class.
In addition to time complexity, there are several other factors like CPU speed, compiler optimization, memory access speed, & data input efficiency. Based on your understanding, which one is most important? Why?
For PCs, memory access speed is the most important, because what users expect the most is high multitasking performance.
On the other hand, for servers, data input efficiency is the most important, especially for database systems. If there is a disk I/O bottleneck on a system, its performance will be decreasing significantly.
Of course, CPU is important as well, but I think CPU performance can not only be measured by clock speeds. It depends on CPU architectures due to differences in vendors.
Chapter 1 discusses 'Software Quality' related topics in detail. Do not look at it right now :-) When you hear the term 'Software Quality', what comes to your mind right away? Explain in your own words.
From the aspect of "Software Quality" for business, you should include not only highly functional programs, but also well-written software design documents such as class diagrams, table definitions, ER diagrams, wire frames, also test data and test cases.
Do the following Exercises in Lewis and Chase (pp 24-25)
As listed under Course Content, I developed the following multimedia tutorial/lecture on inheritance & polymorphism. Turn ON your speakers to hear the audio before opening these links in a new tab to play these Flash videos:
http://sites.google.com/site/jeyak7/inheritance1.swf (Part 1)
http://sites.google.com/site/jeyak7/inheritance2.swf (Part 2)
You can find the PowerPoint presentation and code in this zip:
http://sites.google.com/site/jeyak7/inheritance.zip
Give an example where polymorphism is appropriate, and explain why you think it is a reasonable example. No need for code here, just the names of a few classes and at least one polymorphic method. You may find it helpful to consider some fields (attributes, instance variables) that are common to a parent class, and some others that are unique to each child class. This will require at least one parent and two child classes.
You may find the following presentations helpful too - they are focused on interfaces, but cover many other aspects of Java programming along the way:
http://sandsduchon.org/duchon/interfaces/InterfacesPart1.pdf
http://sandsduchon.org/duchon/interfaces/InterfacesPart2.pdf
http://sandsduchon.org/duchon/math/trees.html
http://sandsduchon.org/duchon/jdk/Java-Exceptions.html
Polymorphism is a mechanism in object-oriented programming that enables to the programmer to send a message to objects but make them work differently as a function of each objects. The advantage of using polymorphism is that the programmer doesn't have to modify the caller method to change the program behaviors.
For example, if there are three classes named Shape, Rectangle, and Triangle, and Shape is the parent of other two classes, polymorphism is utilized. If you want to calculate the area of them, you can define a getArea method in Shape class as an abstract method. The function of this method is only to draw. Then, you can define another getArea methods, in which are implemented detailed functions, in Rectangle and Triangle class.
Method overloading is one of the most important functions to work polymorphism that is to define two or more methods of a same name with a different return value and number/type of arguments within the same class.
Evaluate the following postfix expressions, then create one of your own and evaluate that also.
8 7 6 5 - - -
8 7 - 6 5 - -
8 7 - 6 - 5 -
8 7 6 - - 5 -
8 7 6 - 5 - -
(1) 8 7 6 5 - - -
= 8 7 1 - -
= 8 6 -
= 2
(2) 8 7 - 6 5 - -
= 1 6 5 - -
= 1 1 -
= 0
(3) 8 7 - 6 - 5 -
= 1 6 - 5 -
= -5 5 -
= -10
(4) 8 7 6 - - 5 -
= 8 1 - 5 -
= 7 5 -
= 2
(5) 8 7 6 - 5 - - = 8 1 5 - - = 8 -4 - = 12
Here is my own:
3 4 + 6 2 - * 4 /
= 7 6 2 - * 4 /
= 7 4 * 4 /
= 28 4 /
= 7
Do Programming Project PP 3.7 on pg 67 of Lewis and Chase.
Describe an interesting application/analogy of the linked list data structure.
LinkedList is suited for a FIFO (queue) data structure, because when inserting an element into a LinkedList, it is not reallocated elements unlike ArrayList. Queue is utilized for such as waiting print jobs of a network printer on a LAN.
How does memory consumption vary between linked lists and arrays for storing n items?
According to an article by Chris Bailey, Java Service Architect, IBM, if you compare an array list and a linked list, an array list's memory consumption is 4 bytes per entry, and a linked list's memory consumption is 24 bytes per entry because each its entry needs both value area and address area.
Incidentally, an array list reserves more memory area than a linked list does initially. Because an array list creates ten entries, although a linked list does an entry initially.
Do the following Exercises in Lewis and Chase (pp 66 and 96)
Describe a real-world scenario or an interesting application of the stack (LIFO) data structure. Try to write something new, instead of repeating popular ones already posted in the forum.
An example of stack is Tetris game, which is one of the most popular computer games in the world. When you fit falling pieces of blocks in suitable place, blocks will disappear in order from the top.
Do Programming Project PP 6.14 on pg 182 of Lewis and Chase, implementing a doubly linked list class.
Describe an interesting application of recursion. Try to find applications outside our class. If you do, please give good citations.
An example of a recursive function is DNS (Domain Name System) resolvers. A DNS resolver sends queries to DNS name servers recursively in order to find out DNS resource records for a specific domain.
Here is the equation to compute nth Fibonacci number fib(n) where:
fib(n) = 1, if n = 1 or 2
= fib(n-1) + fib(n-2) when n > 2
Implement a recursive solution based on this equation. What is the time complexity? Is it possible to write more optimal iterative version? What is the time complexity?
Time complexity for recursive solution is (2^n) and for iterative solution is O(n). My code is as below.
public class FibonacciCalculator {
// Recursive solution
public int recurseFib(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return recurseFib(n-1) + recurseFib(n-2);
}
}
// Iterative solution
public int iterateFib(int n) {
int f0 = 0;
int f1 = 1;
int f2 = 1;
if (n == 0) {
return f0;
} else if (n == 1) {
return f1;
} else if (n ==2) {
return f2;
} else {
for(int i = 2; i < n; i++) {
f0 = f1;
f1 = f2;
f2 = f1 + f0;
}
}
return f2;
}
}
Do ONE of the following Exercises in Lewis and Chase (pg 205)
Which sorting algorithm is the most useful one, when the input elements are already almost sorted? Let us define the problem more precisely: Let us say we have an input array of n elements. Each element's position in the input array is guaranteed to be maximum k positions away from its sorted position in the output array. Let us assume k is very small compared to n. Which algorithm is the best for this scenario? Feel free to make a few minor changes to any algorithm to improve the efficiency. Hint: Algorithm should run in O(kn) time (since k is a constant, it is really O(n) time).
I also agree with the idea that the insertion sort is the most useful on small or almost sorted lists because it compares elements in order from the front. Conversely, the worst case time complexity when the list is in descending order is O(n^2).
Quick Sort has the worst case time complexity of O(n2) while the average case time complexity is O(n log n). Do a limited research in the web and explain about it in your own words.
The reason why average time complexity of Quick Sort is O(n log n) is that the number of elements in divided groups decrease at a rapid rate. It will averagely be half every time items are divided. When the number becomes one, the sort is finished. If the number would be half every time dividing into m groups, the number of groups would be n/2m. When n/2m is one, m is log2n.
Do Programming Project PP 8.3 on pg 239 of Lewis and Chase, comparing sorting algorithms.
Given a specific node in binary search tree, how can you find the immediate larger element in the tree?
To find the immediate larger node in binary search tree, you should look at the right child of the given node. This is because a property of BST, that a node should be smaller than the right child of it and larger than the left child of it.
Details of various operations in AVL trees and Red/Black trees can make your head spin :-( What is so special about these trees that makes them better than plan binary search trees? Try to give a simple explain in your own words.
In an AVL tree, height difference between the right children and the left children is up to 1.
In a Red/Black tree, all the nodes are red or black. The root node is black. All the children of red nodes are black and all the parents of red nodes are black conversely. It should have the same numbers of black nodes from the root to any nodes which don't have a child.
Both of the trees are self-balancing binary search trees, which make more efficient to search than standard binary search trees.
Do Programming Project PP 10.8 on pg 330 of Lewis and Chase, implementing the AVL algorithm on a binary search tree.
