EECS2030课程的笔记

This content is for YorkU EECS 2030. I took this course in summer 2016. My professor Navid Mohaghegh is a very nice professor. I do strongly recommend his course.

 

The course title is "Advanced Object Oriented Programming". We use Java in this course. It introduces very basic approach to some of the fundamental data structures.

 

May 12

• extends
• implements
• abstract class
• set/get method
• this.name = name;
• throw new IllegalArgumentException("你需要描述的事件");
• @override
• super() -> refer to parent class (extends)
• public abstract 类名 extends
  public interface 类名 implements 自己完善这个函数

 

---

May 17
Attributes
access [static] [final] type name [= value];

this refer to it self.

 

---

May 19
blocking people using the default constructors:

• 定义一个private的Constructors.

formal definition:

• parameters 收 public static int max(int a, int b){} //a b
• argument 给 Foo.max(x,y); //x y

Attribute Shadowing    使用this 进行区分
Java is Pass-by-value. primitive(原始) and reference types
Interfaces and Generics as Parameters

 

Java comment

可以在描述里面写上html代码，例如 <code>标签

@author
@param 变量名 描述
@return 描述

 

 

Overloads

当overloads 可能存在歧义的时候 ，编译器将会出现问题
例如
method(1,2)
对应于
public double method(int x, double y);
public double method(double x, int y);

 

---

May 24

避免多个对象同时修改一个变量(参见本文 有关 Synchronized的描述)

Static method can only use static attributes
Non-static method can use static attributes and non-static attributes

String is a special object.

 

Immutability

使用final可以确保 method不被Override, 可以确保attribute 中的值不被改变（如果该值是一个地址，不能确保里面的内容不改变）

 

Singleton & Multiton

Singleton
一个Class只有一个存储对象在里面
使用情形：

1. Ensure that there is no more than one instance of a class, and
2. Provide a global point of access to the instance

 

Multiton
一个Class有多个存储对象在里面

1. Multiple instances (each with unique state)
2. Accessor(Getter，访问接口) needs to provide state information
3. Require private constructor(Class帮助用户创建被存储的对象)
4. 存储后的对象应该是不可改变的(immutability)

 

 

 

 

 

---

May 26

使用build.gradle，logger，JUnitTest

 

---

May 31

Aggregation, Composition

不同的数据复制方法，describe the has-a relationship

slide 5

 

Aggregation（聚合）

Has-a Relationship

Does Not implies ownership. 如果父类消失，子类可以独立存在。

在UML图中使用空心菱形

Pass object (reference) to the constructor. The constructor does not create new object for the data.

If the client change the data outside of the class, the data in the class will be changed. Because the class does not hold the object (It holds the reference to the object, and this reference is shared by others).

public class Person
{
	private String name;
	private Date birthDate;
	
	public Person(String name, Date birthDate)
	{
		this.name = name;
		this.birthDate = birthDate;
	}

	public Date getBirthDate()
	{
		return birthDate;
	}
}

public class Main {
	public static void main(String[] args) {
		Calendar cal = Calendar.getInstance();
		cal.set(Calendar.YEAR, 1990);
		cal.set(Calendar.MONTH, 1);
		cal.set(Calendar.DAY_OF_MONTH, 1);
		Date d = cal.getTime();
		
		String n = "Michael";
		Person p = new Person(n,d); //直接传递object
		System.out.println(p.getBirthDate());//Output: 1990-1-1

		n = "ttt";		//但字符串比较特殊，不会受到影响
		d.setDate(5);		//如果对class外部的对象进行修改，会直接影响里面的数据
		
		System.out.println(p.getBirthDate());//Output: 1990-1-5		
	}
}

 

 

Composition（组合）

Contains-A Relationship

Implies ownership. 如果父类消失子类将会不见。

在UML图中使用实心菱形

Pass data to the constructor. The constructor use the data to create new object for the data and store the object. It will use defensive copy in the constructor.

public class Person
{
	private String name;
	private Date birthDate;

	public Person(String name, Date birthDate)
	{
		this.name = new String(name);
			
		Calendar cal = Calendar.getInstance();
		cal.setTime(date);
		this.birthDate = cal.getTime();
	}

	public String getBirthDate()
	{
		return String.format("%s - %s", name, birthDate.toString());//不能直接返回对象
	}
}

 

 

 

Shadow Copy

只复制链接地址

A shadow copy means:

