## Skill improvements after taking quantum mechanics

This term I have take quantum mechanics and in this blog, I will reflect on how taking this course improve my academic skills, including constructing theoretical models, analytical techniques, approximation and numerical methods, design research projects and communicating physics. This course complies very well with the standards set by the American Association of Physics Teachers as an undergraduate course. In terms of constructing theoretical models, I learned how to analyze a microscopic problem by setting up a quantum mechanics model. In this process, the Schrodinger equation often serves as a good start. I have also made improvements on the analytical skills. I can analyze a problem from its Hamiltonian, its angular momentum, and its other invariants. In this process, linear algebra often helps me a lot. We covered a lot on the approximation and numerical methods. We have studied the shooting methods and the matrix diagonalization method. We studied those methods carefully, implemented them in Mathematica and solved problems with them. Towards the end of the term, we also designed research projects on our own. I studied the perturbations on a hydrogen atom. As a result of the study, we communicate the result by writing a paper on it. As for communicating physics, we had plenty of in class discussions that greatly helped our participations and interactions in the class.

## Quantum Mechanics: numerical techniques

In this post, I am going to talk about what I learned from my exposure to numerical techniques.

I am taking quantum mechanics this term and during these weeks, we are exposed to numerical techniques to solve Schrodinger’s equation. In this process, I learned how to solve a Schrodinger’s equation numerically and two techiques were involved: the shooting method and the matrix diagonalization method.

The shooting method is a method that starts with knowing the value of the solution and the first derivative of the solution at some point and proceed from that point to get more of the solution. We assume linear relation locally for the solution and the first derive. When we know the first derivative, we can calculate the change of value of the next point from this point. Also, once we know the second derivative, we can calculate the first derivative at the next point by increasing or decreasing from this point. This process keeps going until we gets somewhere we feel sufficient to understand this system. On the other hand, matrix diagonalization method starts from choosing a basis which is the eigenstates of a known system. From that, we can expression the Hamiltonian in that basis and then get the eigenvectors of the Hamiltonian matrix when we choose a finite size of basis from the infinite. By finding out the eigenvectors and the eigenvalues of the matrix, we manage to get the eigenenergies and reconstruct the eigenstates of the system from the basis chosen. A shortcut that we could take is to split the Hamiltonian matrix into two parts: the parts with diagonal values as the eigenvalues of the chosen basis and whatever is left over from that. A good choice enables us to simplify the problem.

## Physics reflection portfolio

Field I am most confident with: analytical techniques

I am most confident with analytical techniques. I am good at analyzing a physics system. With what I have learned over the last couple of years, I have solid background in math and physics. Math skills are particularly useful for analyzing physical systems. For example, to analyze a simple harmonic oscillation, we need to be able to use differential equations swiftly, which I have no trouble doing. I also gained a lot of knowledge in physics in my toolbox. Not only did I know the equations and theorems, but also I can think of a problem like a physicist. These studies make up my analytical techniques. Even in experimental physics, I can analyze the experiment and identify the errors and assumptions made in the experiment. Thus I feel analyzing techniques is the field that I am most confident with.

Besides, I am able to use very advanced math techniques and this also helps me better analyzing the physical systems. Math plays a very important part in physics and I have taken a significant amount of math over my years at Carleton. This prepares me very well for studying physics. When the physical systems are simple, I can write down simple equations that reflect the exact situation of the system. Using my physics knowledge, I am also enabled to derive a complex system from a simple system such as from a quantum state pointing in x direction to one pointing to any arbitrary direction. Thus, my math skills and physics background gives me great capabilities of analyzing a physics situation.

Contributions to my development of my analytical techniques

In terms of developing my analytical techniques, outside of my coursework, which is obvious, I think my research experience should be the most important. I have done multiple research projects on classical mechanics, engineering and computer science. However, most of my work is experimental work on the detection of gravitational waves.

I started doing research on LIGO in April 2016. I analyzed noises using the coherence tool in O1, ER9, ER10 and O2, identifying the noise sources from the coherence between the strain of the arms and signals in auxiliary sensors. I developed software tools that greatly facilitated the analysis workflow, and recently I am planning to automate the process with a machine learning AI. I also read the technical details of the auxiliary channels to understand the results. The experimental concerns impressed me. I had never worried about seismic movements, quantum noises or thermal noises in any lab before, but when we want to measure a strain of \$10^{23}\$ we must handle them.

