[Course Review]: Algorithms II by Tim Roughgarden

I was just watching House of Cards, and I am at the episode that Peter Rosso was killed. I am so sad, I like that guy. I was hoping he would turn down that girl, I was hoping he never touches that whiskey, and I was hoping he never raises another bottle again. I was just thinking that how stupid he is to give up that easily, and trust somebody he shouldn't. Then I thought about myself, having my days filled with small stuffs, abusing my time on social network and TV. I might as well stop taking the "drink" myself.

Back to the algorithm course I want to talk about. The course ended last week, I cannot say I am doing great at this course, but I am happy with a grade that allows me to pass. This made it the first course that I passed from Coursera. It is not easy for me at all. I had only vague memory about my data structure and graph theory course, and this lecture forced me to review most of them. I choose C++ to be the programming language for the exercise, and this is particularly painful since my last time dealing with pointers is 6 years ago. And I started it when I was writing my master thesis (I finished the whole thesis thing 3 weeks before this course ended, otherwise I don't know if I can pass). So I think I am allowed to be proud that I passed.

There is a lot of compliment for this course online and they are speaking of my opinion. Hard content, nice structure, great lectures, and tough exercises. What I also see is that there is a lot effort in this course, I don't know exactly how much, but I know there is a lot. I occasionally view the Algorithm I archive because I haven't taken it. I can tell that there is a lot of progresses in Part II from Part I, although they come from the same professor, and really are close in time. This is a team that really works to make the course better and better. The TAs in the forum are awesome, I am very surprised at how well they know about algorithms and how devoted they are to answering questions from the students.

So what do I learn from the course. First, I got adapted to C++ though the exercises. I am far from an expert, but I am comfortable using C++. I also got a better sense on the memory that a program might use, partly thanks to my 2GB RAM. On the contrary, I care less about time. It is not to say that time is not important, but a large part of it has been taken care of by those "blazingly fast" algorithms we learned. For me, the bottleneck is always the memory.

Second, and I think more importantly, I have a better sense about algorithm. I used to view algorithms, or at least the algorithms course as just one part of computer science. You have to take it so you know how to program. But what I learned from the course is that single algorithm does not matter (of course, it would matter for a specific problem, but I mean to the knowledge of a person). I watched the course, I did the exam, I implemented the algorithms, but I am sure that I will forget most of the details right away if I don't use them. But that's not a problem. We will only use a few of the algorithms if ever, and we can always look them up when we need. The real issue is, through these examples, we know how to properly design an algorithm for a new problem, where should we start, what's the possible hint.

Third, about the designing paradigms, greedy algorithm, divide and conquer, dynamic programming. Greedy algorithm is, well, greedy. I think it would be the least useful in the real world since you have the make the right call every turn, there is no turning back and correct. Divide and conquer and dynamic programming are in themselves the same. The key issue is to break a problem down into smaller problems. The difference is that divide and conquer has much smaller subproblems, usually half the size of the original one, that's why in the running time there is always a log(n). I think it is always a nice way to think when we encounter a problem, can we break it down to smaller easier problems.

Fourth, the NP-complete. One third of this course is devoted to NP-complete. And this is the part that I least understand. I like the philosophical explanation for the P != NP, which is that checking if the answer is correct should be strictly much easier than finding the answer. I am also glad that this is still an open question. I always thought NP stands for N particles, which is also an unsolvable (or unsolved) issue, I wonder how they would connect. Among the 3 ways to deal with the NP-complete problem that Professor Roughbgarden proposed, I like the second one best which is instead of an accurate answer, we look for a "nearly the best" or even "not so bad" one with reasonable amount of resources. It outlines how people usually work with their problems. For real problems, I mean real problems in the real world, no one is doing brute-force search to find the best choice, this is usually unacceptably expensive if it is ever possible. Instead, people relies a lot on experience, on intuition. Nobody can say that they make the best decision overall, but usually people are doing OK, right? We want computer to think like human, maybe we should start by making it less good at math.

I couldn't help but think about the link between physics and algorithms. Is physics itself an algorithm? Is Newton's laws just the best algorithm for predicting the trajectories of stars, how we could approach this task otherwise, is there other maybe less efficient algorithms? What about the time axis that a physics problem usually have, does it make any difference to the algorithms we are learning? If the world is deterministic (this is an abandoned idea because of the finding of quantum physics and chaos, but nobody can actually know this for sure), meaning we have full prediction of the future if we have enough information about the present, does this lead to an algorithm solving the "Halting" problem? Or, does the restriction on the algorithms reflect the unpredictability in the real world?

Finally, thanks to the team of this course, I benefit a lot from it.

Small tricks

This to keep track of the small tricks I run into that may be useful.

1. pause in C++
system("pause"): this is not a very good way to pause in C++ because it relies on the platform you compile and run. It does not work for my ubuntu system. Basically, system() will run the shell command.
cin.ignore(); This works out for me. I think this has the effect of "press any key to continue".

Something about Latin

For a non-native English speaker, it is hard enough to get used to English. BUT, it seems that some abbreviations come from Latin, which is  impossible to guess. I ran into one today, and that remind me of another one. Just use this to keep in track. It might be fun.

Q.E.D.
This is the one I ran into today. I've seen it a couple of times, I know what it means, I don't know where it comes from. Guess what, they are the initial letters of Latin quod erat demonstrandum, just means "is proved" like I guessed.

e.g.
A common phrase, I always thought it means "example given", which is a bit wired. It also comes from Latin exemplī grātiā, which is more or less like what I'm guessing (I don't know how to type the letters, so just copied from Wiki).