• copy the references only, the references are pointed to the origin.
• do not create new objects

It owns the collection but not the objects.

//Shadow Copy
Line t2 = new Line();
t2.setStartPoint(t1.getStartPoint());
t2.setEndPoint(t1.getEndPoint());

 

Deep Copy

 

复制每一个对象

A deep copy means:

• references refer to new objects.

It owns the collection and the objects. It creates new objects.

//Deep Copy
Line t3 = new Line();
t3.setStartPoint(new Point(t1.getStartPoint()));
t3.setEndPoint(new Point(t1.getEndPoint()));

 

---

June 3

Inheritance

slide 6

Inheritance

Java only supports single inheritance.

Is-A relationship

The ancestors of all the classes in java is Object Class.

• A subclass inherits all of the non-private members(but not constructors)
• A new class has direct access to public and protected attributes
• The new class can re-define (override) its super class methods (non-final methods)
• Static methods and attributes can be hided but not recommended.

A subclass must be able to do everything its ancestor classes can do.

 

---

June 7

注意override 和overload 的区别
Loop Invariant: it might be false after the loop.

父类：super class, base class, parent class
子类：sub class, derived class, extended class, child class

Java only supports single inheritance.

Subclass inherits all of the non-private members
注意：不包括 constructors, 编译器会自动在constructors 里面加上super()，若super class中constructor不存在(默认无参数的一般都是存在的，这里针对的是有参数的constructor)或者constructor是private的，则会出错。

Super class里面call一个函数会call到subclass 里面的同名函数。If a class is intended to be extended then its constructor must not call an override-able method. 但是Java 不会强制要求。也就是建议method只调用同函数内private/static的method。

 

Preconditions

前提条件，注释采用

// Test method
// @pre. 1<= nrg <= 10
public void setEnergy(int nrg){
    if (nrg < 1 || nrg > 10) {
        //抛出异常
    }
}

注意不要滥用try catch

 

 

Postcondition

后置条件，指返回值的条件，注释采用

// Test method
// @post. 1<= nrg <= 10
public int getSize(){

}

 

 

Exception

• Throwable(java.lang.Throwable)
• Exception
• RuntimeException
• IllegalArgumentException

注意高性能并发最好不要使用这些方法

 

可以自己建造一个Exception Hierarchy，也就是说，subclass Exception是可行并且推荐的，这样方便管理

如何产生一个Exception

// in Dog
public void someDogMethod() throws DogException
{
	// can throw a DogException, BadSizeException,
	// NoFoodException, or BadDogException
}

其中DogException有几个subclasses分别处理不同的错误。

当override一个method含有throws的时候需要处理throws，从设计的角度，subclass的method必须含有throw部分，并且后面跟着的Exception classes需要含有原method的throws 的class 或者其subclass. A subclass promises to do everything its super class does; if the super class method claims to throw an exception then the subclass must also.

 

 

Polymorphism （多态性）

有关interface

Late Binding 的概念： Declared type 和 run-time(actual) type 可能是不一样的。（运行时倾向于使用run-time type）

declared type 会限定写代码时候可用method的范围

https://docs.oracle.com/javase/tutorial/java/IandI/polymorphism.html

 

Late Binding : Declare a object as one type, while at run-time we use the method of another type.

static 根本不存在late binding : static method 会使用 defined type 里面的static method

public class LB {
	@Override
	public String toString(){
		return "LBClassToStringMethod!";
	}

	public static void main(String[] args) {
		Object o = new LB();
		//Declared type is Object, while at runtime we will use toString of LB class!
		System.out.println(o.toString());
	}
}

 

 

---

June 9

复习shadow copy/deep copy， Singleton pattern，late binding and dynamic dispatch concept，hiding attributes and the related pitfalls(陷阱) of naive definitions for static attributes

 

 

Abstract Methods

• 不可以直接创建的抽象类
• 使用abstract关键字
• 什么时候使用Abstract：If the base class has methods that only subclasses can define and the base class has attributes common to all subclasses.
• Java 中不能使用instance of 来判别
• The non-abstract subclass must provide definitions for all abstract methods

public abstract class Dog
{
	// attributes, ctors, regular methods
	public abstract String getBreed();

	//可以存在非abstract method
	public void eatFood(){
		print("Something");
	}
}

 

注意，extends 中的 static var的值，一般会跟着原来的class

