# Study Notes

## Putting It All Into Practice

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

## Yeah, But …

This chapter has several common scenarios and advice on each one. Worth a read.

## Move To Action

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

## Explore Others’ Path

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

## State My Path

Share Risky Meaning When it comes to touchy information, the worst is to alternate between blunt and silence (Fool’s Choice). The less...

## Master My Stories

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

## Make It Safe

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

## Learn To Look

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

## Mastering Crucial Conversations

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

## Expressive Appreciation in Nonviolent Communication

The Intention Behind The Appreciation Positive judgments are still problematic judgments. Example: “It was kind of you to…” “You are a...

## Liberating Ourselves and Counseling Others

Resolving Internal Conflicts Depression is indicative of a state of alienation from our own needs. Internal thoughts like “should”,...

## The Protective Use of Force

When The Use of Force is Unavoidable Dialog is great but sometimes the opportunity for dialog may not exist, and force is necessary. The...

## Conflict Resolution and Mediation

Human Connection Creating a connection between the people who are in conflict is the most important thing. The parties need to know from...

## Expressing Anger Fully

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

## Connecting Compassionately With Ourselves

Evaluating Ourselves When We’ve Been Less Than Perfect We chastise ourselves in non-constructive ways when we screw up. Shame and guilt...

## The Power of Empathy

Empathy That Heals Listening empathically to someone (no advice, etc) can really relieve the other person’s tension. Ending the...

## $$z$$ Tests and Confidence Intervals for a Difference Between Two Population Means


## Poisson Distribution Tests


## Some Comments on Selecting a Test Procedure


## p-Values


## Tests Concerning a Population Proportion


## Tests About a Population Mean


## Hypotheses and Test Procedures


## A Confidence Interval For The Median


## Confidence Intervals For The Variance and Standard Deviation of a Normal Distribution


## Intervals for Non-Normal Distributions


## A Prediction Interval for a Single Future Value For a Normal Distribution


## Intervals Based on a Normal Population Distribution: The T-Distribution


## Large Sample Confidence Intervals for a Population Mean and Proportion


## Basic Properties of Confidence Intervals


## Estimating the Mean of a Symmetric Distribution


## Use Power To Educate

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

## Build Them a Golden Bridge

Obstacles to Agreement The other side may stall: Lack of interest, vague statements, delays, breaking agreements, a flat No! There are...

## Reframe

When the other side doesn’t budge, resist the temptation to counter with your position. “That’s interesting. Why do you want that?” “You...

## Step To Their Side

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

## Go To The Balcony

Three Natural Reactions We have 3 natural reactions: Striking back Giving in and yielding to pressure Cutting off the relationship Don’t...

## Prepare, Prepare, Prepare

Before every meeting, prepare. After every meeting, assess and re-prepare for the next meeting. Do not try to wing it. Mapping Out The...

## Getting Past No: Overview

Five Barriers To Cooperation Your Reaction: You either strike back or give in. Both are damaging. Their Emotion: Anger, hostility, fear,...

## Methods of Point Estimation


## Some General Concepts of Point Estimation


## The Distribution of a Linear Combination


## The Distribution of the Sample Mean and Sum

Let $$X_{1}\dots X_{n}$$ be a random sample from a distribution with mean $$\mu$$ and standard deviation $$\sigma$$. Then:...

## Statistics and Their Distributions

When we take a sample and calculate its mean and standard deviation, this is treated as a random variable for the population...

## Expected Values, Covariance and Correlation


## Jointly Distributed Random Variables

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

## Probability Plots

Sample Percentiles Calculating sample percentiles is challenging. What is the 23rd percentile of 10 points? One rule: Order the $$n$$...

## Extreme Value Distribution

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 beta distribution The parameters are $$\alpha,\beta>0$$, and $$A,B$$ with $$B\ge A$$. \begin{equation*}...

## The Lognormal Distribution

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

## The Weibull Distribution

Probability Density Function Let $$\alpha,\beta>0$$ \begin{equation*}...

