PART I Definition

The well ordering principle

Every nonempty set of nonnegative integers has a smalleset element

This statement is known as The well ordering principle.Some sorts of obvious.We can use it to prove some propositions.

The template for The well ordering principle proofs

More generally, to prove that “$P(n)$ is True for all $N\in \mathbb N$” using The well ordering principle you can take the following steps:

• Define the set, $C$,of counterexamples to P being true.Namely, define$$C:=\{n \in \mathbb N \mid P(n) \:is \:false\}$$
• Use a proof by contradiction and assume that $C$ is nonempty.
• By the Well Ordering Principle, there will be a smallest element, n, in $ C$.
• Reach a contradiction (somehow)—often by showing how to use n to find another member of $ C$ that is smaller than n. (This is the open-ended part of the proof task.)
• Conclude that $ C$ must be empty, that is, no counterexamples exist. QED.

To make it clear,I’ll show you a example.
Consider this:for anny positive integers m and n, the faction $m/n$ can be written in lowest terms.
Suppose to the contrary that there were $m, n \in \mathbb Z^+$ such that the fraction $m/n$ cannot be written in lowest terms.Now let $C$ be the set of positive integers that are numerators of such fractions.Then $m \in C$, so $C$ is nonempty.Therefore by well ordering,there must be a smallest integer, $m_0 \in C$.So by definition of C, there is an integer $n_0 \gt 0$ such that
$$\text{the fraction } \frac {m_0}{n_0}\text{cannot be written in lowest terms}$$
This means that $m_0$ and $n_0$ must have a common factor,$p \gt 1$.But $$\frac {m_0/p}{n_0/p} = \frac {m_0}{n_0},$$
so any way of expressing the left hand in lowest terms will also work for right hand, which implies,$$\text{the fraction} \frac{m_0/p}{n_0/p}$$ cannot be written in lowest terms either.
So by definition of $C$, the numerator,$m_0/p$ is in $C$, but $m_0/p \lt m_0$ which contradicts the fact that m0 is the smallest element of $C$.So the assumption is false,that is , the $C$ is empty and hence there are no such fractions at all.QED.

Ordinary Induction

The Principle of Induction.

• $P(0)$is true, and

• $P(n)$ IMPLIES $P(n+1)$ for all nonnegative integers, n,
  then

• $P(m)$is true for all nonnegative integers, m.

PART II Problems

Try to prove:$$1+r+r^2+r^3+…+r^n=\frac {1-r^{n+1}}{1-r}(r\ne1)\tag{1}$$

First , use the well ordering principle.
Suppose to the contrary,some nonegative integers serve as counterexamples to it.Let’s collect them in a set:$$C:=\{ n\in \mathbb N\mid 1+r+r^2+r^3+…+r^n\ne\frac {1-r^{n+1}}{1-r} \}$$.So by well ordering principle, C has a minimum element, call it $c$.That is , $c$ is the smallest conterexample to the theorem.Since $c$ is the smallest, so for all $n\lt c$the theorem will hold.For $n=0$ the above theorem is true so $c \gt 0$.This means $c-1 \ge 0$,the equation (1) for $c-1$ is true.$$1+r+r^2+r^3+…+r^{c-1}=\frac {1-r^{c}}{1-r}(r\ne1)\tag{2}$$.But when we add $r^c$ to both sides we get $$1+r+r^2+r^3+…+r^{c-1}+r^c=\frac {1-r^{c}}{1-r}+r^c=\frac {1-r^{c+1}}{1-r}(r\ne1)\tag{3}$$Which means equation (1) does hold for $c$.This is a contradiction.So set $C$ is empty,and we’re done.QED

Secondly ,we’ll use the induction method.
First for $n=0$,equation (1) obviously is true.Now,suppose for $n=k$ the equation(1) also holds,which means:$$1+r+r^2+r^3+…+r^k=\frac {1-r^{k+1}}{1-r}(r\ne1)$$is true.
Adding $r^{k+1}$ to both sides we get $$1+r+r^2+r^3+…+r^k +r^{k+1}=\frac {1-r^{k+1}}{1-r}+r^{k+1}=\frac {1-r^{k+2}}{1-r}(r\ne1)$$.Thus,if for $k$ the equation is true, then so for $k+1$.So for every nonegative integers the equation holds.QED

题目：
https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

翻转一个链表。数据结构如下

1
2
3
4
5
6
7

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

使用迭代的方法很容易（好吧，一开始我写的代码很丑陋，下面是leetcode给的答案：

1
2
3
4
5
6
7
8
9
10
11
12

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* curr = head;
    struct ListNode* prev = NULL;
    while (curr)
    {
        struct ListNode* tempNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tempNode;
    }
    return prev;
}

使用递归写出的代码更加简洁：

1
2
3
4
5
6
7

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

显然两种方法的复杂度都是O(n)

MIT 6.042J,课程名称Mathematics for Computer Science。作为算法导论的先修课之一难度并不是很大，所以我决定在刷算导前先把这个课过一遍。
课程网址：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/index.htm

第一章讲数理逻辑的一些基本概念。

Propositions（命题）

Def:A proposition is a statement that is either true or false

高中的内容，没什么好说的了（美国高中不教数理逻辑的么？）

Predicates（断言）

Def:A predicate is a proposition whose truth depends on the value of one or more variables.

IMPLIES（推断）

ps:T for True,F for False

这个真值表（True table)是最骚的，因为可以概括为一句话：

An implication is true exactly when the if-part is false or the then-part is true.

也就是说这个命题是True：

If pigs can fly, then you can understand the Chebyshev bound.

因为If中的命题是假的，所以不管Then后面是什么，整个命题都为真。

当两个推断的真值表相同时，称两个推断等价。比如一个命题与其逆否命题命题等价。

还有几天就要开始研究生学习了。大学四年可以说是浑浑噩噩地度过的，虽然最后拿到了所谓的优秀毕业生，但是回想起来几乎是浪费了四年的大好时光。

前些天躺在床上，想了以后的事情。时不我待，研究生毕业也不过是转瞬。我不希望在研究生毕业时还有遗憾，至少这次让我全力以赴。

所以开了这个博客，记录自己的学习心得，也当一个鞭策。

接下来半年，计划是：

1、补习数据结构，把《数据结构C语言实现》过一遍(2m)。TCPL看一遍（1m)。刷POJ。

2、学习Web开发

3、把CMU的CSAPP课程看完。

4、刷完http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/（逃票预定）这个课看了下真心Nice，大名鼎鼎的MIT的算法导论（神课），
不过先修要求是离散数学，好吧，待我先去补一下离散。

不知道这次能不能完成呢。待这学期结束后见分晓把。

测试一下数学公式：$y=ax+b$

一系列点 $(x_i,y_i)(i=1,2,…n,n\ge 3)$

以后博客会涉及领域：

数据结构及算法学习，《算导》暂时不准备看，如果看的话也会写算法分析相关的

机器学习、深度学习（如果有时间的话）

复杂网络，链路预测（我读研期间搞的东西）

各种读书笔记，学习笔记

Web开发相关（跳票预定）