static 的attribute和method 都不能够被override（因其是跟着Class 而不是跟着 Object），因此使用相同名称是被称为Hide。不要 hiding attribute（父类和子类中不要使用名称相同的attribute），不要hiding methods（父类和子类中不要使用名称相同的moethod），因为那样会增加代码的复杂程度。

https://www.ibm.com/developerworks/cn/java/l-javainterface-abstract/

 

Interface

public interface Iterable<T>
{
	Iterator<T> iterator();
}

Reference type (类似于 class)

可以使用多个implements ，但只能extends 一个superclass。

Interface can contain only

• Constants
• Method signatures
• Nested types

Interface cannot be instantiated.

 

Synchronized

volatile keyword 是程度比较轻的synchronized

http://www.ibm.com/developerworks/cn/java/j-jtp06197.html

可以使用synchronized Block

sychronized (UUIDFactory.class){
    //同步的代码块
}

ConcurrentMap<A,B>可以使用并发

ExecutorService 类型可以触发class

 

 

UML diagram

• 第一格类名称，第二格attribute，第三格methods
• - 表示 private
  + 表示 public
• - 变量名称:变量类型
  + 函数():返回类型

例子：http://www.eecs.yorku.ca/course_archive/2015-16/S/2030/UML_Diagram.png 使用Eclipse的插件

 

---

June 14

下次考试考简单题，Do not overkill

1. Definition
2. Late Binding
3. BankAccount
4. Advance

本课主要讲Graphical User Interface. 说明implements 和 extends 的重要性。

注意Eclipse 中的便捷功能

JVM - Java Virtual Machine

Tower of Hanoi.

 

MVC Structure

Model View Controller

• Model
  • Encapsulates app state, responds to state queries
  • Exposes app functionality
  • Send Change Notification to view
• View
  • View is responsible for creating Controller + UI components (Set up Controller)
  • Setup communication of UI events to Controller
  • Presents the user with a sensory representation of the model state
  • A UI element
• Controller
  • Processes and responds to events from view, and translates to model method calls
  • Need to interact with both the view & module but not own them

 

本课程使用Swing架构，ActionListener 和 ArithmeticListener

 

Event Driven Programming : Each UI element is a source of events. When the user interacts with a UI element an event is triggered,  causes an event object to be sent to every object listening for that particular event, the listener respond to the event.

 

Inner Class

An inner class is a (non-static) class that is defined inside of another class.

An inner class has access to the attributes/methods (including private) of its enclosing class.

 

Give the listeners access to the view and model?

• use aggregation
• make the listeners be inner classes of the controller

Use inner class for listener?

• Only the controller needs to create instances of the various listeners
• The listeners need access to private methods inside of enclosing class

 

 

---

June 16

understand UML definition.

 

 

 

Recursion

Base case 是用来检查跳出递归的条件。 

The method terminates & The base cases and the recursive calls are correct Proves Accomplishes your goal

Prevent infinite recursion

1. The method reaches a base case
2. Each recursive call makes progress towards a base case

To solve a problem with a recursive algorithm

1. Identify the base cases
2. Figure out the recursive call

Prove Correctness

1. Prove that each base case is correct
2. Assume that the recursive invocation is correct and then prove that each recursive case is correct

Prove Termination

1. Define the size of a method invocation; the size must be a non-negative integer number
2. Prove that each recursive invocation has a smaller size than the original invocation

Infinite Recursion : If the base case(s) is missing, or never reached, a recursive method will run forever.

Decrease/Divide and conquer : (分治法) common strategy for solving computational problems

 

例子使用递归验证Palindromes(回文), Towers of Hanoi(eecs3101)

     public static boolean isPalindrome(String s) {
    	if (s.length() < 2){
    		return true;
    	}else{
    		if (s.charAt(0) == s.charAt(s.length() - 1)){
    			return isPalindrome(s.substring(1, s.length() - 1));
    		}else{
    			return false;
    		}
    	}    		
    }

 

//使用方法
//move(3, "A", "B", "C");

public static void move(int n, String from, String to, String using) {
	if (n == 1) {
		System.out.printf("move from [%s] to [%s]\n", from, to);
	} else {
		move(n - 1, from, using, to);
		move(1, from, to, using);
		move(n - 1, using, to, from);
	}
}

 

---

June 21

下节课将讨论Quiz2，本节课主要讨论Linked List。

Data structure and algorithms are one of the foundational elements of computer science. 提及了二分查找为例子。