post hoc, ergo propter hoc
This might be less common, I saw this on the West Wing, one of my favorite TV series. It means "after this, therefore because of this", this is supposed to be a common logical error, but sometimes it is the best assumption we can make, and it really has some sense to it. Think about time series, people analyze time series all the time, what's the point of doing this if the relation cannot be build from the fact they are consecutive in time? OK, a bit too far. I haven't been clear about this issue. I planned to use this phrase somewhere in my thesis just to show off, but ...

To be continued (hopefully)...

Bugs & Fix

Here to keep track of the bugs I ran into and how to fix them.

"relocation truncated to fit: R_X86_64_32S against '.bss'"
This happen when the program needs more than 2GB of data.
Compile with -mcmodel=medium/large.
see http://amiatypist.blogspot.de/2010/05/relocation-truncated-to-fit-rx866432s.html

"Warning: ignoring incorrect section type for .lbss"
This follows last error, I did not find how to solve this. According to a post, this is because that the physical memory in computer is not enough.
see https://answers.launchpad.net/mg5amcnlo/+question/219687

"error: ‘exit’ was not declared in this scope "
This maybe a stupid error, but since it may happen for a new C++ user like me.
Including <iostream> and adding 'using namespace std' are not enough, need to add '#include <cstdlib>' to fix this.

" no matching function for call to 'sort(std::vector<Solution::Interval>::iterator, std::vector<Solution::Interval>::iterator, <unresolved overloaded function type>)"
Get this when I was trying to use std::sort. I defined my own comp() function, the problem is that it is defined as a member function within a class, so there is a 'this' parameter. Add 'static' or define the function outside the body of the class.

declaration of ‘std::stack<char> s’ shadows a parameter
stupid error caused by using the same name for different variables.

java STL like List and Map are abstract classes, and when using HashMap, it is better to use containsKey() to check if a key value exists.

java StringBuffer can be initialized with String and int, but not char. The char value will be converted to int, so the compiler does not say anything, but in reality the char is converted to integer.

org.apache.catalina.core.ContainerBase   : A child container failed during start
Spring or Tomcat just breaks all of a sudden. The problem I think is answered in
http://stackoverflow.com/questions/28102134/a-child-container-failed-during-start-java-util-concurrent-executionexception
, where an answer points out that we shouldn't inculde `servlet-api.jar` in WEB-INF/lib.
Although I did use providedCompile for servlet-api, it somehow finds its way to the /lib.

Healthy plan for the summer

1.    Get up at 7 : 00 a.m.

2.    Go out for jogging, roughly 1 hour.

3.    Shower, breakfast.

4.    If sunny, go out and practice Xun, read German. If not, do it at home.

5.    If some time left before lunch, do random things except sleeping.

6.    Lunch, break for 1 hour, find random things except sleeping.

7.    Sleep if tired.

8.    Library, reading, watch Coursera, doing homework. 

9.    Practice guitar.

10.  Simple dinner.

11.  Homework from Coursera.

12.  Random relax, movie, TV, games.

13.  Only sleep if really really tired.

quick sort in C++

