Java Programming 2

Location: Room 223B, 德田館
Time: 1400 ~ 1745

``... it is always a good practice first to make your code right, and then make it fast.''
-- Brian Goetz

Instructor information

Instructor: 盧政良 (Zheng-Liang Lu)
Email: d00922011 at ntu.edu.tw

Wi-Fi Access

SSID: CSIE_guest
account: guest_Z6JQI
pwd: ZXF4JHK6

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

Objectives

Proceeding to Java generics, object design, annotations, and reflection mechanism
Introducing new features of JDK8: lambdas and streams
Understanding concurrent programming
Analyzing problems and developing solutions by selecting proper data structures associated with efficient algorithms
~~Learning the basics of software engineering and exploiting (software) design patterns~~

Prerequisites

Java programming (OOP part)
The equivalents (e.g. C++ and C sharp)

Text

No textbook.

Overview

OOP

Generics
Object: equality, comparison, clone
Reflection
Annotation with some applications (e.g. javadoc, JUnit)
Java lambdas
Java streams
Java Optional: alternative to null (a billion-dollar mistake)
Java Virtual Machine (JVM)

Concurrent programming

Basic concept: Thread & Runnable
Race conditions
Synchronized methods/blocks
Java concurrency framework: semaphores, monitor locks, threads pools with the Executors, Futures and Callables, CompletableFuture
Deadlock: producer-consumer problem, dining philosophers

Data structures and algorithms

Analysis of algorithms
Array list and linked list
Stack and queue
Priority queue (by heap) with heap sort
Binary search tree and its variants (2-3 tree, red-black tree, B-tree)
Hashing and its application (e.g. blockchain)
Undirected/directed graphs (graph traversal by depth first search (DFS) and breadth first search (BFS), also with topological sort and connected components)
Minimum spanning tree and shortest path
Tries
Regular expressions
Data compression
Maximum flow

Design patterns

Class design and SOLID principle
Creational patterns: singleton, factory method, abstract factory, prototype, dependency injection, interning, builder
Structural patterns: adapter, decorator, facade, flyweight
Behavioral patterns: iterator, observer, strategy
Model-control-view model (MVC)

Reactor pattern with RxJava

My wish list

Spring framework
- Spring boot
- Spring MVC
Java WebSocket
Tiny version of JVM (implementation of Java virtual machine and its compiler; an important practice!)
Scala and Hadoop for scalable applications on Java platform
Database theory and JDBC
Online judge system
Trading framework

Schedule [ 281, 282, 283, 288, 289, 291, 295, 297, 304, 306, 307, 310, 311, 312, 315, 318 ]