下节课讲 Iterable Interface

 

Linked List

链表属于一种  Recursive Object.
Linked lists 和 Trees 是计算机科学的经典的用于呈现递归例子。

In linked list each node has: some data and contains a reference to the next node or null if no next

由于客户不需要知道node的细节，所以通常将node定义为 private inner class

Basically all the things have to be done RECURSIVELY.

注意这个老师的linked list使用一个变量记录size，当getNode的时候可以验证数据是否在链表之外(Out of bound)

数据结构包含以下函数 get() set() toString() setIndexOf() indexOf() add() removeAtIndex() insert()这些都可以用递归实现

 

Remove() cause the element most recently returned by next() to be removed from the linked list

"invoke remove() twice at a time"/"invoke remove() before calling next()" will cause IllegalStateException

 

Iterator : 

• current element -- iterator -- next element
• current element is null when iterator at the start of the iteration
• next element is null at the end of the iteration
• both are null when list is empty

 

 

 

---

June 23

Iterable Interface 可以方便实用 foreach statement.

要是iterator 前后都是null，可能证明这个linked list 可能是空的

也可以带cheat sheet half page

JAXBContext、SOA、Marshaller 回去研究一下并发

 

Iterator

Iteraable<E>有1个method

• iterator()

Iterator<E> 有3个methods

• hasNext() 如果有下一个则为真，否则为假
• next() 返回下一个element
• remove() Removes from the underlying collection the last element returned by this iterator (optional operation).

Iterator() 应该属于 inner public class

 

可能产生几种  Exception需要注意

• NoSuchElementException
• IllegalStateException
• IndexOutOfBoundsException

两个重要的变量

• currNode( returned by next() )
• prevNode(不需要，如果不使用 remove() method)

LinkedList.java 非常好

@Override
public boolean hasNext() {
	if (this.currentNode == null) {
		return (head != null);
	} else {
		return (this.currentNode.next != null);
	}
}

@Override
public Character next() {
	if (!this.hasNext()){
		throw new NoSuchElementException();
	}else{
		previousNode = currentNode;
		if (currentNode == null){
			currentNode = head;
		}else{
			currentNode = currentNode.next;
		}
	}
	return currentNode.data;
}

@Override
public void remove(){
	if (previousNode == currentNode){
		throw new IllegalStateException();
	}else{
		if (currentNode == head){
			head = currentNode.next;
		}else{
			previousNode.next = currentNode.next;
		}
		currentNode = previousNode;
		size --;
	}
}

Serializable

java的序列化，方便对象的持久化（进行硬盘的存储）

 

---

June 5 & June 7

Midterm Review

int 的比较需要返回差距数值，而不是简单的 -1 0 1。

Quiz next week: about linked list (add remove hasNext) and a little bit array list.

 

Array List

• Fixed length 定义好长度之后不能改变
• Contiguous area of memory to store data 是连续的
• Can be accessed by index (Index: 0...length - 1)
• Less than other data structure

 

double[] myCollection = new double[10]; //分配尺寸

String[] funString = {"asdf", "asdf3", "as1j2kd"};
System.out.println(funString);//这里仅输出内存地址

int[] numbers = {23, 42, 55, 67};
System.out.println(numbers);//这里仅输出内存地址

//使用 Generics Types
T[] aaa =(T[]) new Object[10];

使用数列解决斐波拉契数列

unsortedFind()  函数

 

 

Stack and Queue

共有方法：

• Size
• isEmpty
• peek (get the top without removing it)
• search
• isFull (for finite size)
• capacity (for finite size)

Stack

Last-In-First-Out.

• push
• pop

Can use a Linked List to implement Stack.

直接使用Java提供的 ArrayList<E> 实现  Stack（期末）.

java.util.Stack 已经提供实现了

 

Queue

First-In-First-Out

• Enqueue
• Dequeue

java.util.Queue 已经提供了实现了

 

---

July 12

Algorithm refers to EECS2011 (Dec 4,2014. Andy Mirzaian)

Binary Tree

evince PDF reader

Quiz 3101 https://en.wikipedia.org/wiki/Introduction_to_Algorithms

tree diverse，翻转二叉树

 

Graph

• Vertices : set of nodes
• Edges : collection of pairs of vertices

图的种类

• Directed edge --> Directed graph
• Undirected edge --> Undirected graph

不同类型的vertices

