Java Exercise: Problems in Searching

Array is a fundamental data structure in Java programming language. It stores a fixed number of items, and we can use index to access each element.

The following 7 exercises are about searching and sorting an array.

Exercise 1

To find the occurrence of a number, I used a for loop to go through the array. Using the parameter key, I can use a if statement to check if the desired element is found and increment the integer variable “occurrence.”

Exercise 2

As the description suggests, we need to find the duplicate elements. Given an unsorted array, I used a inner loop, which starts from the index+1 of the outer loop. In the inner loop, is duplicate element is found once, the program will print the duplicate elements. This prevent the program to print the same duplicate element for more than one times (e.g. if 3 appears 2 times, the program won’t print two “3”s).

Exercise 3

To find the element which appears maximum times, I used an inner loop again to record the occurrence of each number. By comparing the temporary occurrence to the former maximum value, I can record that index and return it. Note that any time a number with the same max occurrence is found, the index will be overwritten.

Exercise 4

Since one element is missing in the sorted array, I just calculated the desired sum by incrementing a variable inside the loop. Then, I subtract the sum of the array elements from the desired sum (with the missing one), and the missing element is shown.

Exercise 5

For this exercise, I still used two loops with the second one starting from the index+1 of the first loop. In the inner loop, I used an if conditional statement: if the sum equals the desired value, the two elements are returned. I also found out that the flag “found” is useless because I print every pairs each time I checked them. Also, since the inner loop begins at i+1, there will be no duplicated pairs.

Exercise 6

To separate the even and odd numbers, I create a new array “separated,” which has the same length as the argument. The mechanism is that each time I find an even number, I put it from the beginning, and each time I find an odd number, I put it from the last spot. I use a and b to be the current available spot for even and odd number respectively. Also, I increment i to loop through the argument array. Since there are three indexes, I used a while loop to simplify the loop. For example, when a new odd number is inserted, I will count down the value of b.

Exercise 7

This question asks me to find the max and min value and return both the index and value. So I will first create the temporary max and min value, then loop through the array to compare the current max and min with the current value, then find out the actual max and min index. Then, I print them using the required format.

Output from the Testing Program

Here is a testing program I wrote in a main method. It shows that everything works fine. To conclude, when doing this kind of programming question, we need to know how many loops we are going to use and then identify how we will increment the index. We may also consider whether we should use flags or additional temporary arrays.

 

MIT Deep Learning & Autonomous Cars

Cars as autonomous agents



This simple diagram perfect depicts an autonomous agent (e.g. Autonomous car). It lives in the environment, perceive by sensors, do action by effectors.

There are 3 types of tasks

* Formal tasks

* Expert tasks

* Mundane tasks

They are arranged from the easiest to the most difficult for AI. In order to know which task driving is, we need to analyze how autonomous cars work.



Using these sensors, an autonomous car need to be able to the following tasks. The first one is localization and mapping. It essential means that cars need to know where themselves are as regard to the environment. The second one is scene understanding: What is the environment like? Is there a tree or a dog in front of the car? Thirdly, a car need to do movement planning, meaning that it needs to know how to travel from point A to point B. The last one is driver state, which is the understanding of the driver’s action.



Here is the block diagram for the autonomous cars as atonomous agents.

Neural Network

Neural network has the same meaning as deep learning.

It is inspired by neuron, the building block for the brain. And the corresponding thing in deep learning is a perceptron. It has three steps of processing data:

1. weigh

2. sum up

3. activate

In a neural network, many perceptrons are linked together to form a network. Sometimes, there are one hidden layer between the input and output, and sometimes there are multiple layers if the problem is very complex. More layers require more calculation power, so it is usually a hard question for people to manually set the number of perceptron and the amount of layers of them.

There are many different types of neural networks, including deep neural network (DNN), recurrent neural networks (RNN), and convolutional neural network (CNN).

Retrieved from sohu.com



