1. Implementing Searching and Sorting Algorithms
   1. Sequential Search
      1. average/best/worst case analysis
   2. Binary Search
      1. O(logN)
   3. Recursive Binary Search
   4. Searching Objects
      1. using .equals()
      2. Comparable or Comparator must be implemented
      3. similar to BS
   5. Selection Sort
      1. O(N^2)
      2. using loop to put the min value one by one
2. Case Study: Implementing Merge Sort
   1. basics
      1. two sorted array=>single sorted array
   2. Splitting and Merge Arrays
      1. split array into two
         1. int[] left = Arrays.copyOfRange(a, 0, a.length/2)
         2. int[] right = Arrays.copyOfRange(a, a.length/2, a.length)
      2. while array, thinking OUTOFBOUNDs
      3. using if to eliminate this error
   3. Recursive Merge Sort
      1. each divided one can be considered as a new array need to be splitted
   4. much better than selection sort
   5. O(NlogN)
      1. logN of split
      2. N of element logN each time
   6. Cost of Java Array Allocation
      1. if computer is asked to auto-initialize an array of length n, then overall algo of merge sort will be O(N^2)
3. Program Complexity
   1. basics
      1. Complexity
      2. empirical analysis
      3. algorithm analysis
         1. pseudocode
      4. fixed time statement
         1. runtime of a group of statement in sequ order
   2. Empirical Analysis
      1. nested loops
         1. N^2
      2. better algorithm
      3. runtime increases by the algorithm's growth
   3. Complexity Classes
      1. Constant-time, O(1)
         1. convert unit
      2. Logarithmic, O(logN)
         1. divide prob space in half repeatedly
      3. Linear, O(N)
         1. count, sum, average, max, or range of list nums
      4. Log-linear, O(NlogN)
         1. Excuting a logarithmic algo over elements of N
      5. Quadratic, O(N^2)
         1. nested loops
      6. Cubic, O(N^3)
         1. count nums in colinear trios of points
      7. Exponential, O(2^N)
         1. print the power set of a datasheet
4. In Java Class Libraries
   1. List
      1. indexOf
         1. sequential
      2. not a List
         1. put it in the list
         2. write by yourself
   2. Binary Search
      1. definition
         1. sorted list
         2. divide by half
      2. Java-->Arrays
         1. if(target.trim().length() == 0) {break}
         2. Arrays.binarySearch
      3. Java-->Lists
         1. Collections.binarySearch
   3. sorting
      1. Array
         1. Array.sort
            1. Comparable interface implemented
      2. quick sort
         1. Arrays.sort + primitive data
      3. merge sort
         1. Arrays.sort/Collections.sort + obj
   4. Shuffling
      1. Collections.shuffle
   5. Custom Ordering with Comparators
      1. define public interface Comparator<T> {public int compare(T o1, T o2);}
      2. String.CASE_INSENSITIVE_ORDER
      3. Comparators
         1. implement ordering by length
         2. implement by Point
         3. can be used in sort, BS, Collection.reverseOrder, ...