• end vertices
• edges incident on a vertex
• adjacent(邻) vertices
• ......

 

Binary Trees

has at most TWO children.

A tree is a data structure made up of nodes. Tree has no cycle. And all the nodes are connected.

 

重要概念

• root: no parents
• leaf: do not have children
• subtree: 从树中分割出一部分

 

重要算法

• 插入一个元素
  • 相对比较简单，根据元素的大小，小的放在左边，大的放在右边
• 移除一个元素
  • 移除leaf
  • 移除root或者中间节点 ：
    1. 检查较小（可能是left subtree）里面最大值
    2. 这个最大值只有 one child 或者 no child, 如果是有right leaf，证明不是最大的
    3. 将找到的这个值，替换掉原元素，然后移除该节点（避免重复）

 

Iteration methods

• Inorder: left root right
• Preorder: root left right
• Postorder: left right root
• BFS(Breadth-first search algorithm) use queue

 

 

public void addNode(T data){
	this.root = addNode(root, data);
}

private Node<T> addNode(Node<T> n, T data){
	if (n == null){
		return new Node<T>(data, null, null);
	}else{
		if(n.data.compareTo(data) > 0){	
			n.left = addNode(n.left, data);
		}else{
			n.right = addNode(n.right, data);
		}
		return n;
	}
}

public void removeNode(T data){
	this.root = removeNode(root, data);
}

private Node<T> removeNode(Node<T> n, T data){
	if (n == null){
		return null;
	}else{
		int compare = n.data.compareTo(data);//自己减去别人
		if (compare == 0){
			if (n.left == null && n.right == null){
				//Is leaf
				return null;
			}else if (n.left != null && n.right != null){
				//has two children
				n.data = this.largestValue(n.left);
				n.left = this.removeNode(n.left, n.data);
				return n;
			}else{
				//has one child
				if (n.left != null){
					return n.left;
				}else{
					return n.right;
				}
			}
		}else if (compare > 0){
			n.left = removeNode(n.left, data);
		}else{
			n.right = removeNode(n.right, data);
		}
		return n;
	}
}

public String toStringBFS(){
	StringBuilder sb = new StringBuilder();
	Queue<Node<T>> q = new LinkedList<Node<T>>();
	q.offer(this.root);
	while (!q.isEmpty()){
		Node<T> element = q.poll();
		sb.append(element.data.toString());
		sb.append(",");
		if (element.left != null){
			q.offer(element.left);
		}
		if (element.right != null){
			q.offer(element.right);
		}
	}
	sb.deleteCharAt(sb.length() - 1);
	return sb.toString();
}

 

 

---

July 14

 

balance tree 的讨论

 

Access Control

• public: full access
• protected: YES class, package, subclass; NO world
• (no-modifier): YES class, package; NO subclass, world
• private: YES class; NO package, subclass, world

Node 一般都用 static

 

---

July 19

two more classes

when we talk about complexity

Is there any algorithm can reduce the time of compare two variables?

loop invariant  用于确认循环可以终止
默写所有的排序方法

ISBN 0-13-198619-6

Searching

Unordered collection :  linear-time operation - O(n)

Ordered collection : Logarithmic-time operation - O(log(n)) using Binary Search

int find = 3;		//查找目标
int left = 0;		//左极限
int right = 19;		//右极限

while (left <= right){
	int mid = (left + right) / 2;
	if (array[mid] > find){
		right = mid - 1;
	}else if (array[mid] < find){
		left = mid + 1;
	}else{
		System.out.printf("index:%d\n", mid);
		continue;
	}
}

 

Sorting

precondition: non-empty list
postcondition: sorted list

比较是不可避免的

Bubble Sort 冒泡排序：

every time when we do comparison, we swap the bigger one to right & the smaller one to left
O(n^2)

1. compare each element with the next one and swap them if needed
2. Repeat until no more swaps are needed

