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...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) Assumptions:...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) For a Poission...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) Things you should...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) The p-value is the...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) Let \(X\) be the...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) Steps to Carry Out...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) The null...

\(\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...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) The one-sample...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) What if you have...

\(\newcommand{\Cov}{\mathrm{Cov}}\) \(\newcommand{\Corr}{\mathrm{Corr}}\) \(\newcommand{\Sample}{X_{1},\dots,X_{n}}\) What if \(n\) is...

\(\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...

The Catalan numbers satisfy the recurrence relation: \begin{equation*} T_{n}=\delta_{n,0}+\sum_{k=0}^{n-1}T_{k}T_{N-k-1} \end{equation*}...

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\) internal nodes (I think leaf nodes are not internal)? These trees...

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...