## The Erlang Distribution

If the time between successive events is independent each with an exponential distribution with $$\lambda$$, then the total time $$X$$...

## The Chi-Squared Distribution

Chi-squared distribution Probability Density Function The parameter is $$\nu$$ and it is a positive integer. It is the gamma...

## The Exponential Distribution

Exponential distribution Probability Density Function Let $$\lambda>0$$ \begin{equation*} f(x;\lambda)=\lambda e^{-\lambda x}...

## The Gamma Distribution

The problem with the normal distribution is that it is symmetric. The Gamma distribution is useful for skewed distributions....

## The Normal Distribution

Probability Distribution Function The parameters are $$-\infty<\mu<\infty$$ and $$\sigma>0$$. \begin{equation*}...

## Pareto Distribution

The Pareto distribution is good for approximating income distributions or population sizes. The pdf is given by: \begin{equation*}...

## Continuous Random Variables and Probability Distributions

Continuous distributions are given by a probability density function (pdf): \begin{equation*} P\left(a\le X\le...

## Zipf Distribution

Suppose you have a library with $$M$$ items and you want to sort them by popularity. The parameters are $$M$$ and $$\alpha$$. The domain...

## Scarcity

People are motivated more by the thought of losing something than the thought of gaining something of the same value. Frame something in...

## Receiving Empathically

Don’t Just Do Something. Stand There! Empathy is emptying our mind and listening with our whole being. The presence that empathy...

## Requesting That Which Would Enrich Life

. Use positive language when making requests! Example of negative language: Asking someone not to do something. Instead, request what...

## Taking Responsibility For Our Feelings

Hearing a Negative Message: Four Options What others say or do may be the stimulus of our feelings, but not the cause. When someone...

## Identifying and Expressing Feelings

“I feel that…” When you use “that” after feel, you are likely not revealing your feelings. Adequately expressing feelings is...

## Observing Without Evaluating

Separate the observation from the evaluation. If you say both in one go, people are more likely to interpret it as criticism and resist....

## Communication That Blocks Compassion

Moralistic Judgments Moralistic judgments are “life-alienating” communications. The focus tends to be on analyzing wrongness then...

## Giving From The Heart

The NVC Components: Observations: State the facts Feelings: State your feelings Needs: State your needs connected to your feelings Make...

## Authority

Titles Study: A person is introduced to various groups as either a student, lecturer, professor, etc. After he leaves the room, people...

## Poisson Distribution

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

## Negative Binomial Distribution

The experiment requires: The trials be independent The outcome is binary (success or failure). The probability of success or failure is...

## Hypergeometric Distribution

The hypergeometric experiment requires: The population is finite, with $$N$$ individuals. The outcome of each trial is binary (success...

## Binomial Distribution

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

## Discrete Random Variables

Random Variables A discrete random variable is one whose set of possible values is countable. Probability Distributions for Discrete...

## Read From UIUC

Read hypothesis testing in Chapter 2 (ML rules). Reliability in Chapter 2

## Probability

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

## Liking

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 and Variability

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

Pictorial and Tabular Methods in Descriptive Statistics Stem and Leaf Display Stem and leaf display Advantages: Useful for displaying...

## Statistics: Overview

Populations, Samples and Processes A census means you poll every member of the population. Univariate vs bivariate or multivariate:...

## Frequently Asked Questions

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

## Putting It All Together

Step One: Prepare By Walking Through The Three Conversations Stories What’s my story? (information, past experiences, rules?) What’s his...

## Problem Solving: Take The Lead

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

## Expression: Speak For Yourself With Clarity

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

## Learning: Listen From The Inside Out

People have a deep desire: To be heard To know that others care enough to listen Listening Transforms The Conversation Mother has...

## Getting Started: Begin From The Third Story

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

## What’s Your Purpose: When to Raise It and When To Let Go

Pick your battles! You can’t have every difficult conversation you come across. Deciding whether to raise an issue or not torments us....

## Ground Your Identity: Ask Yourself What’s At Stake

Difficult Conversations Threaten Our Identity Sometimes the anxiety is not due to facing others, but facing ourselves. The conversation...

## Have Your Feelings Or They Will Have You

Don’t focus on just the objective facts. Feelings have to be part of the conversation. At the same time, having them explode is...

## Abandon Blame: Map The Contribution

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

Social proof is also a convenient shortcut for decision making. Kids who are scared to play with dogs become willing to merely by...

## Commitment and Consistency

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

## Reciprocation

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

## Influence: Weapons of Influence

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

## Don’t Assume They Meant It

Intentions strongly influence our judgments. Watch your sentences and notice how often you are attributing intentions to the...

## Stop Arguing About Who’s Right

At the heart of the What Happened conversation is a disagreement. Argument is the natural outcome of disagreement. But it is...

## The Three Conversations

You need to understand what people are thinking and feeling, but not saying. Every difficult conversation is really a mix of...

## Difficult Conversations

What makes a conversation difficult? Usually it is the fear of consequences. If we avoid the conversation, we feel taken advantage of,...

## Start Your Own Support Group

You can start a support group yourself. Rule: The group has no “leaders”. All the members own it. Meeting Format (Suggestion) Run a...

## A Little Structure Goes a Long Way

The principles in the book can be applied informally, but success is much higher if you formalize it. (My idea): To an extent, perhaps...

## Step Nine: Fake It Till You Make It

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

## Step Eight: Commit To Improvement

Benefits of making a commitment: Liberating to admit your problems By committing publicly, you are more likely to follow through. Public...

## Step Seven: Diagnose Your Weakness

Common problems: The struggler: Craves attention. Seeks turmoil and impossible situations. The conflict avoider: Downplays...

## Step Six: Learn to Fight

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

## Step Five: Create Your Personal Success Wheel

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

## Step Four: Broaden Your Goal Setting Strategy

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

## Step Three: Practicing The Art of The Long Slow Dinner

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

## Step Two: Find Your Lifeline Relationships

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

## Step One: Activate Your Vision

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

## 4th Mindset: Accountability

Accountability is the 4th mindset. We all make efforts to change (e.g. corporate workshops, trainings, etc), but most efforts don’t have...

## 3rd Mindset: Candor

Realize that opening yourself to get feedback from others is risk free! They will have their perceptions of you regardless of your...

## 2nd Mindset: Vulnerability

When introducing yourself, don’t just list accomplishments. Tell a story about your dreams, how you’re getting there, and what...

## 1st Mindset: Generosity

What do I have to offer others? There are two types of generosity currency: Universal and personal. Universal currency is very...

## Who’s Got Your Back

Everyone needs confidants for their professional work. People who care about your success and will not let you fail. Most people have...

## Liberals vs Conservatives

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

## The Definition of Morality

For Western/modern society, the author favors rule utilitarianism (best rules that will produce the greatest good) as opposed to act...

## Religion and Charity

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

## Religion and the New Atheists

You cannot understand religion by looking at the individual. You must look at the collective. The Lone Believer Critics of religion...

## Hives

The hive switch: The ability to temporarily transcend self-interest and lose ourselves in something bigger. It is essentially a...

## Group Selection

Group Selection: If a trait benefits the group against other groups, but not the individual against other individuals in the same group,...

## Punishment for Improving Cooperation

Reciprocal altruism theory explains why altruism/fairness behavior develops among pairs (tit for tat) but does not explain it...

## Hierarchy vs Egalitarianism

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

## Moral Foundations

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

## Bentham and Kant: Bias Towards Reason as a Root of Morality

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

## The Ethic of Divinity

Psychologists have a tendency to study the mind independent of culture. Anthropologists tend to study the culture and not the mind....

## WEIRD People

Most research in psychology is conducted on WEIRD people. WEIRD stands for Western, Educated, Industrialized, Rich and Democratic. But...

## The Rationalist Delusion

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, Cheating, Voting and Confirmation Bias

Self-Esteem Is self-esteem about how we perceive ourselves, or about how we perceive other’s perceptions about ourselves? Levy Study:...

## The Search For Truth?

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

## When Does an Elephant Listen to Reason?

Primarily by engaging with others. On can change via introspection, but others are more likely to give us non-confirmatory evidence....

## Deontologists vs Utilitarianists

Utilitarianism (save the most lives) vs Deontologism (cannot impinge on individual rights - even to save many lives). Both claim their...

## Infants’ Sense of Morality

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

## Psychopaths

1% of males are psychopaths. Fewer females are. Most are nonviolent. But virtually half of crimes like serial rape and killing,...

## Cleanliness and Morality

The sense of smell impacts moral judgments. Asking participants to fill out a survey on moral scenarios in the presence of fart smell...

## Implicit Association Test

Affective Priming: Flash words like sunshine or cancer to the screen. You need to judge whether the word is positive or negative. If you...

## Brains Evaluate Instantly and Constantly

Our brains evaluate everything instantly in terms of potential threat or benefit, and adjusts behavior to get more of the good and less...

## Thalia’s Hypnosis Study

Hypnotized one set of students and made them dislike the word “take”. Hypnotized another set and made them dislike “often”. Gave them 6...

## Does Reason Exist to Serve The Passions? Or Vice Versa?

The rationalist delusion: The worship of reason and the distrust of passions. It is a delusion because once you declare it to be an...

## Negotiations - The Coursera Treatment 2: Seidel

Should I Negotiate? Consider the time spent in preparing and executing the negotiation, and the expected gain. Is the time spent worth...

## Sociocentrism vs Individualism Part 2

To tackle Turiel’s concern that the “harmless” stories could be interpreted as harmful, Haidt decided to do a similar story, but added a...

## Sociocentrism vs Individualism

Most societies have a need to “resolve” the tension between individuals and the society. Most societies are sociocentric: The group has...

## The Anthropologist View

Anthropologists had studied and documented that many unrelated cultures had: Witchcraft and sorcery themes - with a great deal of...

## Morality vs Social Conventions

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 Kids Learn About Morality? Role-playing

How do children learn right from wrong? There used to be 2 theories: Nature: Nativist (be it through God or evolution) Nurture:...

## The Righteous Mind

Introduction Intuitions come first, strategic reasoning comes second. Moral intuitions arise automatically - long before moral reason....

## Mutation Via References

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

## First Class Functions and Functional Programming

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

## Tail Recursion

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

## Exceptions

exception MyException exception AnException of int*int raise MyException e1 handle ex => e2 e1 handle ex(x,y) => e2 (* More generally *)...

## Nested Patterns

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

## Polymorphic Types and Equality Types

The type ''a represents an equality type: It means anything that can be compared with the equality operator. Not everything can be...

## Functions and Type Inference

If you use patterns to access records or function arguments, you usually do not need to specify their types. They will be inferred from...

## Functions, Pattern Matching And Val Bindings

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

## Case Expressions

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

## Datatype Bindings

Example: datatype newtype = TwoInts of int*int | Str of string | Pizza newtype is a new type that is added to the environment. TwoInts,...

## Type Synonyms

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

## Records

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

## Immutability

Most of Standard ML has immutability. Behind the scenes, references may be in use for optimization purposes, but the language guarantees...

## Options

Consider this motivating example: I want to write a function that takes a list of integers, and returns its sum. What should it return...

## Let Expressions

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 and Lists

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

## Functions

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

## Standard ML - Basics

Comments Comments begin with (* and end with *). You can nest comments. Statement Ends In the REPL, each statement must end in a...

## Ten Questions People Ask About Getting To Yes

Much of the material with the tag gty comes from Getting To Yes. Does Positional Bargaining Ever Make Sense Principled negotiation is...

## What If They Use Dirty Tactics?

Much of the material with the tag gty comes from Getting To Yes. Examples: Deception Throwing Off Balance Nibbling (asking for stuff...

## What If They Won’t Play?

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

## What If They Are More Powerful? Protecting Yourself

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

## Insist On Using Objective Criteria

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

## Invent Options For Mutual Gain

Much of the material with the tag gty comes from Getting To Yes. Diagnosis There are typically 4 reasons that prevent the invention...

## Focus on Interests, Not Positions

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

## Separate The People From The Problem

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

## Don’t Bargain Over Positions

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

## Introduction

Much of the material with the tag gty comes from Getting To Yes. Negotiation is easier if both sides know how to perform it.

## Negotiations (Getting To Yes)

Much of the material with the tag gty comes from Getting To Yes.

## Story Writing Checklist

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

## Handling Critique

People’s critiques will be very subjective and very related to themselves. They may hate a character because it reminds them of someone...

## Show Them Once So They Know

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

Superior position is when the audience knows something the characters do not. It is a useful tool for suspense, but can serve other...

## Dialogue

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

## Subplots or Supporting Plots?

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

## God From the Machine

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

## Climax

The climax should bring masculine and feminine elements together. It shows how a character changed (or didn’t).

## Genre

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

## Show, Don’t Tell: Teaching vs Preaching

A storyteller teaches, not preaches. If you talk about what you want to say, you are preaching. If you show, you are teaching. The...

## The Masculine and the Feminine

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

## Tell the Truth

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

## Character Development

Ritual Pain Think of rites of passage. In many cultures, one has to undergo severe pain to become a man (not for women). Gang...

## The Use of Clones

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

## The Armature

People tell stories to teach something. It is likely the origin of stories - a way to teach something beyond simply using boring facts....

## The Recipe for All Narratives

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

## Negotiations - The Coursera Treatment

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

## Common Tactics Others Use

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Lies about the bottom line and alternatives: Never...

## Bargaining With the Devil

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. The more ethical you are, the higher the cost...

## Closing and Giving Commitment

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Scarcity Effect: People will value (or overvalue) a...

## Opening and Making Concessions

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. If your opponent is competitive, you may need to...

## Exchanging Information

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. 3 aspects to it: Rapport development Discovering...

## Preparing Your Strategy

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. There are 4 steps to negotiations: Preparation...

## Leverage

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Leverage gives you power to reach an agreement on...

## The Other Party’s Interests

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. It is imperative to ask yourself how achieving your...

## Relationships

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Reciprocity is the key to sustaining trust...

## Authoritative Standards and Norms

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. There exist several norms and standards. Examples:...

## Your Goals and Expectations

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. Research shows: The more specific your vision of...

## Your Bargaining Style

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. There are typically 4 steps in negotiation:...

## Bargaining For Advantage - Introduction

Much of the materials with the tag bfa comes from the Bargaining for Advantage book. When negotiating, it is vital to be yourself: If...

## Burrows-Wheeler Transform

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

## LZW Compression

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

## Huffman Encoding

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

## Run Length Encoding

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

## Substring Matching

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

## Tries

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

## Symbol Tables

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

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

## Hash Functions

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

## Suffix Arrays

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

Counting Sort Suppose we have $$N$$ elements, but we know the elements are drawn from a fixed, finite list (called the alphabet in this...

## Max Flows and Min Cuts

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

## Shortest Paths Summary

There are many “kinds” of shortest paths. Algorithm Constraint Typical Worst Case Topological Sort No directed cycles $$N+M$$ $$N+M$$...

## Negative Cycles

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

## Shortest Paths

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

## Minimum Spanning Trees

Given a connected graph $$G$$, with positive edge weights, the spanning tree is a subgraph $$T$$ that is both a tree (connected and...

## Finding the Strongly Connected Components of a Digraph

Applications When looking at code/library dependencies, one may want to see which code pieces form strongly connected components, and...

## Topological Sort

Topological Sort A topological sort is a traversal of a digraph with ordering constraints. Let each node have some value/weight. It is a...

## Minimum Cut of a Graph

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

## Karatsuba Multiplication

In grade school we learn an algorithm for multiplying two $$N$$ digit integers. Let our basic operation to be the multiplication or...

## Rectangle Intersection

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 ## 2-D Range Search, Points in a Box Search and K-D Trees 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... ## 1-D Range Search and Line Intersection Search Sample problems we want to solve: What are all the keys between two keys? (Relevant to databases) How many keys exist between two keys?... ## Red Black Trees We introduced 2-3 trees with highly desirable properties. Here we’ll convert them into binary trees while maintaining all the... ## Asymptotic Expansions A decreasing sequence \(g_{k}(N)$$ is called an asymptotic scale if $$g_{k+1}(N)=o(g_{k}(N))$$. $$f(N)\sim... ## The Average Number of Leaves in a Binary Tree of \(N$$ Internal Nodes

Let’s use generating functions to count the average number of leaves in a binary tree with $$N$$ internal nodes. Definitions Let $$P$$...

## The Average Number of 1’s in a Binary String of Length $$N$$

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

## Counting With Generating Functions

Generating functions can be used for counting. Consider the problem of finding the number of trees with internal nodes. Let $$T$$ be the...

## 2-3 Trees

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

## Exponential Generating Functions

To form a generating function, we multiplied by $$z^{N}$$ and summed. This is not the only way to form a generating function. Another...

## Catalan Numbers

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

## Solving Recurrence Relations With Ordinary Generating Functions

Technique The basic technique is to multiply the equation with $$z^{N}$$, sum over all $$N$$, recast in terms of the generating function...

## Ordinary Generating Functions

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

## Motivation for Generating Functions (Classical Approach)

Problem How many bits are needed to represent a binary tree with $$n$$ internal nodes (I think leaf nodes are not internal)? These trees...

## Binary Search Trees

A binary search tree is a fairly useful structure for storing ordered data. The invariant for a binary search tree is straightforward:...

## Heap Sort

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

## Binary Heaps & Priority Queues

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

## K-th Largest Element

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

## Quick Sort

A quick sort works recursively: Shuffle the list. This protects against a carefully crafted input that will make the algorithm...

## Convex Hull Problem

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

## Sorting Complexity Analysis

Any comparison based sorting algorithm must use at least $$\lg(N!)\sim N\lg N$$ comparisons for the worst case. This is absent any...

## Finding the Closest Pairs in a Plane

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

## Counting Inversions

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

## Dealing With Recurrence Relations

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

## Merge Sort

A merge sort works recursively: Split the list into two roughly equal halves. Sort each half using mergesort. Merge the two...

## Shuffling Caveats

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

## Shell Sort

A shell sort works somewhat recursively. It first sorts every $$k$$ elements (i.e. the sublist formed by elements 0, $$k$$, $$2k$$,...

## Insertion Sort

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

## Inversions & Partial Sortedness

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

## Selection Sort

A selection sort starts out by traversing the whole list, finding the minimal element, and swapping it with the first element. It then...

## Loop Invariants

A loop invariant is a statement that holds true just before and after each iteration. It may be violated within the iteration, but the...

## Graphs Using NetworkX

NetworkX is a Python library for handling graphs. In [1]: %matplotlib inline In [14]: import networkx as nx import pylab as plt In [3]:...

## Breadth First Search And Finding the Distance Between Two Nodes

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

## Depth First Search

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

## Queues

A queue is a data structure for holding objects. It is a FIFO structure. It supports two operations: enqueue and dequeue dequeue returns...

## Graphs

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

## Stacks

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 and 3-Sum

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

## Percolation: An Application of Union Find

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

## Union-Find Algorithm

Dynamic Connectivity & Disjoint Sets Given $$N$$ nodes, some connected amongst themselves, does a path exist between any two...

## Asymptotic Notation

An asymptotically positive function $$f(n)$$ is one that is always positive for sufficiently large $$n$$. A similar definition holds for...

## Probability Review

Linearity of expectation: $$E(aX+bY+c)=aE(x)+bE(Y)+c$$. This holds even when $$X$$ and $$Y$$ are dependent. Exploit this! Independent...

## Useful Inequalities

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