First, I am totally new to C++. I've learned to program in C, but that was long time ago. I am now more comfortable with Matlab, IDL, or python. I plan to get familiar with C++ by using it to do the assignments from the online course Algorithm 2.  The first task from the course involves a sorting problem. So that's where we started.

I did not expect this to take away a whole afternoon from me. That is to say, I did not expect to learn so many stuff from this practice, it's worth to put them down.

1).  before using a variable, declare it first. This is annoying after getting used to Matlab. The type of the function, and the type of parameters all have to be decided in front. I saw in the textbook that the function have to be declared before the main function so I also did this. I think it is necessary.

2).  the variables that declared inside a block are local variables. This block even include a IF statement! Although I like the idea of local variable, I am constantly running out of short names like 'x', 'y', 'i', 'j', 'k'. It is so stupid that one cannot declare new variables inside an IF statement or FOR loop and use it outside. Me myself have trouble to believe in this. But when I tried to declare a new array inside an IF, it cannot be accessed outside that IF statement. I cannot declare it outside because I want to read the size from a file, and I believe it is necessary to add an IF to check that the file is actually opened. I haven't  found a proper way to do this till now.

3).  pointers. '&' means "the address of" and '*' means "the value this pointer points to". The '*' used differently when declaring a pointer, you do like 'int*' to say it is a pointer points to an integer. The interesting part is that when you point to an array, the pointer behaves just like the array.
For example,
int array[5] = {1, 2, 3, 4, 5};
int* pointer;
pointer = array;
Then pointer[3] = 4, just like array[3].
I use pointers as a parameter in the sub-function because I thought in this way the original values can be changed in the sub-function. I am actually not sure that this cannot be done by passing the array directly, since an array is basically a constant pointer. Need to check another time.

4).  file operations are done by "fstream" package (package?). In my case of reading a '.txt' file, the 'file >>' reads one data at one time and ignores the space and enter in between.

5).  quick sort. The idea is to choose a number in the array (randomly chosen is OK, I just use the rightmost value) as a pivot, and put the values that are larger than the pivot to the right side of the array, and the values that are smaller than the pivot to the left side of the array. After this, what we've done is, i) we find the correct position for the pivot, ii) we break the array into two sub-arrays, in one array all the values are smaller than pivot and in the other larger. So the next step is to repeat what has been done to till now to the sub-arrays separately till only one value left in the sub-array. The repeating part can be done by calling the quick sort recursively. It is said the expect running time is O(nlog(n)). I need to check on that.

6) code. The WLK is just a struct I created, the WLK.key value is used for sorting.

Give up physics, joining the job searching

古剑二，吐槽

慢悠悠的终于把古剑二几乎玩完了，玩到一半的时候就在想玩完的时候怎么怎么吐槽，趁着这通宵之后，组会之前的一段时间，一吐为快。

首先是战斗系统，被改的已经无法操作了。本来，仙剑古剑这种回合制的战斗模式，简单不要操作，虽说即时战斗的爽快，也有自己的优点。现在战斗模式一改，彻底的没法玩了。跑得慢，转身慢，出手慢，各种状态五行生克复杂的一塌糊涂，配合什么的估计都是设想而已。玩dota的时候零点几秒的抬手都嫌长，这里一招能放个一分钟。好在自动战斗也不比我操作的差，于是就多买补给开个自动战斗，人去做俯卧撑了，这样感觉游戏打的不虚度光阴，倒比dota好了。

然后就是剧情。有了古剑一的对照古剑二的剧情简直不能看。当然我对偃甲这种神不神鬼不鬼的东西有点先天的抗拒。忽略这种个人情感，剑二的剧情本身也毫无亮点，男一和男二都没有性格，女二是个呆萌妹，只有女一稍微的性格饱满点。谢衣大概是全剧唯一的出彩点，那个初七的故事确实有点出人意料。设置的主题也很陈旧，男一女一都是要保护所爱的人，从古剑一继承下来的老主题。男二我觉得突出人妖平等，这本是仙四的主题之一，但仙四的铺垫做的好，故事合情合理。天河本身就是个不懂世俗规矩的野人，梦璃本身就是妖，与他们形成对比的是在修仙门派下长成，立志降妖除魔的紫英，最后由于鬼界一行再加上发现好友是妖，紫英观念的转变让人妖平等这一主题自然的展现。古剑二中，男二是半妖，仙女无偏见也就算了，在世俗观念中成长起来的男一女一凭什么直接接受妖，连一点挣扎都没有，难道他们都玩过仙四么？最后一段我还没玩，貌似是一出煽情戏，结局的大概早就透的一清二楚。有人说这是最悲情的boss团，他们把玄宵和欧阳少恭放在哪里？

