---
tags: java
---

# Java Programming

* This is the online course of [Java Programming](https://www.csie.ntu.edu.tw/~d00922011/java.html) offering in [台大資訊系統訓練班](https://train.csie.ntu.edu.tw/train/).
* The class provides than 15 hours of online lectures and 6 hours of physical lectures.

## Instructor Information
* Instructor name: 盧政良 (Zheng-Liang Lu)
* Email address: [e-mail]

## Grading Policy
* The participants who <font color = "red">finishs all lab assignments</font> will acquire a certificate for this class.

## Lecture Overview
### Part I: Algorithm-Based Programming
0. Syllabus
1. Installation of [JDK8](https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html) and [Eclipse](https://www.eclipse.org/)
2. First program: Hello World
3. Second program: Circle Area
4. Variable declaration: `int`, `double`
5. Naming rules
6. Variable as alias for memory address
7. Binary system: bit & byte
8. Integers: `byte`, `short`, `int`, `long`
9. Floats: `float`, `double` (IEEE754)
10. Machine epsilon
11. Assignment operator
12. Arithmetic operators
13. CPU-memory model
14. Put it together: type matters!!!
15. Type conversion
16. Text: `char` & `String`
17. The type `boolean` with only two possible values: `true`, `false`
18. Rational operators
19. Logical operators with truth table
20. Compound arithmetic operators
21. Reference type: `Scanner`
22. Memory model: stack & heap
23. Flow controls
24. Selection: `if-else if-else`
25. Selection: `switch-case-default`
26. Selection: `A ? B : C`
27. Loop: `while`
28. ++Lab 1: Number Guessing++
29. Algorithm: bisection method
30. Loop: `do-while`
31. Loop: `for`
32. Nested loop: multiplication table
33. Nested loop: triangle stars
34. Analysis of algorithms: big-$O$ notation
35. Array
36. Array indexing
37. Data processing: max, sum
38. ++Lab 2 Contagion Control++
39. Sorting algorithm: bubble sort, selection sort, insertion sort
40. Linear search & binary search
41. For-each loop
42. Cloning an array: shallow copy & deep copy
43. 2D array
44. ++Lab 3 Performance Benchmark for Sorting Algorithms++
45. Method feat. `return`
46. Call stack
47. Variable scope
48. Special issue: method overloading
49. Special issue: variable input arguments
50. Special issue: `public static void main(String[] args)`
51. Recursion
52. ++Lab 4: Fast Power++

### Part II: Object-Oriented Programming
0. Object
1. Class
2. Encapsulation: private vs. public
3. Constructor
4. `this` operator
5. Static member vs. instance member
6. Garbage collection
7. HAS-A relationship: aggregation
8. Object feat. memory allocation
9. IS-A relationship: inheritance
10. Constructor chaining & `super` operator
11. Method overriding
12. Case study for OOP
13. Subtype polymorphism
14. `instanceof` operator
15. The gist of OOP ==Program to Abstraction==
16. Final variable/method/class
17. `abstract` method/class
18. IS-A relationship: `interface`
19. Anonymous class
20. Design patterns: singleton, iterator
21. ++Lab 5 Refactoring Number-Guessing Game by Using Design Patterns++
22. Wrapper classes
23. `enum` type
24. Exception & exception handling: `try-catch-finally`, `throw` and `throws`

## Programming Labs

### Lab 1 Number-Guessing Game
Write a program for number-guessing game. The program first generates a secret number ranging between 0 and 99, inclusive. Then the program asks the player to guess a number. If the input value is equal to the secret number, then the player wins. If not, then update the range depending on the input accordingly. (For example, assume that the secret number is 42. If the player types 50 for the first time, then the program shows (0, 49) on the screen.) When there is only one integer left, the player loses the game. Also, make sure that the player types a number in the feasible range; otherwise, ask the user to redo the input.


#### Lab 1-1
Add some strategies (AI?) to play this game and calculate each winning rate by using these strategies for 1e5 times. For example, the naive strategy is to guess a number in random, and its result is around 66%. Surprisingly, the winning rate for binary search is about 63%, not as expected to beat the naive one. Why?

#### Lab 1-2
Find the optimal strategy to beat the former two. The result is shown below. As you could see, the winning rate of my optimal strategy reaches 99%!


#### Lab 1-3 (optional)
Modify the game loop which allows the player to guess at most 7 times (why?). Also report their performance like below:


The performance of binary search remains ~63% while the other two degrade severely!

### Lab 2 Contagion Control
The virus, [COVID-19](https://en.wikipedia.org/wiki/Coronavirus_disease_2019) (aka Wuhan coronavirus), is spread from close contact with an infected person. Now you are going to design an algorithm to find the chain of the virus from one person to the next, identifying and isolating those people. For simplicity, let N be the number of citizens, each denoted by 0, 1, 2, ..., N − 1. Then each citizen writes down the citizen he/she comes in contact with. To avoid typing these numbers by hand, use the shuffling algorithm to generate a random sequence of 0, 1, 2, ..., N − 1 for testing. Be aware that all elements are distinct. For example, consider N = 16 and start from the first citizen. A possible output is shown below.


#### Lab 2-1
Modify your solution to show all group members and calculate how many groups in the random sequence. For example, consider N = 16 and the outputs are shown as follows.



#### Lab 2-2
Replace the native array by `ArrayList`. This lab asks you to understand the usage of `ArrayList` and Java generics, which won't be introduced comprehensively in this lecture (see Java Programming 2).

### Lab 3 Performance Benchmark for Sorting Algorithms
First, implement three sorting algorithms (bubble sort, selection sort, and insertion sort) mentioned in class. Then compare the running time of these sorting algorithms together with Arrays.sort() (check its API here). Since the performance of these comparison-based sorting algorithms is sensitive to the order of data sequence, I suggest that you could calculate the average running time for various sizes and make a benchmark for these four algorithms (using the doubling hypothesis), shown as below.

#### Lab 3-1
Compare the growth rate of running time for each sorting algorithm to the theoretical prediction by big-$O$. Recall that the first three sorting algorithms runs in $O(n ^ 2)$ time while Arrays.sort() runs in $O(n \log n)$ time.


### Lab 4 Fast Power Using Recursion
Let x be any real number and n be any nonnegative integer. Write a program which calculates $x ^ n$ by recursion. For example, $2 ^ {10} = 1024$. Try to make your program run in $O(\log n)$ time. Note that you are not allowed to use `Math.pow()` and any loop in your solution.

#### Lab 4-1
Compare your solution to the naive method (running in O(n) time). Report the speedup.


#### Lab 4-2
As you can see, the double overflow occurs when the exp exceeds 1000. To calculate the correct numbers, you may use `BigDecimal` for arbitrary digits.

### Lab 5 Refactoring Number-Guessing Game by Using Design Patterns
Rewrite your program of Lab 1 in OOP style. First analyze the functionalities in Lab 1 and then define any number of classes if necessary. For example, you could create two objects: one object is for the game procedure, the other object for the player. In this way, you should define a protocol so that the game has minimal dependency on the player. The resulting UML is shown below.


#### Lab 5-1
Try various strategies for this game. For example, the naive strategy is to guess a number in random, and the binary-search strategy is to return the number in the middle of the feasible range. Then compare the winning rates by simulating these strategies for 1e5 times.