After that, I have been working on another project on the signal recycling system. In this project, the configurations of the signal recycling system are optimized for every laser power input at the power recycling mirror and low-frequency cutoffs of 10Hz, 15Hz and 20Hz. We started with a particular laser power and low-frequency cutoff and then generalized to other interferometer designs. We also considered two models for the stochastic background, the flat model and the power law model created by all binary mergers in the history. I learned a lot about the experimental side of LIGO, with relevant applied optics and quantum mechanics. Very interesting results were found in this research and now the paper is being reviewed by LSC members.

These research experience gave me the chance to reflect on how I am actually thinking about physics. The analytical skills developed out of numerous practice, observation and repetitions. For example, when I was analyzing the noises in the interferometers, I need to look at the data and compare it with the historical data. In this process, I think about the physics that might be going on behind the data and this contributes a lot to my analytical skill. Similarly, I need to learn about the optics of the signal recycling system to be able to analyze it for searching the stochastic background. When we got the data the first time, I saw some difference than what I expected and that led me to more interesting questions regarding the system. In these repetitions of questioning and answering, my analytical techniques are developed.

Field I needs to work on: Designing research projects

I need to work on designing a research project. I have done a lot of research under the supervision of a professor or work under a more senior personnel. However, I feel I lack initiation in the process and thus sometimes need a big picture about the direction. This would require me to stand higher, learn widely and think actively about not only “how to do” but also “what to do”. It is a very important ability to become a great scientist, being able to design a research project. Thus in order to improve my ability to design research projects, I should work on this, observing how others operate and thinking about how research can go further.

## Bootstrap: use grid in inline forms

Today,  I am trying to put some bootstrap form controls into one line, and that gives me a bit of headache at first.

## The Problem

I have a select box, an input box and a submit button. I want to put them into one line. I started by trying the class “inline-form“. However, that did not really work for me, as is shown in the screenshot below.

The code is

```<form class='inline-form'>
<select class="form-control" style='width:100%' id="sel1">
<option>1</option>
<option>2</option>
<option>3</option>
<option>4</option>
</select>
<input type="text" class="form-control" id="inlineFormInputGroup"       style='width:100%' placeholder="Username">
<button type="submit" class="btn btn-primary">Submit</button>
</form>```

## Trail 1: Removing ‘form-control’

We realize that the problem is in the class ‘form-control‘, which displays the elements as blocks. Thus, we tried to remove them (and the style width:100%). That did work: all the elements are on the same line. However, that removed all the css features of a bootstrap form, as is expected.

Thus, we have to put the class back since using the style is the whole point of using Bootstrap. It did not work.

## Trial 2: Using Grid System

The next thing we should try is the grid system, which is a triumph of Bootstrap that can is flexible for different screen sizes. The grid system divides a row into 12 columns and you can specify how many columns each element can take. Thus, if we use the form as a row and specify each element’s columns. It will lay in the same line.

However, that did not work with the form-control class. The elements are still displayed in different lines.

The code is shown below. As we can see from the code, we put the form-control class back and added the grid system. The form is defined as a row and the select box has 3 columns, the input 3 column and the button 1 column. We did not use up the 12 columns but it should be fine. All elements should float on the left.

```<form class='inline-form row'>
<select id="sel1" class='col-md-3 form-control'>
<option>1</option>
<option>2</option>
<option>3</option>
<option>4</option>
</select>
<input type="text"  id="inlineFormInputGroup"  placeholder="Username" class='col-md-3 form-control'>
<button type="submit" class="btn btn-primary form-control col-md-1'>Submit</button>
</form>```

That did not work but put us on the right direction: using the grid system. We still know that it is the problem of the form-control class and now we have to deal with how to use the form-control class and the grid system together.

## Solution

After playing with the code for a while. I tried adding <div> outside the elements so it will be the <div>s that directly interact with the grid system and act as an element in the system, not the form elements themselves, which have to carry the form-control class. It worked as a charm, as is shown in the screenshot below.

The code is given below. Using <div> as the agent for the form elements to directly interact with the grid system worked as for putting the elements with form-control class onto the same line.

```<form class='inline-form row'><form class='inline-form row'>
<div class='col-md-3'>
<select id="sel1" class='col-md-3 form-control'>
<option>1</option>
<option>2</option>
<option>3</option>
<option>4</option>
</select>
</div>
<div class='col-md-3'>
<input type="text"  id="inlineFormInputGroup"  placeholder="Username" class='col-md-3 form-control'>
</div>
<div class='col-md-1'>
<button type="submit" class="btn btn-primary form-control">Submit</button>
</div>
</form>```

## Delete all files / folders in subdirectories with a certain pattern on terminal

Today I had a problem on terminal. I have such a folder structure:

`./<level_A>/<level_B>_good`

or

`./<level_A>/<level_B>_bad`

Thus I have some folders(level_A) and in each folder there are another level of folders(level_B). On level_B, there are “good” folders and “bad” folders. “Good” folders end with “_good” and “bad” folders end with “_bad”. Also, there are files in all level_B folders.

For example, a good folder can be

`./folder_A_1/folder_a_good`

and a bad folder can be in the same directory on level A

`./folder_A_1/folder_b_bad`

Normally, when we want to delete a group of folders that ends with a particular name, we just use

`rm -r *_bad`

However, this approach does not apply here because I have too many folders on level_A. If I use the rm command, I have to enter and exit all the folders such as

```cd folder_A_1

cd ../folder_A_2

...```

I have too many folders on level A: folder_A_1 up to folder_A_1000. Hence, I can not use this common approach.

Then I thought of another command I have used: find. That command lists everything in the directory recursively so it is able to target the folders in the subdirectories. That is good. However, how to find, filter and delete? That means, find all the folders recursively, select those paths ending with “_bad”, and delete them. Fortunately, by looking at the manual of find, it turns out that we have a very nice option -delete. Thus we can find all the directories ending with “_bad” using this command

`find . -type d -name "*_bad"`

-type d requires the target to be a directory. -name “*_bad” specifies the pattern of the name. By this, we find and filtered to target all the directories and subdirectories that ends with “_bad”.

Next, we will make use of the command -delete.

`find . -type d -name "*_bad" -delete`

That deleted all the “bad” subdirectories for me and solved my problem. Yay!

I think this can be generalized as a way to simplify processing the system files on terminal. Usually, when it comes to complicated group processing, we have to write bash scripts. However, if we can make good use of the built-in commands, that can save our time.

## Copy a folder of files excluding certain files on Mac terminal

Say I want to copy a folder with 1000 files and lots of subfolders, and I need to do this on Mac terminal because it is a part of streamlined process programmed on bash script. Thus I can not just open Finder, select all and copy from there. I can do this very easily with

`cp -r source_folder target_path`

However, what if I want to exclude some files/subdirectories in this code?

So far, I have put the following requirements:

• There are lots of files to copy, like 1000.
• There are still lots of files to exclude, like 50.
• It must be programmed in bash so no Finder / manual work. One command done

Unfortunately, cp does not offer the function to exclude certain files. Here we need to use rsync.

According to the manual of rsync, it has the following features

1. It basically copies, like cp, or rcp (remote copy)
2. It has a lot more options than the basic copy.
3. It is much faster.

Thus it is good to use rsync. Now let’s go back to the topic: excluding some files or subdirectories during copy. We need to use –exclude option.

We can either put a specific file name or something more general with the asterisk. For example, this one below exclude all hidden files or directories from the copying.

`rsync -r source_folder target_path --exclude='.*'`

Also, we should notice that, just like cp, copying folders using rsync should put -r. If we only want to exclude a folder called bin, we then should

`rsync -r source_folder target_path --exclude='bin'`

## Excluding multiple elements

If we have more than one element to exclude, we just add more –exclude.

`rsync -r source_folder target_path --exclude='bin' --exclude='scripts'`

## Excluding only hidden folders?

Now that we successfully excluded all hidden files or certain files. What if I still want the files but not the folders? In this case, we use a slash ‘/’ to indicate folders. Like the command below, .*/ means all hidden folders.

`rsync -r source_folder target_path --exclude='.*/'`

## Include back certain files/folders

Say I want to exclude all hidden files but not the hidden folders. However, .*/ means only folders; .* means both files and folders. I did not find anyway to mean only files. Thus, we should use the –include option to include the folders first and then exclude everything, like the command below. To better understand this, according to the manual of rsync, –include tells rsync “not to exclude a pattern”.

