Long Gong Reading time ~1 minute

Countability

Theorem 1: For any finite alphabet \(\Sigma\), the set of string defined on it is countable. proof:

[basic idea: build a 1-1 map from string to natural number]

First of all, we consider . It is obvious that any string defined on such alphabet can be considered as a number in base-2 system. However, that is not enough because it is not a 1-1 map, since a lot of string might be mapped to the same integer, for example, \(0001\) and \(1\). We can fix this issue by adding a ``1” before the string. Thus, we get a 1-1 map from a string to natural number.

Then, we extend the above proof to more general cases. It is easy to figure out that, for $\mid\Sigma\mid = k$, we can transform any string defined on it as a number expressed in base-k by using similar approach as above.

Therefore, for any finite alphabet, the set of string defined on it is countable.

Theorem 2: The set of language on a finite alphabet is uncountable.

proof:

[hint: Cantor’s diagonalization method]

Undecidability

Theorem 1: is undecidable.

proof:

[hint: Cantor’s diagonalization method, note that is also a string]

Theorem 2: is undecidable.

proof:

[hint: reduction from ACCEPT]

Theorem 3: Determining whether a TM accepts any string is undecidable.

proof:

[hint: construct a parametric TM and reduce from ACCEPT]

Corollary 3.1: Determining whether a TM rejects all strings is undecidable.

proof:

Corollary 3.2: Determining whether two TM’s $M_1, M_2$ accept the same language $L$ is undecidable.

proof:

Long Gong Reading time ~1 minute

Theorem: For randomized quicksort, the expected number of comparisons is \(O(n\log n)\).

proof: Denote the input array as \(A=[a_1,a_2,…,a_n]\), while the sorted version is \(S=[s_1,s_2,…,s_n]\). Let \(X\) be the # of comparisons over the execution of quicksort, and \(X_{i,j}\) be the indicator random variable which is defined as,

Then, the total number of comparisons can be expressed as,

Now, let’s focus on the probability of \(X_{i,j}= 1\), which equals to the probability that \(s_i\) and \(s_j\) are compared. As in quicksort, only when one of two elements is selected as pivot, and before that they are in the same sub-array, the two elements need to be compared. That is to say, the probability that \(s_i\) and \(s_j\) are compared equals to the probability that one of \(s_i\) and \(s_j\) is selected as pivot, and before that, they are in the same sub-array, which mean \(s_{i+1},s_{i+2},…,s_{j-1}\) can not be selected as pivot before them. Therefore,

Finally, we obtain that,

Long Gong Reading time ~1 minute 

#include <chrono>  
#define TIMING  

#ifdef TIMING  
#define INIT_TIMER auto start = std::chrono::high_resolution_clock::now();  
#define START_TIMER  start = std::chrono::high_resolution_clock::now();  
#define STOP_TIMER(name)  std::cout << "RUNTIME of " << name << ": " << \  
    std::chrono::duration_cast<std::chrono::milliseconds>( \
            std::chrono::high_resolution_clock::now()-start \
    ).count() << " ms " << std::endl; 
#else  
#define INIT_TIMER  
#define START_TIMER  
#define STOP_TIMER(name)  
#endif
Long Gong Reading time ~1 minute

1. Fast Commit

git commit -a -m "commit message"

2. Remember Credential on Windows

$ git config credential.helper store
$ git push http://example.com/repo.git
Username: <type your username>
Password: <type your password>

[several days later]
$ git push http://example.com/repo.git
[your credentials are used automatically]

3. Reset Last Commit

$ git commit -m "Something terribly misguided" # your last commit
$ git reset --soft HEAD^   # reset

It is extremely useful, when you encounter LARGE file problems

4. Skip Certain Changes

git update-index --no-skip-worktree <file>
git add -p <file>
git update-index --skip-worktree <file>

If you want skip (ignore) certain type of files, the following configuration can be applied: Edit file “.gitignore”, and add the types you want to ignore, for example,

# ignore thumbnails created by windows
Thumbs.db
# Ignore files build by Visual Studio
*.user
*.aps
*.pch
*.vspscc
*_i.c
*_p.c
*.ncb
*.suo
*.bak
*.cache
*.ilk
*.log
[Bb]in
[Dd]ebug*/
*.sbr
obj/
[Rr]elease*/
_ReSharper*/

Push Local Branch to New Remote Repository

Suppose you have made a empty repository and named it myapp.git, you can:

git remote add <branch_name> <repository_url>

where <branch_name> can be any valid name you want. Then, you can push your local branch to the newly created remote repository by using

git push <branch_name> master

Resolve Large File Failure Problem

Suppose you git push your local repository to Github, however it failed because of some large-size files. And you might continue to experience git push failure, even if you have removed or ignore such large files. You can use the following commands to resolve such a problem by deleting those files in your history.

git filter-branch --index-filter 'git rm -r --cached --ignore-unmatch <file/dir>' HEAD

Of course, by using the above solution, you cannot upload your large file to Github. Recently, Github had released a tool to help you handle with large file. More details, you can refer to An open source Git extension for versioning large files

Long Gong Reading time ~1 minute

Find Configuration File “Exit.edt”

options -> options interfaces … -> Advanced Configuration … -> Event Handlers -> Exit

the file looks like this:

// WinEdt Exit (Cleanup) Macro
 
   PushTagsandRegisters;
 
 //  CloseAppl("YAP");         // Close YAP if running?
 //  CloseAppl("Complete");    // Close Complete Wizard if running?
 
 // Remove Local ini and edt files if they are empty or the same as global
 // Users probably forget to do this before upgrading
 // so it is best to keep it tidy as we go...
 
 Exe('%b\Config\Cleanup.edt');
 
 PopTagsandRegisters;
 
 End;

Add Following Sentence Just Before “End;”

RegDeleteValue('HKEY_CURRENT_USER', 'Software\WinEdt 9', 'Inst');

Close WinEdit and Reopen