Geospatial Information Science

University of Maryland, College Park

Ph.D in Computer Science

University of Minnesota, Twin Cities

This page is currently under construction and links have not been added to bullets.

- P vs NP: A Millennium Problem
- Karp's 21 Problems
- Frequently used hardness classes: Definitions (e.g., NP-hard, APX-hard, NPO-complete)
- Hardness: Deterministic and non-deterministic Turing machines
- Hardness of approximation: PCP Theorem
- Examples:
- Proof of NPO-completeness:
- Proof of APX-hardness:
- Proof of NP-completeness:

- Pseudopolynomial: Strong NP-hard vs. weak NP-hard
- Approximation: Polynomial-Time Approximation Scheme (PTAS) and Fully Polynomial-Time Approximation Scheme (F-PTAS)
- Common misconceptions
- Direction of reduction/proof
- Parameters: Fixed value / bounded values vs. flexible values
- Classic Problems:
- Recent Problems:
- Mapping 3-Satisfiability (3-SAT) problem to two-dimensional spatial problems

- Convoluational Neural Network for theme classification:
- r-CNN framework for object detection:
- You-Only-Look-Once (YOLO) and YOLOv2 frameworks for object detection:
- Libraries: tensorflow, keras, darknet ...
- Open-source repositories on Github: Implemented with tensorflow - ; Darknet - ;
- Visualizing kernels of deep networks:
- Deconvolutional neural networks:
- Adverserial learning:
- Will it converge?
- Limitations of deep networks: interpretability, success and failure modes, robustness against pixel manipulation...

- Recurrent Neural Networks (RNN)
- Gated RNNs, e.g., Long Short-Term Memory (LSTM)

- Problem formulations and reformulations
- Dual problems
- Linear programming
- Convex optimization
- Convergence
- Gradient descent
- Descent direction
- Step size
- Optimal first-order approaches
- Coordinate gradient descent
- Non-smooth functions and Subgradient
- Projected gradient descent and Proximal gradient methods

- Alternating direction method of multipliers (ADMM)
- LASSO
- Semidefinite programming

- Integer programming
- Exact algorithms
- Branch and bound, Branch and price, Branch and cut, etc.
- Column generation
- Dynamic programming (sometimes pseudo-polynomial)
- Cutting-Planes

- Approximation algorithms
- Randomized algorithms
- LP relaxition and integrality gap
- Problem-specific algorithms

- Heuristic algorithms (meta-heuristics)
- Genetic algorithms
- Simmulated annealing
- Tabu search
- Others: Ant colony optimization, particle swarm optimization, Metropolis heuristic, etc.

- Backdoors to combinatorial optimization
- Classic problem: Knapsack problem and its variations
- 0-1 Knapsack problem
- Common misconceptions about its hardness
- In what sense it is NP-complete?
- Is the pseudo-polynomial algorithm good enough for common real problems?
- Indirect effect of number of items

- Approximation algorithms and accelerations

- Common misconceptions about its hardness
- Multiple-choice Knapsack problem
- Multi-dimensional and Multiple-choice Knapsack problem
- 2D Knapsack problem

- 0-1 Knapsack problem

- Distributions
- Stochastic processes
- Significance testing
- Common misconceptions of p-value
- Statistical power
- Frequentist vs. Bayesian
- Computer science and statistics
- Autocorrelation and spatial statistics

- Derivatives of Matrices
- Matrix factorizations (e.g., QR, SVD) and numerical stability
- Numerical stability of gradient checking
- Tricks to improve numerical stability
- Arbitrary precision arithmetic
- Solving linear systems, Accelerations
- Matrix operations and positive (semi)definite matrix
- Hadamard operations and positive (semi)definite matrix
- Matrix cookbook