回首剑一给我留下的感触，太子长琴的命中寡亲缘情缘，红玉的旁观少恭为人，大师兄衬出的屠苏的本领，晴雪在众人害怕中坚定的走向屠苏，和战龙千百年的约定，方兰生的痴心与无赖，欧阳少恭难以理解的变态，晴雪最后的生死感悟。古剑一建立了一个完整的世界架构，其中的神会死，其中的轮回有限。百里屠苏顽强的与天命抗争，因着那悲剧的结尾更加动人心魄。旁观无异悲谢衣，更像是空喊出的悲伤，没有感染力。或许因为着完美的古剑一，我才会对古剑二格外的失望吧。

最后，优点。家园系统绝对是古剑二的亮点，比剑一升级好多，新开创的试菜谱也是很有创意的一招。而且更加让人愿意花时间在上面。我觉得现在的家园应当是在最恰当的设置，其实要说元素略多，不过还没有多到讨厌的地步，而用处很实在。希望以后的家园不要胡乱的添加元素，过于繁复反而会使人望而却步。

想想仙剑一的成功后不是也推出了反响平平的仙剑二，但之后的仙剑三四大方异彩。希望古剑也是如此，在初期的成功和之后的平淡后，爆发出更精彩的篇章。

邂逅

天气很热，阳光似乎要将周围的一切熔化一般。空气纹丝不动，周围异常的安静，行人当然没有，连蝉也似乎被空气捂住了喉咙。我却不知为何，在这阳光下走着。路没有尽头一般，不知引向何方，看到右手旁的斜坡下有一条小河，去河边洗洗脸解解暑，倒是不错的选择。

我踏上了有小腿长的草地，往前走了几步才发现前面坐了个女生，头发披在肩上，一身白色的长裙，在阳光之下，似乎淡淡的发出光芒。这样的走过去倒是有要搭讪的嫌疑，我本能的想绕开，去前面一点的地方，可是她却回过头，对我微微的笑了笑。或许是觉得这样走开不太礼貌，或许是受了那笑容的鼓励，我直直的走了过去。“你好“，走过她时，我略拘谨的打了个招呼，她没有应，我就继续向河边走去，背后传来了若有若无的一声，”原来是今天“。

在河边给脸上，胳膊上都拍上了水，世界都清凉了。既然那个女生没有理我，还是早点走开吧。这时她却站起身，说了句“你好”。我走上坡去，她又坐了下来，似乎想继续说话的样子，我也找了个地方坐下。“今天天气很热啊”“嗯”“不过河边还是挺舒服的”，仿佛为了应和我说的话，空气微微动了动，周围似乎也不那么热了，“是呀”。我不知该说什么了，在我的前方，草地中间或开出或黄或白的小花，河水闪着粼粼的波光慢慢的向前走着，若是“逝者如斯夫”，这慢悠悠的河水倒是和慵懒的夏日时光符合的很好。

“你记得昨天的事么，比如吃了什么？”她突然开口。我看向她，“昨天没什么事啊，吃的也很普通，昨天遇见过你么？”她的皮肤白皙，脸型微圆，很漂亮，年纪看上去比我还略小一些，额头上连一点汗都没有，眼睛中难掩兴奋的光芒。她很开心，是因为遇见我吗？这种自恋的想法连自己都觉得可笑，还是早点忘掉吧。“果然，还是听到的比较好。你可骗不过我的哟。”她似乎已经跟我很熟了，我却有点听不懂了。她又接着问，“那前天的事呢，前一年的都能记得吧，前十年的呢？”“前天当然，前一年的或许会比较模糊吧。十年谁说的准呢。”虽然觉得莫名其妙，既然是美女问的，我还是认认真真的答了。“真厉害。”听了这句话，我都在想着她是不是在讽刺或者嘲弄我，但转头看到她开心的表情，那种发自内心的欢喜，不可能是假的。“你，。。。不记得么？”我只能想到这么白痴的问句。“嗯，过去的只能记得小半日，”她像是专等我问完这句一般，“未来的，未来一年很模糊，未来十年谁说的准呢。”她转向我，像是有些得意的捕捉到了我惊讶的表情，略带调皮的表情里却透着真诚。那句“开玩笑的吧，你怎么证明”在我嘴边徘徊了两圈，终究回到了肚子里。问出来不仅显得我小气，也唐突了她。我的心里，似乎早已相信了。