CNN is usually used for image analysis, because it is good to analyze two dimensional data set and it is very efficient in finding the features of the image. The most useful application of CNN maybe object detection. By extracting the features of a certain image, the algorithm can identify the possibility that something belongs to a certain object.

Deep Learning & Autonomous Cars

Google’s Way. Retrieved from waymo.com



Thanks to the advanced machine learning algorithm, autonomous cars can perceives the environment better.

As an autonomous agent, a car must perceive the environment accurately and know where it is. The image got by the sensors can be analyzed in the micro-processor, which is equipped with deep learning algorithms like CNN. Then, as the objects near the car are detected, the car can then calculate the path to avoid crash.

However, there are some disadvantage of using machine learning algorithms. Firstly, it requires tons of data, which is time consuming. Also, if it is a self-learning algorithm, like reinforcement learning, human might not understand the logic behind the cars’ decisions, thus being unable to avoid errors. Moreover, object detection algorithm is easily fooled. For example, in the video, the algorithm mistakenly identifies some unrecognizable pictures as other objects because of the noise added to the picture.

Retrieved from a blog from OpenAI



This might lead to safety issues if the car mistakenly categorized the objects beside it. Also, people may attach the AI by using an adversarial input. Therefore, to conclude, autonomous car should still improve its algorithm and try to avoid safety issue before it can be used in every life.

Abstract and Polymorphism

Abstract Class and Methods

Abstract classes are classes that have at least one abstract method. An abstract method is a method that is not implemented.

Here is an example of an abstract method:

public void draw(Graphics g);

In this method, you should not write the {} after the method’s signature.

In an abstract class, there must be at least one abstract method. Reversely, if there is an abstract method in a class, the class is also abstract.

Here is an picture of the class card of an abstract class.



Remember the title should be italic.

In addition, because the class is not complete implemented, it cannot instantiate objects. Also, if a class inherits from an abstract class, it must implement all the abstract methods in the super class.

In conclusion, an abstract class is used as a “template” for subclasses. Since the subclasses are forced to implement the abstract methods, the proper functions that a subclass must have are ensured.

Polymorphism

Polymorphism used to be an very abstract term for me. It means the state of having multiple forms. After having CS class, I know that this concept is truly abstract: Subclasses can have some unique functionalities while sharing the same functions with the parent class.



http://www.byte-notes.com/sites/default/files/field/image/plymorphism-in-C%2B%2B.jpg

The advantages are as follows:

* we can treat the objects of the subclass as the objects of the same parent class. For example, the draw methods that draw different shapes can exist in different subclasses. The different objects can all call the draw method.

* the method names are the same. So it’s easier to memorize and use.

* subclass has their own variations by overriding.

* Reusability of code is achieved.

Overriding & Overloading



http://www.javatpoint.com/method-overloading-in-java

This diagram shows the difference between overriding and overloading. Overloading is to add a method of the same name but different parameters and implementation. An example will be add(){i+1;} and add(int n){i+n;}.

Overriding means that, in the subclass, a new method with the same name but different implementation is written. Therefore, when this method is called, the old method implementation is replaced by the new one, like add(){i+1;} and add(){i+2;}. Both overriding and overloading provide variations and flexibility to the program.

Programming Activity

In this activity, we used our knowledge about inheritance and polymorphism to finish writing a problem that can draw tortoise and rabbits and let them compete.

Here is the class diagram of it.



We can see that there is a abstract method called racer. Then, there are two variations, which are the two animals. The hollow triangular arrow represents the relationship “is a,” which is inheritance. Also, the other arrows represent association, which is a “use a” relationship.



From this picture we can see that there are two abstract methods: move() and draw(Graphics g); In the subclasses, they are implemented:



For example, this is the Hare class. The Hare moves in a random speed according to this move method. Also, the draw method actually draws a grey rabbit. In contrast, in the Tortoise class, these two methods are different:



This is exactly how polymorphism works!

