Java Programming 2

Location: Room 108, 德田館
Time: 1330 ~ 1715

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

``What I cannot create, I do not understand.''
-- Richard Feynman

Instructor Information

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

WiFi Access

SSID: N/A
Account: N/A
Passwords: N/A

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
Learning the basics of software engineering and exploiting (software) design patterns
Introducing new features of JDK8: Stream API (with lambdas), Optional API
Understanding concurrent programming with Concurrency API

Prerequisites

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

Overview

Advanced topics of Java

Generics
Stream API with lambdas
Optional: alternative to null (a billion-dollar mistake)
Reflection and annotations with applications (e.g. JUnit)
Java Virtual Machine (JVM)

Concurrent programming

Basic concept: Thread & Runnable
Race conditions: synchronized methods/blocks
Dining philosophers: deadlock, livelock, starvation
Producer-consumer problem (bounded-buffer problem)
High-level concurrency framework: thread pools, fork-join pools, asynchronous computation, concurrent data structures, atomic variables, synchronizers, monitor locks

Data structures and algorithms

Analysis of algorithms
Array list & linked list
Stack & queue
Priority queue (by heap) with heap sort
Binary search tree & its variants (2-3 tree, red-black tree, B-tree)
Hashing
Undirected/directed graph (graph traversal by depth first search (DFS) & breadth first search (BFS), also with topological sort and connected components)

Minimum spanning tree of edge-weighted undirected graph

Shortest path on edge-weighted directed graph

Dynamic programming

Greedy algorithms

Backtracking

Tries

Regular expressions

Data compression

Maximum flow

Design patterns

Class design and SOLID principle
Creational patterns: factory method, abstract factory, builder, dependency injection, prototype, singleton
Structural patterns: adapter, bridge, decorator, proxy, facade, sharing (interning, flyweight)
Behavioral patterns: strategy, iterator, observer (publish/subscribe)
Model-control-view model (MVC)
Reactor pattern with RxJava

TODO

Writing lecture notes ... you are welcomed to join me to writing lecture notes
Spring framework
Projects: online judge system for programming, shopping carts, trading system
Scalable application: Scala and Hadoop
Virtualization: docker
Dependency management: maven & gradle

Schedule [ 281, 282, 283, 288, 289, 291, 295, 297, 304, 306, 307, 310, 311, 312, 315, 318, 319, 320, 321, 322, 325, 326, 328, 333 ]

