* CMSC350 - Data Structures and Analysis [#h7353af6]

#contents

** Biography [#naf52121]

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.

** Week1 Topic1 [#g2a00865]

- Question

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?

- Answer

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.

** Week1 Topic2 [#dc492a56]

- Question

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. 

- Answer

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.

** Homework1 [#k057f850]

- Description

Do the following Exercises in Lewis and Chase (pp 24-25)
-- EX 2.1
-- EX 2.2
-- EX 2.3
-- EX 2.4
-- EX 2.5

** Week2 DQ1 [#a26711c2]

- Question

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

- Answer

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.

** Week2 DQ4 [#cef403c0]

- Question

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 - -

- Answer

(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

** Project1 [#q2f9f88c]

- Description

Do Programming Project PP 3.7 on pg 67 of Lewis and Chase. 

** Week3 DQ1 [#ue310d00]

- Question

Describe an interesting application/analogy of the linked list data structure. 

- Answer

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.

** Week3 DQ4 [#ye295ff8]

- Question

How does memory consumption vary between linked lists and arrays for storing n items?  

- Answer

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.

** Homework2 [#qf5d3b64]

- Description

Do the following Exercises in Lewis and Chase (pp 66 and 96)
-- EX 3.4
-- EX 3.5
-- EX 4.1
-- EX 4.2
-- EX 4.4
-- EX 4.5

** Week4 Topic1 [#of2b6dcc]

- Question

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. 

- Answer

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.

** Project2 [#qb4e1ceb]

- Description

Do Programming Project PP 6.14 on pg 182 of Lewis and Chase, implementing a doubly linked list class.
-- You will want to ask questions to clarify the requirements of this project.
-- You will want many test cases to make sure your program is behaving correctly.
-- I strongly suggest using a Spiral Development approach - this is a rather long program with lots of pieces.

** Week5 Topic1 [#i38577a1]

- Question

Describe an interesting application of recursion. Try to find applications outside our class. If you do, please give good citations.

- Answer

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.

** Week5 Topic4 [#ea6244f5]

- Question

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? 

- Answer

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;
 	}
 }

** Homework3 [#uade39c9]

- Description

Do ONE of the following Exercises in Lewis and Chase (pg 205)
-- EX 7.8 or
-- EX 7.10

** Week6 Topic3 [#gf59f251]

- Question

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).

- Answer

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).

** Week6 Topic5 [#w1968441]

- Question

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.

- Answer

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.

** Project3 [#kd91d8ad]

- Description

Do Programming Project PP 8.3 on pg 239 of Lewis and Chase, comparing sorting algorithms.
-- You should test these algorithms on a variety of lists - which can be just lists of integers.
-- Try some small lists, some large lists. I suggest creating lists of integers using the random number generator class java.util.Random.
-- Document your experiments and results.
-- You will want to ask questions to clarify the requirements of this project.
-- You will want many test cases to make sure your program is behaving correctly.
-- I strongly suggest using a Spiral Development approach - this is a rather long program with lots of pieces.

** Week7 DQ3 [#a973838b]

- Question

Given a specific node in binary search tree, how can you find the immediate larger element in the tree?

- Answer

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.

** Week7 DQ5 [#x402f0b1]

- Question

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. 

- Answer

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.

** Final Project [#h9be412f]

- Description

Do Programming Project PP 10.8 on pg 330 of Lewis and Chase, implementing the AVL algorithm on a binary search tree.
-- Start with the attached code: BinarySearchTreeND.java
-- We will compare my implementation with the one in the text in our weekly conferences.
-- Test your code with many test cases confirming that the AVL algorithm is indeed working correctly.
-- You will want to ask questions to clarify the requirements of this project.
-- You will want many test cases to make sure your program is behaving correctly.
-- I strongly suggest using a Spiral Development approach - this is a rather long program with lots of pieces.
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS