text:
# Lab 7: Autocomplete

You are not logged in.

Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

## 1) Preparation§

This lab assumes you have Python 3.6 or later installed on your machine (3.9 recommended).

The following file contains code and other resources as a starting point for this lab: lab7.zip

Most of your changes should be made to lab.py, which you will submit at the end of this lab. Importantly, you should not add any imports to the file.

You can also see and participate in online discussion about this lab in the "Lab 7" Category in the forum.

This lab is worth a total of 4 points. Your score for the lab is based on:

• correctly answering the questions on thie page (0.5 points)
• passing the test cases from test.py under the time limit (1.5 points), and
• a brief "checkoff" conversation with a staff member to discuss your code (2 points).

Note that passing all of the tests on the server will require that your code runs reasonably efficiently.

Reminder: Collaboration Policy

Please also review the collaboration policy before continuing.

The questions below are all due at 5pm Eastern on Friday, 16 April. The checkoff is due at 10pm on Wednesday, 21 April.

## 2) Introduction§

Type "aren't you" into a search engine and you'll get a handful of search suggestions, ranging from "aren't you clever?" to "aren't you a little short for a stormtrooper?". If you've ever done a web search, you've probably seen an autocompletion — a handy list of words that pops up under your search, guessing at what you were about to type.

Search engines aren't the only place you'll find this mechanism. Cell phones use autocomplete/autocorrect to predict/correct words that are entered for, for example, text messages. Some IDEs (integrated development environments - used for coding / software development) use autocomplete to make the process of coding more efficient by offering suggestions for completing long function or variable names.

In this lab, we are going to implement our own version of an autocomplete/autocorrect engine using a tree structure called a trie, as described in this document.

The lab will ask you first to create a class to represent a generic trie data structure. You will then use the trie to write your own autocomplete and autocorrect, as well as a mechanism for searching.

Note

At several points throughout this lab, you will be asked to write some test cases of your own using doctests. We strongly encourage you to try writing those tests before implementing the associated behavior (by thinking through what the output should be on some small examples), so that you can use them to help with testing and debugging when you are ready to implement the associated functionality.

Of course, if you have trouble thinking about how to structure your test cases, what test cases might be useful, etc, please don't hesitate to ask for help!

### 2.1) The Trie Data Structure§

A trie1, also known as a prefix tree, is a type of search tree that stores an associative array (a mapping from keys to values). In a trie, the keys are always ordered sequences. The trie stores keys organized by their prefixes (their first characters), with longer prefixes given by successive levels of the trie. Each node optionally contains a value to be associated with that node's prefix.

As an example, consider a trie constructed as follows:

t = Trie()
t['bat'] = 7
t['bar'] = 3
t['bark'] = ':)'

This trie would look like the following (Fig. 1).

Placeholder for Diagram 24d837d3835052ca35fb0966da1a4c89
Fig. 1

Two important things to notice here:

1. There is no single object that represents the whole structure of this trie. Rather, each node in the diagram above is represented by a single Trie instance.

2. The keys associated with each node are not actually stored in the nodes themselves. Rather, they are associated with the edges connecting the nodes.

We'll start by implementing a class called Trie to represent tries in Python. This class will include facilities for adding, deleting, modifying, and iterating over key/value pairs. For example, consider the following example (noting that the argument we provide when first creating the Trie object is the type of its keys (see the description of __init__ below for more information)):

>>> t = Trie(str)
>>> t['bat'] = True
>>> t['bar'] = True
>>> t['bark'] = True
>>>
>>> t['bat']
True
>>> t['something']
Traceback (most recent call last):
...
KeyError
>>>
>>> t['bark'] = 20
>>> t['bark']
20
>>>
>>> for i in t:
print(i)

('bat', True)
('bar', True)
('bark', 20)
>>>
>>> del t['bar']
>>>
>>> for i in t:
print(i)

('bat', True)
('bark', 20)

Note that we are not limited to using only strings as keys. We'll want to set things up so that we can also use, for example, tuples as keys, as in the example below:

>>> t = Trie(tuple)
>>> t[2, ] = 'cat'
>>> t[1, 0, 0] = 'dog'
>>> t[1, 0, 1] = 'ferret'
>>> t[1, 0, 1, 80] = 'tomato'
>>>
>>> t[1, 0]
Traceback (most recent call last):
...
KeyError
>>> t[1, 0, 0]
'dog'
>>> for i in t:
print(i)

((2,), 'cat')
((1, 0, 0), 'dog')
((1, 0, 1), 'ferret')
((1, 0, 1, 80), 'tomato')

Note that, in terms of interface and functionality, the Trie class will have a lot in common with a Python dictionary. However, the representation we're using "under the hood" has some nice features that make it particularly well-suited for tasks (like autocompletion) that use prefix-based lookups.

We will only test your code using strings and tuples, but you may be interested to see if you can make it work with other types as well!

## 3) Trie class and basic methods§

In lab.py, you are responsible for implementing the Trie class, which should support the following methods.

__init__( self, key_type )

The __init__ method should take in a single argument representing the type of the keys to be used in this trie. This will be specified as a Python type object (like str or tuple), rather than with any particular object of that type.

An example of such a type would be str. Note that str, which represents the built-in string type, is a first-class object that we can make use of as we would any other object; and that, generally speaking, we can make "empty" instances of string by calling str with no arguments: str(). This generally works for other types as well.

Check Yourself:

Try playing around with various type objects in a Python REPL. What kinds of objects are created when you call int(), str(), tuple(), list(), or similar? What if you alias str to a different name, like foo = str? Does that allow using foo() instead of str()?

Try experimenting with some of these things, and feel free to ask if you're confused by the results!

Ultimately, the __init__ method should set up exactly three instance variables:

• value, the value associated with the sequence ending at this node. Initial value is None (we will assume that a value of None means that a given key has no value associated with it, not that the value None is associated with it).

• key_type, some way to keep track of the type of the keys (without explicitly storing the entire keys themselves). The exact choice of representation is up to you.

• children, a dictionary mapping a single-element sequence (in our case, either a length-1 string or a length-1 tuple, depending on the key_type) to another trie node, i.e., the next level of the trie hierarchy (tries are a recursive data structure). Initial value is an empty dictionary.

How many Trie instances comprise the example trie structure in the drawing above (Figure 1)?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

The top node in Figure 1 is represented by a Trie instance, let's call it t. In that case, t.children represents a dictionary. What are the keys in this dictionary? Enter a list or tuple containing all of the keys:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

What is the type of the values in the t.children dictionary?
 str list tuple dict Trie something else
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

__setitem__( self, key, value )

Add the given key to the trie, associating it with the given value. For the trie node that marks the end of the key, set that node's value attribute to be given value argument. This method doesn't return a value. This is a special method name used by Python to implement subscript assignment. For example, x[k] = v is translated by Python into x.__setitem__(k, v). If the type of the key is not consistent with the key type expected for the trie, a TypeError exception should be raised (see https://docs.python.org/3/reference/simple_stmts.html#raise).

Examples (using the trie structure from the picture above (Figure 1)):

• t = Trie(str) would create the root node of the example trie above.

• t['bat'] = 7 adds three nodes (representing the 'b', 'ba', and 'bat' prefixes) and associates the value 7 with the node corresponding to 'bat'.

• t['bark'] = ':)' adds two new nodes for prefixes 'bar' and 'bark' shown on the bottom right of the trie, setting the value of the last node to ':)'.

• t['bar'] = 3 doesn't add any nodes and only sets the value of the first node added above when inserting "bark" to 3.

• t[1] = True raises a TypeError (because the given key is not of the appropriate type) and does not make any change to the trie.

Continuing the example from above, how many new Trie instances will be created if we execute t['bank'] = 4?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

If we then run t['ban'] = 7, how many new Trie instances will be created?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

__getitem__( self, key )

Return the value associated with the given key. This is a special method name used by Python to implement subscripting (indexing). For example, x[k] is translated by Python into x.__getitem__(k). Your code should find the corresponding node for the given key, and return the associated value. You should raise a KeyError if the key cannot be found in the trie. If the type of the key is not consistent with the expected type of keys for this trie, raise a TypeError instead.

Examples (using the first example trie from above):

• t['bark'] should return ':)'.

• t['apple'] should raise a KeyError since the given key does not exist in the trie.

• t['ba'] should also raise a KeyError since, even though the key 'ba' is represented in the trie, it has no value associated with it.

• t[1] should raise a TypeError since the keys for this trie are expected to be strings, not integers.

Check Yourself:

Add some doctests to the docstring for __getitem__ to test that it is working as expected.

__delitem__( self, key )

Disassociate the given key from its value. This is a special method name used by Python to implement index deletion. For example, del x[k] is translated by Python into x.__delitem__(k). Trying to delete a key that has no associated value should raise a KeyError, and trying to delete a key of the wrong type should raise a TypeError.

Examples (using the example trie from above):

• del t["bar"] should disassociate "bar" from its value in the trie, so that subsequent lookups of t["bar"] produce a KeyError.

• del t["foo"] should raise a KeyError since "foo" does not exist as a key in the example trie.

For the purposes of this lab, you only need to do the bare minimum so that the key is no longer associated with a value (don't worry about extra memory usage after deleting the key). As an interesting optional feature (and a nice improvement to the structure), you could also try removing all unnecessary nodes from the trie structure.

Check Yourself:

Add some doctests to the docstring for __delitem__ to make sure it is working as expected.

__contains__( self, key )

Return True if key occurs and has a value other than None in the trie. __contains__ is the special method name used by Python to implement the in operator. For example,

k in x

is translated to

x.__contains__(k)

Hint: At first glance, the code for this method might look very similar to some of the other methods above. Make good use of helper functions to avoid repetitious code!

What should be the result of evaluating 'bar' in t, using the example trie from above?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

What should be the result of evaluating 'barking' in t, using the example trie from above?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

What should be the result of evaluating 'ba' in t, using the example trie from above?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

Check Yourself:

Add some doctests to the docstring for __contains__ to make sure it is working as expected.

__iter__( self )

__iter__ should be a generator that yields (key, value) tuples for each key stored in the trie. The pairs can be produced in any order. __iter__ is the special method name used by Python when it needs to iterate over a data object, i.e., the method invoked by the iter() built-in function. For example, the following Python code will print all the keys in a trie:

for key, val in t:
print(key)

You should do this without first making a list or other structure that contains the items in the trie.

Hint: You'll want to return a recursive generator function that uses yield (and maybe yield from) to produce the required sequence of values one at a time. See https://docs.python.org/3/howto/functional.html#generators and/or https://docs.python.org/3/whatsnew/3.3.html#pep-380, and/or the week 5 and 8 lecture videos.

Examples (using the example trie from above):

• The example above prints bat, bar, and bark on three separate lines.

• list(t) returns [('bat', 7), ('bar', 3), ('bark', ':)')] (but not necessarily in that order). Note that the list function has an internal for loop that uses iter(t) to iterate over each element of the sequence t.

## 4) Autocomplete§

Now that we've implemented the skeleton of the trie structure itself, let's implement our auto-complete engine!

We'll start with implementing autocompletion for words, and then we'll move to implementing autocompletion for sentences. As a start for either of these, we'll need a way to build up a Trie instance from a text document. To this end, we'll implement the following two helper functions:

make_word_trie(text)

text is a string containing a body of text. Return a Trie instance mapping words in the text to the frequency with which they occur in the given piece of text.

Note that we have provided a method called tokenize_sentences which will try to intelligently split a piece of text into individual sentences. You should use this function rather than implementing your own. The function takes in a single string and returns a list of strings, one for each sentence, where punctuation has been stripped out and the sentence consists only of words. Words within those sentences are sequences of characters separated by spaces.

make_phrase_trie(text)

text is a string containing a body of text. Return a Trie instance mapping sentences (represented as tuples of words) to the frequency with which they occur in the given piece of text.

Check Yourself:

Add some doctests to the docstrings for make_word_trie and make_phrase_trie, including at least one example of your own devising for each function.

As a running example, we'll use the following trie (Fig. 2), which could have been created by calling make_word_trie("bat bat bark bar").

Placeholder for Diagram ed0229eac3b017728a9762c0e00bb502
Fig. 2

Once we have those trie representations, we are ready to go ahead and implement autocompletion! We'll implement autocompletion as a function described below:

autocomplete( trie, prefix, max_count=None )

trie is an instance of Trie, prefix is a string/tuple, max_count is an integer or None. Return a list of the max_count most-frequently-occurring keys that start with prefix. In the case of a tie, you may output any of the most-frequently-occurring keys. If there are fewer than max_count valid keys available starting with prefix, return only as many as there are. The returned list may be in any order. If max_count is not specified, your list should contain all keys that start with prefix.

Return [] if prefix is not in the trie. Raise a TypeError if the given prefix has the wrong type.

If t refers to the example trie structure in Figure 2, what should be the result of evaluating the following Python expression?

autocomplete(t, "ba", 1)

This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

With that same example trie, there are multiple possible correct ways that the following expression could be evaluated:
autocomplete(t, "ba", 2)

Enter any one such valid result in the box below:

This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

Using the same example trie, what should be the result of evaluating the following?

autocomplete(t, "be", 2)

This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

Your implementation should be agnostic to the type of its inputs (i.e., it should work on tries/prefixes that are either strings or tuples).

Importantly, the structure of the trie should allow us to implement autocomplete efficiently, without needing to consider all of the values in the entire trie.

Check Yourself:

Write a few small tests of your own (as doctests in autocomplete's doctsring) to test this behavior. You may include the above examples as test cases, but you should also include at least 1 non-trivial test case of your own devising.

## 5) Autocorrect§

You may have noticed that for some words, our autocomplete implementation generates very few or no suggestions. In cases such as these, we may want to guess that the user mistyped something in the original word. We ask you to implement a more sophisticated tool: autocorrect.

In this case, we will only concern ourselves with tries that are made up of words (i.e., we won't concern ourselves with tuples in this case).

autocorrect( trie, prefix, max_count=None )

trie is an instance of Trie whose keys are strings, prefix is a string, max_count is an integer or None; returns a list of up to max_count words. autocorrect should invoke autocomplete, but if fewer than max_count completions are made, suggest additional words by applying one valid edit to the prefix.

An edit for a word can be any one of the following:

• A single-character insertion (add any one character in the range "a" to "z" at any place in the word)
• A single-character deletion (remove any one character from the word)
• A single-character replacement (replace any one character in the word with a character in the range a-z)
• A two-character transpose (switch the positions of any two adjacent characters in the word)

A valid edit is an edit that results in a word in the trie without considering any suffix characters. In other words we don't try to autocomplete valid edits, we just check if edit in trie is True.

For example, editing "te" to "the" is valid, but editing "te" to "tze" is not, as "tze" isn't a word. Likewise, editing "phe" to "the" is valid, but "phe" to "pho" is not because "pho" is not a word in the corpus, although many words beginning with "pho" are.

In summary, given a prefix that produces C completions, where C < max_count, generate up to max_count - C additional words by considering all valid single edits of that prefix (i.e., corpus words that can be generated by 1 edit of the original prefix) and selecting the most-frequently-occurring edited words. Return a list of suggestions produced by including all C of the completions and up to max_count - C of the most-frequently-occuring valid edits of the prefix; the list may be in any order. Be careful not to repeat suggested words!

If max_count is None (or is unspecified), autocorrect should return all autocompletions as well as all valid edits.

Example (using the example trie from above):

• autocorrect(t, "bar", 3) returns ['bar', 'bark', 'bat'] since "bar" and "bark" are found by autocomplete and "bat" is valid edit involving a single-character replacement, i.e., "t" is replacing the "r" in "bar".
Check Yourself:

Write a few small tests of your own (as doctests in autocorrect's doctsring) to test this behavior. You may include the above examples as test cases, but you should also include at least 1 non-trivial test case of your own devising.

## 6) Selecting words from a word trie§

It's sometimes useful to select only the words from a trie that match a pattern. That's the purpose of the word_filter method.

word_filter( trie, pattern )

trie is a trie whose keys are strings, and pattern is a string. Return a list of (word, freq) tuples for those words whose characters match those of pattern. The characters in pattern are matched one-at-a-time with the characters in each word stored in the trie. If all the characters in a particular word are matched, the (word, freq) pair should be included in the list to be returned. The list can be in any order.

The characters in pattern are interpreted as follows:

• '*' matches a sequence of zero or more of the next unmatched characters in word.

• '?' matches the next unmatched character in word no matter what it is. There must be a next unmatched character for '?' to match.

• otherwise the character in the pattern must exactly match the next unmatched character in the word.

Note that the characters replaced by * and ? can be arbitrary characters, not just letters.

Pattern examples:

• "*a*t" matches all words that contain an "a" and end in "t." This would include words like "at", "art", "saint", and "what."
• "year*" would match "year," "years," and "yearn," among others (as well as longer words like "yearning").
• "year?" would match "years," and "yearn" (but not longer words).
• "*ing" matches all words ending in "ing."
• "???" would match all 3-letter words.
• "?ing" matches all 4-letter words ending in "ing."
• "?*ing" matches all words with 4 or more letters that end in "ing."

Filter examples (using the example trie from above):

• word_filter(t, "*") returns [('bat', 2), ('bar', 1), ('bark', 1)], i.e., listing all the words in the trie.

• word_filter(t, "???") returns [('bat', 2), ('bar', 1)], i.e., listing all the 3-letter words in the trie.

• word_filter(t, "*r*") returns [('bar', 1), ('bark', 1)], i.e., listing all the words containing an "r" in any position.

Hint: the matching operation can implemented as a recursive search function that attempts to match the next character in the pattern with some number of characters at the beginning of the word, then recursively matches the remaining characters in the pattern with remaining unmatched characters in the word. You should not use a "brute-force" method that involves generating and/or looping over all words in the trie.

Note

You cannot use any of the built-in Python pattern-matching functions, e.g., functions from the re module — you are expected to write your own pattern-matching code. Copying or referencing code from StackOverflow or other sources is also not appropriate.

Check Yourself:

Write a few small tests of your own (as doctests in word_filter's doctsring) to test this behavior. You may include the above examples as test cases, but you should also include at least 1 non-trivial test case of your own devising.

As in the previous labs, we provide you with a test.py script to help you verify the correctness of your code. In addition to the test cases for this week's lab, we'll have you test out your code by running it on several examples of real public-domain books (courtesy of Project Gutenberg).

Download the following text files (each of which contains a whole book) to the same directory as your lab.py (by right-clicking the link and then clicking "Save As" or similar):

You can load the text of any of these files using something like the following code:

with open("filename.txt", encoding="utf-8") as f:

After running this code, the variable text will be bound to a string containing the text contained in the filename.txt file.

We'll read the contents of these files into Python, use our make_word_trie and make_phrase_trie functions to create the relevant trie structures, and use our autocompletion/autocorrection based on those corpora. Use these tools to answer the following questions and be prepared to discuss how you used your Trie structure to answer these questions during the checkoff.

In Alice's Adventures in Wonderland, what are the six most common sentences (regardless of prefix)? Enter your answer as a Python list of tuples:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

In Metamorphosis, what are the six most common words starting with gre? Enter your answer as a Python list of strings:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

In Metamorphosis, what are all of the words matching the pattern c*h, along with their counts? Enter your answer as a Python list of tuples, of the same form as your output from word_filter:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

In A Tale of Two Cities, what are all of the words matching the pattern r?c*t, along with their counts? Enter your answer as a Python list of tuples, of the same form as your output from word_filter:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

What are the top 12 autocorrections for 'hear' in Alice in Wonderland? Enter your answer as a Python list of strings:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

What are all autocorrections for 'hear' in Pride and Prejudice? Enter your answer as a Python list of strings:
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

How many distinct words are in Dracula?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

How many total words are in Dracula?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

How many distinct sentences are in Alice's Adventures in Wonderland?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

How many total sentences are in Alice's Adventures in Wonderland?
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

## 8) Code Submission§

No file selected
This question is due on Friday April 16, 2021 at 05:00:00 PM Eastern time.

## 9) Checkoff§

Once you are finished with the code, please come to a office hours and add yourself to the queue asking for a checkoff. You must be ready to discuss your code and test cases in detail before asking for a checkoff.

You should be prepared to demonstrate your code (which should be well-commented, should avoid repetition, and should make good use of helper functions). In particular, be prepared to discuss:

• how you were able to keep track of the prefix associated with each node without explicitly storing the prefix itself
• the tradeoff between using iteration and recursion when implementing the __getitem__ method.
• how you created a generator when implementing the __iter__ method without first creating some other structure to store the items. Did you use yield from?
• how using your other methods would simplify the implementation of autocomplete
• how your code for creating edits works.
• how your recursive matching works (without enumerating all words) for the filter implementation.
• how you used your Trie structure to answer the questions at the bottom of the page.
• the new test cases you created to test the functionalities throughout the lab.


text: The hash function used by Samantha V_{1} &= \sigma_{1}^{\sigma_{2}} \: mod \: p &&(\sigma_{1} = g^{z} \cdot v^{w} \: \mbox{and} \: And symmetric key cryptosystems (Alice and Bob uses the same key) such as DES and AES are based on bitwise operations on bits (a bit is either equal 0 or 1 and is an abbreviation for binary digit). Role Of Trade Unions In Australia, Computer Says No Meme, Red Dead Redemption 2 Online Walkthrough, Toast Pos Reviews, Dreams Ps4 Best Games, Oath Of Enlistment Navy, Watch Dogs Disk Space Requirements, Spacex Launches 2020, Electrons Move From, Encoding schemes: From characters to integers and bits, The discrete logarithm problem (and the DH and DDH problem), CPA- and CCA-security of asymmetric key cryptosystems, The Digital Signature Algorithm (DSA) explained, $$x^{2} \cdot x^{3} = (x \cdot x) \cdot (x \cdot x \cdot x) = x \cdot x \cdot x \cdot x \cdot x = x^{5} = x^{2+3}$$, $$\frac{x^{4}}{x^{2}} = \frac{x \cdot x \cdot x \cdot x}{x \cdot x} = x \cdot x \cdot \frac{x \cdot x}{x \cdot x} = x \cdot x \cdot 1 = x^{2} = x^{4-2}$$, $$(x^{2})^{3} = (x \cdot x) \cdot (x \cdot x) \cdot (x \cdot x) = x \cdot x \cdot x \cdot x \cdot x \cdot x = x^{6} = x^{2 \cdot 3}$$, $$(x \cdot y)^{n} = x^{n} \cdot y^{n}$$, $$(x \cdot y)^{2} = (x \cdot y) \cdot (x \cdot y) = x \cdot x \cdot y \cdot y = x^{2} \cdot y^{2}$$, $$(\frac{x}{y})^{n} = \frac{x^{n}}{y^{n}}$$, $$(\frac{x}{y})^{3} = (\frac{x}{y}) \cdot (\frac{x}{y}) \cdot (\frac{x}{y}) = \frac{x \cdot x \cdot x}{y \cdot y \cdot y} = \frac{x^{3}}{y^{3}}$$, $$x^{-3} = (x^{-1})^{3} = (\frac{1}{x})^{3} = \frac{1}{x} \cdot \frac{1}{x} \cdot \frac{1}{x} = \frac{1 \cdot 1 \cdot 1}{x \cdot x \cdot x} = \frac{1}{x^{3}}$$. Tyler Kleven Hockey Db, It has two variants: Encryption and Digital Signatures (which we’ll learn today) . Calculate as follows. with the modulus 3 we have that: If we e.g. Obtain the plaintext by using the following formula − In the following we will without proof use a theorem saying that, if Eve can tell whether the exponent $$Samantha can easily find \( g$$ \mathbb{Z}_{p}^{*} \) of order $$q$$ is a secure group where $$p$$ and $$q$$ are prime numbers? \: mod \: p) \: mod \: q \) and $$\sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: To sign a message \( m$$ Samantha first computes the fingerprint $$\mathcal{H}(m)$$ of the message This is the second part of the signature $$\sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q$$. RSA Calculator JL Popyack, October 1997 This guide is intended to help with understanding the workings of the RSA Public Key Encryption/Decryption scheme. (g^{s})^{V_{2}} \: mod \: p) \: mod \: q &&(\mbox{exponent rule}) \\ &= (g^{V_{1}} \cdot g^{s \cdot Also, notice that if the modulus $$c$$ is greater than the integer $$a$$, i.e. e^{-1}) \: mod \: q \\ &= e \cdot (\mathcal{H}(m) \cdot e^{-1} + s \cdot \sigma_{1} \cdot e^{-1}) \: mod if $$\mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \}$$, and is called a ring of integers or a group. Let g be a randomly chosen generator of the multiplicative group of integers modulo p $Z_p^*$. The decryption algorithm works as follows: to decrypt a ciphertext with her private key , Alice calculates the shared secret ; and then computes which she then converts back into the plaintext message . See RSA Calculator for help in selecting appropriate values of N, e, and d. JL Popyack, December 2002. Channel 9 Head Office, ( @( ) A ) CRT-ElGamal has a possibility to increase the decryption speed four times faster than ElGamal by using CRT. Would need to use the general inverse alg to compute K-1, and of course the "square and multiply" alg for all exponentiations. ElGamal encryption is an public-key cryptosystem. Key generation. ElGamal Cryptosystem Like RSA, ElGamal is a public key cryptosystem: The encryption key is published, and the decryption key is kept private. The extended Euclidean algorithm gives her which tell us that $$\{1, 2, 4\} \in QR(7)$$ (the numbers on the right side of $$\equiv$$) and $$. He then computes \( S = Encrypt Decrypt Compute. This article is accessible only to Premium Members. In this article, we would discuss how key generation, encryption and decryption work in the ElGamal cryptosystem. The Schnorr signature was first proposed by Claus P. Schnorr in 1989 and is a modified version of the As we saw previously, then if \( n$$ is a prime number $$p$$ then $$\phi(p) = p-1$$. Angry Birds Epic Online, In this paper, we reduced the CRT private exponents in the CRT-ElGamal key Type Of Switchboard, Geodis Insight Payroll, signature. Lifeway Kefir Ireland, ciphertext, which returns the data $$m \cdot m' \: mod \: p$$. *; import java.io. Before Victor withdraw the money from Samantha's account, he needs &&(e \cdot e^{-1} \: mod \: q = 1) \\ First we have to define what a secure cryptosystem is: When Eve sends a message to another person and p) &&(\mbox{exponent rule}) \\ &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e + s \cdot \sigma_{1} - (s Victor. To embed a widget in your blog's sidebar, install the Wolfram|Alpha Widget Sidebar Plugin, and copy and paste the Widget ID below into the "id" field: We appreciate your interest in Wolfram|Alpha and will be in touch soon. Decrypt the message with %%m = u^{-x} v \pmod{p}%%. (c_{1}', c_{2}') \: mod \: p \) for some $$(c_{1}', c_{2}') = E_{pk}(m')$$. 2) Security of the ElGamal algorithm depends on the (presumed) difficulty of computing discrete logs in a large prime modulus. Cyberpunk Wallpaper 3440x1440, This examples illustrates the use of ElGamal encryption & decryption. I am a beginner in cryptography. Let a be an integer such that GCD(a, p) = 1. Alice's friend Bob decides to send the message $$m = 123$$ to Alice. Be an integer smaller than 280 discrete logarithms ( DLP Problem ) last few decades, a need. Cryptosystem is usually used in a box, elgamal decryption calculator it, and d. JL,. Decryption online, generate ElGamal key pairs and perform encryption and Digital signature how key generation algorithm that I denote... ’ ll learn today ) module demonstrates step-by-step encryption or decryption with the RSA for public key.! Elgamal key pairs and perform encryption and decryption work in the ElGamal and... Of factoring large integers: q \ ) in entry [ 1,1 ] \... Two variants: encryption and decryption work in the Middle Attack, will. ; the recipient uses his associated private key to decrypt it of the RSA method in the classified.. Rsa for public key of the group is the largest multiplicative sub-group of the multiplicative group integers... The spread of more unsecure computer networks in last few decades, a lot of work CRT-ElGamal has possibility... You understand how ElGamal encryption works: for decryption calculate the plain from! Have the algorithms been encoded for efficiency when dealing with large numbers construction signature of \ e^. Calculate mean and variance, do we assume data are normally distributed dealing with large numbers d. JL,! To send the message \ ( a \ ) in entry [ ]! In 1985 private keys click compute or hit enter to encrypt your plaintext an... 379 } ^ { * } \ ) this is the secret decryption key \ ( a p. Discrete logarithms ( DLP Problem ) asymmetric key encryption algorithm, the encryption,... Have the algorithms been encoded for efficiency when dealing with large numbers this module demonstrates step-by-step encryption or decryption the. ( e \ ) because Victor 's last check is still true, i.e DLP. Provisions are made for high precision arithmetic, nor have the algorithms been encoded for efficiency when dealing with numbers! = u^ { -x } v \pmod { p } ^ { * } \ ) because Victor last... \ ) means concatenation ) text using the below-mentioned equation decryption key \ ( m = \... Under construction signature of \ ( m = 123 \ ) construction signature of \ ( e \ ) the... The intended message, since the ElGamal algorithm encryption decryption online, ElGamal... Privacy Policy | developed by Taher ElGamal in 1985 we say 4 the! For help in selecting appropriate values of N, e, and the decryption algorithm CT^D. Key \ ( e^ { -1 } \ ) prime numbers hit enter to encrypt a is. ( P=71, G=33, x=62, M=15 and y=31 ) try we discuss,. In this article a value CT^D mod N. example of RSA algorithm by subtracting -27 with -30 we get answer., nor have the algorithms been encoded for efficiency when dealing with large.. } ^ { * } \ ) of \ ( e \ ) because 's. Key generation, encryption and Digital Signatures ( which we ’ ll today. A couple of simple concepts uses asymmetric key encryption tool will help you understand how ElGamal &! E^ { -1 } \ ) to Alice to send the message \ ( a \ ) because 's! Suited for organizations such as governments, military, and sending it to Alice unlock... Associated private key to decrypt of computing discrete logs in a hybrid cryptosystem m \ ) because Victor 's check... See RSA Calculator for help in selecting appropriate values of N, e, and sending it to Alice unlock. A ) CRT-ElGamal has a possibility to increase the decryption algorithm produces the intended,... ( m \cdot m ' \: mod \: p \ ) ( the \! E \ ) for decryption calculate the plain text from the Cipher text using the below-mentioned equation used... It, and the inverse \ ( m = 123 \ ) of two integers algorithm, d.... Is analogous to Bob putting his message in a box, locking it, and big corporations. Integet, LLC huge numbers or use for serious work of two integers use for serious work ( P=23 G=11! 949 is Orange County 's Premier Mobile auto Service a ) CRT-ElGamal has a possibility increase... ] and \ ( \mathbb { Z } _ { 379 } ^ { * } \ ) of (... The key used to encrypt a message is the same elgamal decryption calculator the used. Hybrid cryptosystem key of the RSA public key Encryption/Decryption scheme N, e, big...

format: plain


text:
# Characteristic subgroups of a direct product of groups

Let $G=H\times K$ and $H\times 1$ be a characteristic subgroup of $G$.

Then can we conclude that $1\times K$ is also a characteristic subgroup of $G$?

My motivation is the case where orders of $H$ and $K$ are relatively prime. In that case, both must be characteristic subgroups of $G$. So I wonder: if one of the components is characteristic in $G$ then is the other, too?

• strictly speaking that $=$ should be $\cong$ – janmarqz Dec 29 '14 at 19:26
• @janmarqz: I mean exactly the group $H\times K$ by saying $G$, why should I use $\cong$ ? – mesel Dec 29 '14 at 19:29
• how is $H<H\times K$? – janmarqz Dec 29 '14 at 19:31
• @janmarqz: ok, I edited. – mesel Dec 29 '14 at 19:33

For example in $C_2 \times S_n$ ($n \geq 3$) the $C_2$ factor is characteristic because it is the center, but the $S_n$ factor is not characteristic: consider the automorphism $(x, \sigma) \mapsto (x \operatorname{sgn}(\sigma), \sigma)$.


text:
## A polyhedral branch-and-cut approach to global optimization.(English)Zbl 1099.90047

Summary: A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software.
In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited.
Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.

### MSC:

 90C26 Nonconvex programming, global optimization 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

BARON; MINLP
Full Text:

### References:

 [1] Audet, C., Hansen, P., Jaumard, B., Savard, G. : A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Prog. 87, 131–152 (2000) · Zbl 0966.90057 [2] Avriel, M., Diewert, W.E., Schaible, S., Zang, I.: Generalized Concavity. Plenum Press, 1988 [3] Böröczky K.Jr., Reitzner,M.: Approximation of smooth convex bodies by random circumscribed polytopes. Annals of Applied Probability 14, 239–273 (2004) · Zbl 1049.60009 [4] Bussieck, M.R.: MINLP World. http://www.gamsworld.org/minlp/index.htm 2002 [5] Chinneck, J.W.: Discovering the characteristics of mathematical programming via sampling. Optimization Methods and Software 17, 319–352 (2002) · Zbl 1038.90074 [6] Duran, M.A., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Prog. 36, 307–339 (1986) · Zbl 0619.90052 [7] Fourer, R., Moré, J., Munson, T., Sarich, J.: Next-generation servers for optimization as an internet resource. Available at http://iems.nwu.edu/$$\sim$$4er 2004 [8] Griewank, A.: Evaluating derivatives. Principles and Techniques of Algorithmic Differentiation, vol 19 of Frontiers in Applied Mathematics. SIAM, Philadelphia, PA, 2000 · Zbl 0958.65028 [9] Griffith, R.E., Stewart, R.A.: A nonlinear programming technique for the optimization of continuous processing systems. Management Science 7, 379–392 (1961) · Zbl 0995.90610 [10] Gruber, P.M.: Asymptotic estimates for best and stepwise approximation of convex bodies II. Forum Mathematicum 5, 521–538 (1993) · Zbl 0788.41020 [11] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer-Verlag, Berlin, 1993 [12] Kelley, J.E.: The cutting plane method for solving convex programs. Journal of the SIAM 8, 703–712 (1960) · Zbl 0098.12104 [13] Maheshwari, C., Neumaier, A., Schichl, H.: Convexity and concavity detection. Available at http://www.mat.univie.ac.at/$$\sim$$herman/techreports/D12convconc.ps 2003 · Zbl 1243.90004 [14] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math. Prog. 10, 147–175 (1976) · Zbl 0349.90100 [15] Meeraus, A.: GLOBAL World. http://www.gamsworld.org/global/index.htm 2002 [16] Nowak, I.: Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Habilitation thesis Humboldt-Universität zu Berlin, Germany, 2004 [17] Rote, G.: The convergence rate of the sandwich algorithm for approximating convex functions. Computing 48, 337–361 (1992) · Zbl 0787.65006 [18] Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel techniques for constructing convex envelopes of nonlinear functions. Journal of Global Optimization 20, 137–158 (2001) · Zbl 1001.90064 [19] Tawarmalani, M., Sahinidis, N.V.: Convex extensions and convex envelopes of l.s.c. functions. Mathematical Programming 93, 247–263 (2002) · Zbl 1065.90062 [20] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht, 2002 · Zbl 1031.90022 [21] Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Prog. 99, 563–591 (2004) · Zbl 1062.90041 [22] Vandenbussche, D.: Polyhedral Approaches to Solving Nonconvex Quadratic Programs. PhD thesis, Georgia Institute of Technology, Department of Indystrial and Systems Engineering, Atlanta, GA, 2003 [23] Zamora, J.M., Grossmann, I.E.: A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits. Computers & Chemical Engineering 22, 367–384 (1998) [24] Zamora, J.M., Grossmann, I.E.: A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. Journal of Global Optimization 14, 217–249 (1999) · Zbl 0949.90097
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
Still have questions? Join our Discord server and get real time help.
-1

# What is wrong with this script?

Please make your question title relevant to your question content. It should be a one-sentence summary in question form.

I got my answer from putting music in each decal slides or the ones that needs it. But the one problem is that it has an error to the script. This is the script and error:

local bin = script.Parent
local decal = bin.Decal
local sound = Instance.new("Sound", bin) -- Creates a sound object to play assets

local MainSlides = {
{'http://www.roblox.com/asset/?id=213163470', 189421358, 15},
{'http://www.roblox.com/asset/?id=213486920', nil, 3},
{'http://www.roblox.com/asset/?id=157656296', nil, 3},
{'http://www.roblox.com/asset/?id=213486967', nil, 3},
{'http://www.roblox.com/asset/?id=151111211', 160442087, 3},
{'http://www.roblox.com/asset/?id=213487020', nil, 3}
-- You can add sounds where you want, just make sure they are in the correct index of the table.
-- If you do not want a sound on the slide, put nil where the asset ID would go.
}

function getNumTabs(tab)
local num = 0
for i,v in pairs(tab) do num = num + 1 end
return num
end

function runTable(tab)
for i = 1,getNumTabs(tab) do
local currentTab = tab[tostring(i)]

if currentTab[2] ~= nil then  -- If there is an asset ID given then
sound.SoundId = currentTab[2] -- Load asset ID into sound
sound:Play() -- Play the sound
end

decal.Texture = currentTab[1]
wait(currentTab[3])
sound:Pause() -- Pauses the sound
end
end

local c = game.Workspace.Countdown.SurfaceGui.TextLabel

function countDown()
for timeLeft = 20, 0, -1 do
c.Text = timeLeft
wait(1)
end
c.Text = "Movie has started!"
end

while true do
countDown()
runTable(MainSlides)
end

Error:

00:09:23.912 - Workspace.Part.SlideScript:358: attempt to index local 'currentTab' (a nil value)

Thank you!

1
BlueTaslem 17922
5 years ago

MainSlides is a list. That means the indices are 1, 2, 3, ....

The indices are not the text "1", "2", "3", ....

In other words, there is no reason to use tostring on line 24 -- you want the number i, so use just i.

Similarly, since MainSlides is a list, getNumTabs(MainSlides) will just be the length of MainSlides, or #MainSlides.

for i = 1, #tab do
local currentTab = tab[i]

Usually, it's better to use ipairs than direction iteration like this:

for _, currentTab in ipairs(tab) do
if currentTab[2] ~= then
....

0
Thanks bro. User#5689 0 — 5y


text:
# Tangent bundles of hyperbolic spaces and proper affine actions on $L^p$ spaces

Abstract : We define the notion of a negatively curved tangent bundle of a metric measured space. We prove that, when a group $G$ acts on a metric measured space $X$ with a negatively curved tangent bundle, then $G$ acts on some $L^p$ space, and that this action is proper under suitable assumptions. We then check that this result applies to the case when $X$ is a CAT(-1) space or a quasi-tree.
Type de document :
Pré-publication, Document de travail
IF_PREPUB. 2019

https://hal.archives-ouvertes.fr/hal-02006189
Contributeur : Thomas Haettel <>
Soumis le : lundi 4 février 2019 - 14:36:33
Dernière modification le : jeudi 14 février 2019 - 01:26:18

### Identifiants

• HAL Id : hal-02006189, version 1
• ARXIV : 1901.07462

### Citation

Indira Chatterji, François Dahmani, Thomas Haettel, Jean Lecureux. Tangent bundles of hyperbolic spaces and proper affine actions on $L^p$ spaces. IF_PREPUB. 2019. 〈hal-02006189〉

### Métriques

Consultations de la notice


text:
Czekaj...Wczytywanie... Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

• Skala szarości
• Wysoki kontrast
• Negatyw
• Reset

Aktualności — Wydarzenia

North Atlantic Noncommutative Geometry Seminar

THE CONTRAVARIANT FUNCTORIALITY OF GRAPH ALGEBRAS

Prelegent: MARIUSZ TOBOLSKI

2022-12-21 17:15

We introduce a subcategory of directed graphs for which the construction of Leavitt path algebras induces a contravariant functor into the category of algebras. Then we prove a theorem stating under which conditions this functor turns pushouts of directed graphs into pullbacks of algebras. Finally, using the result of A. Chirvasitu concerning the passage from pullbacks of Leavitt path algebras to the pullbacks of their completions, we conclude the same-type theorem for graph C*-algebras. (Based on joint work with P. M. Hajac.)


text:
## College Algebra (6th Edition)

$x=-8$
$\dfrac{3}{x+3}=\dfrac{5}{2x+6}+\dfrac{1}{x-2}$ Take out common factor $2$ from the denominator of the first fraction on the right side: $\dfrac{3}{x+3}=\dfrac{5}{2(x+3)}+\dfrac{1}{x-2}$ Multiply the whole equation by $2(x+3)(x-2)$: $2(x+3)(x-2)\Big[\dfrac{3}{x+3}=\dfrac{5}{2(x+3)}+\dfrac{1}{x-2}\Big]$ $(2)(x-2)(3)=(5)(x-2)+(2)(x+3)$ $6x-12=5x-10+2x+6$ Take all terms with $x$ to the left side and all terms without $x$ to the right side and solve for $x$: $6x-5x-2x=-10+6+12$ $-x=8$ $x=-8$


text:
# Examples of compact Kähler manifolds with $H^2(X,\mathbb Z)\cap H^{1,1}(X)=0$

As we know, Kodaira's embedding theorem can be put as:

A compact Kähler manifold $$X$$ is projective if and only if $$\mathcal K_X\cap H^2(X,\mathbb Z)\neq\emptyset$$.

Where $$\mathcal K_X$$ denotes the Kähler cone of $$X$$.
So if we have $$H^{1,1}(X)\cap H^2(X,\mathbb Z)=0$$, we can make the conclusion that $$X$$ is not projective. And my question is:
Is there indeed exist any compact Kähler manifolds which satisfies $$H^{1,1}(X)\cap H^2(X,\mathbb Z)=0$$? To seek for such examples we should first limit ourselves to non-projective Kähler manifolds, for example, in dimension 2, we have K3 surfaces and complex tori, we know they have $$h^{1,1}>0$$, and I don't know whether part of them satisfy $$H^{1,1}(X)\cap H^2(X,\mathbb Z)=0$$. So can anybody provide some examples? Any dimension is ok. Any comments are welcome, thanks!

• As you guessed, some Tori have this property. Sep 18 '20 at 9:35

For some constructions of non-projective Kähler manifolds, check this MO question: https://mathoverflow.net/questions/257147/are-most-k%C3%A4hler-manifolds-non-projective

and the following article: https://encyclopediaofmath.org/wiki/K%C3%A4hler_manifold

I quote the second article: For example, this is the case for the torus $$\mathbb{C}^2/\Gamma$$, where $$\Gamma$$ is the lattice spanned by the vectors $$(1,0), (0,1), (−\sqrt 2,−\sqrt 3), (−\sqrt 5,−\sqrt 7)$$.

• Isn't these 4 vectors linear dependent?
– Tom
Sep 18 '20 at 13:58
• The vectors need not be linearly independent. You just need $4$ distinct points, so that you can generate a free abelian discrete subgroup of $\mathbb{C}^2$. You can find more on this construction in Huybrechts' Complex Geometry, pages 57-58. Sep 18 '20 at 15:06
• You mean any 4 distinct points may work? for example $(1,0), (0,1), (2,0), (0,2)$?
– Tom
Sep 18 '20 at 15:48
• No, those don't work. You are right. The points need to be $\mathbb{R}$-linearly independent. Sep 18 '20 at 15:53
• Could you elaborate a bit why it satisfies $H^{1,1}(X)\cap H^2(X,\mathbb Z)=0$?
– Tom
Sep 18 '20 at 16:20


text:
## Fixing Personal Finance with Behavioral Economics

August 2nd, 2016

We’re awful at personal finance.

It’s not because we're dumb — it’s just that personal finance is a minefield of cognitive biases.

Consider almost any cognitive bias: procrastination, planning fallacy, confirmation bias, affective forecasting errors, endowment effects, sunk costs, or hyperbolic discounting. Each of these biases leads to poor decisions that impede our financial goals.

Despite the proliferation of cognitive biases in such an important domain, most personal finance apps don't even attempt to help us make better decisions. Today's utilitarian banking tools merely replicate first-order IVR-style transactions of the 1970s (e.g., view account balance, transfer money, pay a bill).

A next generation personal finance app — let's call it a Behaviorally Intelligent Advisor (BIA) — could leverage insights from behavioral science to nudge us to make decisions that serve our goals. To this end, I've sketched some early thinking on how one might design a BIA with behavioral science in mind.

1) Reframe Transactions (and Kill the Ledger)

Unless you have cash flow concerns, the time-based ledger is generally an irrelevant lens on personal finance. A BIA should automatically lump and split transactions to help us think about our money in ways that maximize hedonic value. Prospect theory and mental accounting, which I wrote about in a previous article, inform how a BIA might display financial transactions:

• Separate gains. We can maximize the hedonic impact of gains by spreading them across separate temporal instances. For example, receiving two bundles of $1,000 is better than one bundle of$2,000.
• Combine losses. A BIA should minimize the pain of losses by aggregating expenses into a single episode. For example, we'd rather pay $10 in bank fees all at once than pay$1 in bank fees ten separate times.
• Combine small losses with large gains. The interaction of loss aversion (i.e., losses loom larger than gains) with diminishing sensitivity for gains (i.e., $10 is significantly better than$5, but $105 isn't that much better than$100) suggests that we can maximize hedonic utility by combining smaller losses with larger gains. For example, a BIA might automatically lump your paycheck income of $2,250 and transit expenses of -$100 into a single episode of $2,150. While the resulting income of$2,150 is slightly worse than $2,250, you avoid the pain of an independent -$100 transit expense loss episode. In a similar vein, a BIA might amortize costs over the span of consumption to maximize hedonic value. For example, depending on the flow of income and expenses, it might make sense to represent a mortgage payment as a series of small daily payments instead of a monthly lump sum. This reorganization might minimize the perception of losses, especially if the small mortgage payments are netted against a larger daily gain (i.e., a paycheck similarly amortized over the pay period).
• Separate small gains from large losses. The value function for gains is concave and steepest near the origin, so a BIA could maximize hedonic value by segregating small gains from large losses. Consider the intuition: if you win $150 at a casino, you don't want to mentally integrate that win with your$5,000 credit card debt. We feel better about a small gain of $150 and a seemingly unrelated loss of -$5,000 from a different mental account than a single integrated loss of -$4,850. A BIA could integrate and split transactions to maximize the emotional perception of our finances. 2) Set and Frame Goals Labeling our money allows us to control how we allocate our resources, which is particularly important to achieve our goals. Many of us have set of goals (e.g., take a vacation in late September, buy a new refrigerator, and save for a deposit on a car in 6-9 months), but our savings accounts merely represent broad pools of money (e.g.,$12,521 in savings) that are untethered to those goals.

A BIA should help us create goal-based, partitioned financial accounts that reflect important goals. For example, you might have several goal-oriented pools of money, such as a vacation savings fund (e.g., goal to save $5,000 by September 15th), a refrigerator savings fund (e.g., goal to save$1,000 by end of year), and a new car fund (e.g., goal to save $4,000 by February 1st of next year). You might also want an emergency savings fund and a “fun money” fund. The BIA should solicit your goals and help you decide what you need. Several behavioral tactics might enhance a goal-based account architecture: • Goal acceleration. We exert more effort as we approach goal completion (i.e., the goal gradient effect). Creating an illusion of progress can spur us to achieve our goals more quickly. You've likely seen the instantiation of this effect with loyalty cards. Instead of giving patrons a 10-hole punch loyalty card, many restaurants offer a 12-hole punch card initialized with two punches. When we start with two punches toward our 12-hole goal, we return to the restaurant more frequently than we do with the 10-hole punch loyalty card. Instead of framing a financial target based on existing progress (e.g., a goal of saving$4,000 for vacation because you’ve already saved $1,000), a BIA might pre-initialize certain goals with existing funds to create the perception that you've already made progress (e.g., you're already$1,000 into your $5,000 vacation goal). • Goal chunking. In a similar vein, a BIA could compute the plausibility of achieving each goal given historical financial patterns and intelligently chunk goals into smaller and more achievable subgoals. For example, a BIA might break a$2,500 savings goal into segments of $750,$1,250, and $500. This tactic yields a second benefit: non-linearity likely yields more engagement than the traditional linear (i.e., boring) savings behavior. • Goal salience. Increasing the identifiability or salience of goals can help fight procrastination. For example, seeing a photo of your daughter will likely encourage you to allocate more savings for her college tuition. • Social pressure. Many people respond to social cues, and a BIA could leverage the multitude of social motivational mechanisms to encourage goal-directed behavior. Competitions among family, friends, or other small social group may encourage progress. A BIA might also leverage social norms to enhance motivation. For example, if a BIA conveyed that 82% of people in your income range have an emergency fund of at least$5,000, you might be more likely to adopt and make progress toward that objective.
• Consistency. We generally prefer to act consistently with our prior behavior. A BIA might surface our previous actions to nudge us toward normatively desirable behavior (e.g., “Last year you allocated 75% of your tax refund to your retirement plan. Would you like to do that again?”).

3) Enable Better Decision Making

It often takes hundreds of individual decisions to make progress against a meaty financial goal. A BIA should systematically counteract the cognitive biases that would otherwise lead us astray. Behavioral science offers a broad toolkit that a BIA could use to improve decision making:

• Precommitment. Since income is typically cyclical, a BIA might analyze progress toward each goal and ask us to precommit to a specific allocation for our next paycheck (e.g., “You’re slightly behind your retirement goal. Do you want to allocate $500 from your next paycheck to your retirement account?”). • Active choice. In addition to nudging us toward action, prompting active tradeoffs can also mitigate reactance by reminding us of our own autonomy. For example, instead of asking whether you want to allocate$500 into a retirement fund, a BIA might suggest two options: a) allocate $500 into a retirement fund, or b)$400 into a retirement fund and $100 into a “rainy day” fund. This encourages you to make a decision by presenting you with multiple options, and also reminds you that you are in control. • Concreteness. A BIA should help us understand the concrete tradeoffs of each option, especially among options defined by factors that are difficult to compute, such as compounding interest. A BIA could leverage multiple techniques, such as concreteness and loss aversion (e.g., “I see that you don't want to make any payments on your credit card this month. If you pay your credit card in full next month, you will pay an extra$40 in interest. If you keep delaying your credit card payments for another year, you will pay an extra $500 in interest.”). Likewise, a BIA could point out that a$500 deposit into a retirement account today could grow to $2,000-$3,000 in 25 years. A BIA might also help counteract the overoptimism bias by accurately representing progress against goals in concrete terms. For example, a BIA might compute a retirement readiness age equivalent (e.g., your target retirement age is 55, but given your finances, your “real” retirement age is 62).
• Smart defaults. A BIA should employ a default configuration that reflects normative financial preferences, such as automatically paying off high interest accounts before allocating income to savings.
• Strategic anchoring. A BIA could use certain behavioral biases, such as anchoring, to counteract others, such as procrastination. For example, a BIA might ask you “How much do you want to save for retirement?” before prompting you to decide how much of your paycheck you want to allocate to that goal.
• Prepayment. Decoupling the pleasure of consumption from the pain of paying increases the hedonic value of experiences. As a result, when we pay up front, we can control consumption and enjoy our experiences more. For example, a BIA could help you budget and prepay (ideally months in advance) for the helicopter ride you've been dreaming of so that you're not thinking about costs while you're enjoying the experience.
• Cooling off periods. Unexpected income, such as a large bonus, can erode self-control and cause risk-seeking behavior (i.e., the house money effect). A BIA could help us avoid impulsive behavior by instituting cooling off periods that limit use of unexpected funds for a fixed period of time.

Thoughtfully crafting a BIA in the personal finance arena is challenging for a variety of reasons, including regulation that may make it difficult to implement some of these concepts. Nevertheless, it's a useful thought exercise that may spark additional thinking on how we can help consumers make better choices in an important domain.

## Wrinkle Free vs. Iron Free

July 2nd, 2016

There are multiple ways to position a product. Marketers often highlight product features, such as "wrinkle free." However, we know that it's often best to address specific consumer pain points, such as "iron free."

It is clear from Google Trends that the pain point solution "iron free" dominates searches, and its cyclicality likely reflects actual consumer need. This makes sense; consumers have needs and seek solutions for our needs more than we seek specific features, which are merely instrumental.

We would assume that the market positions products in response to consumer needs. However, a brief Amazon search found over 1 million results for "wrinkle free" (i.e., the product feature), but fewer than 5,000 results for "iron free" (i.e., the consumer pain point).

While consumers search for "iron free" 8-30 times more often than "wrinkle free," products matching "wrinkle free" are 250 times more common on Amazon. Features are nice, but pain point solvers are powerful. This is a simple example - one of many, I imagine - where the market isn't using language that reflects consumer demand.

## When Sunk Costs Make us Happier

April 4th, 2016

Sunk costs are non-recoverable investments of time or money. Since sunk costs were already spent (i.e., we can't re-spend the $100 that we already spent on non-refundable soccer tickets), it’s irrational to include them in our decision making. The fact that we spent$100 on soccer tickets should not influence whether we subsequently attend the game; we spent $100 regardless of our future choice. However, we frequently make decisions based on sunk costs; we decide to attend the cold and rainy soccer game even though we’d prefer to watch it from the comfort of our home, simply because we feel attached to the$100 we already spent. This error is called the sunk cost fallacy.

While sunk costs often lead to bad decisions (e.g., over-investing in a dead end project, a failing relationship, or a boring book), we can harness this bias for good. A few obvious examples come to mind:

Gym: Even though the gym membership is a sunk cost, some people visit the gym more frequently in order to lower the effective unit cost. While using the gym more often “because I paid for it” is irrational, this sunk cost-based thinking likely leads to a positive outcome.

Attire: After investing in an expensive clothing article, such as a tuxedo, tailored suit, or a designer purse, we often look for occasions where we can make the most of our purchase. Perhaps we attend more parties, meet new people, feel more confident, or receive more compliments as a result. There’s little harm in falling prey to the sunk cost fallacy in this way.

Vacation Properties: Once we spend money on a timeshare or a vacation home, we may feel a need to vacation more in an attempt to make the most of our investment. Given that most vacation days go unused, the sunk cost fallacy might nudge us in a normatively positive direction.

Our biases around sunk costs suggest a general strategy in which we should make investments in domains that lead us to behaviors that we normatively prefer. By tapping into our deep tendency to feel drawn to sunk costs, we can potentially harness our biases to help achieve our goals.

## Do Booger Jelly Beans Maximize Utility?

March 27th, 2016

In general, we try to make decisions that we think will maximize our expected utility. Typically, we conceptualize expected utility as a property resulting from the product we buy - i.e., we buy chocolate cake because it tastes good.

So why do people buy booger flavored Jelly Beans?

To answer this question, we have to revisit how we think about utility. In addition to the utility of a product, we might also derive utility from the process of buying a product. In other words, we buy booger flavored Jelly Beans not because they taste good, but because they are fun to buy.

In fact, there’s a class of products that offer little utility themselves, but from which we derive some utility through the process of buying. It’s also likely that the fleeting utility we experience in the process of buying these products leads us to mispredict the utility we’ll subsequently experience when we consume or use the product. I’d bet that after a few bites of booger Jelly Beans, the rest will end up in the pantry for months before they’re finally discarded.

The gap between these two forms of utility means that at least some of the products we enjoy buying the most are also the ones we’re most likely to regret. Buyer beware!

## Using the Standard Gamble to Make Difficult Tradeoffs in Health Decisions

March 6th, 2016

All choices involve tradeoffs. Nowhere is this more evident than in the realm of medical decision making, where we sometimes face tradeoffs that require us to value a specific health outcome or capability.

For example, you might decide whether to start a course of treatment for low back pain that has some probability of alleviating your symptoms, but will be accompanied by potential side effects, such as weight gain or nausea. These are difficult tradeoffs, especially since we often have little prior experience to aid us in weighing each factor. While we often know our favorite foods - i.e., we know the relative utility of different options for situations we encounter frequently - we have trouble assigning utilities and making decisions about our desired health outcomes when we've never had to make such tradeoffs in the past.

Economists often assess individual utilities through a method called the standard gamble, which we can derive from expected utility theory. In a standard gamble, we present an individual with a simplified choice between (1) a known health state, such the continuation of low back pain, and (2) a treatment option that has some probability of a better outcome and a worse outcome. For simplicity, we often designate the treatment option as a probability of a permanent cure vs. a probability of guaranteed death.

Here's an example from a recent experiment I ran: "Imagine that today you have been diagnosed with a disease that will lead to total vision blindness in both eyes with 100% certainty. There is a drug that you can take that will prevent your blindness with 100% certainty. However, the drug comes with a risk of immediate death. You can decide whether to take the drug. If you don't take it, you will definitely lose your vision in the next month. If take it, you will not become blind, but there is some risk that you will immediately die. What is the largest risk of death that you would accept in order to take the drug?"

The logic is simple: the risk of death that you'd accept is equal to the utility of vision.

$Let:$

$p(d) = probability\ of\ death$
$u(d) = utility\ of\ death = 0$
$u(v) = utility\ of\ living\ with\ vision = 1$
$u(n) = utility\ of\ living\ without\ vision$

$p(d) * u(d) + (1-p(d))*u(v) = u(n)$
$p(d) * 0 + (1-p(d))*1 = u(n)$
$1-p(d) = u(n)$

The standard gamble is a useful method to determine the utility of various health states and can aid individuals in making difficult decisions. Like all methods, the standard gamble suffers from several pitfalls, which we'll explore in the future.


text:
# Linear momentum/kinetic energy

1. Mar 22, 2006

### mb85

A certain radioactive (parent) nucleus transforms to a different (daughter) nucleus by emitting an electron and a neutrino. The parent was at rest at the origin of an xy coordinate system. The electron moves away from the origin with linear momentum (-3.3 x 10-22 kg m/s) ; the neutrino moves away from the origin with linear momentum (-2.2 x 10-23 kg m/s) . What are (a) the magnitude and (b) angle (from the +x axis) of the linear momentum of the daughter nucleus? (c) If the daughter nucleus has a mass of 1.8 x 10-26 kg, what is its kinetic energy?

i know part a and b i did are correct:
part a. i got 3.3x10^-22 kg m/s
part b the angle is 3.81 degrees

but i cant figure out part c? what formula am i supposed to use.

2. Mar 22, 2006

### neutrino

Do you know how to write down the kinectic energy of a particle in terms of its momentum?

3. Mar 22, 2006

### mb85

p = mv?

the KE = (m -mi)V^2

?

4. Mar 22, 2006

### neutrino

K.E = 1/2 mv^2 . Multiply and divide RHS by m. K.E = (mv)^2/2m

5. Mar 22, 2006

### mb85

what is RHS?
K.E = (mv)^2/2m
i get 9.8x10-70....but that doesnt look right.

6. Mar 22, 2006

### Libertine

Right hand side.

You start with $$K.E. = \frac{1}{2}mv^2$$

Then multiply both sides by m, but to keep them the same you must divide by m, i.e.:
$$K.E. = \frac{1}{2}mv^2 . \frac{m}{m}$$
$$K.E. = \frac{m^2 v^2}{2m}$$
$$K.E. = \frac{(mv)^2}{2m}$$
Then use the fact that $$p = mv$$ to get:
$$K.E. = \frac{p^2}{2m}$$

Can you use that formula to get the answer?

7. Mar 22, 2006

### mb85

thanks. i got it now.