Recording Classroom Lectures Policy Recording of classroom lectures is prohibited unless advance written permission is obtained from the class instructor and any guest presenter(s).
This course is designed for the students who want to learn Java but have no programming experiences before. We will start with the very beginning of program design and fundamental concepts about programs and machines. You are expected to be capable to implement your idea in Java independently after 30 hours of lectures. Furthermore, I wish you could learn other programming languages without suffering from starting over.
The topics delivered in the following weeks are as follows:
Date | Summary |
---|---|
2019.7.8 | programs, computational solutions, computer systems (CPU-memory model), programming languages, algorithms, JDK + Eclipse, first Java program, variables; HW0: Lab 0; Human Resource Machine (on sales until 7/9!!!); |
2019.7.9 | data types (int, double, char, boolean) (see computer arithmetics), assignment operator (=), arithmetic operators (+, −, *, /, %), type conversion, casting, rational operators (>, <, ==), logical operators (!, &&, ||, ∧), compound arithmetic operators (+=, ++), reference types, Scanner object, stack & heap; |
2019.7.10 | selections (if-else if-else, switch-case-default, ?: operator), while loops, do-while loops, for loops (also see pp. 8-10 of the slides 20180824.pdf for programming games); |
2019.7.11 | jump statements, nested loops, analysis of algorithms (also read analysis of algorithms for further details); DeepMind: AlphaGo (video); HW: Lab 1 due 7.15; |
2019.7.15 | arrays, for-each loops, briefing data structures, sorting algorithms, searching algorithms, higher-dimensional arrays; |
2019.7.16 | methods, call stack, scope of variable, method overloading, recursion; |
2019.7.17 | class & object (also read what makes OOP ``good''?), fields and methods, encapsulation, constructors, this operator, static members, garbage collection, HAS-A relationship (aggregation) (also see memory and objects from Stanford University), IS-A relationships, inheritance, super operator, method overriding (worth to read these slides), subtype polymorphism (try examples), up/down casting, instanceof operator, final variable/method/class, abstract class/method, interface; Java graphics and GUIs, Java event handling; |
2019.7.18 | lab hours: Lab 2, Lab 3, Lab 4, and Lab 5 due 7.19 (you may start with my incomplete codes here); feedback sheet; |
Promotion | Java Programming 2 (sign-up); |
Grading Policy Since Java 310, I've canceled the final exam for your final grade. As the minimal requirement to acquire the certificate of course completion, you need to finish all labs w/o OPTIONAL. I suggest that you could try optional labs as many as possible. For the record, this course is offered without any course credit of National Taiwan University, in compliance with Implementation Regulations Governing Colleges Continuing Education, Ministry of Education.
Late Homework Policy All programming labs should be submitted before the last date of class in order to deliver your final grades to the office so that the certificates can be issued soon. (See a recent complaint letter here.)
Homework Submission Send the source code (the file with .java extension) to my email shown in the beginning of this page. Remember to indicate this class number, your full Chinese name, and homework number in your email title. For example, [Java314] Homework 1 盧政良. Do not attach any class file because any executable file will be ruled out by Gmail.
Install JDK8 and Eclipse (or any IDE you have been familiar with, say IntelliJ) in your computer (desktop/laptop). You don't need to send me email for this lab unless you cannot complete the installation.
Write a program for number-guessing game (you may refer to Guess the Number if you have never played this 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. The figure shown below illustrates the case you lose.
Write an AI program which plays this game. For example, the naive strategy is to guess a number in random. Also, calculate the winning rate by simulating your AI program for 1e5 times.
Read the problem statement in p.7 of the slides: 程式實作題 for APCS. Let N be the number of students, denoted by 0, 1, 2, ..., N − 1. First, implement an algorithm which generates a sequence of 0, 1, 2, ..., N − 1 in random order. Note that all elements in sequence are distinct. Then write an algorithm to determine the number of groups among students and also report the members of each group. For example, N = 16.
Keyword: permutation index.
Replace the native array by ArrayList
First, implement three sorting algorithms (bubble sort, selection sort, and insertion sort). You then compare the efficiency of these three sorting algorithms together with Array.sort (check its API) by running Monte Carlo simulation (estimating the average running time) for various sizes and benchmarking the time cost of these four algorithms (using the doubling hypothesis), shown as below.
You may use System.currentTimeMillis() or System.nanoTime() to make timestamps (remember to use long variables). Note that the actual numbers in the table may differ from mine due to variety of runtime environments. If you are interested, you may watch this video for 15 sorting algorithms.
Implement Shell's sorting algorithm which runs in O(n (log n)^2) time. You may refer to shell sort in Wikipedia.
Implement the merge sort algorithm which runs in O(n log n) time. You may refer to merge sort in Wikipedia.
Let x be any real number and n be any positive 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.
Keyword: exponentiation by squaring.
Compare your solution to the naive method (running in O(n) time). Report the speedup.
As you can see, the double overflow occurs when the exp exceeds 1000. To calculate the correct numbers, you may use the class BigDecimal for arbitrary digits.
Modify your solution for negative n.
Convert the recursion version into the loop version.
Introduce bitwise operators (&) and shift operators (>>) to your solution.
Let M be any positive int value. Write a function to calculate x ^ n mod M for n = 10000000. You may use the polynomial remainder theorem (see here).
Rewrite the program in Lab 1 in object-oriented programming. You need to analyze the functionalities in Lab 1. You may define any number of classes if necessary. For example, you can consider in this way: one object for the game procedure, the other object for the player. In this way, you should define a protocol so that the game object has minimal dependency on the player. The resulting UML is shown below. If so, you can easily develop various strategies to play this game and see which strategy is more promising.
Keyword: OOP, class inheritance, method overriding, subtype polymorphism, dependency injection.
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.
The following problems interest me.
Write a program which estimates the Euler constant e ~ 2.7183 by Monte Carlo simulation. The procedure is as follows: (1) Set N = 1e5 and M = 0; (2) for each iteration, find the minimal number k of random numbers which follows a standard uniform distribution (simply use Math.random() in this case) so that the sum of these random numbers is greater than 1; (3) do M += k; (4) then the estimator of e can be done by M / N.
Keyword: Monte Carlo, Euler constant.
Write a program which calculates the price of European call options. The input is as follows: (1) S (spot price), (2) X (strike price), (3) T (time to maturity, year), (4) v (annual volatility), (5) r (annual interest rate). The price of European call options can be done as follows: (1) Set N = 1e5 and c = 0; (2) for each iteration, calculate the asset price S' by S' = S * exp((r − 0.5 * v ^ 2) * T + v * sqrt(T) * RANDN), where RANDN is a random variable following a standard normal distribution (use the method nextGaussian() of Random objects; see Random from Oracle); (3) if S' − X > 0, do c += S' − X; (4) after N iterations, do c /= N. Finally, output the option price c. For example, the European call price is 14.2xxx for the case of S = 100, X = 100, T = 1, v = 0.3, r = 0.05.
Keyword: Monte Carlo, option price, Black-Scholes model, geometric Brownian motion, financial engineering.
Write a program to display all permutation of N distinct items.
Keyword: permutation, Heap's algorithm.