. Introduction First, you must shift your own focus and attention. Instead of focusing on what you don’t want the kid to do, focus on...
. Simplify Strip every sentence to its cleanest components. Examine every word to see if it needs to be there, and simplify or remove...
An alternative to the one hot representation is where you figure out the meaning of a word by the words that frequently appear nearby....
The one hot representation of a word is a vector the length of the vocabulary, with all 0’s except a 1 to represent that...
(D2.2.1): Addition of natural numbers. Let \(m\) be a natural number. To add 0 to \(m\), define \(0+m=m\). Assume inductively we have...
(D2.3.1) Multiplication of natural numbers. Let \(m\) be a natural number. We define \(0\times m=0\). Now if we know \(n\times m\), we...
(D2.1.1): A natural number is any element of the set: \begin{equation*} \mathbf{N}:=\{0,1,2,3,4, \ldots\} \end{equation*} Let \(n++\)...
Given \(N\), how do I generate all the valid push/pop sequences (or draw all the trees)? I’ll generate the sequence of 1’s and 0’s....
We showed that the number of binary trees with \(N\) nodes is the Catalan numbers. It is also the number of valid push/pop sequences for...
Say we have the numbers from 1 to \(N\) in sequence. We will do a random sequence of pushes and pops into a stack: \(N\) pushes and...
Suppose we want to populate \(2n\) positions with exactly \(n\) 1’s and \(n\) -1’s. But we have a constraint. For any given \(k\) where...
He describes a focusing exercise that will get you focused within two minutes. It’s a breathing/meditation exercise. I don’t want to...
The Unschedule asks you to commit to starting for 30 minutes. What you accomplished is less important than the fact that you got...
If you’ve had to go through not being able to solve a problem that others found easy, or if you’ve been criticized often for less than...
One of the worst things about procrastination is that it leads to putting off living. At the end, you didn’t get much work done, nor did...
How you talk to yourself determines the attitudes and beliefs that determine how you feel and act. Statements like “I should do it” or...
Every polynomial with real coefficients can be written as a product of linear or quadratic terms, each having real coefficients. Proof:...
If a polynomial \(f(x)\) has real coefficients, and has a nonzero constant term, then the number of positive real roots is the number of...
To check if a function is symmetric about the origin, replace \(y\) with \(-y\) and \(x\) with \(-x\) and see if the equation of the...
TODO: Note the equations. Parabola A parabola is the set of all points that are equidistant from a point (the focus) and a fixed line...
If two lines are perpendicular, then \(m_{1}m_{2}=-1\) where \(m_{i}\) is the slope of the line. Proof Without Trigonometry Here’s the...
Here is an example of proving something using induction in Sage. Suppose we want to prove that: \begin{equation*}...
When You Know 2 Sides and 1 Angle \begin{equation*} A=\frac{1}{2} b c \sin \alpha \end{equation*} When You Know 1 Side and 2 Angles...
Law of Sines Consider this triangle. Draw a line vertically down from \(B\). Label the length of this line as \(h\) (for height). Now...
Formula for \(\cos(\alpha-\beta)\) Consider the unit circle below: Here, we make \(\overline{AB}=\overline{CD}\), so they have the...
Some things to note: The sum of all the coefficients is \(2^{n}\). To prove this, evaluate \(\left(a+b\right)^{n}\) with \(a=1,b=1\) The...
We know that: \begin{equation*} \sum_{k=1}^{n} k=\frac{n(n+1)}{2} \end{equation*} We want to find the expression for \begin{equation*}...
\(A\ge G\ge H\) if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) { var align = "center", indent = "0em", linebreak =...
The sum of a geometric sequence is: \begin{equation*} S_{n}=\frac{a\left(r^{n}-1)}{r-1} \end{equation*} Note, this is assuming \(n\)...
The sum of an arithmetic series is: \begin{equation*} S=\frac{1}{2}\left(a+l\right) \end{equation*} where \(l\) is the last term. if...
Say we want the roots of \(z^{n}=1\). Let \(z=re^{i\theta}\). Then \(z^{n}=r^{n}e^{in\theta}=1\). We immediately see that \(r=1\). Thus...
Given \(x^{2}+bx+c=0\), let the roots be \(\alpha,\beta\). Then: \begin{equation*} \alpha+\beta=-b \end{equation*} \begin{equation*}...
Remainder Theorem If a polynomial \(p(x)\) is divided by \(x-r\), then the remainder is \(p(r)\). To prove this, let \(p(x)=Q(x)(x-r) +...
Equations of the Form \(\sqrt{ax^{2}+bx+c}\pm\sqrt{ax^{2}+bx+d}=k\) \begin{equation*} \sqrt{ax^{2}+bx+c}+\sqrt{ax^{2}+bx+d}=k...
\begin{equation*} 2*x^{2}-xy+y^{2}=4 \end{equation*} \begin{equation*} 4*x^{2}-5xy+3y^{2}=6 \end{equation*} Manipulate the two equations...
Determinant of a 2x2 matrix: \begin{equation*} \left|\begin{array}{ll}a & b \\ c & d\end{array}\right|=ad-bc \end{equation*} The minor...
\begin{equation*} \ ||z_{1}|-|z_{2}||\le|z_{1}+z_{2}|\le|z_{1}|+|z_{2}| \end{equation*} The second inequality follows from the triangle...
\(z^{n}+\overline{z}^{n}\) is a real number for all positive \(n\). Proof 1 Treat \(z=re^{i\theta}\) and you can show that the sum...
Given: \begin{equation*} \frac{a}{b}=\frac{c}{d} \end{equation*} Componendo: \begin{equation*} \frac{a+b}{b}=\frac{c+d}{d}...
Chapter 2 Aim high, but set incremental goals. You have to continually know people’s objections, and prepare the responses in advance....
How fast is the iterative version of the Fibonacci algorithm? You’d think it is \(O(n)\), but it’s really \(O(n^{2})\), because for...
In backtracking algorithms, you make a sequence of decisions. Every recursive call will make one decision, and will take as an input...
Given a set \(X\) of positive integers, can you find a subset that sums to \(T\)? The general idea is that you have two choices: Either...
Suppose you have a game on an \(n\times n\) board with some rules and players take turns. Assume no randomness in the game. For most...
Let \(x,y\) be two non-negative integers. We want to compute \(p\), the product: Set p=0 While x > 0: if x is odd: p = p + y x = x/2...
Let \(X\) be the vector of all your features (i.e. \(X=(X_{1}, X_{2},\dots, X_{p})\), then the output is: \begin{equation*}...
There are (mostly) two types of concurrency bugs: Non deadlock and deadlock bugs. Of the non-deadlock bugs, the main types are:...
A semaphore has an integer value that you set when you initialize. It has two operations: wait and post. The wait operation will first...
Sometimes we want a thread to check if a condition is true before continuing execution. You could just use a global variable and check...
Concurrent Counters What if you have a shared counter, and you want several threads to update it? Simply locking before update will...
Normally, we create threads, but the OS schedules them however it likes. Locking/unlocking gives the programmer some semblance of...
When creating a lock, you must do two things: Initialize the lock Check if lock/unlock failed! (i.e. check the error code). It’s common...
A thread is lot like a process, except that it shares memory with other threads. A thread has its own program counter from which it gets...
When choosing a lawyer/agent, don’t pick the one who knows the field best. Pick the one who is the best negotiator. The two qualities do...
. Introduction Claim: People advance in their career due to technical skills and social skills. The estimate is that 85% of success is...
Note that this chapter is mostly about a fixed amount of value, so it’s a zero sum negotiation. Preparing To Negotiate Step 1: Assess...
Pilot projects: If the buzz is positive, then early setbacks are seen as expected. But if the buzz is negative, then each new problem...
There are really two audiences: The rational calculator and the intuitive decision maker. If you don’t make your ideas accessible to the...
The two most reliable ways to persuade people: Offer them solid reasons to say “yes” Back those reasons up. You don’t need to do much if...
Don’t assume people know what they want or need. Be prepared to educate them if you sense this is the case. Ask yourself: Why might it...
Nervous or unconfident people tend to focus exclusively on their message rather than getting a feel of what the other person is...
The five barriers: Lack of relationships Poor credibility Miscommunication Contrary beliefs Conflicting interests Credibility is not...
A Technique For Producing Ideas He took this from James Webb Young’s book: A Technique For Creating Ideas. Strongly recommends the book....
Six persuasion channels: Channel 1: Interest Based Persuasion Any time someone frames a sales pitch in terms of the other person’s...
There are usually four steps: Survey your situation Confront the five barriers Make your pitch Secure your commitments You must form a...
. Introduction She points out that several of our role models (Rosa Parks, etc) were introverts. Yet the message society often gives us...
Keep in mind that the debugger interferes with the program - especially when real time behavior is involved. Read this chapter for ways...
Some useful information here. M-x speedbar could be really handy here.
The GDB Text User Interface (TUI) is a terminal interface which uses the ‘curses’ library to show the source file, the assembly output,...
Sequences User Defined Commands You can assign a name to a sequence of commands. You can allow for arguments. They are accessed using...
Prompt You can change the prompt. If yoru gdb has python scripting enabled, you have prompt extensions. Command History You can set the...
While nearly all GDB commands are available for all native and cross versions of the debugger, there are some exceptions. This chapter...
This section has information on how to do remote debugging.
This is when you want to debug remotely or on a different architecture.
To change the program you want to debug, type file FILENAME. It will look at $PATH if it doesn’t find it. You can also load .o files...
Assignment To modify x, do print x=4 You can also use set. Or set variable. Continuing at a Different Address Use jump LOCATION to...
You can do things like query which symbol is at an address (or close to it). You can demangle names. Or the information about the...
If gdb doesn’t figure out the language automatically, you can set it using set language. show language shows the current language. This...
Now these three stages of analytical reading are the ideal. You will read very few books to this ideal. Most are not worth it.
If you’ve read a book thoroughly and want to say “I don’t understand”, then you are saying the book has a fault. Your job is to locate...
Reading a book is a conversation between you and the author. If you do not internalize this, you are not performing deeper reading. You...
If your program is too large to fit completely in your target system’s memory, you can sometimes use “overlays” to work around this...
In some applications, it is not feasible for the debugger to interrupt the program’s execution long enough for the developer to learn...
We need to find out what the author’s propositions are. He may tell us outright. But keep in mind that his propositions are nothing but...
Find out all the important words/phrases in the book and examine how the author is using them. Figure out what they mean with relation...
Rule 1: You must know what kind of book you’re reading. Find this out early in the process. You should be able to state what the book...
gdb has stuff for handling macros, but you likely need to compile your program in a way to add these to the debug symbols. See this...
Normally you would use p to examine data. You can also use a Python pretty printer. print EXPR You can use the x command to see a more...
Printing Source Lines Note: You can use GDB with Emacs, and viewing the source via Emacs is convenient. list prints 10 lines. To change...
Stack Frames GDB labels each existing stack frame with a “level”, a number that is zero for the innermost frame, one for the frame that...
On some platforms, GDB provides a special “process record and replay” target that can record a log of the process execution, and replay...
Sometimes you realize that you went past the interesting point in your program. Occasionally you can rewind if the target environment...
While reading, you should have 4 questions you need to answer: What is the book about? What is said in detail, and how? Is the book...
Is the book even worth reading? Skim the book to find out. This post says how. First, do the following: Look at the title page,...
To break conditionally, do: break ... if COND … could be a function, location, address, etc. You can set a breakpoint such that it...
You can modify the environment so that your program runs as if in that environment (and not the environment gdb was launched under). See...
How do you repeat the last command? Just type Enter. It doesn’t work on all commands. If you want to repeat an earlier sequence of...
To attach to a running process, do: gdb PROGRAM
To start gdb on a certain program, type gdb progname. If, for whatever reason, you want to change the width of the text (to fit in your...
Hugues’s paper. Look it up.
This method is useful when your intermediate precision is the same as the target precision.
Given the input \(x\), the first step is to find a \(y\) such that \(f(x)\) can easily and accurately be calculated from \(f(y)\)....
In general, when approximating a function, we’ll split the domain into multiple intervals and approximate each one with a polynomial....
Here are some concerns: Say you want to compute \(a+b+c+d\) and they are all of 32 bit precision, but the machine supports 64 bit....
A function call can be either $(FUNCTION ARGUMENTS) or ${FUNCTION ARGUMENTS} If one of your arguments needs to have a comma or a brace,...
Example of a conditional: ifeq ($(CC),gcc) $(CC) -o foo $(objects) $(libs_for_gcc) else $(CC) -o foo $(objects) $(normal_libs) endif...
To refer to a variable, do either $(name) or ${name}. Now if you omit the parenthesis or the brace, like $abc, then this is interpreted...
The recipe of a rule consists of one or more shell command lines to be executed, one at a time, in the order they appear. Typically, the...
Sequential Evaluation of Polynomials If you don’t have any parallelism available, Horner’s scheme is a good option. And if you have the...
If you run make without a target, it picks the first target of the first rule. But a target beginning with a period cannot be the...
The book provides an algorithm. I didn’t bother writing the details.
When the condition number is not high, one can do the naive algorithm for the dot product. Otherwise, one should do the...
You can include other makefiles into the current one: include FILENAMES You can include variables and globs as filenames: include foo...
Rules The format of a rule is: TARGET ... : PREREQUISITES ... RECIPE ... ... The prerequisites are files that are required to run the...
Changing your environment (e.g. vacation trip) often gives you fresh ideas. Try to meet different types of people in your daily life...
He encourages plugging into many feeds (Facebook, Twitter, etc). But the feeds should have a lot of diversity. Microcelebrities are...
Home cooked dinners are powerful. And details like whether you have a table to put plates on, or disposable plates instead of fancy...
80% of building and maintaining relationships is staying in touch (“pinging”). New people need to see or hear your name in at least 3...
Two ways to gain power: Sheer will and effort By being indispensable to those around you (i.e. make others successful) When in a...
The three most common motivations for doing anything: Making money, finding love, or changing the world. So to connect with others, be a...
Reordering the Operands, and a Bit More General ideas: Sort all your summands in ascending order (magnitude). Even more complex, sort...
The problem with the previous error bounds is that they are in terms of quantities like \(\sum|a_{i}|\), which are not known in advance,...
Theorem for FMA Let \(x,y,z\) be nonnegative floating point numbers. Assuming underflow does not occur, then \(xy+z\le...
Let the rounding mode be RN. Assume no overflow occurs. Then if you do recursive summation, the following inequality related to the...
Unless specified otherwise, everything in this chapter assumes no underflow. We often will have many factors of \((1+\epsilon_{i})\),...
An Iterative Method Compute the minimax approximation in a wider format. Then round the coefficient of the constant term. Then recompute...
We discussed calculating the minimax polynomial using Remez’s Algorithm, but we overlooked some subtleties. While the algorithm does...
The error of an FMA calculation is not always a floating point number. However, we can use two floating point numbers to exactly...
Suppose you need to multiply by a constant that is not exactly representable. Think \(\pi\) and the like. We’d like to multiply and...
This is a short section with some details and magic numbers. I did not bother.
The algorithms are in the book. I did not reproduce them here. I did not read the rest of the section. There are a lot more details there.
This section deals with changing bases. The most obvious application is to go back and forth between decimal and binary (to make it easy...
The Basic Methods One way is to use Newton’s iteration on \(f(x)=x^{2}-a\). This method for calculating square root goes back thousands...
This section deals with floating point \(a,b\) values, not necessarily between 1 and 2. Assume they are non-negative, though. For this,...
We need to calculate \(o(a/b)\) where \(a,b\) are binary floating point numbers, and \(o\) is RN, RD, RU or RZ. We have a useful proof:...
Assume \(\beta=2\) for this section. Some of it may not work for decimal. We want to approximate \(b/a\). Assume \(1\le a,b<2\). In...
In this section, assume \(\beta=2\). Now given a floating point \(x\), we want to form two floating point numbers \(x_{h}\) and...
For this article, define a representable pair for a floating point number \(x\) to be any pair \((M,e)\) such that...
The 2MultFMA Algorithm This has been covered elsewhere. It works well when you use FMA. If No FMA Is Available If there is no FMA...
Let \(a,b\) be two floating point numbers. Let \(s\) be \(\RN(a+b)\). Regardless of which number it picks in a tie, it can be shown that...
When you multiply a floating point number by a power of \(\beta\), the result is exact provided there is no over or underflow. Another...
Sterbenz’s Lemma: If your floating point system has denormals, and if \(x,y\) are non-negative, finite floating point numbers such that...
To get \(p\) of the floating point system you are on: i = 0 A = 1.0 B = 2 # The radix. while (A + 1.0) - A == 1.0: A = B * A i += 1...
Suppose we want to compute the radix of a floating point system. The code below will do it for you - it works assuming the...
We never discussed how to calculate \(||f-p||_{\infty}\). Maple has a function to do this, but it can be inaccurate. Most people will...
Sometimes you need a fairly high degree polynomial to get reasonable accuracy, but can achieve a far greater accuracy with a much lower...
Remez’s algorithm is one that converges to the minimax polynomial of a function. The author recommends using a polynomial approximation...
Chebyshev vs Minimax Note that the best minimax polynomial approximation need not be the Chebyshev polynomial. The latter is the best...
The supremum norm is given by \(||f-p||_{\infty}=\max_{a\le x\le b}|f(x)-p(x)|\). It is denoted by \(L^{\infty}\). Given a function...
First, just a definition: A monic polynomial is one whose leading coefficient is 1. We want to find a polynomial of degree \(n\) that...
Do not assume that the operations in a programming language will map to the ones in the standard. The standard was originally written...
We often will approximate functions as polynomial or rational functions. When doing this, we introduce two types of errors:...
I skipped the rest of the chapter (inlcuding hardware details).
NaN Signaling NaNs do not appear as the result of arithmetic operations. When they appear as an operand, they signal an...
Invalid The default result of such an operation is a quiet NaN. The operations that lead to Invalid are: Most operations on a...
This section addresses how one can convert a character sequence into a decimal/binary floating point number. Decimal Character Sequence...
The standard requires that you can compare any two floating point numbers, as long as they share the same radix. The unordered condition...
Study on people with major depression. Three groups: Exercise 30 minutes a day 3 times a week Take Zoloft Exercise and take Zoloft...
Mind wandering is when our mind is thinking about something other than what we should focus on. Ruminating, jumping around, etc. Studies...
Kindness Finding ways to be more kind improves your happiness. In one study, people were asked to do 5 acts of kindness. They could do...
If you enjoy an activity, you have an intrinsic motivation to do it. Once people give you extrinsic motivations to do it, and then take...
Rounding Direction Attributes IEEE 754-2008 requires that the following be correctly rounded: Arithmetic operations: Addition...
Arithmetic Operations and Square Root Handling Signed 0 If \(x,y\) are nonzero, and \(x+y=0\) or \(x-y=0\) exactly, then it is \(+0\)...
Signature Strengths Martin Seligman made a list of 24 attributes that tend to be correlated with happiness, and that aren’t culture...
The standard defines several interchange formats to allow for transferring floating point data between machines. They could be as bit...
Concretely Reexperience Your Reference Points Say you got your dream job, and then a year later it has now become your reference point,...
The target format is the format of the result. The target precision is the precision of the target format. When computing polynomials,...
Let \(a,b\) be 2 floating point numbers. It can be shown that \((a+b)-\RN(a+b)\) is a floating point number. This may not be true for...
Savoring Activities that enhance savoring: Talking to others about how good you feel Looking for others to share it with Thinking about...
Basic Notions For a binary floating point system, if \(x\) is normal, then the leading bit is 1. Otherwise it is 0. If we have some...
Because of hedonic adaptation, don’t invest too much in stuff - especially long lasting stuff. Things that stick around and don’t change...
It has been shown that \(\beta=2\) gives better worst case and average accuracy than all other bases. if...
Floating point addition and multiplication are still commutative. Associativity is compromised, though. An example: Let...
In IEEE-754, the implementer can signal an exception along with the result of the operation. Usually (or perhaps mandated?), the signal...
Let \(o\) be the rounding function, and \(a,b,c\) are floating point numbers. Then \(\mathrm{FMA}(a,b,c)\) is \(o(ab+c)\). if...
Converting From ULP Errors to Relative Errors Let \(x\) be in the normal range, and \(|x-X|=\alpha\ulp(x)\). Then: \begin{equation*}...
There are multiple definitions of unit in the last place. I think most agree when \(x\) is not near a boundary point. Here is the...
Ranges The normal range is the set of real numbers: \(\beta^{e_{\textit{min}}}\le|x|\le\Omega\) and the subnormal range are where...
Most people’s happiness is not due to the absolute outcomes, but the relative outcomes. Medvec (1995) showed that the happiness of...
The IEEE 754-2008 specifies five rounding functions: Round toward \(-\infty\) (RD): It is the largest floating point number less than or...
Small talk is the “talk” between two people who do not know each other. The ability to make conversation in any circumstance is a huge...
0 (some systems have signed 0’s as well) NaN for any invalid operation \(\infty\) (some systems are signed, some are not). In the IEEE...
Underflow before rounding occurs when the absolute value of the exact value is strictly less than \(\beta^{e_{\textit{min}}}\) (i.e. the...
We would like a unique way to represent \(x\). One approach is to pick the one which gives the smallest exponent possible (while still...
A radix \(\beta\) floating point number \(x\) is of the form \(m\beta{e}\), where \(|m|<\beta\) is called the significand and \(e\) is...
Assume there is a 30 foot plank on the ground, and your task is to walk across it. Not a big problem. Now assume it is 100 ft off the...
Example: Say you’re making a product to sell to lawyers. If you know a lawyer, ask if he and some friends of his would like an early...
Lyubomirsky did some research on the role of genetics and life circumstances on happiness. She found that genetics affects about 50% of...
Material “Stuff” In 1976, they asked 12000 freshmen what material items would make them happy, and then followed up with them 20 years...
Gilbert showed that college students, when rejected for a job, did not become particularly unhappy. For a fair decision, they were very...
Savoring is the act of stepping out of an experience to review it and really appreciate it while it’s happening. Think about why a...
Superconnectors are people with a lot of connections. You’ll probably have a few of them in your network. Don’t assume that the person...
Knowing How You Spend Your Time Start with knowing where your time goes. For the next 3 days, allow yourself to behave as you normally...
The GI Joe Fallacy: People who know what makes us happier (e.g. psychologists) are not necessarily happier or better able to practice...
One view of procrastination is that it is a form of preserving self-worth. There are 3 deep inner fears that cause us to procrastinate...
First, decide if the ROI from relationships created there exceed the costs. If not, don’t go! Help the Organizer. Or Better, Be...
After a meeting, do a prompt followup. Put some emotions into it (Why was it nice to meet him?) Do it within 12-24 hours. Expressions of...
Networking events are not that good. Use shared interests: Race Religion Gender Business Personal Hobbies Focus on the quality of the...
Invisibility is far worse than failure. Keep your social calendar full. Always remain visible and active among your network. Example of...
It is hard to get hold of important people. They often have gatekeepers (e.g. secretaries). Never get on their bad side. And elevate...
You’ll never get over the fear and anxiety of a cold call. Just dive in! And have the mindset/attitude that you can get what you want...
For your goals, list the people who can help achieve them. Do not list organizations! Make sure it is an actual person. Use LinkedIn...
Whom you meet, how you meet them, and what they think of you afterwards, should not be left to chance. For anyone you meet, ask: Who...
When the pressure is on, we fall to our highest level of preparation. It is key to prepare! Don’t prepare to the extent that you have a...
Black swans are unknown unknowns. Finding Leverage in the Predictably Unpredictable A black swan is an event we never imagined. So we...
If you make an offer, then any response other than an outright rejection means there is room for negotiation. What Type Are You Three...
The work is not done when you have an agreement. The implementation details are critical. “Yes” Is Nothing Without “How” Practice...
Successful negotiation is getting your counterpart to do the work for you and suggesting the solution himself. Remove the hostility in...
An important lesson: There is always leverage. Some examples: Fear of deadlines Power of odd numbers Views on fairness Don’t Compromise...
“I guess so” means things are not going well. “That’s right” means things are going well. Get to “That’s right”! They may not say the...
Other negotiation books try to get the other side to say “Yes” to anything. Or get them to say “Yes” to an abstract principle...
Good negotiators label emotions. Tactical empathy: Understand the needs and feelings behind the other’s mindset. It is not about...
Your mindset should be that of discovery, and extracting as much information as possible. Which is why smart people can be poor at...
All pages tagged as nstd are notes from the book Never Split The Difference. An overriding principle: People want to feel they are good...
\(\newcommand{\Cov}{\mathrm{Cov}}\) The notes in this class are for Coursera’s Introduction to Financial Markets taught by Shiller. Let...
How do we put all this into practice? It is daunting. At the first level, focus on two principles: Learning to look and making safety....
This chapter has several common scenarios and advice on each one. Worth a read.
Once everyone has added meaning to the pool (after reaching safety, etc), there is still a need for action. What should we do with this...
Sometimes the problem is that the other person is resorting to silence/violence. What then? One option is to simply make it the other’s...
Share Risky Meaning When it comes to touchy information, the worst is to alternate between blunt and silence (Fool’s Choice). The less...
Claim One: Others don’t make you mad. You make you mad. Claim Two: Once you’re upset, there are only two routes: Act on them or be acted...
If someone says something sarcastic or a side remark, that means they need safety. Do not ask “What is that supposed to mean?” It can...
Most crucial conversations are about two things: Content and emotions. When we get deeply involved in one, we usually focus on only one...
The problem is not that our behavior degenerates. It is that our motives do. In crucial conversations, our motive often changes to...
The Fool’s Choice The Fool’s Choice: When you feel you have only two choices: Silently accept the problem Speak about the problem but...
The Intention Behind The Appreciation Positive judgments are still problematic judgments. Example: “It was kind of you to…” “You are a...
Resolving Internal Conflicts Depression is indicative of a state of alienation from our own needs. Internal thoughts like “should”,...
When The Use of Force is Unavoidable Dialog is great but sometimes the opportunity for dialog may not exist, and force is necessary. The...
Human Connection Creating a connection between the people who are in conflict is the most important thing. The parties need to know from...
Hurting people is one of the weakest ways to express our anger. The goal of nonviolence is not to stifle anger, but to express it in...
Evaluating Ourselves When We’ve Been Less Than Perfect We chastise ourselves in non-constructive ways when we screw up. Shame and guilt...
Empathy That Heals Listening empathically to someone (no advice, etc) can really relieve the other person’s tension. Ending the...
Motivation Suppose you have a population with known \(\mu\) and \(\sigma\). You then take a sample (perhaps not randomly) and discover...
For a Poission distribution with large \(n\), use \(Z=\frac{\bar{X}-\lambda}{\sqrt{\lambda/n}}\) (i.e. \(\lambda\) instead of \(S\)). It...
Things you should think about: What are the implications of your choice of \(\alpha\)? How much did intuition play a role in deciding...
The p-value is the smallest significance level (i.e. \(\alpha\)) at which \(H_{0}\) would be rejected. So if \(p\le\alpha'\), you reject...
Let \(X\) be the number of successes. If \(n<
Steps to Carry Out The Experiment Identify the parameter of interest. Determine the null value and state the null hypothesis. State the...
The null hypothesis (\(H_{0}\)) vs the alternative hypothesis (\(H_{a}\)): The null hypothesis is assumed to be true (default). The...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) If \(\Sample\) be...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) Let \(\Sample\) be...
The one-sample t-distribution confidence interval is robust for small or even moderate departures from normality, unless \(n\) is very...
What if you have \(n\) observations in a normal distribution and want to predict \(X_{n+1}\)? The prediction interval is \(\bar{x}\pm...
Say you take a sample where \(n\) is not large. Then the CLT doesn’t apply. We must then know/assume a distribution. Suppose we know it...
Let \(\Sample\) be independent and identically distributed from \(N(\mu,\sigma^{2})\). Define the following random variable:...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) For any...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) Assume you have a...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) A good estimate...
Some people just want to win, and their measure of success is how much you lose. If your goal becomes victory, realize you’re stuck in a...
Obstacles to Agreement The other side may stall: Lack of interest, vague statements, delays, breaking agreements, a flat No! There are...
When the other side doesn’t budge, resist the temptation to counter with your position. “That’s interesting. Why do you want that?” “You...
Do not ignore the emotions while focusing on the problems. You need to defuse them, and you do it by surprise. If they stonewall, they...
Three Natural Reactions We have 3 natural reactions: Striking back Giving in and yielding to pressure Cutting off the relationship Don’t...
Before every meeting, prepare. After every meeting, assess and re-prepare for the next meeting. Do not try to wing it. Mapping Out The...
Five Barriers To Cooperation Your Reaction: You either strike back or give in. Both are damaging. Their Emotion: Anger, hostility, fear,...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) The Method...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) Notation: \(\hat{\mu}=\bar{X}\) means the point estimator of...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) Let \(X_{1}\dots X_{n}\) have means \(\mu_{i}\) and variances...
Let \(X_{1}\dots X_{n}\) be a random sample from a distribution with mean \(\mu\) and standard deviation \(\sigma\). Then:...
When we take a sample and calculate its mean and standard deviation, this is treated as a random variable for the population...
\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) Expected Value The expected value of a function \(h(X,Y)\) is...
Probability Given two random variables \(X,Y\), the joint pdf is given by \(p(x,y)=P(X=x,Y=y)\). Let \(A\) be an event. Then the joint...
Sample Percentiles Calculating sample percentiles is challenging. What is the 23rd percentile of 10 points? One rule: Order the \(n\)...
For Weibull, let \(Y=\ln(X)\). This has both scale and location parameters. Location is \(\theta_{1}=\ln(\beta)\) and scale is...
The beta distribution The parameters are \(\alpha,\beta>0\), and \(A,B\) with \(B\ge A\). \begin{equation*}...
If \(Y=\ln X\) is a normal distribution, then \(X\) is log-normal. \begin{equation*} f(x;\mu,\sigma)=\frac{1}{\sqrt{2\pi\sigma}...
Probability Density Function Let \(\alpha,\beta>0\) \begin{equation*}...
If the time between successive events is independent each with an exponential distribution with \(\lambda\), then the total time \(X\)...
Chi-squared distribution Probability Density Function The parameter is \(\nu\) and it is a positive integer. It is the gamma...
Exponential distribution Probability Density Function Let \(\lambda>0\) \begin{equation*} f(x;\lambda)=\lambda e^{-\lambda x}...
The problem with the normal distribution is that it is symmetric. The Gamma distribution is useful for skewed distributions....
Probability Distribution Function The parameters are \(-\infty<\mu<\infty\) and \(\sigma>0\). \begin{equation*}...
The Pareto distribution is good for approximating income distributions or population sizes. The pdf is given by: \begin{equation*}...
Continuous distributions are given by a probability density function (pdf): \begin{equation*} P\left(a\le X\le...
Suppose you have a library with \(M\) items and you want to sort them by popularity. The parameters are \(M\) and \(\alpha\). The domain...
People are motivated more by the thought of losing something than the thought of gaining something of the same value. Frame something in...
Don’t Just Do Something. Stand There! Empathy is emptying our mind and listening with our whole being. The presence that empathy...
. Use positive language when making requests! Example of negative language: Asking someone not to do something. Instead, request what...
Hearing a Negative Message: Four Options What others say or do may be the stimulus of our feelings, but not the cause. When someone...
“I feel that…” When you use “that” after feel, you are likely not revealing your feelings. Adequately expressing feelings is...
Separate the observation from the evaluation. If you say both in one go, people are more likely to interpret it as criticism and resist....
Moralistic Judgments Moralistic judgments are “life-alienating” communications. The focus tends to be on analyzing wrongness then...
The NVC Components: Observations: State the facts Feelings: State your feelings Needs: State your needs connected to your feelings Make...
Titles Study: A person is introduced to various groups as either a student, lecturer, professor, etc. After he leaves the room, people...
\(X\) is of a Poisson distribution if its pmf is \(p(x;\lambda)=\frac{e^{-\lambda}\lambda^{x}}{x!}\) where \(x\) is 0, 1, 2, etc....
The experiment requires: The trials be independent The outcome is binary (success or failure). The probability of success or failure is...
The hypergeometric experiment requires: The population is finite, with \(N\) individuals. The outcome of each trial is binary (success...
Bernoulli Distribution A Bernoulli random variable is one whose only possible values are 0 and 1. \(P(X=1)=p\) \(E[X]=p,V[X]=p(1-p)\)...
Random Variables A discrete random variable is one whose set of possible values is countable. Probability Distributions for Discrete...
Read hypothesis testing in Chapter 2 (ML rules). Reliability in Chapter 2
Sample Spaces and Events The sample space \(\mathcal{S}\) is a set. An event is a subset of the sample space. A simple event is an event...
A common tactic: A salesperson who has completed a sale with you will ask for a list of friends, and call them up and talk about how...
Measures of Location When reporting a sample mean, use one extra significant digit. Sample mean: \(\bar{x}\) Population mean: \(\mu\)...
Pictorial and Tabular Methods in Descriptive Statistics Stem and Leaf Display Stem and leaf display Advantages: Useful for displaying...
Populations, Samples and Processes A census means you poll every member of the population. Univariate vs bivariate or multivariate:...
What If The Other Person is a Bully, Lying, or Trying to Derail While it does happen, most of our evaluations about the other person are...
Step One: Prepare By Walking Through The Three Conversations Stories What’s my story? (information, past experiences, rules?) What’s his...
Most people don’t have the conversation skills. You’ll talk about understanding and they’ll talk about who’s right. You’ll talk about...
Don’t just listen - you need to share your side of the story. Orators Need Not Apply Do not try to be eloquent or witty. Do not try to...
People have a deep desire: To be heard To know that others care enough to listen Listening Transforms The Conversation Mother has...
A bad beginning can crater the conversation. But a good one helps you immensely. Why Our Typical Openings Don’t Help Don’t dive in with...
Pick your battles! You can’t have every difficult conversation you come across. Deciding whether to raise an issue or not torments us....
Difficult Conversations Threaten Our Identity Sometimes the anxiety is not due to facing others, but facing ourselves. The conversation...
Don’t focus on just the objective facts. Feelings have to be part of the conversation. At the same time, having them explode is...
Someone screws up, which causes you to screw up. You can blame him/her explicitly (“You screwed up!”) or implicitly (“Let’s do better...
Social proof is also a convenient shortcut for decision making. Kids who are scared to play with dogs become willing to merely by...
We have a deep desire to be/appear consistent. This is why when people bet on a horse, they are more confident it will win after they’ve...
We try to repay, in kind, what someone else has given us - even we didn’t want it or take it! We feel obligated. Society provides a very...
A group of people are waiting in line to use a photocopying machine. Someone says “May I use the machine because I am in a rush?” to...
Intentions strongly influence our judgments. Watch your sentences and notice how often you are attributing intentions to the...
At the heart of the What Happened conversation is a disagreement. Argument is the natural outcome of disagreement. But it is...
You need to understand what people are thinking and feeling, but not saying. Every difficult conversation is really a mix of...
What makes a conversation difficult? Usually it is the fear of consequences. If we avoid the conversation, we feel taken advantage of,...
You can start a support group yourself. Rule: The group has no “leaders”. All the members own it. Meeting Format (Suggestion) Run a...
The principles in the book can be applied informally, but success is much higher if you formalize it. (My idea): To an extent, perhaps...
Making a commitment is like making a resolution. If you don’t stick to it, it’s useless. Don’t fear the mistakes you’ll make along...
Benefits of making a commitment: Liberating to admit your problems By committing publicly, you are more likely to follow through. Public...
Common problems: The struggler: Craves attention. Seeks turmoil and impossible situations. The conflict avoider: Downplays...
Learn to spar with your team: Sparring is where they can grill you - hold you accountable, but not in a way that causes injury. It is...
Take a week off in December to reassess everything. Use the Personal Success Wheel or make your own. The elements in the wheel are not...
Goal setting should be done be a team! Don’t insist on setting all your goals yourself. Let the team help you. His opinion: Goals may be...
Once identified, the lifeline needs to be eased into the process. The benefit of a long, slow dinner is that the clock stops. No rush to...
Sources of Lifelines Your confidant need not be someone close to you - sometimes those close to you are very poor at it. We have close...
His view: People spend too much time meticulously recycling vs living up to their talents and abilities. You get only one life. What...
Advice from his mentor: “What do you really want? Define your greatness. Then be convinced of it and start acting like it. Someone will...
Accountability is the 4th mindset. We all make efforts to change (e.g. corporate workshops, trainings, etc), but most efforts don’t have...
Realize that opening yourself to get feedback from others is risk free! They will have their perceptions of you regardless of your...
When introducing yourself, don’t just list accomplishments. Tell a story about your dreams, how you’re getting there, and what...
What do I have to offer others? There are two types of generosity currency: Universal and personal. Universal currency is very...
Everyone needs confidants for their professional work. People who care about your success and will not let you fail. Most people have...
Haidt claims that genes account for whether you are left/right a lot more than upbringing does. A single gene doesn’t predict much. But...
For Western/modern society, the author favors rule utilitarianism (best rules that will produce the greatest good) as opposed to act...
Is God a Force of Good or Evil? Religious people generally give more in charity, but usually to their own kind or through their own...
You cannot understand religion by looking at the individual. You must look at the collective. The Lone Believer Critics of religion...
The hive switch: The ability to temporarily transcend self-interest and lose ourselves in something bigger. It is essentially a...
Group Selection: If a trait benefits the group against other groups, but not the individual against other individuals in the same group,...
Reciprocal altruism theory explains why altruism/fairness behavior develops among pairs (tit for tat) but does not explain it...
Republicans appeal to all 5 moral tastes than Democrats, who appeal to only 1 or 2. This is why the former tend to have an edge...
Notable was Haidt’s criticism of amateur evolutionary theorists: They pick a trait and see if they can find a story that explains it. A...
Moral monism is the reduction of morality to a single principle (e.g. don’t do harm). Haidt argues this is unhealthy for society. Is...
Psychologists have a tendency to study the mind independent of culture. Anthropologists tend to study the culture and not the mind....
Most research in psychology is conducted on WEIRD people. WEIRD stands for Western, Educated, Industrialized, Rich and Democratic. But...
So do good reasoning skills lead to more moral behavior (the atheist’s dream)? A study found that moral philosophers behave just like...
Self-Esteem Is self-esteem about how we perceive ourselves, or about how we perceive other’s perceptions about ourselves? Levy Study:...
There has existed for a long time a dilemma: Is it better to be just and honest in a world that will never recognize you as such, vs...
Primarily by engaging with others. On can change via introspection, but others are more likely to give us non-confirmatory evidence....
Utilitarianism (save the most lives) vs Deontologism (cannot impinge on individual rights - even to save many lives). Both claim their...
Infants do not appear to be born with a blank slate. They have certain expectations on the physical laws, as well as the social laws. By...
1% of males are psychopaths. Fewer females are. Most are nonviolent. But virtually half of crimes like serial rape and killing,...
The sense of smell impacts moral judgments. Asking participants to fill out a survey on moral scenarios in the presence of fart smell...
Affective Priming: Flash words like sunshine or cancer to the screen. You need to judge whether the word is positive or negative. If you...
Our brains evaluate everything instantly in terms of potential threat or benefit, and adjusts behavior to get more of the good and less...
Hypnotized one set of students and made them dislike the word “take”. Hypnotized another set and made them dislike “often”. Gave them 6...
The rationalist delusion: The worship of reason and the distrust of passions. It is a delusion because once you declare it to be an...
Should I Negotiate? Consider the time spent in preparing and executing the negotiation, and the expected gain. Is the time spent worth...
To tackle Turiel’s concern that the “harmless” stories could be interpreted as harmful, Haidt decided to do a similar story, but added a...
Most societies have a need to “resolve” the tension between individuals and the society. Most societies are sociocentric: The group has...
Anthropologists had studied and documented that many unrelated cultures had: Witchcraft and sorcery themes - with a great deal of...
To gauge a child’s developmental level, it is important that the method of gauging doesn’t rely on the child’s verbal abilities - this...
How do children learn right from wrong? There used to be 2 theories: Nature: Nativist (be it through God or evolution) Nurture:...
Introduction Intuitions come first, strategic reasoning comes second. Moral intuitions arise automatically - long before moral reason....
val x = ref 42 val y = ref 42 (* Although the number is the same, x and y do NOT point to the same thing! *) val z = x (* z is now a...
Functions can take other functions as arguments. Consider: fun compose (f, n, x) = if n = 0 then x else f(compose(f, n-1, x)) This calls...
A tail call is when the callee’s result is merely returned without being used (i.e. it is not multiplied or added to anything, etc). In...
exception MyException exception AnException of int*int raise MyException e1 handle ex => e2 e1 handle ex(x,y) => e2 (* More generally *)...
We can nest patterns as deep as we like. Anywhere we put a variable in our pattern, we can put another pattern. exception BadTriple fun...
The type ''a represents an equality type: It means anything that can be compared with the equality operator. Not everything can be...
If you use patterns to access records or function arguments, you usually do not need to specify their types. They will be inferred from...
The pattern {f1=x1, ..., fn=xn} will match against a record (assuming all the types match) {f1=v1,...,fn=vn}. Note that since all tuples...
Example (newtype is defined in a previous post). fun f (x : newtype) = case x of Pizza => 3 | Str s => 8 | TwoInts(i1, i2) => i1 + i2 To...
Example: datatype newtype = TwoInts of int*int | Str of string | Pizza newtype is a new type that is added to the environment. TwoInts,...
type aname = t aname becomes an alias for type t. Useful for giving meaningful names: type date = int*int*int Think of it like typedef in C++.
Example: val x = {k1=3, k2=false} Ordering of keys does not matter. You can nest records. The type is: {k1:int, k2:bool}. You use #k1 to...
Most of Standard ML has immutability. Behind the scenes, references may be in use for optimization purposes, but the language guarantees...
Consider this motivating example: I want to write a function that takes a list of integers, and returns its sum. What should it return...
Syntax let b1 b2 ... bn in e end The keywords are let, in, end. bi are bindings. e is an expression. Note that often bi are each on...
Tuples Syntax (e1, e2, ..., en) Note that the length of a tuple is known in advance. Type Checking ei will have type ti (the types need...
Defining Functions Look at the following example to declare a function: fun pow(x:int, y:int) = if y = 0 then 1 else x * pow(x, y-1) If...
Comments Comments begin with (* and end with *). You can nest comments. Statement Ends In the REPL, each statement must end in a...
Much of the material with the tag gty comes from Getting To Yes. Does Positional Bargaining Ever Make Sense Principled negotiation is...
Much of the material with the tag gty comes from Getting To Yes. Examples: Deception Throwing Off Balance Nibbling (asking for stuff...
Much of the material with the tag gty comes from Getting To Yes. They may stick to their position. They may attack you instead of...
Much of the material with the tag gty comes from Getting To Yes. If you are trying to make a deal that is very important to you, it is...
Much of the material with the tag gty comes from Getting To Yes. Deciding On The Basis of Will is Costly Examples of negotiating on the...
Much of the material with the tag gty comes from Getting To Yes. Diagnosis There are typically 4 reasons that prevent the invention...
Much of the material with the tag gty comes from Getting To Yes. The basic problem in a negotiation is not in conflicting positions, but...
Much of the material with the tag gty comes from Getting To Yes. Do not ignore the human factor, with all its emotions. Do not just...
Much of the material with the tag gty comes from Getting To Yes. A wise agreement is one that: Meets the legitimate interests of each...
Much of the material with the tag gty comes from Getting To Yes. Negotiation is easier if both sides know how to perform it.
Much of the material with the tag gty comes from Getting To Yes.
Is there something wrong in the third act? Then it is wrong in the first act. Are you writing because you have something to say, or...
People’s critiques will be very subjective and very related to themselves. They may hate a character because it reminds them of someone...
In Jurassic Park, a character diverts a dinosaur’s attention by throwing a flare away from him. The dinosaur chases the flare while they...
Superior position is when the audience knows something the characters do not. It is a useful tool for suspense, but can serve other...
With dialogue, it is important to set up the subtext. If you have established that two people hate each other, and then you have them in...
Do not use subplots to make the world more complex. Use them only to support the main plot. You are a slave to the story. You do not...
Deus Ex Machina is horrible. Do not use it to solve problems. However, feel free to use it to create problems. No one minds it, and it...
The climax should bring masculine and feminine elements together. It shows how a character changed (or didn’t).
Genre is visible (e.g. western, horror, etc). Do not think in terms of genre. Focus on the story, and then choose an appropriate genre....
A storyteller teaches, not preaches. If you talk about what you want to say, you are preaching. If you show, you are teaching. The...
Consider this quote: “The King died and then the Queen died” is a story. “The King died and then the Queen died of grief” is a plot. -...
Truth is not about the facts. In a horror movie, a girl going down a scary basement is not the truth. Real scared women will not do...
Ritual Pain Think of rites of passage. In many cultures, one has to undergo severe pain to become a man (not for women). Gang...
A clone in a story is a tool for showing, not telling. They are characters that represent what could, should, or might happen to the...
People tell stories to teach something. It is likely the origin of stories - a way to teach something beyond simply using boring facts....
Less is more. Don’t go for a complex plot. Simplicity rules. There are seven steps in all narratives: Once upon a time And every day...
The Pie The first principle in negotiation: Figure out what the pie you are fighting over is. It may not be obvious, and the parties may...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Lies about the bottom line and alternatives: Never...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. The more ethical you are, the higher the cost...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Scarcity Effect: People will value (or overvalue) a...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. If your opponent is competitive, you may need to...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. 3 aspects to it: Rapport development Discovering...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. There are 4 steps to negotiations: Preparation...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Leverage gives you power to reach an agreement on...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. It is imperative to ask yourself how achieving your...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Reciprocity is the key to sustaining trust...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. There exist several norms and standards. Examples:...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Research shows: The more specific your vision of...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. There are typically 4 steps in negotiation:...
Much of the materials with the tag bfa comes from the Bargaining for Advantage book. When negotiating, it is vital to be yourself: If...
The method: Given a string of, say, length 8, form all 8 rotations of it, and then sort them lexicographically. Then form the 8 letter...
The idea: First assign a number to all the letters of the alphabet. Say A is 41, B is 42, etc. Now let’s say we’re compressing the...
The problem with run length encoding was that our chunk size (e.g. 4 bits) is fixed. This is nonoptimal. With Huffman encoding, we can...
We have a large string (e.g. text file). Usually, ASCII is not the optimal space allocation for the file. There are various schemes for...
We have a string of length \(N\), and wish to find an \(M\) character string in it. Brute Force Keep moving through the string till the...
An R-way trie is a tree where each node has \(R\) children. It’s best described by an example: Each node consists only of two...
A symbol table is an associative array. It’s a good idea to make the keys orderable for performance reasons (it also opens up more...
Bloom filters are an application of hashing. It is a data structure that allows us to check if an object has already been seen (without...
We often want to store an object for quick retrieval, or see if a given object has been observed before in \(O(1)\) time. Let \(U\) be...
A suffix array is an array formed by taking a string, and storing pointers to all the suffixes in the array. As an example, if the...
Least Significant Digit Suppose we have \(N\) strings of length \(W\). The idea behind the LSD sort is to first sort the last “digit”...
Counting Sort Suppose we have \(N\) elements, but we know the elements are drawn from a fixed, finite list (called the alphabet in this...
Mincut Problem An s-t cut is a cut with \(s\) in one set and \(t\) in the other. Call the sets \(A\) and \(B\). Given a digraph, with...
There are many “kinds” of shortest paths. Algorithm Constraint Typical Worst Case Topological Sort No directed cycles \(N+M\) \(N+M\)...
A negative cycle is a directed cycle where the sum of the edge weights is negative. A shortest paths tree exists if and only if there...
Given a digraph, we may wish to find the shortest distance between two nodes, or between a node and all other nodes, etc. Each edge has...
Given a connected graph \(G\), with positive edge weights, the spanning tree is a subgraph \(T\) that is both a tree (connected and...
Applications When looking at code/library dependencies, one may want to see which code pieces form strongly connected components, and...
Topological Sort A topological sort is a traversal of a digraph with ordering constraints. Let each node have some value/weight. It is a...
A cut of a graph is a partitioning of the nodes into two nonempty sets. A minimum cut is a cut that minimizes the number of edges...
In grade school we learn an algorithm for multiplying two \(N\) digit integers. Let our basic operation to be the multiplication or...
Given \(N\) rectangles, find all the intersections. This algorithm is very similar to the 1-D line intersection search. The difference...
Suppose we have \(N\) 1-D intervals of the form \((a,b)\) where \(a
This is like the 1-D range search, but where the keys can now have two coordinates. It’s finding the number of points in a rectangle...
Sample problems we want to solve: What are all the keys between two keys? (Relevant to databases) How many keys exist between two keys?...
We introduced 2-3 trees with highly desirable properties. Here we’ll convert them into binary trees while maintaining all the...
A decreasing sequence \(g_{k}(N)\) is called an asymptotic scale if \(g_{k+1}(N)=o(g_{k}(N))\). \(f(N)\sim...
Let’s use generating functions to count the average number of leaves in a binary tree with \(N\) internal nodes. Definitions Let \(P\)...
Let’s use generating functions to count the average number of 1’s in a binary string of length \(N\). Definitions Let \(P\) be the set...
Generating functions can be used for counting. Consider the problem of finding the number of trees with internal nodes. Let \(T\) be the...
A 2-node is like a regular node in a binary search tree: It has one key and two children. A 3-node has 2 keys and 3 children. The middle...
To form a generating function, we multiplied by \(z^{N}\) and summed. This is not the only way to form a generating function. Another...
Technique The basic technique is to multiply the equation with \(z^{N}\), sum over all \(N\), recast in terms of the generating function...
Definition An ordinary generating function of a sequence \(\left\{a_{k}\right\}\) is: \begin{equation*} A(z) = \sum_{k\ge 0}a_{k}z^{k}...
Problem How many bits are needed to represent a binary tree with \(n\) nodes? A lower bound is given by the fact that \(m\) bits can...
A binary search tree is a fairly useful structure for storing ordered data. The invariant for a binary search tree is straightforward:...
One way to sort a list is to use the heap data structure. Given an array of \(N\) unsorted elements, build a max heap in place. Start...
At times we want a structure similar to a queue or stack, but instead of LIFO or FIFO, we want it to pop the maximum element each time....
Sometimes we wish to find the k-th largest element in a list. Brute Force A brute force way to do this would be to sort the list and...
A quick sort works recursively: Shuffle the list. This protects against a carefully crafted input that will make the algorithm...
Say you have \(N\) points on a Euclidean plane. You want to find the polygon with the smallest area that can be formed connecting a...
Any comparison based sorting algorithm must use at least \(\lg(N!)\sim N\lg N\) comparisons for the worst case. This is absent any...
Suppose we have \(N\) points in a plane, and we wish to find the closest pair. The brute force algorithm takes \(\Theta(N^{2})\). We can...
Why would we want to count the number of inversions? One application may be to see how close two different people’s rankings of the same...
Useful Identities \begin{equation*} \sum_{k=m}^{n}\dbinom{k}{m}=\dbinom{n+1}{m+1} \end{equation*} The mnemonic for this is: Suppose you...
A merge sort works recursively: Split the list into two roughly equal halves. Sort each half using mergesort. Merge the two...
When using a random number generator for shuffling, be wary of simple issues. Using cards as an example: If the seed is 32 bits, you’ll...
A shell sort works somewhat recursively. It first sorts every \(k\) elements (i.e. the sublist formed by elements 0, \(k\), \(2k\),...
An insertion sort starts from the first element in the list, and then for each element will check with the previous one to see if it is...
An inversion in a list of elements is a pair of elements where the 2nd element is smaller than the first (i.e. the 2nd element would be...
A selection sort starts out by traversing the whole list, finding the minimal element, and swapping it with the first element. It then...
A loop invariant is a statement that holds true just before and after each iteration. It may be violated within the iteration, but the...
NetworkX is a Python library for handling graphs. In [1]: %matplotlib inline In [14]: import networkx as nx import pylab as plt In [3]:...
We wish to find the distance between two nodes \(a\) and \(b\). Let’s generalize this further and find the distance from \(a\) to all...
The depth first search algorithm is a way to traverse all the nodes in a graph. The algorithm is trivial: Start at a given node. Mark it...
A queue is a data structure for holding objects. It is a FIFO structure. It supports two operations: enqueue and dequeue dequeue returns...
An undirected graph is defined by \((V, E)\) where \(V\) is a set of nodes and \(E\) is a set of edges (each edge is an unordered set of...
A stack is a data structure for holding objects. It is a LIFO structure. It supports two operations: pop and push. pop returns (and...
2-Sum Problem Statement Given a set of \(N\) integers, find how many pairs sum to 0. Brute Force Sum all pairs and count whichever sum...
Consider an \(N\times N\) square grid, where all the grids are black. Now let each square in the grid be white with probability \(p\)....
Dynamic Connectivity & Disjoint Sets Given \(N\) nodes, some connected amongst themselves, does a path exist between any two...
An asymptotically positive function \(f(n)\) is one that is always positive for sufficiently large \(n\). A similar definition holds for...
Linearity of expectation: \(E(aX+bY+c)=aE(x)+bE(Y)+c\). This holds even when \(X\) and \(Y\) are dependent. Exploit this! Independent...
\begin{equation*} \sum_{k=2}^{n}\frac{1}{k}\le\ln n \end{equation*} To see this, look at the curve \(1/x\), and integrate it from 1 to...