Java Programming 2

Location: Room 108, 德田館
Time: 1245 ~ 1630, Saturday and Sunday

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

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

Objectives

Continuing Java Programming for advanced syntaxes
Introducing new features of JDK 8: lambdas and streams
Understanding concurrent programming
Analyzing problems and developing computational solutions by selecting proper data structures associated with efficient algorithms
Learning the basics of software engineering and applying (software) design patterns

Prerequisites

Java programming (OOP part)
The equivalents, for example, C, C++, and C sharp

Text

No textbook.

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

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

Wifi access

SSID: CSIE_guest
account: guest_W4GRZ
pwd: 8WGPVV3U

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 (e.g. AVL tree and balanced search 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
Shortest path
Tries
Regular expressions
Data compression
Greedy algorithms
Dynamic programming

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

Scala and Hadoop for scalable applications on Java platform
Tiny version of JVM (implementation of Java virtual machine and its compiler; an important practice!)
Database theory and JDBC
Spring family
- Spring, Spring MVC, Spring Boot, Spring Data, Spring Security

Schedule [ 281, 282, 283, 288, 289, 291, 295, 297, 304, 306 ]

Date	Summary
2018.11.24	OOP: a quick review (FYI) Simon Ritter, Java is still free (FYI) Simon Ritter, JDK 9, 10, 11 and Beyond generics (FYR) generics tutorial by Oracle (FYR) wildcard capture and helper methods (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
2018.11.25	generics (cont'd) Object class with equals, compare and clone
2018.12.1	reflection and annotation Java reflection and annotation (FYR) Java reflection tutorial Java annotation tutorial Glen McCluskey, using Java reflection, 1998 (FYR) object relational mapping (ORM): Java persistence layer (FYR) object-relational mapping and Hibernate (FYR) Java annotation design javadoc JUnit in Eclipse (also read unit test) Java lambdas and streams lambdas and streams (FYR) lambda calculus (FYR) JDK 8: stream style, Oracle tiny project for parallel streams: MonteCarloByStream.zip (FYR) 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) For parallel streams, see parallel functional programming in Java Raoul-Gabriel Urma, Java SE 8's Optional, Oracle, 2014 (FYR) Baeldung, guide to Java 8 Optional, 2018.4.18
2018.12.2	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: tiny jvm by Jserv (FYR) (Youtube) OpenJDK vs. Dalvik/ART virtual machine by jserv by Jserv, JCConf, 2014 (FYI) virtualization and cloud computing by King Abdullah University, and virtualization by Harvard University concurrent programming multithreads synchronization (FYR) lesson: concurrency, Oracle (FYR) Java 多執行緒的基本知識 by popcornylu (FYR) Java executors and synchronizers (FYR) Brandon Skerritt, concurrent programming in Java (FYR) volatile variables and Java memory model (FYR) (Youtube) 作業系統概念: 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 (FYR) OSI model (FYR) three-way handshake by 鄭中勝 (FYR) wireshark (FYR) list of TCP and UDP port numbers
2018.12.8	analysis of algorithms array list, linked list, stack, queue priority queue, heaps, and heap sort Try CollisionSystem.zip (FYR) Fibonacci heaps
2018.12.9	symbol table binary search tree (FYR) another example for trees: Java DOM (also see DOM tree) hash table (FYR) the reason of ``one of a billion bug'' could be found in integer overflow blockchains: creating your first blockchain with Java (github: simple blockchain)
2018.12.15	undirected graph you may try Maze.jar; donwload the source code here (dependency of Maze can be found in CollisionSystem.zip) (FYR) Pacman project: search problem directed graph minimum spanning tree (FYR) shortest path tries regular expressions (FYR) data compression
2018.12.16	event-driven programming events, listeners, callbacks Java graphics and GUIs Java event handling (FYR) Java 2D games tutorial, snake game design patterns design patterns 1 design patterns 2 MVC patterns (FYR) Spring Framework Guru, principles of design patterns, reactive programming in Java 8 with RxJava, Java 8 Stream API and RxJava comparison, and android architecture (FYR) Spring Boot tutorial (FYR) Spring Boot tutorial for beginners

Sample code

/java2/306/code/

Java Programming 2

Objectives

Prerequisites

Text

References

Java

Data structures and algorithms

Hashing and its applications

Concurrent Programming

Computer organization/architecture

Object-oriented analysis and design

Design patterns

Databases

Spring framework

Online judge systems

Additional reading

Wifi access

Overview

OOP

Concurrent programming

Data structures and algorithms

Design patterns

My wish list

Schedule [ 281, 282, 283, 288, 289, 291, 295, 297, 304, 306 ]

Sample code

Gradebook