# CS1103 Discussion Post

## Discussion Unit2
When should you consider using recursive algorithms when writing a program?

Discuss in terms of advantages and disadvantages

### Recursion has these 2 properties:
After I read the textbook (Eck, 2019), I conclude that recursion should have the following properties:

1. can be divided into smaller sub-problems
2. the smallest sub-problems should be identified as the end of recursion

### What are the advantages of recursion?
Knowing the 2 properties of recursion, what benefits do they bring to us?

**1. It can solve complex problems in few lines of code**

Since recursion applies to problems that can be divided into smaller problems, it can simply solve these smaller sub-tasks using the same code, thus saving lots of lines that would be necessary with another solution.

**2. Elegant and simple solution to problems involved with reference to objects with same type**

Since data structures come in the form of objects, operating these structures will need the help of references. As we learned from CS1102, variables that objects are assigned to don't store the objects themselves but the references to them. When it comes to manipulating the data structures that involve referencing to other objects, recursion would come in handy.

For example, in section 9.2.3 of the textbook a recursive method to print a linked list in reverse order is introduced. The solution comes in no more than 10 lines:

public static void printReversed( Node head ) {
    if ( head == null ) {
        // Base case: The list is empty, and there is nothing to print.
        return;
    }
    else {
        // Recursive case: The list is non-empty.
        printReversed( head.next ); // Print strings from tail, in reverse order.
        System.out.println( head.item ); // Then print string from head node.
    }
}

### What are the disadvantages of recursion?

**1. Recursion requires more memory space to store the intermediate results**

Since recursion finds a solution by solving smaller sub-problems until the bases are met, the intermediate results need to be stored during the process (Collegenote, n.d.). This means recursion would need more memory space compared to non-recursive solutions.

**2. Recusrion can be difficult to understand or analyze**
Since recusrion is defined by itself in part, it can be difficult to understand what it is under the hood. When we tried to trace the excution results for each call of recursion, the whole process may not make much sense to us at a glance. Such an example is given when the author printed the output of TowersOfHanoi.java with simply 4 disks as input. It's difficult to follow the details inside the recursion.

**3. Generally recursion is slower than non-recursive solution**
Although recursion solution is usually simple and elegant, it is not always the best one. In many cases, recursion is slower than non-recursive solution. Common examples are: calculating Fibonacci series and computing factorials. These 2 problems can be sovled with a loop and the performance of both surpasses the recursion version.

An example of computing factorials with recursion and loop is given below. We can see that with loop the time of computing factorial of 10000 is less than 1 millisecond while with recursion it takes 1 millisecond. And experiment with larger number would lead to java.lang.StackOverflowError with recursion.

/**
 * @author Xuan-Huai, Weng
 * class Factorial compares the performance of computing factorial with recursion and loop 
 * Sample output
 * N: 10000
 * facotrialRecursion takes: 1.0
 * factorialLoop takes: 0.0
 */
public class Factorial {
	
	static int facotrialRecursion(int n) {
		if (n == 1) {
			return 1;
		}
		return n*facotrialRecursion(n-1);
	}
	
	static int factorialLoop(int n) {
		int result = 1;
		for(int i = 1; i <= n; i++) {
			result *= i;
		}
		return result;
	}
	public static void main(String[] args) {
		int N = 10000;
		System.out.println("N: " + N);
		double startTime = System.currentTimeMillis();
		facotrialRecursion(N);
		double runTime1 = System.currentTimeMillis() - startTime;
		System.out.println("facotrialRecursion takes: " + runTime1);
		
		startTime = System.currentTimeMillis();
		factorialLoop(N);
		double runTime2 = System.currentTimeMillis() - startTime;
		System.out.println("factorialLoop takes: " + runTime2);
	} 
}

**4. The system may run out of memory if the base cases are never met**
As mentioned above, one property of recursion is that it needs base cases as the smallest sub-problems. And with first disadvantage that recursion requires more memory space in mind, it's possible that the system runs out of memory before the recursion reaches the base cases, not to mention the case that if the recursion is not written appropriately, it will become infinite calls of itself.