Date	Summary
2019.7.22	OOP: a quick review feat. memory and objects
2019.7.23	event-driven programming (FYR) events, listeners, callbacks Java graphics and GUIs Java event handling (FYR) Java 2D games tutorial, snake game (FYI) Simon Ritter, Java is still free Java generics generics (FYR) generics tutorial by Oracle (FYR) you can find generic programming in many languages (FYR) see type theory and category theory if you want to know how to design generics (FYR) Ronald Garcia, etc., a comparative study of language support for generic programming, 2003
2019.7.24	Object class with equals, compare, and clone Java reflection and annotation reflection and annotation (try ReflectionDemo.zip) (FYR) Glen McCluskey, using Java reflection, 1998 (FYR) Java reflection tutorial, Java annotation tutorial application: JUnit in Eclipse (also read unit test), javadoc
2019.7.25	Java lambdas and streams lambdas and streams (try stream_examples.zip) more examples could be found in Java 8 no more loop Raoul-Gabriel Urma, Java SE 8's Optional, Oracle, 2014 (FYI) Java collection framework (FYR) what is lambda? see lambda calculus (FYR) JDK 8: stream style, Oracle (FYR) lambda expressions and functional programming, lambdas & streams in JDK 8: beyond the basics, Java 8 lambda expressions & streams (FYR) parallel functional programming in Java (advanced level) (FYR) Baeldung, guide to Java 8 Optional, 2018.4.18 Java virtual machine (JVM) JVM (see animated slides for Java activation records for bank account example) (FYR) introduction to jvm (FYR) you may implement a JVM by C language: tiny jvm by Jserv (FYI) virtualization and cloud computing by King Abdullah University, and virtualization by Harvard University
2019.7.29	Java concurrent programming multithreads (try MultithreadDemo2.java) (FYI) process in OS by Jerry Breecher, OS - Ch3 行程 Process by Mr. Opengate synchronization (FYR) lesson: concurrency, Oracle (FYR) Java 多執行緒的基本知識 by popcornylu (FYR) synchronized statement, advanced locking, Java executors and synchronizers, volatile variables and Java memory model (FYR) Brandon Skerritt, concurrent programming in Java (FYR) 作業系統概念: Concurrency 程式設計篇 by Jserv (FYR) Amdahl's law (todo) an example for Amdahl's law multithreaded server; you may download client_server_model_sample.zip; also see Java socket programming examples supplementary material for computer network OSI model three-way handshake by 鄭中勝 wireshark list of TCP and UDP port numbers programming model, programming language, execution model: programming models, execution model concurrent collections, Oracle data structures and algorithms analysis of algorithms array list, linked list, stack, queue
2019.7.30	data structures and algorithms (cont'd) priority queue, heaps, and heap sort application: many-body simulation (CollisionSystem.zip) symbol table binary search tree balanced search tree (FYR) B-trees, data structures in Java: B-trees (FYR) tree application: Java DOM
2019.7.31	data structures and algorithms (cont'd) hash table (FYR) the reason of ``one of a billion bug'' could be found in integer overflow application: creating your first blockchain with Java (github: simple blockchain) (FYR) double hashing, perfect hashing undirected graph you may try Maze.jar; download the source code here (dependency of Maze can be found in CollisionSystem.zip) (FYR) Pacman project: search problem in python (FYR) Pacman in Java: Java2DPacmanGame, 2017 directed graph (FYI) application: influence maximization problem
2019.8.1	data structures and algorithms (cont'd) minimum spanning tree shortest path data compression (FYR) tries, regular expressions (try regexone), maximum flow (FYR) EXAMS from COS226 in the CS department of Princeton University feedback sheet

Sample code

/java2/315/code/

Gradebook

References

Java

Patrick Niemeyer and Daniel Leuck, Learning Java, 4/e, 2013
Benjamin J Evans and David Flanagan, Java in a Nutshell, 6/e, 2014
Joshua Bloch, Effective Java, 3/e, 2018 (highly recommended!!!) (notes on Effective Java - 3rd Edition Notes)
Scott Oaks, Java Performance: The Definitive Guide, 2014
Grant Malcolm, Advanced Object-Oriented Programming, Department of Computer Science, University of Liverpool, 2014
Hyunyoung Lee, CSCE 314 Programming Languages, Department of Computer Science and Engineering, Texas A&M University, 2016fa

Data structures and algorithms

Robert Sedgewick and Kevin Wayne, Algorithms, 4/e, 2011 (You may refer to its official website for slides and sample codes: http://algs4.cs.princeton.edu/home/.) (highly recommended!!!)
Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser, Data Structures and Algorithms in Java, 6/e, 2014
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3/e, 2009
Steven S Skiena, The Algorithm Design Manual, 2/e, 2008
Eric Rowell, bigocheatsheet
en.VisuAlgo.net, National University of Singapore
Erik Demaine, 6.851: Advanced Data Structures, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 2014sp
Thomas Vidick, Advanced Algorithms, Department of Computing and Mathematical Science, Caltech, 2016 Winter
Guy Blelloch and Anupam Gupta, 15-853: Algorithms in the "Real World", Computer Science Department, Carnegie Mellon University, 2015fa
Satish Rao and Di Wang, Combinatorial Algorithms and Data Structures, Department of Electrical Engineering and Computer Sciences, UC Berkeley, 2013sp
Sanjeev Arora and Pravesh Kothari, Computer Science 521 Advanced Algorithm Design, Computer Science Department, Princeton University, 2016fa
Andrew McGregor, CMPSCI 311: Introduction to Algorithms, College of Information and Computer Sciences, University of Massachusetts Amherst, 2016fa
Andrew McGregor, CMPSCI 611 - Advanced Algorithms, College of Information and Computer Sciences, University of Massachusetts Amherst, 2017fa
Sergei Vassilvitskii, COMS 6998-12: Dealing with Massive Data, Computer Science Department, Columbia University, 2011
Avrim Blum and Manuel Blum, CMU 15-451 Algorithms, School of Computer Science, Carnegie Mellon University, 2011fa
Avrim Blum and Manuel Blum, 6.893 Sub-linear Algorithms, Massachusetts Institute of Technology, 2013sp
Douglas Wilhelm Harder, Algorithms and Data Structures, Department of Electrical and Computer Engineering, University of Waterloo, 2010
CS166: Data Structures, Stanford Computer Science Deparment, 2017fa
Computer Science E-22 Data Structures, Harvard University, 2018fa
Yaron Singer, CS284r: (Social) ata Mining, Harvard University, 2014fa

Computing theory

Michael Sipser, Introduction to the Theory of Computation, 2013, 3/e

Hashing and its applications

Ittay Eyal, CS 5437: Principals and Practice of Cryptocurrencies, Cornell University, 2016sp
Bart Preneel , Cryptographic Hash Functions: Theory and Practice, Katholieke Universiteit Leuven
Arvind Narayanan,‎ Joseph Bonneau,‎ Edward Felten,‎ Andrew Miller, and‎ Steven Goldfeder, Bitcoin and Cryptocurrency Technologies, 2016
Chun-Ming Chen, 密碼貨幣與區塊鏈原理, 銓安智慧科技, 2017

Concurrent Programming

Brian Goetz, Java Concurrency in Practice, 2006
Carlo A. Furia, Concurrent Programming - TDA383/DIT390, Chalmers University of Technology, 2017 (highly recommended!!!)
Prof. Oscar Nierstrasz, CP: Concurrency: State Models and Design Patterns, Universität Bern, 2015fa
Shan He, SSC: Networks/Concurrency 2014/2015, School of Computer Science, University of Birmingham
Maurice Herlihy, CS176: Multiprocessor Synchronization, Brown University, 2012
Alois Schütte, Parallel Programming in Java, University of Wisconsin-Platteville, 2002fa
Jeff Preshing, An Introduction to Lock-Free Programming, 2012
Kai Engelhardt, COMP3151/9151 Foundations of Concurrency, 2017

Computer organization/architecture

Randal E. Bryant, David R. O'Hallaron, Computer Systems: A Programmer's Perspective, 3/e, 2015

Object-oriented analysis and design

Grady Booch, Robert A. Maksimchuk, Michael W. Engle, Bobbi J. Young, Jim Conallen, and Kelli A. Houston, Object-oriented Analysis and Design with Applications, 3/e, 2007
Stephen Schach, Object-Oriented and Classical Software Engineering, 8/e, 2010
C. D. Skrien, Object-Oriented Design and Patterns, 3/e, 2011
Kenneth M. Anderson, Object-Oriented Analysis & Design, Department of Computer Science, University of Colorado, 2012fa (highly recommended!!!)
Max Goldman and Armando Solar-Lezama, 6.005: Software Construction, EECS, Massachusetts Institute of Technology, 2016fa
Zach Tatlock, CSE 331: Software Design and Implementation, Computer Science & Engineering, University of Washington, 2017 winter (highly recommended!!!)
Josh Bloch and Charlie Garrod, Principles of Software Construction: Objects, Design, and Concurrency, Carnegie Mellon School of Computer Science, 2016fa
Stephen Wong, Comp310: Advanced Object-Oriented Programming and Design, Rice University, 2017sp
CS 2112: Object-Oriented Design and Data Structures - Honors, Department of Computer Science, Cornell University

Design patterns

Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, Grady Booch, Design Patterns: Elements of Reusable Object-Oriented Software, 1994
Alexander Shvets, Gerhard Frey, and Marina Pavlova, Design Patterns
Eric Freeman,‎ Bert Bates,‎ Kathy Sierra,‎ Elisabeth Robson, Head First Design Patterns: A Brain-Friendly Guide, 2004

Databases

Abraham Silberschatz, Henry Korth, and S. Sudarshan, Database System Concepts, 6/e, 2010
Donnie Pinkston, Introduction to Relational Database Systems, Caltech Computer Science
Markus Krötzsch, Database Theory, International Center for Computational Logic, TU Dresden, 2016
Markus Krötzsch, Foundations of Databases and Query Languages, International Center for Computational Logic, TU Dresden, 2015
Christopher Ré, CS145 Introduction to Databases, Department of Computer Science, Stanford University
Reinhard Pichler, Database Theory, Institut f¨ur Informationssysteme Arbeitsbereich DBAI, Technische Universit¨at Wien, 2017
Kristin Tufte, CS487/587 Database System Implementation, Portland State University, 2014
Andy Pavlo, 15-445/645 DATABASE SYSTEMS, Carnegie Mellon University, 2017fa

Spring framework

Trading system

Cyan Spring Algorithmic Trading Software, 2012
A list of online resources for quantitative modeling, trading, portfolio management: EliteQuant, 2018

Online judge systems

Additional reading

What makes OOP ``good''?, StackExchange, 2013.5.19
Top 10 Algorithms for Coding Interview
RAMBABU POSA, Compare Functional Programming, Imperative Programming and Object Oriented Programming, JournalDev, 2015
TOI 臺灣國際資訊奧林匹亞競賽選訓營, 題庫, National Taiwan Normal University
Linus Torvalds, The Mind behind Linux, TED
Jserv's enlightenment
- 「進階電腦系統理論和實作」課程說明, Department of Computer Science and Information Engineering, National Cheng Kung University, 2018fa
- Re: [問卦] 寫程式語言的語言是怎麼來的？, 2018.9.28
- Re: [問卦] 作業系統學Linux就好?, 2019.2.19
- Re: [問卦] C語言最難的部分是哪一個?, 2019.1.17
- Linux 核心設計: 記憶體管理 (1), 2019.4.11
- Linux 核心設計: 記憶體管理 (2), 2019.4.14
- Re: [問卦] 不用函數庫和亂數寫程式求pi值的方法?, 2019.4.19
- Re: [問卦] C語言編譯器用哪個才夠專業?, 2019.4.22