2021-11-01

Be the Best of Whatever You Are

If you can’t be a pine on the top of the hill,
Be a scrub in the valley — but be
The best little scrub by the side of the rill;
Be a bush if you can’t be a tree.

If you can’t be a bush be a bit of the grass,
And some highway happier make;
If you can’t be a muskie then just be a bass —
But the liveliest bass in the lake!

We can’t all be captains, we’ve got to be crew,
There’s something for all of us here,
There’s big work to do, and there’s lesser to do,
And the task you must do is the near.

If you can’t be a highway then just be a trail,
If you can’t be the sun be a star;
It isn’t by size that you win or you fail —
Be the best of whatever you are!

2021-10-31

Fall, leaves, fall

by Emily Brontë

Fall, leaves, fall; die, flowers, away;
Lengthen night and shorten day;
Every leaf speaks bliss to me
Fluttering from the autumn tree.
I shall smile when wreaths of snow
Blossom where the rose should grow;
I shall sing when night’s decay
Ushers in a drearier day.

2021-10-30

Plane Division by Lines

Problem

How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?

What is the maximum number $ L_n $ of regions defined by n lines in the plane?

Solution

The nth line (for n > 0) increases the number of regions by k if and only if it splits k of the old regions, and it splits k old regions if and only if it hits the previous lines in k-1 different places. Two lines can intersect in at most one point. Therefore the new line can intersect the n-1 old lines in at most n-1 different points, and we must have $ k \leq n $. We have established the upper bound
$ L_n \leq L_{n-1} + n, \qquad \text{for n>0. } $

Furthermore it’s easy to show by induction that we can achieve equality in this formula. We simply place the nth line in such a way that it’s not parallel to any of the others (hence it intersects them all), and such that it doesn’t go through any of the existing intersection points (hence it intersects them all in different places).

recurrence relation

$ L_0=1; $
$ L_n=L_{n-1}+n, \qquad \text{for n>0. } $

Simply put, each number equals a triangular number plus 1.

In other words, $ L_n $ is one more than the sum $ S_n $ of the first n positive integers.

$ L_n = \frac{1}{2}n(n+1)+1 $

resources

2021-10-24

A Psalm of Life

What The Heart Of The Young Man Said To The Psalmist.

by Henry Wadsworth Longfellow

Tell me not, in mournful numbers,
Life is but an empty dream!—
For the soul is dead that slumbers,
And things are not what they seem.

Life is real! Life is earnest!
And the grave is not its goal;
Dust thou art, to dust returnest,
Was not spoken of the soul.

Not enjoyment, and not sorrow,
Is our destined end or way;
But to act, that each to-morrow
Find us farther than to-day.

Art is long, and Time is fleeting,
And our hearts, though stout and brave,
Still, like muffled drums, are beating
Funeral marches to the grave.

In the world’s broad field of battle,
In the bivouac of Life,
Be not like dumb, driven cattle!
Be a hero in the strife!

Trust no Future, howe’er pleasant!
Let the dead Past bury its dead!
Act,—act in the living Present!
Heart within, and God o’erhead!

Lives of great men all remind us
We can make our lives sublime,
And, departing, leave behind us
Footprints on the sands of time;

Footprints, that perhaps another,
Sailing o’er life’s solemn main,
A forlorn and shipwrecked brother,
Seeing, shall take heart again.

Let us, then, be up and doing,
With a heart for any fate;
Still achieving, still pursuing,
Learn to labor and to wait.

2021-10-13

LeetCode - Algorithms - 221. Maximal Square

Problem

221. Maximal Square

Java

dynamic programming

class Solution {
    public int maximalSquare(char[][] matrix) {
        final int[][] D = {
                {-1, 0},  // up
                {0, -1},  // left
                {-1, -1}  // diagonal
        };
        int h = matrix.length;
        int w = matrix[0].length;
        int[][] countMatrix = new int[h][w];
        for (int i = 0; i < w; i++) {
            countMatrix[0][i] = matrix[0][i] == '1' ? 1 : 0;
        }
        if (h > 1) {
            for (int j = 1; j < h; j++) {
                countMatrix[j][0] = matrix[j][0] == '1' ? 1 : 0;
            }
            for (int i = 1; i < h; i++) {
                for (int j = 1; j < w; j++) {
                    if (matrix[i][j] == '1') {
                        int minCount = Integer.MAX_VALUE;
                        for (int k = 0; k < 3; k++) {
                            int x = i + D[k][0];
                            int y = j + D[k][1];
                            if (minCount > countMatrix[x][y])
                                minCount = countMatrix[x][y];
                        }
                        countMatrix[i][j] = minCount + 1;
                    } else {
                        countMatrix[i][j] = 0;
                    }
                }
            }
        }
        int maxCount = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (countMatrix[i][j] > maxCount)
                    maxCount = countMatrix[i][j];
            }
        }
        return maxCount * maxCount;       
    }
}