**References**
Eck, D. J. (2019). Introduction to programming using Java, version 8.1. Hobart and William Smith College. http://math.hws.edu/javanotes.

Collegenote. (n.d.). Advantages/disadvantages of recursion. Advantages/Disadvantages of Recursion. Retrieved June 25, 2022, from https://www.collegenote.net/curriculum/data-structures-and-algorithms/41/454/

## Discussion unit 3
Using ADTs (abstract data types) has advantages for program modularity. Discuss

To start off the discussion of advantages for program modularity, let's look at the definitions of abstract data types and program modularity:

### Abstract data types (ADT):
The textbook defines data types as "a set of possible values and a set of operations on those values" (Eck, 2019) and abstract as "without any specification of how the values are to be represented or how the operations are to be implemented" (Eck, 2019). With that in mind, I find it very similar to what we have learned in the previous courses: interface. Then I found a related discussion on stackoverflow (Abstract data type and interface, 2013) and verified my idea. We can conclude that java's interfaces serve to implement ADTs. If you are interested in the diffeerence between interfaces and ADTs, you can check out the reference link.

### Program modularity
"Modular programming is the process of subdividing a computer program into separate sub-programs.(Techopedia, 2014)

According to the definition of modular programming, I conclude the following features of a modular program:

- Separate but easy to integrate
A module should be separate, or decoupled, from other components. This represents the reusability of a module: It can be used in whatever scenarios where it fits. Users don't need to know the implementation details but the behaviors of it.
- When changes are made internally in a module, it won't affect other components
It is another important characteristic of a module. A good module has a behavior contract that defines what it does. If there's any modifcations made to the implementation, it should be expected to behave in the same way so that it won't affect other components.

### Advantages ADTs have for program modularity

After the discussion of ADT and program modularity, it is intuitive to link both of them together. Here I list the advantages ADTs have for program modularity:

- Reusability
As ADT is a set of data values and a collection of operations defined on them, we can see that it has a behavior contract. Its operations are defined so that it can be applied to many programs where it promises to perform its functions. It can save developers lots of effort from rewriting the same code.

- Maintainability
Another benifit ADT can bring is that it is easy to debug and maintain the program. As we already know the behaviors of an ADT, whenever a bug happens, we can quickly locate where the problem could be. Also, due to the abstraction of ADT, we only need to focus on the logical errors that could lead to the bug. ADTs make programs much easier to maintain.

In conclusion, both reusability and maintainablitiy correspond to the features of modular programming. Thus it's not hard to see the advantages ADTs can bring to program modularity.

### references
Stack Overflow. (2013, October 8). Abstract data type and interface. Stack Overflow. Retrieved July 4, 2022, from https://stackoverflow.com/questions/19239471/abstract-data-type-and-interface#:~:text=The%20combination%20of%20data%20with,all%20methods%20are%20not%20implemented.

Techopedia. (2014, October 8). What is modular programming? - definition from Techopedia. Techopedia.com. Retrieved July 4, 2022, from https://www.techopedia.com/definition/25972/modular-programming

## Unit4
The class Object defines an *equals* method to compare objects.

Specify the advantages and disadvantages of using this method and suggest an alternative for equality.

The equals method of the class Object basically check what the == operator does: to check if the 2 object pointers point to the same address in the memroy. Thus by defualt, Object.equals is a reference comparator. After doing some research and look into the *equals* method, here I conclude its advantages and disadvantages:

### Advantages
1. Convenience
It is easy to use. Simply call the instance method *equals* and you can check the equality of 2 objects.
2. Polymorphism
Object.equals by defualt is a reference comparator. But in many cases, it is not practical when we want to compare the contents or the instance variables of objects. For example, when we compare 2 String objects, we actually want to compare their sequence of letters, rather than memory addresses. In such case, the *equals* method Object's subclasses must be overriden to adapt to user-defined equality. The polymorhpic *equals* method allows the comparison to be more **generic** in java. (Nero & Nero, 2019)
### Disadvantages
1. It is generally required to override *hashCode* method