Date	Summary
2020.8.17	OOP: a quick review feat. memory and objects Part I: Object-oriented programming (cont'd) Wrapper classes Immutability by example: String (try a mutable text type, StringBuffer) Enumeration Packages & access controls (public/protected/package/private) Imports Inner class (composition) by example: stack by linked list Anonymous class by example Iterator pattern: Iterable/Iterator associated with for-each loop Static class Exception & exception handling
2020.8.18	Part I: Generics Generics Supplementary materials for generics Pankaj, Java generics example tutorial – generic method, class, interface, JournalDev, 2018 Oracle, Generics tutorial, guidelines for wildcard use, wildcard capture You can find generic programming in many languages See type theory and category theory if you want to know how to design generics Ronald Garcia, etc., a comparative study of language support for generic programming, 2003 Exercise: object comparison Comparison Sample code: ComparableDemo.zip
2020.8.19	Part I: Stream API (with lambda expressions) & Optional API Lambdas and streams (try StreamDemo.zip) Raoul-Gabriel Urma, Java SE 8's Optional, Oracle, 2014 Marius Herring, Java 8 no more loop, 2015 Another example: ParallelStreamWordCount.java with a text file The King James Bible Supplementary materials for Stream framework Alonzo Church, lambda calculus proposed in 1930s Ted Neward, Java 8: lambdas part 1 and Java 8: lambdas part 2, Oracle, 2013 Does a lambda expression create an object on the heap every time it's executed?, StackOverflow, 2017 Oracle tutorial: lambda expressions Mario Fusco, Richard Warburton, and Raoul Urma, Java 8 lambdas - a peek under the hood Sergey Kuksenko, JDK 8: lambda performance study, Oracle, 2014 Baeldung, Java infinite streams JDK 8: stream style, Oracle More slides are listed below: lambda expressions and functional programming, lambdas & streams in JDK 8: beyond the basics, Java 8 lambda expressions & streams Parallel functional programming in Java (advanced level) Baeldung, guide to Java 8 Optional, 2018.4.18 Use Java 8 parallel streams to read a file and tally word counts 林信良, 神秘的Monad不神秘, 2014.4.11 Part I: Reflection & annotation Reflection and annotation (try ReflectionDemo2.zip) Supplementary materials for reflection & annotation Glen McCluskey, using Java reflection, 1998 Java reflection tutorial, Java annotation tutorial, reflection from Washington University Jakob Jenkov, Java reflection - arrays, 2014 Reflection and Metadata for C# developers Reflection of C# Application: unit test How to use Junit: official user guide Tiny approximation of junit by using reflection & annotation: TinyJUnitDemo.zip How to do a good unit test: unit test, Washington University How to put a time restriction: JUnit 5: timeout Application: javadoc (TODO) Application: automatic grading (using reflection & annotation and JUnit)
2020.8.20	Part I: Java virtual machine (JVM) JVM (see animated slides for Java activation records for bank account example) Supplementary materials for JVM 老錢, 老大難的Java ClassLoader再不理解就老了, 2018 Introduction to JVM You may implement a JVM by C language: tiny JVM by Jserv More related to virualization: virtualization and cloud computing by King Abdullah University, and virtualization by Harvard University Part II: Concurrent programming Basics of operating systems (OS) Jerry Breecher, processes and threads Mr. Opengate, OS - Ch3 行程 Process Jserv, Linux 核心設計: 作業系統術語及概念, 2020 Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, 2018 (online version): virtual memory (FYR) Virtual memory CH8 記憶體管理 (Memory Management Strategies), 2018.1.9 CH9 虛擬記憶體管理 (Virtual-Memory Management), 2018.1.9 Translation lookaside buffer (TLB) Multithreading basics Java threads Race condition: bank accounts as example RaceConditionDemo.zip Parallelism is always good? (See MapReduceDemo.java and Amdahl's law) Fred Brooks says that ``... adding manpower to a late software project makes it later ...'' in his famous book, The Mythical Man-Month: Essays on Software Engineering, first published in 1975. Application (feat. parallel stream): MonteCarloMultiThreadDemo.zip
2020.8.24	Part II: Concurrent programming (cont'd) Synchronization (Try SemaphoreDemo.java) Supplementary materials for concurrency Oracle tutorial: lesson: concurrency Brandon Skerritt, concurrent programming in Java Vivek Sarkar, synchronized statement, advanced locking, Java executors and synchronizers, volatile variables and Java memory model Jim Huang (Jserv), 作業系統概念: Concurrency 程式設計篇 Jim Huang (Jserv), Linux kernel, 2019 Hyunyoung Lee, concurrency in java, 2019 Linus Torvalds, a reply to discussion about spinlock implementation and Linux scheduler (1, 2, 3, 4), 2020.1.3 (also read news) How to implement synchronized methods/blocks in Java? An Introduction to Lock-Free Programming, 2012.6.22 Application: multithreaded server (client_server_model_sample.zip) Supplementary materials for computer network Ray Toa, Java socket programming examples OSI model 鄭中勝, three-way handshake List of TCP and UDP port numbers Wireshark Concurrent framework Popcorny Lu, Java 多執行緒的基本知識 Code: ConcurrentFramework.zip (FYR) JavaScript Promise 全介紹
2020.8.25	Part III: Data structures and algorithms (FYR) Oracle, collections framework overview and concurrent collections Additional programming exercises are selected from LeetCode: Algorithm Labs Analysis of algorithms A_quick_review_on_analysis_algorithms.pdf Illustration for log-time algorithm: log-time_algorithm.pdf (FYR) Analysis of algorithms from Princeton University (FYI) Some computer games related with algorithms and optimization: LightBot, Kids Coding (by Google), Human Resource Machine, 7 Billion Humans, Mini Metro Array list, linked list, stack, queue Priority queue, heaps, and heap sort with application: simulation of many-body motion (CollisionSystem.zip)
2020.8.26	Part III: Data structures and algorithms (cont'd) (FYR) Symbol table Binary search tree Balanced search tree Supplementary materials for search trees 紅黑樹 vs. AVL tree 对各种树形结构的总结 B-trees Data structures in Java: B-trees Syntax tree: preorder, inorder, postorder traversal 为什么MySQL使用B+树 and MySQL索引设计概要 Let's Build a Simple Database: Writing a sqlite clone from scratch in C, 2016 Hash table Supplementary materials for hashing The reason of ``one of a billion bug'' is integer overflow Application: creating your first blockchain with Java (simple blockchain on github) Advanced hashing techniques: double hashing, perfect hashing, and cuckoo search with a Chinese explantion here
2020.8.27	Part III: Data structures and algorithms (cont'd) Undirected graph (try Maze.jar; download the source code here while dependency of Maze.java can be found in CollisionSystem.zip) Supplementary materials for undirected graphs Pacman project in python: search problem from Berkeley University Pacman project in Java: Java2DPacmanGame, 2017 Minimum spanning tree Directed graph Supplementary materials for directed graphs (digraphs) Application: influence maximization problem Shortest path (you may need union-find) Combinatorial search Dynamic programming: 1, 2, 3 Greedy algorithms: 1, 2 More topics about data structures and algorithms Divide & conquer: 1, 2, 3 Tries Regular expressions (try regexone) Data compression Maximum flow You may evaluate yourself by taking exams offered by COS226 in the CS department of Princeton University Part IV: Design patterns Head first design patterns, 2014, O'Reilly (中文翻譯版) Dive Into Design Patterns Design patterns by example, strategy, bridge, and factory design patterns MVC patterns, application: free marker (FYR) Module design, principles of design patterns, design patterns 1, design patterns 2 (FYR) Reactive programming: reactive programming in Java 8 with RxJava, Java 8 Stream API and RxJava comparison (FYR) A Design-Pattern Quick Reference (FYR) 蔡昇達, 設計模式與遊戲開發的完美結合, 2016 (code examples) (FYR) Case study: android architecture Part V: misc Refactoring Tomasz Linkowski, 5 refactoring principles by example, 2019 Refactoring, SourceMaking, 2019 Len Chen, Ninja Code, 2019.9.14 Spring framework tutorial Spring Boot Startup (FYR) Spring Boot Tutorial For Beginners (FYR) Spring Framework (FYR) Spring Framework Guru (FYR) Zero Cheng, 30天學習J2EE Spring+Hibernate學習心得記錄 Aspect-oriented programming (AOP) Wiki (2014) Pro Spring (pp. 166-244).pdf Dynamic proxy by Justin Lin Application: Java logger Profiling VisualVM Java Microbenchmark Harness (JMH) Jenkov, JMH Tutorial Docker Docker核心技术与实现原理 Dependency manager Maven Gradle Comparison Maven和Gradle對比認識 Gradle 專案建置自動化工具依赖管理工具漫谈-从Maven,Gradle到Go Modern Java Programming 技術漫談系列

Sample code

/java2/333/code/

Gradebook

References

Java

Raoul-Gabriel Urma, Mario Fusco, Alan Mycroft, Modern Java in Action, 2018
Patrick Niemeyer and Daniel Leuck, Learning Java, 5/e, 2020
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

Object-oriented analysis and design (design patterns)

Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, Grady Booch, Design Patterns: Elements of Reusable Object-Oriented Software, 1994
Robert C. Martin, Agile Software Development, Principles, Patterns, and Practices, 2005
Alexander Shvets, Gerhard Frey, and Marina Pavlova, Dive Into Design Patterns, 2018
Eric Freeman,‎ Bert Bates,‎ Kathy Sierra,‎ Elisabeth Robson, Head First Design Patterns: A Brain-Friendly Guide, 2004
Kenneth M. Anderson, Object-Oriented Analysis & Design, Department of Computer Science, University of Colorado, 2012fa (highly recommended!!!)
Zach Tatlock, CSE 331: Software Design and Implementation, Computer Science & Engineering, University of Washington, 2017 winter (highly recommended!!!)
Max Goldman and Armando Solar-Lezama, 6.005: Software Construction, EECS, Massachusetts Institute of Technology, 2016fa
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

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

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

Chris Schaefer, Clarence Ho, Rob Harrop, Pro Spring, 4/e, 2014
Iuliana Cosmina, Rob Harrop, Chris Schaefer, Clarence Ho, Pro Spring 5, 5/e, 2017
Craig Walls, Spring Boot in Action, 2015