Submission Detail

74 / 74 test cases passed.
Runtime: 5 ms, faster than 51.51% of Java online submissions for Maximal Square.
Memory Usage: 49 MB, less than 8.01% of Java online submissions for Maximal Square.

2021-10-03

My English Words List - October - 2021

brownie

noun

a small square or rectangle of rich usually chocolate cake often containing nuts

The dinner will include Swiss steak, baked potato with sour cream and butter, slaw, green beans, roll and butter, and a brownie.

Chocolate brownie

ranch

noun

a large farm for raising horses, beef cattle, or sheep

lives on a cattle ranch in Texas that’s as big as the whole state of Rhode Island

Ranch

dove

noun

any of numerous pigeons especially : a small wild pigeon

Columbidae

reconciliation

noun

National Day for Truth and Reconciliation

duo

noun

The comedy duo will perform tonight.

liar

noun

a person who tells lies

She called him a dirty liar.

Lie

A person who communicates a lie may be termed a liar.

tilde

noun

the mark used to indicate an approximate value

Tilde

receipt

noun

Keep your receipt in case you need to return anything.

Receipt

anthem

noun

“O Canada“ is the national anthem of Canada.

celestial

adjective

the sun, moon, and stars are celestial bodies

The moon is Earth’s closet and most studied celestial neighbour

knead

verb

kneading dough

Knead the dough until it is smooth.

My grandfather taught me how to knead the bread dough.

tortilla

noun

a thin round of unleavened cornmeal or wheat flour bread usually eaten hot with a topping or filling (as of ground meat or cheese)

Tortilla

tortilla chip

a thin, hard piece of food (called a chip) that is made from corn and usually salted

Tortilla chip

hummus

noun

a soft food made of ground chickpeas, garlic, and oil

Hummus

guacamole

noun

pureed or mashed avocado seasoned with condiments
a Mexican food made of mashed avocado usually mixed with chopped tomatoes and onion

Guacamole

lien

noun

a legal claim that someone or something has on the property of another person until a debt has been paid back

The bank had a lien on our house.

Lien

The owner of the property, who grants the lien, is referred to as the lienee and the person who has the benefit of the lien is referred to as the lienor or lien holder.

deductible

noun

an amount of money that you have to pay for something (such as having your car fixed after an accident) before an insurance company pays for the remainder of the cost

I have an insurance policy with a $1,000 deductible.

Deductible

warranty

noun

a one-year warranty for the refrigerator

Warranty

New car factory warranties commonly range from one year to five years and in some cases extend even 10 years, with typically a mileage limit as well. Car warranties can be extended by the manufacturer or other companies with a renewal fee.

Used car warranties are usually 3 months and 3,000 miles

trade-off

noun

a balancing of factors all of which are not attainable at the same time
a situation in which you must choose between or balance two things that are opposite or cannot be had at the same time

Trade-off

spine

noun

Numbering order of the vertebrae of the human spinal column

The vertebral column, also known as the backbone or spine, is part of the axial skeleton.

Vertebral column

ulna

noun

Ulna

blob

noun

a small drop or lump of something viscid or thick

flicked a blob of jelly on the toast and began to spread it around

calcium

noun

Her doctor said she should eat more foods that are high in calcium, such as milk and cheese.

Calcium

casual

adjective

a casual meeting

casual clothing

causal

adjective

There is a causal link between poverty and crime.

spam

noun

e-mail that is not wanted
e-mail that is sent to large numbers of people and that consists mostly of advertising

Email spam

Email spam, also referred to as junk email or simply spam, is unsolicited messages sent in bulk by email (spamming).

pantry

noun

homemade jams and pickles are stored in a separate pantry off the kitchen

Pantry

A pantry is a room where beverages, food, and sometimes dishes, household cleaning chemicals, linens, or provisions are stored.

prism

noun

A rectangular prism

Prism

defect

noun

This small defect greatly reduces the diamond’s value.

tote

noun

A tote bag

Tote bag

mandarin

noun

the official language of China
the group of closely related Chinese dialects that are spoken in about four fifths of the country and have a standard variety centering about Beijing