To override the default *Object.equals* method, it's suggested to override both the *eqauls* and *hashCode* methods. this could be a disadvantage if the developer overlooks to override the hashCode method and cause problems in collection objects like HashSet, HashMap or HashTable, which reply on hashCode to function properly.

"If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same
integer result." (Java Platform SE 6)

Given the specification from the java document, if we override the *equals* method and didn't override *hashCode*, it's likely that we would have 2 objects that are eqaul but don't share the same hashcode. A problem that may be caused is having duplicate items in HashSet, which expects to have unique items only.

2. Equals method needs to obey the general contract

"The *equals* method implements an equivalence relation on non-null object references:

- It is reflexive: for any non-null reference value x, x.equals(x) should return true.
- It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
- It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
- It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified. For any non-null reference value x, x.equals(null) should return false." (Java Platform SE 6)

If an overidden *equals* method fails to follow any one of the rules above, there can be many possible ways to go wrong in the program. And it can also be hard to debug when the program gets bigger.

### Conclusion and alternatives for equality

So when to override the equals method? When the logical equality is different from the default one (reference equality). And there is no existing *equals* method overridden by the superclasses that have this logical equality. Examples like this often exist in value classes (Bloch & Shibata, 2008). For classes simly representing values, such as Date, Integer and String, it's often required to have an overidden *equals* method to compare the values logically.

### References
Nero, J. C. B. R. del, & Nero, R. del. (2019, August 22). Comparing java objects with equals() and Hashcode(). InfoWorld. Retrieved July 10, 2022, from https://www.infoworld.com/article/3305792/comparing-java-objects-with-equals-and-hashcode.html

Java Platform SE 6. (n.d.). Retrieved July 10, 2022, from https://docs.oracle.com/javase/6/docs/api/

Bloch, J., & Shibata, Y. (2008). Effective java. Piason Edukēshon.

https://stackoverflow.com/questions/8180430/how-to-override-equals-method-in-java

## Unit5
## When writing a data structure, what should be our guidelines for choosing the right Java Collection?

Under the Java collection interface, there are mainly 3 interfaces: Set, List and Queue, each of them are a kind of data structure and has differnet use cases. After study the chapter 10.2 and 10.3, here I will talk about their use guidelines to implement each of the interface.

### List

"A list consists of a sequence of items arranged in a linear order. A list has a definite order, but is not necessarily sorted into ascending order." (Eck, 2019, p.498)

From Eck's descripition, we see that list is a simple while fundamental data structure. In fact, all the sorting algorithms we learned so far serve to sort a list of items. There are 2 built-in classes from java.util that implement the List interface: *java.util.LinkedList* and *java.util.ArrayList*. Why do we bother to have 2 types of List? The answer is that there is no such one list that is efficient in all operations. So in the following discussion I will talk about the properties of LinkedList and ArrayList.
- LinkedList

We have learned LinkedList in the previous chapter. It is made up of nodes and pointers pointing to the nodes. Thanks to the pointer, operations like add and remove are more efficient than arrays in Java. Such operations have runtime of $\Theta$(1). On the other hand, add and remove item in a Java array requires moving the whole items up or down 1 position in the array, which is of runtime $\Theta$(n). This is when LinkedList comes handy: when **add and remove** operations are often performed.

- ArrayList

ArrayList comes efficent when accessing items is often conducted. It has runtime of $\Theta$(1). In contrast, LinkedList has runtime of $O$(n) to access items because it has to traverse among items using pointers. Moreover, ArrayList has an advantage of dynamic size over Java array. Thus, use ArrayList when **random access** is used more heavily than add and remove operations.

### Set
"A set is a collection that has no duplicate entries. The elements of a set might or might not be arranged into some definite order." (Eck, 2019, p.498)

The most significant differnece between List and Set is that Set **doesn't have duplicate items.** Thus it is easy for us to decide when to use Set instead of List. In contrast to List, Set has operations like mathematic set operations: **intersection**, **difference** and **union**. In Java there are 2 classes implementing the Set interface: *java.util.TreeSet* and *java.util.HashSet*.

- java.util.TreeSet