```rsync -r source_folder target_path --include='.*/' --exclude='.*'
```

## Counting could be recursive

There are lots of algorithm problems that asks for the count of something. They are mostly combinatorics problems. Those problems usually deal with really big numbers and some common strategies apply to a lot of them.

Talking about combinatorics problems, usually what comes up first to my mind is that “I do not know combinatorics; I have not take the course at Carleton.” There is a math course offered once every two years at Carleton called combinatorics. I did not get a chance to take the course. Thus, when the problem asks me to count, I usually start with a slight panic.

However, after I tried a couple of the problems. I realized that the counting problems, although they deal with really large numbers, are not as mathematical as I thought they were. There are some methods that could be used to a lot of the algorithm problems without being an expert on combinatorics.

The most important one I am going to talk about is recursion. The relation of the number of counting with respect to the input could be recursive. It does not mean that the algorithm needs to be implemented with recursion; it means that there might be some useful recursive relation between the output for this problem and the output for a smaller problem. We can take advantage of the recursive relation to implement a dynamic programming algorithm or even a greedy algorithm, which runs much faster than enumerating all possible solutions.

I should start with a problem called k-inverse-pairs array on Leetcode. The problem asks how many arrangements of 1 to n having k inverse pairs. An inverse pair is an occasion that a number comes later is greater than a number comes before it. For example, if we have n = 4, the numbers are 1,2,3,4 and k = 2. We are looking for the number of arrangements of 1,2,3,4 that have 2 inverse pairs. They are

3,1,2,4

2,3,1,4

1,3,4,2

2,1,4,3

1,4,2,3

Thus the answer when n = 4, k = 2 is 5. There are five inverse pairs. Knowing that the point of this post is that counting could be recursive, how to find the recursive relation between the solution for n, k and a set of smaller problems?

First of all, we notice that the max inverse pair is generated when all the numbers are reverted, like when 1,2,3,4 are arranged as 4,3,2,1. There will be n * (n – 1) / 2 inverse pairs generated. Thus, when k is greater than n * (n – 1) / 2, the answer must be zero. When k is equal to n * (n – 1) / 2, the answer must be 1.

Second, we will observe some cases with small n. When n is 1, there is no inverse pair so the answer is zero no matter what. When n is 2, we have 1,2. Thus, when n is 0, we have 1, when n is 1, we have another 1. Those considerations could serve as the base case for our recursive relations.

Third, based on the considerations that we are looking for a recursive relation, we are attacking the main point: the relation between the solution of a general n, k that does not belong to either of the two points above and a smaller problem. We will use ans(n ,k) to denote the generic answer when the input is n and k, where n is greater than 1 and k is less than or equal to n * (n – 1) / 2. We should consider the recursive relation like this: say that we have all the solutions to the all the subproblems with n – 1 elements, What can we do with the last element to make it a solution to the n, k solution?

If we take a solution of n – 1, k. We can just put n at the end of the arrangement to make it a solution of n, k since there are already k inverse pairs in the original array and we append the last element to the end so that no more inverse pair is created. This should allow us to create ans(n – 1, k) solutions. Next, if we take a solution of n – 1, k – 1, we can insert n to the second to the last element so that one more inverse pair is created. That gives us another ans(n – 1, k – 1) solutions. We can generate all the solutions in this manner, following the cases when the last element generates 0, 1, 2… inverse pairs.

However, when we are going down the cases, there are two different restrictions that could end it. First, n can not create more than n – 1 inverse pairs. In other words, it can not be put at a place before the first element. When it is put to the beginning, n – 1 inverse pairs are created. It can not go over that. Second, n can not generate more than k inverse pairs. If n alone generates more inverse pairs than needed for our problem, that is not going to be a solution. We stop whenever either of the two restrictions ends the sum.

By this, we have the recursive solution as such

ans(n , k) = sum(ans(n – 1, i), i, max(0, k – n + 1), k).