public static int[] bubbleSort(int[] a) {
	// Compare each element with the next one, and swap if needed
	// LI: no more swaps are required
	// O(n^2) simple
	for (int i = a.length - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (a[j] > a[j + 1]) {
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	return a;
}

 

Selection Sort 选择排序 ：

select the smallest/biggest element and move it to the beginning/ending of the list.
O(n^2)

分支：双向选择排序。

1. find the smallest element not yet sorted
2. swap it with the first element not yet sorted
3. repeat until no more swaps are required

public static int[] selectSort(int[] a) {
	// Find the smallest element not yet sorted,
	// swap it with the first element not yet sorted,
	// repeat until no more swaps are required
	// LI: all the elements are sorted
	// O(n^2) more consistent
	for (int i = 0; i < a.length; i++) {
		int tag = i;
		for (int j = i + 1; j < a.length; j++) {
			if (a[tag] > a[j]) {
				tag = j;
			}
		}
		if (tag != i) {
			int temp = a[tag];
			a[tag] = a[i];
			a[i] = temp;
		}
	}
	return a;
}

 

 

Insertion Sort 插入排序：

insert the variable to the correct position
O(n^2)

1. Insert the elements to the sorted sub list
2. until all the elements are in that sub list

public static int[] insertionSort(int[] a) {
	// Insert element to the sorted sublist
	// LI: the sorted sublist is equals to the length of the original list
	// O(n^2)
	// better if the list is almost sorted, if the list is still receiving
	// elements
	for (int i = 1; i < a.length; i++) {
		int temp = a[i];
		int j = i - 1;
		while (j >= 0) {
			if (a[j] < temp){
				break;
			}
			j--;
		}
		for (int k = i - 1; k > j; k--) {
			a[k + 1] = a[k];
		}
		a[j + 1] = temp;
	}
	return a;
}

 

 

Merge Sort 归并排序：

repeatedly divide the collection to half, .
O(n log(n))

1. repeatedly divide the collection in halves until each sub list has only one element
2. merge pairs of those adjacent sub lists such that their elements are sorted

public static int[] mergeSort(int[] a) {
	int[] buffer = new int[a.length];
	mergeSort(a, 0, a.length, buffer);
	return a;
}

public static void mergeSort(int[] array, int begin, int end, int[] buffer) {
	if ((end - begin) > 1) {
		int middle = (begin + end)/2;
		mergeSort(array, begin, middle, buffer);
		mergeSort(array, middle, end, buffer);
		
		int i = begin;
		int j = middle;
		int k = begin;
		while(true){
			if(array[i] < array[j]){
				buffer[k++] = array[i++];
			}else{
				buffer[k++] = array[j++];
			}
			if (i >= middle){
				System.arraycopy(array, j, buffer, k, end - k);
				break;
			}
			if(j >= end){
				System.arraycopy(array, i, buffer, k, end - k);
				break;
			}
		}
		
		System.arraycopy(buffer, begin, array, begin, end - begin);
	}
}

 

 

---

July 21

Quiz4  Binary search tree, what is BST what is unique, finding a element big-O of add/contains/sort explain .
This course is mainly about the debug.
merge sort is important.

last lecture, review next week

 

---

July 26

lecture, final exam

 

Quiz 4

Binary Search Tree: add remove toString Preorder Inorder postOreder

Merge Sort: split, running time(O(n * log(n)))

 

Final Exam

underline keyword in the final exam

static method/attribute(Midterm 笔试中的问题 1,0,1,0)
able to read UML
how to write implements/extends/private/public/ : Bank Account
Pass-by-value/ pass-by-reference difference
method Overloading one question - may even invalid
generic - create generic linkedlist<T>
loop invariant - perhaps
class declared - banking fee (no final!!!) don't do all public static final
coding format - attributes - starts with lower case - public int id - check Style documents
default constructor -
singleton - yes one question
accessors - getter / setters  - the rest if going to like these
deep copy/ shadow copy - yes - don't go int, go Integer - provide example in exam - privacy leaks
Exception - yes - create custom exception class - use try-catch block - multi-catch block - small to big
toString - (might in Binary Search Tree)
equal - not
comparable - compareTo - yes - minus things
class invariant  - yes
singleton - synchronized
Aggregation and Composition - one of these in question
Composition and Mutators - yes -  what is the difference - use example in the slides
Inheritance - yes - is-a has-a relation - "this"/ "super" / "abstract" / "interface" keywords
Late binding - yes - complior nothing to do with LB - use example in the quiz
HashMap - no
multiple interfaces - yes
MVC - know
Recursion - yes - merge sort ! - binary search tree ! - two example in slide
Fibonacci - two way approach - different complexity
Hanoi - complexity
Proving termination - yes
Linked List - add / remove method - set all the pointer properly - like in the quiz
methods of Iterator - yes
difference between arraylist and linkedlist - running time
Tree - toString() - Tree traversal
running time of a merge sort() - split method() - check the example that he posted