TreeSet is implemented as a self-balancing binary search tree.(TreeSet in Java 2022) Thus, items in TreeSet are sorted in ascending order. Also, thanks to its balanced structure, inserting, deleting and searching are efficient with runtime of $\Theta$(log(n)). Eck suggests using TreeSet if the self-sorting property is needed.

- java.util.HashSet

By sotring items in hash table, HashSet is more efficient in finding, adding and removing than TreeSet. It has runtime of $O$(1) for those operations. (HashSet in Java 2022) Eck suggests using hashSet when elements are not comparable (since it does not sort items.), or when order is not important, or when efficiency matters.

### Queue

Queue is a list-like data structure. In contrast to List, it has a **"first in, first out" (FIFO) property**. We have learned this in the previous chapter. This property marks the biggest differnce between a normal list and it also has common use cases in scheduling problems. (Applications of queue data structure 2022) In java PriorityQueue implements the Queue interface:

- PriorityQueue

In addition to the FIFO property, the items in PriorityQueue also are assigned a **certain priority** that decides their order. With the both properties, the remove operation gives us the item with the minimum priority. PriorityQueue is implemented using heap data structure (we haven't learned it yet) that allows remove and add operations to have runtime of $\Theta$(log(n)) (Priorityqueue in Java 2022). As mentioned before, queue is widely applied to solve scheduling problems. Eck gives an example of using priority queue to solve computer's job scheduling problem. (Eck, 2019, p.506)

In addition to these 3 data structures above, there is also the Map data structure that has items in form of (key, value) pairs. However, due to the differnet properties that (key, value) pair has, Map does not implement Collection inteface. It does not implement all the operations of Collection, either. So I did not discuss it in this post. Yet it is still an important data structure.

### References

Eck, D. J. (2019). Introduction to programming using Java, version 8.1. Hobart and William Smith College. http://math.hws.edu/javanotes.

TreeSet in Java. GeeksforGeeks. (2022, July 7). Retrieved July 17, 2022, from https://www.geeksforgeeks.org/treeset-in-java-with-examples/

HashSet in Java. GeeksforGeeks. (2022, July 7). Retrieved July 17, 2022, from https://www.geeksforgeeks.org/hashset-in-java/

Applications of queue data structure. GeeksforGeeks. (2022, June 17). Retrieved July 17, 2022, from https://www.geeksforgeeks.org/applications-of-queue-data-structure/

Priorityqueue in Java. GeeksforGeeks. (2022, July 7). Retrieved July 17, 2022, from https://www.geeksforgeeks.org/priority-queue-class-in-java/

- map
like generilzed array. the indexed not defined for only integers but any objects of a specified type. It's also called "associative map". Also can be considered a set of associations (key /value pair)

use case:
- TreeMap
keys are sorted in ascending order
needs to implement comparable or comparator
- HashMap
needs to have equals and hashCode method overridden
more efficient than TreeMap unless there is need for ordering

## Unit6
What are the differences of handling Socket and ServerSocket ?

After reading the chapter 11.4 of the textbok (Eck, 2019), here I try to give a comparative introduction of Socket and ServerSocket along with thier differences:

### The Server/Client model

Before we talk about sockets, I would like to briefly introduce the Server/Client model as this is important in understading the differnce between a ServerSocket and Socket:

In chapter 11.4.2, Eck says that TCP/IP is abbreviated form for Tansmission Control Protocol and the Internet Protocol. For 2 programs to communicate with TCP/IP, each of them should create a socket and have both sockets connected. Moreover, each of the socket has its input and output stream. The data written into an output stream is delivered to the other's input stream. In this scenario, the socket waiting to be connected is called a **server socket**. And the program that creates it is called a **server**. On the other hand, the programm that connects to the server is called a **client** and its socket is called a **client socket**. This secnario is know as the sercver/client model.

By the way, for those who may find the word "socket" confusing, you can think of a socket as an abstraction serving to connect one program to another. As Eck describes, a socket "comes from an image of physically plugging a wire into a computer to eastablish a connection to a netwrok." (Eck, 2019, p.575)

### ServerSocket

In Java's imlementation of TCP/IP connections, there are 2 classes from the **java.net** package: **ServerSocket** and **Socket**. As described before, ServerSocket is a socket waiting(or listening, optionally) to receive connection requests from client sockets. **The main difference** is that a ServerSocket itself **does not take part in the connections**. All it does is listening for the requests and creates sockets accordingly to process connections.

To create a ServerSocket, we need to specify the port where it will be running. A port number is a 16-bit positive integer. It is used to make multiple network connections possible on a computer. Thus, from the textbook, the use of ServerSocket is illustrated below (Eck, 2019, p.580):

try {
    ServerSocket server = new ServerSocket(1728);
    while (true) {
        Socket connection = server.accept();
        provideService(connection);
    }
}
catch (IOException e) {
    System.out.println("Server shut down with error: " + e);
}

Note that a port number 1728 is speciified to create the ServerSocket server object. And afterwards, a while loop is created to keelp listening to connection requests. When the **accept()** method is called, it will return a Socket object if a request is received, or throw an exception if errors occur. Then we can use this Socket object, connection, to provide the what this server is meant to do. The **provideService** is a user-defined method that implement the service.

### Socket

On the other hand, to create a Socket object, both the server computer and a port number specifiying where the server is located are required. The server computer can be specified by either its IP address or its domain name. After a Socket is initialized, we can use its 2 methods: **getInputStream()** and **getOutPutStream()** to communicate over the connection. A code snippet of using Socket on a client side can also be found in the textbook (Eck, 2019, p.581):

void doClientConnection(String computerName, int serverPort) {
    Socket connection;
    InputStream in;
    OutputStream out;
    try {
        connection = new Socket(computerName,serverPort);
        in = connection.getInputStream();
        out = connection.getOutputStream();
    }
    catch (IOException e) {
        System.out.println(
        "Attempt to create connection failed with error: " + e);
        return;
    }
    .
    . // Use the streams, in and out, to communicate with the server.
    .
    try {
        connection.close();
            // (Alternatively, you might depend on the server
            // to close the connection.)
    }
    catch (IOException e) {
    }
} // end doClientConnection()

In conclusion, in the Server/Client model, ServerSocket is used on the server side to create a listening socket that waits for connection requests. It does not really participate in the connections because it creates Socket objects to process the connection requests when they are recieved. On the other hand, Socket
implements the input and output stream methods to allow the communications over a connection.

### References

Eck, D. J. (2019). Introduction to programming using Java, version 8.1. Hobart and William Smith College. http://math.hws.edu/javanotes.

## Unit 7

The Model-View-Controller design pattern decouples data access, business logic, data presentation, and user interaction. Discuss.

After reading the chapter 13.4.1, 13.4.2 and 13.4.3 of the textbook(Eck ,2019), here I will summarize and introduce the origin of MVC and its ideas.

### A little history of MVC
The MVC design pattern is believed to be introduced in 1979 by a Norwegian computer scientist, Trygve Reenskaug (Wilkins, 2021). It was firstly used in SmallTalk, which is also discussed by Eck in the chapter of generic programming of the textbook. According to Wilkins, MVC design pattern was popular for desktop application in 1980s. And in the 1990s, it became trendy with web applications, too.

Why do we need MVC? Eck says that MVC implements an important principle of object-oriented programming -- division of responsibilities. An object should have clearly defined role and responsibilities. As this chapter focuses on the MVC patterns adopted by GUI programming in Java, in the following discussion I will also use the context in the textbook:

### Model
In a scenario where MVC design pattern is applied to an application (or a component in the context of the textbook), model manages the data logic and store data behind it.

In GUI programming, view needs to consult model to get the data and render it as presentation. Due to the idea of division of responsibility, the data should be stored in another model object. And when model data changes, the view should be able to adjust accordingly to reflect the model change. And we have learned that it is done with events and listeners in GUI programming.
### View
View is probably the simlper concept to understand: it is the part of the application/component that users see on the screen.

In GUI programming, Eck says that view object registers itself as a listener for the events generated by the model objects. When model data changes, an event is generated and will be delivered to the view. Finally, the view will update the visual presentation on the screen accordingly.
### Controller
Controller can be considered the brain of the application/component whose job is to serve as the bridge between view and model and commnunicate with them.

Although controller's responsibilities are clear in the definition above, Eck says that it is not that clearly defined in the Swing components because its responsibilities exist in many objects. They might be the mouse or keyboard listeners that are in charge of processing users' events from the view. It is noted in the textbook that generally the controller responds to the user events by modifying the model. And as a result the view is modified in response to the changes to the model.

### Conclusion

After introducing each of the MVC ideas, here I provided a visualization of how MVC components interact with each other (MVC - MDN Web Docs Glossary: Definitions of Web-related terms: MDN)

MVC design patterns are adopted widely in Java's GUI programming package, Swing. There are many examples in the textbook, such as JButton, JList and JTable. It is interesting and important to learn how MVC is implemented in these components. And after reading this chapter, I came to realize why MVC is required in developing services or applications.

### References
Eck, D. J. (2019). Introduction to programming using Java, version 8.1. Hobart and William Smith College. http://math.hws.edu/javanotes.

Wilkins, J. (2021, September 24). MVC Architecture – what is a model view controller framework? freeCodeCamp.org. Retrieved July 31, 2022, from https://www.freecodecamp.org/news/mvc-architecture-what-is-a-model-view-controller-framework/#:~:text=The%20MVC%20pattern%20was%20first,the%20programming%20language%20Small%20Talk.

MVC - MDN Web Docs Glossary: Definitions of Web-related terms: MDN. MDN Web Docs Glossary: Definitions of Web-related terms | MDN. (n.d.). Retrieved July 31, 2022, from https://developer.mozilla.org/en-US/docs/Glossary/MVC

## Unit8

When developing new software, we should take into account how to create a specific "Look and Feel" per customer. What are the advantages of using Java GUI?

It is the first time that I heard the term "Look and Feel". After reading Oracle's tutorial (How to set the look and feel), I came to learn that the "Look" refers to the appearance of GUI widgets (JComponents) and "feel" refers to the way the widgets behave.

With that in mind, let's look at the advantages of Java GUI porgramming. There are 3 GUI programming packages we learned in Java: AWT, SWING and SWT (Advantages and disadvantages of AWT/Swing/SWT in Java Gui Programming). Here I will summarize the introduction of these 3 packages in the article:

### AWT
AWT stands for "Abstraction Windows Toolkit". Due to Java's philosophy of "compile once, run everywhere", AWT's graphics capabilities are confined to the common graphical functions shared among general operating systems. It mainly has the following advantages:

1. Robust: they rarely crash, especially in non-desktop environments.
2. Fast response: The local components are rendered by the operating systems.

### Swing
Swing is built on AWT and serves to solve the shortcomings of AWT. It has the functionality of AWT and expand it as improvement. It is considered the most powerful GUI package. The advantages of Swing:

1. Rich components: Swing provides a big collection of standard components that come with great scalibility. In addition to standard components, it also provides many third-party components, either commerical or open-source.
2. Rich compenent features: Swing not onlt provides the features that a component shars across platforms, but also has additional features specific to a platform.
3. Good API model support: As we learned in the previous lesson, Swing follows MVC desgin, which provides great flexibility and scalibility during the years of evolution.

### SWT
SWT stands for "Standard Widgettoolkit". It is developed by IBM in the hope to solve the problems that AWT and Swing have with bringing the advantages of both. It can be considered the combination of AWT and Swing. So the advantages of SWT basically are a collection of those mentioned above: Rich components, Rich component features and faster response time. However, note that it is still not in the standard library of the JRE, nor is it robust across platforms.

### References

How to set the look and feel. How to Set the Look and Feel (The Java™ Tutorials > Creating a GUI With Swing > Modifying the Look and Feel). (n.d.). Retrieved August 10, 2022, from https://docs.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html

Advantages and disadvantages of AWT/Swing/SWT in Java Gui Programming. (n.d.). Retrieved August 10, 2022, from https://topic.alibabacloud.com/a/advantages-and-disadvantages-of-awtswingswt-in-java-gui-programming_1_27_30391034.html