Mandarin Chinese

Mandarin orange

refuge

noun

a wildlife refuge

treat

noun

the act of providing another with free food, drink, or entertainment

Trick-or-treating is a customary celebration for children on Halloween. Children go in costume from house to house, asking for treats such as candy or sometimes money, with the question, “Trick or treat?” The word “trick” implies a “threat” to perform mischief on the homeowners or their property if no treat is given.

Trick-or-treating

trick or treat

noun

a Halloween practice in which children wearing costumes go from door to door in a neighborhood saying “trick or treat” when a door is opened to ask for treats with the implied threat of playing tricks on those who refuse

We got all dressed up for trick or treat.

‘Trick or Treat’: A History

2021-10-01

October

by Robert Frost

O hushed October morning mild,
Thy leaves have ripened to the fall;
Tomorrow’s wind, if it be wild,
Should waste them all.
The crows above the forest call;
Tomorrow they may form and go.
O hushed October morning mild,
Begin the hours of this day slow.
Make the day seem to us less brief.
Hearts not averse to being beguiled,
Beguile us in the way you know.
Release one leaf at break of day;
At noon release another leaf;
One from our trees, one far away.
Retard the sun with gentle mist;
Enchant the land with amethyst.
Slow, slow!
For the grapes’ sake, if they were all,
Whose leaves already are burnt with frost,
Whose clustered fruit must else be lost—
For the grapes’ sake along the wall.

2021-09-30

Thirty Days Hath September

Thirty days hath September,
April, June and November.
All the rest have thirty-one,
Excepting February alone,
And that has twenty-eight days clear
And twenty-nine in each leap year.

2021-09-16

Bernhard Riemann

The answer to these questions can only be got by starting from the conception of phenomena which has hitherto been justified by experience, and which Newton assumed as a foundation, and by making in this conception the successive changes required by facts which it cannot explain. Researches starting from general notions, like the investigation we have just made, can only be useful in preventing this work from being hampered by too narrow views, and progress in knowledge of the interdependence of things from being checked by traditional prejudices.
This leads us into the domain of another science, of physic, into which the object of this work does not allow us to go to-day.

One now finds indeed approximately this number of real roots within these limits, and it is very probable that all roots are real. Certainly one would wish for a stricter proof here; I have meanwhile temporarily put aside the search for this after some fleeting futile attempts, as it appears unnecessary for the next objective of my investigation.

Natural science is the attempt to comprehend nature by precise concepts.

The word hypothesis has now a somewhat different significance from that given it by Newton. We are now accustomed to understand by hypothesis all thoughts connected with the phenomena.

Newton was far from the crude thought that explanation of phenomena could be attained by abstraction.

No mathematician is more associated with the midnineteenth-century transition from algorithmic to conceptual thought than Riemann. (The Princeton Companion to Mathematics)

It is clearly a preliminary note and might not have been written if L. Kronecker had not urged him to write up something about this work (letter toWeierstrass, Oct. 26 1859). It is clear that there are holes that need to be filled in, but also clear that he had a lot more material than what is in the note. What also seems clear: Riemann is not interested in an asymptotic formula, not in the prime number theorem, what he is after is an exact formula! (Atle Selberg comments about Riemann’s paper On the Number of Primes Less Than a Given Magnitude)

黎曼的这篇1854年的论文，是非常重要的，也是几何里的一个基本文献，相当一个国家的宪法似的。爱因斯坦不知道这篇论文，花了七年的时间想方设法也要发展同样的观念，所以爱因斯坦浪费了许多时间。… 不过很有意思的是我想 Riemann-Christofell 曲率张量是一个很伟大的发现，黎曼就到法兰西科学院申请奖金。科学院的人看不懂，就没有给他。… 得不得到奖不是一个很重要的因素，黎曼就没有得到奖。他的 Riemann-Christofell 张量在法兰西的科学院申请奖没有得到。 (什么是几何学, 陈省身)

Before Riemann introduced the notion of what is now called a ‘Riemann surface’, mathematicians had been at odds about how to treat these socalled ‘many-valued functions’, of which the logarithm is one of the simplest examples. … Riemann taught us we must think of things differently. (The Road to Reality, chapter 8 Riemann surfaces and complex mappings, Roger Penrose)

Only the genius of Riemann, solitary and uncomprehended, had already won its way by the middle of the last century to a new conception of space, in which space was deprived of its rigidity, and in which its power to take part in physical events was recognized as possible. (Albert Einstein)