Also, I am asked to finish the code in the controller method “RacePoly.”

Here are the codes:



This is the first question, which asks me to write a switch statement to do user interaction.



The second one is to call the move and draw method in all objects of the subclasses. This is an implementation of polymorphism because the same method “move” and “draw” exist in both subclasses.



This one is similar to the previous one. However, this draws the racers first before the race starts.

Then, the final product will be like this!





Interesting, isn’t it?

To conclude, from this programming activity, I practiced to use the concept of polymorphism in real java code. Also, it reminds me of Arraylist and switch statement, which I nearly forgot before I did this activity. Polymorphism is really useful in real life programming. Whenever we need to use different subclasses of the same parent at the same time, we can use what we learned about polymorphism to make the program more efficient.

Searching and Sorting an Array

In programming, we often need to handle a large amount of data. To find or change something in the dataset, there are several algorithms to achieve that.

Searching Algorithms

sequential Search

Sequential search, or linear search, is the algorithm that goes through all items in a collection and tries to find the desired item. If the item is found, this algorithm may return that item; if not, it will return -1.

The pseudocode is shown below:

set POSITION  to 0
set FOUND to false
loop while(POSITION < LENGTH AND NOT FOUND)
    if (numbers [position] equals searchitem) then
        set FOUND  to true
    else
        set POSITION to POSITION + 1
end loop

my java program

This is the static method that I wrote to search an item in a given array.


This is an interactive program that requires the user to type in the search item and also verify if the item is an integer.

Sorting an Array

when the array is very long and the elements are random, sequential search needs to go through all items in the array, which is very inefficient, So we sort the array so that we can then use other searching methods that are more efficient.
Among the algorithms, the complexity or the amount of computation can be represented by the big O notation. For example, the linear search algorithm big O notation is O(n), which shows a linear relationship between the amount of data and calculating power required.

Sorting Algorithms

Sorting is to arrange the items in a collection in a certain order. Here are two sorting algorithms that I will talk about:

• Bubble sort
• Selection sort

Bubble Sort

Bubble sort is one of the most basic sorting algorithms. It will compare the first two consecutive items, and switch them if they are not in correct order. Then, it will continue to compare the second and third item, and third and fourth, and so on.
During the process, the collection can be divided into two groups: Sorted an unsorted. This is because once an iteration is finished, an item is past to the end and its position is fixed.
The big O notation for bubble sort is O(n^2), which growth exponentially as n increases.

pseudocode:

set firstUnsorted to 0
set SWAP to true
while (firstUnsorted < LENGTH - 1 AND SWAP) //first while loop
    set SWAP to false
    //start of “Bubble up” function
    set INDEX to LENGTH - 1
    while (INDEX > firstUnsorted) //second while loop
        if (DATA[INDEX]) < DATA(INDEX -1)
            swap DATA[INDEX] and DATA[INDEX - 1] 
            set SWAP to true
        set INDEX to INDEX - 1 
    end while
    //end of “Bubble up” function
    set firstUnsorted to firstUnsorted + 1 
end while

my java program

Here is the code inside of the main method:

The output:


Selection Sort

Selection sort is another sorting algorithm that is inefficient for a large set of data, as has a big O notation of O(n^2). It divides the data into two groups, sorted and unsorted. At first, all data are in the unsorted list, then the program go through the data, find the smallest item and switch it with the left most data, then this item is categorized as sorted data.

pseudocode

my java program

Then, according to the sudocode, I developed a program that can sort a given array. This time, I make the program interactive so that it can let user input and then sort the inputted array.
Here is my code of the sorting method.



Here is the output:



Conclusion

As we want to find something in a collection, we may just go through all the items one by one. However, if we first sort them into a certain order, either from the largest to the smallest or the opposite, we can then use more efficient algorithm to search the collection. In real life, there are many applications related to data analysis, etc. In the future, I may learn about other more efficient algorithms.