It sums ans(n – 1, i) with i going from max(0, k – n + 1) to k. The max of 0 and k – n + 1 reflects the two restrictions we mentioned in the previous paragraph. i is the number of inverse pair of the n – 1 elements. Zero indicates that it can not create less than 0 inverse pairs; in other words, the last element can not create more than k inverse pairs. The k – n  + 1 reflects the restriction that the last element can not create more than n – 1 inverse pairs, in which case the rest of the n – 1 elements will create k – n + 1 inverse pairs.

At this point, we are at a good position in terms of theoretical analysis of the problem. We have a polynomial solution based on a recursive relation. Obviously, we can implement the algorithm with dynamic programming. However, there are two details to note.

• When implemented in DP, the algorithm could make use of calculate sum, such as ans(n, k – 1), instead of summing from 0 to the max all the time. That reduces the running time from n cube to n square.
• The problem requires modulo 10^9 + 7, which is a, though reasonable, but tricky requirement. If we do the modulo each time after we calculate the sum, we may risk going over the limit of integers. That would give us negative numbers. Thus, we have to use a long to temporarily store the sum and then do the modulo and convert it back to int.

From this problem, the most important thing we learned is that counting can be done recursively such as with DP, not just with brute-force enumeration. Another similar problem to look at is find the derangement of an array, which reflects exactly the same idea.

Categories: CS

## Course Schedule III

Today, I was thinking about a question on Leetcode, Course Schedule III.

The problem first appeared on its weekly online contest. I went to the contest but did not manage to solve it there. Let me rephrase the question here. You have a list of courses and, for each course, you have two numbers: duration and deadline. Duration is the time it takes to complete the course. Deadline is the time you have to finish the course. Then, you have to decide how many courses you are able to take at most, assuming that you can not take two courses at the same time.

Hence, this question is a weird version of the greedy scheduling problems: a hybrid of activity scheduling and deadlines. Activity scheduling has durations but not deadlines. However, this one has deadlines. Deadline scheduling always goes for the earliest possible deadline and it does not work for this problem since if the task with the earliest deadline takes a lot of time that should have been used for more courses, that would not be optimal. For example, if we have

Course 1: duration 10, deadline 10;

Course 2: duration 2, deadline 11;

Course 3: duration 2, deadline 11.

If we go for Course 1, which has the earliest deadline, we waste our time take the long course 1 and the time could have been used to take course 2 and 3, a plan that allows us to finish two courses.

Thus, in activity scheduling, we always go for the shortest activity, so here, what about alway taking the shortest course first? That does not work either.

Course 1: duration 10, deadline 32

Course 2:  duration 11, deadline 11

Course 3: duration 11, deadline 22

In this case, if we use our strategy, we will go for Course 1 first since it has the shortest duration. However, that means we can not take Course 2 since, after course 1, we will be at time 10, and there is not enough time to finish course 2 by time 11. However, we should be able to finish all three courses if we take them as course 2, 3, and then 1. Thus, this strategy does not work either.

None of the strategy works. It seems we have to find a “trade-off” between the deadline and the duration. My thinking during the contest ends here.

When I look at the answer, I find this is what the answer does. It checks each course by deadline and keeps track of the selected courses up to the current index. If we can take the next course, we take it; otherwise, we see if we can abandon the longest course taken and take the next course. If the alternative still does not work, that means the new course is longer than any course we have taken before so we do take it.

That is the answer to the problem but why does it work? I need some insights. After thinking about it for a few days, I realize tonight that this is based on a recursive relation between the optimal of a solution and the optimal plus possibly a new course. All courses selected before course k must be finished by the deadline of course k. That is the same for k + 1. We also have to make sure that the total duration is optimized, which means, if there are multiple ways to accomplish the same number of courses before the deadline, we have to make sure that the duration used up is minimum. Hence, two conditions:

1. Max courses.
2. Min duration for the same number of courses.

Thus, if the new course is good and can be finished by the new deadline, we are good since we have one more course. Otherwise, we still keep the same amount of course so we have to make sure that duration is minimum. The new course, although can not be added, might still be taken by taking away the longest course. Thus, if the new course is shorter than the longest course, we take it and drop the longest current course.

What we must learn is that we should never forget that a lot of things are recursive. We should always make a try to find recursive relations. Greedy, DP, DFS, BFS are all based on recursive relations. The reason why I did not solve this problem during the contest is that I only tried to use those existing solutions to directly solve this problem, instead of going one level further into their fundamentals, recursive relation.