His contemporaries were to see nothing of him while he waded through Cauchy’s output. Several weeks later Riemann resurfaced, declaring that ‘this is a new mathematics’. What had captured Cauchy and Riemann’s imagination was the emerging power of imaginary numbers. (The Music of the Primes, Riemann’s Imaginary Mathematical Looking-Glass, Marcus du Sautoy)

Euclid in Alexandria. Euler in St. Petersburg. The Göttingen trio — Gauss, Dirichlet, Riemann. The problem of prime numbers had been passed on like a baton from one generation to another. The new perspectives of each generation provided impetus for a fresh surge along the track. Each wave of mathematicians left its characteristic mark on the primes, a reflection of their era’s particular cultural outlook on the mathematical world. (The Music of the Primes, chapter 5 The Mathematical RelayRace: Realising Riemann’s Revolution, Marcus du Sautoy)

Selberg spoke about his view on the Riemann Hypothesis. Although he had made a major contribution on the way to a proof. he stressed that there was still very little to support its truth. ‘I think the reason that we were tempted to believe the Riemann Hypothesis then was essentially that it is the most beautiful and simple distribution that we can have. You have this symmetry down the line. It would lead also to the most natural distribution of primes. You think that at least something should be right in this universe.’
Some misinterpreted his comments, thinking that Selberg was casting doubt on the validity of the Riemann Hypothesis. Yet he was not as pessimistic as Littlewood who believed the lack of evidence meant the Hypothesis was false. ‘I have always been a strong believer in the Riemann Hypothesis. I would never bet against it. But at that stage I maintained that we didn’t really have any results either numerical or theoretical that pointed very strongly to its truth. What the results pointed to was that it was mostly true.’ (The Music of the Primes, chapter 7 Mathematical Exodus: From Göttingen to Princeton, Marcus du Sautoy)

Many of the mathematicians who have contributed to our understanding of the primes have been rewarded with long lives. Having proved the prime number theorem in 1896, Jacques Hadamard and Charles de la Vallée-Poussin both lived into their nineties. People had begun to believe that their having proved the Prime Number Theorem had made them immortal. The belief in a connection between longevity and the primes has been further fulled by Atle Selberg and Paul Erdös, whose alternative elementary proof the Prime Number Theorem in the 1940s saw both of them live into their eighties. Mathematicians joke about a new conjecture: anyone who prove the Riemann Hypothesis will indeed become immortal. (The Music of the Primes, Chapter 12 - The Missing Piece of the Jigsaw, Marcus du Sautoy)

While for many mathematicians “intuitive work” can be hit-or-miss, Riemann’s mathematical intuitions were incredibly acute, and his results generally turned out to be correct. (The Millennium Problems: the Seven Greatest Unsolved Mathematical Puzzles of Our Time, Keith Devlin)

Bernhard Riemann
Bernhard Riemann
Math is only available to a few. It is like explaining music to someone who is deaf. (Isadore Singer)
Speed means nothing. Math doesn’t depend on speed. It is about deep. (Yuri Burago)

2021-09-05

My English Words List - September - 2021

ukulele

noun

a musical instrument that is like a small guitar with four strings

Ukulele

PIN

abbreviation

personal identification number

Personal identification number

tuba

noun

Tuba

easel

noun

a frame for supporting something (such as an artist’s canvas)

pickle

noun

an article of food that has been preserved in brine or in vinegar specifically : a cucumber that has been so preserved

Pickled cucumber

hitchhike

verb

Her car broke down, so she had to hitchhike back home.

Hitchhiking

chapel

noun

a wedding chapel in Las Vegas

Chapel

hedgehog

noun

porcupine

noun

Porcupine

allergy

noun

a condition in which a person is made sick by something that is harmless to most people

Allergy

Many people have some form of allergy.

allergy aware school

attorney

noun

a person and usually a lawyer who acts for another in business or legal matters

finished law school and became an attorney

annul

verb

to say officially that something is no longer valid
to make (something) legally void

wants the marriage annulled

to cancel by law
take away the legal force of

annul a marriage

acorn

noun

the nut of the oak tree

Acorn

typo

noun

a mistake (such as a misspelled word) in typed or printed text

I spotted three typos on the menu.

Typographical error

A typographical error (often shortened/nicknamed to typo), also called misprint, is a mistake (such as a spelling mistake) made in the typing of printed (or electronic) material.

alumnus

noun

plural alumni

someone who was a student at a particular school, college, or university

Alumnus