Java Programming 2

Location: Room 108, 德田館
Time: 1300 ~ 1600, Saturday and Sunday

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

Wifi access

SSID: CSIE_guest
account: guest_SDKR5
pwd: AGJ6NQYW

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 ]

Date	Summary
2019.3.9	OOP: a quick review feat. memory and objects (FYI) Simon Ritter, JDK 9, 10, 11 and Beyond, Java is still free
2019.3.10	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 Object class with equals, compare, and clone
2019.3.16	Java reflection and annotation reflection and annotation (FYR) Java reflection tutorial Java annotation tutorial Glen McCluskey, using Java reflection, 1998 (FYR) object relational mapping (ORM): Java persistence layer javadoc JUnit in Eclipse (also read unit test)
2019.3.17	Java lambdas and streams lambdas and streams (FYR) lambda calculus (FYR) JDK 8: stream style, Oracle tiny project for parallel streams: MonteCarloByStream.zip more examples could be found in Java 8 no more loop (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) Raoul-Gabriel Urma, Java SE 8's Optional, Oracle, 2014 (FYR) Baeldung, guide to Java 8 Optional, 2018.4.18 Java virtual machine (JVM) JVM 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.3.23	Java concurrent programming multithreads 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
2019.3.24	data structures and algorithms analysis of algorithms array list, linked list, stack, queue priority queue, heaps, and heap sort application: many-body simulation (CollisionSystem.zip)
2019.3.30	data structures and algorithms (cont'd) symbol table binary search tree balanced search tree (FYR) B-trees, data structures in Java: B-trees (FYR) tree application: Java DOM
2019.3.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) 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 directed graph (FYI) application: influence maximization problem
2019.4.13	data structures and algorithms (cont'd) minimum spanning tree shortest path tries regular expressions (FYR) regexone
2019.4.14	data structures and algorithms (cont'd) data compression design patterns design patterns 1 design patterns 2 MVC patterns (FYR) principles of design patterns (FYR) reactive programming: reactive programming in Java 8 with RxJava, Java 8 Stream API and RxJava comparison (FYR) Spring Framework, Spring Framework Guru, Spring Boot tutorial, Spring Boot tutorial for beginners (FYR) case study: android architecture feedback

Sample code

/java2/310/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

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

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
Jim Huang, 「Linux核心設計」課程說明, Department of Computer Science and Information Engineering, National Cheng Kung University, 2019sp