Java Programming 2

Instructor information

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

Wifi access

• SSID: CSIE_guest
• account: guest_SDKR5
• pwd: AGJ6NQYW

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.

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, 307 ]

Sample code

• /java2/307/code/

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

• Spring Tool Suite™ Downloads
• Spring Framework Guru

Online judge systems

• LeetCode Online Judge
• 高中生程式解題系統 (An Online Judge System For Beginners)

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

Gradebook