## 算法设计与分析笔记0x10 —— Extending the Limits of Tractability

Must sacrifice one of three desired features.

• Solve problem to optimality.
• Solve problem in polynomial time.
• Solve arbitrary instances of the problem.

## 算法设计与分析笔记0x0F —— PSPACE

P Decision problems solvable in polynomial time.
PSPACE Decision problems solvable in polynomial space.

• P PSPACE
• 3-SAT is in PSPACE
• NP PSPACE

## Partitioning Problems

### 3-Dimensional Matching

3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T X × Y × Z of triples, does there exist a set of n triples in T such that each element of X Y Z is in exactly one of these triples?

## 算法设计与分析笔记0x0D —— Part 2 NP完全

CIRCUIT-SAT. Given a combinational circuit built out of AND, OR, and NOT gates, is there a way to set the circuit inputs so that the output is 1?
Theorem CIRCUIT-SAT is NP-complete.

## 算法设计与分析笔记0x0C —— Part 1 NP完全

Algorithm design patterns.

• Greedy.
• Divide-and-conquer.
• Dynamic programming.
• Max-flow min-cut.
• Reductions.

Algorithm design anti-patterns.

• NP-completeness.
• PSPACE-completeness.
• Undecidability.

## 微博数据爬取

• 爬取内地、港台明星势力榜前50名的明星近期微博数据。
• http://chart.weibo.com/?rank_type=3&version=v1
• http://chart.weibo.com/?rank_type=5&version=v1

• 爬取共100名明星微博。
• 共计24219条微博。

## Sketchy OAuth2 & Docker & SSH

I wrote this post for Environment Setup & Basic Knowledge for Data Science. (of course under Ubuntu16.04, but also other Debian systems should be OK)

For python, I’ve written a series of notes. https://today2tmr.com/2017/07/18/python-爬虫学习笔记目录/ https://today2tmr.com/2017/12/13/python-数据分析与展示笔记目录/

## OAuth2

Authorization Grant Types
Refer to http://www.ruanyifeng.com/blog/2014/05/oauth_2_0.html

• 授权码模式 Authorization Code
• User-Agent applies for code
• Client uses code to apply for token
• 简化模式 Implicit
• Client applies for token directly
• 密码模式 Resource Owner Password Credentials
• User tells Client password to apply for authorization.
• 客户端模式 Client Credentials
• Client applies for authorization in the name of itself.

## English Linking Patterns and Rules

B站王霸胆视频的学习笔记 https://www.bilibili.com/video/av5243511/

Take place between LAST syllable of the first word and FIRST vowel of the second word.

## Pattern 1: Unvoiced -> Voiced

• t/s/f -> d/z/v
• trends to be voiced consonant

## 数据排序

• .sort_index()方法在指定轴上根据索引进行排序，默认升序
• .sort_index(axis=0, ascending=True)
• For DataFrame, first argument is some index or columns by which data is sorted.
• NaN统一放在排序末尾