“你以前没遇到过忘族的人吧，就是我这样，不记得过去而记得未来的人。”“没有，能知晓未来的人，哪那么容易遇到。”她来自“忘族”，那就是还有和她一样的人了，她们一族，都会被当作神一样的对待吧，她倒是一点架子也没有呢。

“很多忘族的人都觉得记忆过去是传说中的事情，但我不这么认为，我一直记得会在这里遇到你呢。”“你们没见过不会预见未来的人么？”她摇头，原来对于她来说，我也是“传说中的存在”呢，难怪她那么开心。想到这里的我，却不知为什么略感失落。

“那你帮我预测下未来吧。”她笑着说：“我又不是神，哪有预测的能力呢？我只知道记忆中的事情而已，记忆的真假，也说不准呢。”“你的记忆里没有我了？”她摇头。我的部分的“未来”倒是被断言了，不过我却不大愿意相信，“或许你记错了呢，我们的记忆也是会出错的，有人做过研究。”她却坚定的摇了摇头，“若是再遇见你，我肯定会记得，不会有错的。”那一丝的怀疑被斩断，我突然感到命运如此强有力的横在我面前，而我，连质疑一下的余地都没有。

既然不能再见，那留个名字吧。“我的。。。”“请不要。”“恩？”“我并没有真名作为交换，还是不要交换姓名的好。”对呀，她不记得过去，可是难道连自己的名字也不记得？“难道你不记得你的名字么？那你的父母，也对，他们或许都不记得给你起过名字。”“名字是神赐的，一般人懂事后会记得自己的假名，那是记忆里别人来称呼他的名字，至于真名，神会挑选时机告诉我们。”“不是父母起的么？”名字神赐，倒是有点意思，“那神怎么告诉你们呢？”“多是遇到相伴终身之人，真名即是刻在墓碑上的名字，有人相伴終老时所称呼的，就是彼此的真名，也有少数在有子女时领悟，也有终生不悟真名的人。”“终生不悟真名之人，岂不是孤独終老么？”“所以真名是神最大的赏赐。”“不过你们一见面，不，还没见面就知道对方是不是自己能终身相伴的人，你不知道我们这里有多麻烦呢。”她肯定记得她的相守终生的人，真名未悟，那是还没遇到么？“是么，不过痴心一片，明知没有神的祝福但依然执着的人，也不在少数，那是让人相当揪心的事呢。”她仍在说着，我突然发现我的心里却绕来绕去仍在想着她的那相伴終老的人，不由苦笑，明知不会再见，想那么多干嘛。

我们继续这样聊着天，她向我介绍了很多忘族的事情，也问了我一些对过去的记忆，言语中透出对过去无限的向往，人总是贪恋自己没有的东西，能记得过去时盼望预知未来，能记得未来后又向往回忆。我委婉的向她表达了这一想法。“不错，忘族即是妄族，狂妄的妄，传说人本来只有回忆，忘族的祖先经过修行，参悟未来，达到全知全能之境，但窥探天机，終受惩罚，后人被抹去回忆。”她又像自我辩解一样，“不过未来終是虚幻，回忆倒更真实一些。”她往身后的草地一靠，说：“跟你说话很开心，你完全不知道自己要说什么，也不知到我要说什么。”这句夸奖听起来怎么那么不像夸奖呢。不过，她全知道么？对了，她该是记得的啊，在我们说话前，她完全记得我们要说什么。“能从早已知道的对话中找到乐趣，你们也是相当的乐观啊。”这句话说完，我忽然有些理解她为什么羡慕我了，有些未来还是不知道为好，何况这是以失去回忆为代价。

草地上一个斜长的身影站了起来，我也跟着站起来，看来是分别的时候了。或许是我的错觉，她的眼圈似乎红了，要是我就一直跟在她后面会怎么样呢，命运也无法阻挡我这么做吧。可她转身离开时，我却如钉在地上一般，一动都不能动，远远的飘来她的告别，“对你而言的遇见，却是对我来说永久的遗忘，早安。”