Computer Science and Engineering

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