Categories: CS

## Max Points on a Line

Today I am solving an algorithm problem on Leetcode: Max Points on a Line. This is tagged as a hard problem and it is indeed not a easy one. I did not manage to solve it before I look at the answer so I think it worth reflecting a bit so as to learn from this problem.

I should state the problem again. The problem asks us to write an algorithm that gives the max number of collinear points among a set of points. Hence, the input is an array of Point objects, Point[], and the output is an integer. Each point object contains two attributes, x and y. We need to find the max number of points among the array of points that are on the same line.

I started solving the problem with dynamic programming since I noticed that it is a optimization problem, finding the max number of points that are on the same line. Then I went on looking for the optimal substructure: the relation between the optimal solutions for subsets of the problem to the original problem. In our case, this will be a relation between the max collinear points of all the points with the max collinear points of some subsets of the points. I started thinking about relation between the optimal for a full array and the optimal for all but the last one. The relation does not seem to exist because there might be ties for the max number of collinear points, which means, there might be two subsets of points on the same line that have the same number of points. In this case, if the last point is on one of the lines, there will be no way to guarantee we can choose the one that is good for the next point, which will be predicting the future. Also, what makes it worse, the last point can also be on a line that is not the best in the subset. In this case, the optimal substructure totally disappeared. Hence, this does not seem to work.

Then, I tried another dynamic programming approach, looking for the relation between the max number of collinear of points on the same line that contains the new point with that of the subset. I am only looking for the lines that contains the last point, and at the end, I will calculate the max of the whole array. This is a common trick of DP problem: when we are in trouble looking for optimal substructure directly between the answers, we take a step back and look for the max that contains the new member. Then, we have to get the max of all, instead of just returning the last element. An orthodox example of this is the longest increasing subsequence. In this case, there is a pretty good relation: the max collinear line that contains the new point is either the max of any subset before plus this point if it is on the line, or two, when it is not on any of them. For a while, I thought it was correct. I realized that I should record the max lines to identify if the new point is on any line of the subset. This leads to the same problem as before: if there are ties, the information about the tied lines will be missing. Then, if the new point is a part of the tied lines, we will get the wrong answer. Since in DP problems, all the answers depend on each other, the whole problem will be wrong if we get a subproblem wrong. Thus, at this point, I have to say that DP does not work for this problem, despite that it is an optimization problem, a strong indicate of a DP solution.

Then, driving by the desire to get something accepted, I also tried brutal force. Then DP solutions tried above aim for a complexity of O(n^2); however, brutal force is O(n^3). The idea is pretty simple: try all pairs of points and see how many points are on the line of line determined by the two points. Trying all pairs take O(n^2) and checking all other points gives O(n) so the total takes O(n^3). The idea is simple but it has many edge cases.

1. Two points may be on the same vertical or horizontal line.
2. Two points may overlap. What’s worse, two neighboring points in the array may overlap. In this case, the “pair” that we started with overlaps.

Those edge cases give us too many if statements and logical pains. I struggled a while with it and give up. It does not worth it spending too much time on a solution that will eventually fail with timing out.

Finally I checked the solution and find out that I was in the wrong direction. I forgot about maps. The solution fix one of the points, check all other points and see how many of them are on the same line. It identify each line passing through the point with the slope of the line. It creates a map between the slope and the number of points with that slope. When it checks all the points, it classifies the points with the slope. That is such an easy approach.

Where I got wrong is that I failed to identify the classifying nature of the problem. Like I said above, I totally forgot about maps. When you stand at some point, looking at all other points, a finite number of points, around you, you can easily say that a point has a certain slope. Especially we want the max number of points on a line, a basic idea will be to classify all the points as they are on the same line. Although the idea is simple, I would say the problem is indeed a hard one since the classification nature is not obvious, or even elusive since the slope is a continuous value which usually does not welcome classifying. We can classify it just because the number of points is finite. Classification are mostly indicated by some discrete nature of the problem, such as finding the duplicate number in an array. However, here we have a plane where each point has great freedom of being where it wants to be. It is indeed hard to think of maps when solving a problems with such a great freedom. Anyway, at least, I should learn that DP, divide and conquer and brutal force are not the only ways to solve a optimization problem. There is one more way, simpler and more elegant, classification.

Categories: CS