text:
# Biblatex-apa not replacing ampersand for citations and references with Spanish options

I have read that the spanish-apa.lbx file contains the command \setcounter{smartand}{0} to prevent the ampersand from showing up and uses y instead. However, I can't seem to manage to get this right when using \parencite, or actually any other citation for more than one author while using the Spanish biblatex-apa style.

MWE:

\documentclass{article}
\usepackage[english,spanish]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[style=apa,backend=biber]{biblatex}
\DeclareLanguageMapping{spanish}{spanish-apa}
\usepackage{csquotes}

\begin{filecontents}{refs.bib}
@book{Guy2010,
Author = {Some Guy and Another Dude},
Publisher = {A Publisher},
Title = {A reference book to everything},
Year = {2010}
}
\end{filecontents}

\addbibresource{refs.bib}

\begin{document}
Localisation is a headache. \parencite{Guy2010}
\printbibliography
\end{document}

The Spanish lbx file is up to date, and everything in general works as expected.

edit:

I followed the instructions given below (refer to Alan Munn's answer) but it turns out I was doing in the wrong place. After I created the proper local texmf structure to host the renewed file where it should be, everything is working as expected. Thank you very much for the expertise!

• Welcome to TeX.sx and thanks for adding a nice minimal example. What happens if you add \setcounter{smartand}{0} after the \DeclareLanguageMapping{spanish-apa} declaration? – Alan Munn Jul 5 '15 at 1:16
• Nothing changes, no matter where I place it. – absay Jul 5 '15 at 1:23
• Ok, but actually the setting that spanish-apa.lbx uses is 0 which means all 'y' and 'e' get replaced by '&'. So this is the expected behaviour. Do you want to get 'y' and 'e' instead? – Alan Munn Jul 5 '15 at 1:32

## 2 Answers

The default setting for the spanish-apa style is that all 'and' gets replaced by &, i.e., it will not be realized as 'y' or 'e'.

For reasons I don't quite understand, changing the value of the counter anywhere has no effect. I think this is due to the following description in the biblatex documentation about how localization files are loaded:

All localization modules are loaded on demand in the document body.

So if I make a local copy of spanish-apa.lbx and comment out the \setcounter{smartand}{0} line, I can then change the value of the counter in the preamble and things work as expected (0= always '&', 1= 'y' or 'e' depending on context, 2=always 'y', 3=always 'e').

## Simple solution

The simple solution in Ulrike's answer is probably the easiest to implement:

\begin{document}
\setcounter{smartand}{1}
\selectlanguage{spanish}

## More permanent solution

So for the moment (unless someone can explain how to overcome the behaviour) you will need to make a local copy of spanish-apa.lbx with the \setcounter line commented out and then set the value of smartand yourself in the preamble.

To make a local copy of the .lbx file, it's preferable to rename it to something else so that you remain aware that you are using a modified copy of it. The copied file should reside either in the same folder as your .tex file (if you are only doing this once), or in your local texmf folder, inside texmf/tex/latex/biblatex. Then instead of loading spanish-apa you load your renamed copy. Here's an example of what your document would look like. I've named the local copy smartand-spanish-apa.

\documentclass{article}
\usepackage[english,spanish]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[style=apa,backend=biber]{biblatex}

\DeclareLanguageMapping{spanish}{smartand-spanish-apa}
\setcounter{smartand}{3} % 0, 1, 2 or 3

\usepackage{csquotes}

\begin{filecontents}{\jobname.bib}
@book{Guy2010,
Author = {Some Guy and Another Dude},
Publisher = {A Publisher},
Title = {A reference book to everything},
Year = {2010}
}
\end{filecontents}

\addbibresource{\jobname.bib}

\begin{document}

Localisation is a headache. \parencite{Guy2010}
\printbibliography
\end{document}

• Thank you. Unfortunately, while setting the value to 1, 2 or 3 works for the citation, the reference is duplicating the surname of the last author. – absay Jul 5 '15 at 1:56
• Yes, I got that once, but can't reproduce it. Try deleting all your aux files and recompiling. – Alan Munn Jul 5 '15 at 2:06
• Done. Problem persists on my end. – absay Jul 5 '15 at 2:17
• @absay Strange. I have changed the counter to all the values and it works fine. – Alan Munn Jul 5 '15 at 2:24
• Sorry for the question but when you say "make a local copy" you mean I have to copy the contents of spanish-apa.lbx into the preamble of my tex file? – absay Jul 5 '15 at 2:31

The smartand value is used in spanish.lbx which is loaded by spanish-apa.lbx. So you don't have a chance to change it. But you can do this:

\documentclass{article}
\usepackage[english,spanish]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[style=apa,backend=biber]{biblatex}
\DeclareLanguageMapping{spanish}{spanish-apa}
%reactivate smartand:
\makeatletter
\DefineBibliographyExtras{spanish}
{\setcounter{smartand}{1}% or some other value
\let\lbx@finalnamedelim=\lbx@es@smartand
\let\lbx@finallistdelim=\lbx@es@smartand}
\makeatother
\usepackage{csquotes}

\begin{filecontents}{refs.bib}
@book{Guy2010,
Author = {Some Guy and Another Dude},
Publisher = {A Publisher},
Title = {A reference book to everything},
Year = {2010}
}
\end{filecontents}

\addbibresource{refs.bib}

\begin{document}
Localisation is a headache. \parencite{Guy2010}
\printbibliography
\end{document}

## Edit

An alternative is to change the value after the begin of the document and trigger the reevaluation of the language settings:

\begin{document}
\setcounter{smartand}{1}
\selectlanguage{spanish}


text:
| English | 简体中文 |

# 48. Rotate Image

## Description

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

format: plain


text:
Guide to Understanding Generics in Java - Stack Abuse

# Guide to Understanding Generics in Java

### Introduction

Java is a type-safe programming language. Type safety ensures a layer of validity and robustness in a programming language. It is a key part of Java's security to ensure that operations done on an object are only performed if the type of the object supports it.

Type safety dramatically reduces the number of programming errors that might occur during runtime, involving all kinds of errors linked to type mismatches. Instead, these types of errors are caught during compile-time which is much better than catching errors during runtime, allowing developers to have less unexpected and unplanned trips to the good old debugger.

Type safety is also interchangeably called strong typing.

Java Generics is a solution designed to reinforce the type safety that Java was designed to have. Generics allow types to be parameterized onto methods and classes and introduces a new layer of abstraction for formal parameters. This will be explained in detail later on.

There are many advantages of using generics in Java. Implementing generics into your code can greatly improve its overall quality by preventing unprecedented runtime errors involving data types and typecasting.

This guide will demonstrate the declaration, implementation, use-cases, and benefits of generics in Java.

### Why Use Generics?

To provide context as to how generics reinforce strong typing and prevents runtime errors involving typecasting, let's take a look at a code snippet.

Let's say you want to store a bunch of String variables in a list. Coding this without using generics would look like this:

List stringList = new ArrayList();

This code won't trigger any compile-time errors but most IDEs will warn you that the List that you've initialized is of a raw type and should be parameterized with a generic.

IDE-s warn you of problems that can occur if you don't parameterize a list with a type. One is being able to add elements of any data type to the list. Lists will, by default, accept any Object type, which includes every single one of its subtypes:

List stringList = new ArrayList();

Adding two or more different types within the same collection violates the rules of type safety. This code will successfully compile but this definitely will cause a multitude of problems.

For example, what happens if we try to loop through the list? Let's use an enhanced for loop:

for (String string : stringList) {
System.out.println(string);
}

We'll be greeted with a:

Main.java:9: error: incompatible types: Object cannot be converted to String
for (String string : stringList) {

In fact, this isn't because we've put a String and Integer together. If we changed the example around and added two Strings:

List stringList = new ArrayList();

for (String string : stringList) {
System.out.println(string);
}

We'd still be greeted with:

Main.java:9: error: incompatible types: Object cannot be converted to String
for (String string : stringList) {

This is because without any parametrization, the List only deals with Objects. You can technically circumvent this by using an Object in the enhanced for-loop:

List stringList = new ArrayList();

for (Object object : stringList) {
System.out.println(object);
}

Which would print out:

Apple
1

However, this is very much against intuition and isn't a real fix. This is just avoiding the underlying design problem in an unsustainable way.

Another problem is the need to typecast whenever you access and assign elements within a list without generics. To assign new reference variables to the elements of the list, we must typecast them, since the get() method returns Objects:

String str = (String) stringList.get(0);
Integer num = (Integer) stringList.get(1);

In this case, how will you be able to determine the type of each element during runtime, so you know which type to cast it to? There aren't many options and the ones at your disposal complicate things way out of proportion, like using try/catch blocks to try and cast elements into some predefined types.

Also, if you fail to cast the list element during assignment, it will display an error like this:

Type mismatch: cannot convert from Object to Integer

In OOP, explicit casting should be avoided as much as possible because it isn't a reliable solution for OOP-related problems.

Lastly, because the List class is a subtype of Collection, it should have access to iterators using the Iterator object, the iterator() method, and for-each loops. If a collection is declared without generics, then you definitely won't be able to use any of these iterators, in a reasonable manner.

This is why Java Generics came to be, and why they're an integral part of the Java ecosystem. Let's take a look at how to declare generic classes, and rewrite this example to utilize generics and avoid the issues we've just seen.

### Generic Classes and Objects

Let's declare a class with a generic type. To specify a parameter type on a class or an object, we use the angle bracket symbols <> beside its name and assign a type for it inside the brackets. The syntax of declaring a generic class looks like this:

public class Thing<T> {
private T val;

public Thing(T val) { this.val = val;}
public T getVal() { return this.val; }

public <T> void printVal(T val) {
System.out.println("Generic Type" + val.getClass().getName());
}
}

Note: Generic types can NOT be assigned primitive data types such as int, char, long, double, or float. If you want to assign these data types, then use their wrapper classes instead.

The letter T inside the angle brackets is called a type parameter. By convention, type parameters are single lettered (A-Z) and uppercase. Some other common type parameter names used are K (Key), V (Value), E (Element), and N (Number).

Although you can, in theory, assign any variable name to a type parameter that follows Java's variable conventions, it is with good reason to follow the typical type parameter convention to differentiate a normal variable from a type parameter.

The val is of a generic type. It can be a String, an Integer, or another object. Given the generic class Thing declared above, let's instantiate the class as a few different objects, of different types:

public void callThing() {
// Three implementations of the generic class Thing with 3 different data types
Thing<Integer> thing1 = new Thing<>(1);
Thing<String> thing2 = new Thing<>("String thing");
Thing<Double> thing3 = new Thing<>(3.5);

System.out.println(thing1.getVal() + " " + thing2.getVal() + " " + thing3.getVal());
}

Notice how we're not specifying the parameter type before the constructor calls. Java infers the type of the object during initialization so you won't need to retype it during the initialization. In this case, the type is already inferred from the variable declaration. This behavior is called type inference. If we inherited this class, in a class such as SubThing, we also wouldn't need to explicitly set the type when instantiating it as a Thing, since it'd infer the type from its parent class.

You can specify it in both places, but it's just redundant:

Thing<Integer> thing1 = new Thing<Integer>(1);
Thing<String> thing2 = new Thing<String>("String thing");
Thing<Double> thing3 = new Thing<Double>(3.5);

If we run the code, it'll result in:

1 String thing 3.5

Using generics allows type-safe abstraction without having to use typecasting which is much riskier in the long run.

In a similar vein, the List constructor accepts a generic type:

public interface List<E> extends Collection<E> {
// ...
}

In our previous examples, we haven't specified a type, resulting in the List being a List of Objects. Now, let's rewrite the example from before:

List<String> stringList = new ArrayList<>();

for (String string : stringList) {
System.out.println(string);
}

This results in:

Apple
Orange

Works like a charm! Again, we don't need to specify the type in the ArrayList() call, since it infers the type from the List<String> definition. The only case in which you'll have to specify the type after the constructor call is if you're taking advantage of the local variable type inference feature of Java 10+:

var stringList = new ArrayList<String>();

This time around, since we're using the var keyword, which isn't type-safe itself, the ArrayList<>() call can't infer the type, and it'll simply default to an Object type if we don't specify it ourselves.

### Generic Methods

Java supports method declarations with generic parameters and return types. Generic methods are declared exactly like normal methods but have the angle brackets notation before the return type.

Let's declare a simple generic method that accepts 3 parameters, appends them in a list, and return it:

public static <E> List<E> zipTogether(E element1, E element2, E element3) {
List<E> list = new ArrayList<>();
return list;
}

Now, we can run this as:

System.out.println(zipTogether(1, 2, 3));

Which results in:

[1, 2, 3]

But also, we can throw in other types:

System.out.println(zipTogether("Zeus", "Athens", "Hades"));

Which results in:

[Zeus, Athens, Hades]

Multiple types of parameters are also supported for objects and methods. If a method uses more than one type parameter, you can provide a list of all of them inside the diamond operator and separate each parameter using commas:

// Methods with void return types are also compatible with generic methods
public static <T, K, V> void printValues(T val1, K val2, V val3) {
System.out.println(val1 + " " + val2 + " " + val3);
}

Here, you can get creative with what you pass in. Following the conventions, we'll pass in a type, key and value:

printValues(new Thing("Employee"), 125, "David");

Which results in:

Thing{val=Employee} 125 David

Though, keep in mind that generic type parameters, that can be inferred, don't need to be declared in the generic declaration before the return type. To demonstrate, let's create another method that accepts 2 variables - a generic Map and a List that can exclusively containString values:

public <K, V> void sampleMethod(Map<K, V> map, List<String> lst) {
// ...
}

Here, the K and V generic types are mapped to the Map<K, V> since they're inferred types. On the other hand, since the List<String> can only accept strings, there's no need to add the generic type to the <K, V> list.

We've now covered generic classes, objects, and methods with one or more type parameters. What if we want to limit the extent of abstraction that a type parameter has? This limitation can be implemented using parameter binding.

### Bounded Type Parameters

Parameter Binding allows the type parameter to be limited to an object and its subclasses. This allows you to enforce certain classes and their subtypes, while still having the flexibility and abstraction of using generic type parameters.

## Git Essentials

Check out this hands-on, practical guide to learning Git, with best-practices and industry-accepted standards. Stop Googling Git commands and actually learn it!

To specify that a type parameter is bounded, we simply use the extends keyword on the type parameter - <N extends Number>. This makes sure that the type parameter N we supply to a class or method is of type Number.

Let's declare a class, called InvoiceDetail, which accepts a type parameter, and make sure that that type parameter is of type Number. This way, the generic types we can use while instantiating the class are limited to numbers and floating-point decimals, as Number is the superclass of all classes involving integers, including the wrapper classes and primitive data types:

class InvoiceDetail<N extends Number> {
private String invoiceName;
private N amount;
private N discount;

// Getters, setters, constructors...
}

Here, extends can mean two things - extends, in the case of classes, and implements in the case of interfaces. Since Number is an abstract class, it's used in the context of extending that class.

By extending the type parameter N as a Number subclass, the instantiation of amount and discount are now limited to Number and its subtypes. Trying to set them to any other type will trigger a compile-time error.

Let's try to erroneously assign String values, instead of a Number type:

InvoiceDetail<String> invoice = new InvoiceDetail<>("Invoice Name", "50.99", ".10");

Since String isn't a subtype of Number, the compiler catches that and triggers an error:

Bound mismatch: The type String is not a valid substitute for the bounded parameter <N extends Number> of the type InvoiceDetail<N>

This is a great example of how using generics enforces type-safety.

Additionally, a single type parameter can extend multiple classes and interfaces by using the & operator for the subsequently extended classes:

public class SampleClass<E extends T1 & T2 & T3> {
// ...
}

It's also worth noting that another great usage of bounded type parameters is in method declarations. For example, if you want to enforce that the types passed into a method conform to some interfaces, you can make sure that the type parameters extend a certain interface.

A classic example of this is enforcing that two types are Comparable, if you're comparing them in a method such as:

public static <T extends Comparable<T>> int compare(T t1, T t2) {
return t1.compareTo(t2);
}

Here, using generics, we enforce that t1 and t2 are both Comparable, and that they can genuinely be compared with the compareTo() method. Knowing that Strings are comparable, and override the compareTo() method, we can comfortably use them here:

System.out.println(compare("John", "Doe"));

The code results in:

6

However, if we tried using a non-Comparable type, such as Thing, which doesn't implement the Comparable interface:

System.out.println(compare(new Thing<String>("John"), new Thing<String>("Doe")));

Other than the IDE marking this line as erroneous, if we try running this code, it'll result in:

java: method compare in class Main cannot be applied to given types;
required: T,T
found:    Thing<java.lang.String>,Thing<java.lang.String>
reason: inference variable T has incompatible bounds
lower bounds: java.lang.Comparable<T>
lower bounds: Thing<java.lang.String>

In this case, since Comparable is an interface, the extends keyword actually enforces that the interface is implemented by T, not extended.

### Wildcards in Generics

Wildcards are used to symbolize any class type, and are denoted by ?. In general, you'll want to use wildcards when you have potential incompatibilities between different instantiations of a generic type. There are three types of wildcards: upper-bounded, lower-bounded and unbounded.

Choosing which approach you'll use is usually determined by the IN-OUT principle. The IN-OUT principle defines In-variables and Out-variables, which, in simpler terms, represent if a variable is used to provide data, or to serve in its output.

For example, a sendEmail(String body, String recipient) method has an In-variable body and Out-variable recipient. The body variable provides data on the body of the email you'd like to send, while the recipient variable provides the email address you'd like to send it to.

There are also mixed variables, which are used to both provide data, and then reference the result itself, in which case, you'll want to avoid using wildcards.

Generally speaking, you'll want to define In-variables with upper bounded wildcards, using the extends keyword and Out-variables with lower bounded wildcards, using the super keyword.

For In-variables that can be accessed through method of an object, you should prefer unbounded wildcards.

#### Upper-Bounded Wildcards

Upper-bound wildcards are used to provide a generic type that limits a variable to a class or an interface and all its subtypes. The name, upper-bounded refers to the fact that you bound the variable to an upper type - and all of it's subtypes.

In a sense, upper-bounded variables are more relaxed than lower-bounded variables, since they allow for more types. They're declared using the wildcard operator ? followed by the keyword extends and the supertype class or interface (the upper bound of their type):

<? extends SomeObject>

Here, extends, again, means extends classes and implements interfaces.

To recap, upper-bounded wildcards are typically used for objects that provide input to be consumed in-variables.

Note: There's a distinct difference between Class<Generic> and Class<? extends Generic>. The former allows only the Generic type to be used. In the latter, all subtypes of Generic are also valid.

Let's make an upper-type (Employee) and its subclass (Developer):

public abstract class Employee {
private int id;
private String name;
// Constructor, getters, setters
}

And:

public class Developer extends Employee {
private List<String> skillStack;

// Constructor, getters and setters

@Override
public String toString() {
return "Developer {" +
"\nskillStack=" + skillStack +
"\nname=" + super.getName() +
"\nid=" + super.getId() +
"\n}";
}
}

Now, let's make a simple printInfo() method, that accepts an upper-bounded list of Employee objects:

public static void printInfo(List<? extends Employee> employeeList) {
for (Employee e : employeeList) {
System.out.println(e.toString());
}
}

The List of employees we supply is upper-bounded to Employee, which means we can chuck in any Employee instance, as well as its subclasses, such as Developer:

List<Developer> devList = new ArrayList<>();

devList.add(new Developer(15, "David", new ArrayList<String>(List.of("Java", "Spring"))));
devList.add(new Developer(25, "Rayven", new ArrayList<String>(List.of("Java", "Spring"))));

printInfo(devList);

This results in:

Developer{
skillStack=[Java, Spring]
name=David
id=15
}
Developer{
skillStack=[Java, Spring]
name=Rayven
id=25
}

#### Lower-Bounded Wildcards

Lower-bounded wildcards are the opposite of upper-bounded. This allows a generic type to be restricted to a class or interface and all its supertypes. Here, the class or interface is the lower bound:

Declaring lower-bounded wildcards follows the same pattern as upper-bounded wildcards - a wildcard (?) followed by super and the supertype:

<? super SomeObject>

Based on the IN-OUT principle, lower-bounded wildcards are used for objects that are involved in the output of data. These objects are called out variables.

Let's revisit the email functionality from before and make a hierarchy of classes:

public class Email {
private String email;
// Constructor, getters, setters, toString()
}

Now, let's make a subclass for Email:

public class ValidEmail extends Email {
// Constructor, getters, setters
}

We'll also want to have some utility class, such as MailSender to "send" emails and notify us of the results:

public class MailSender {
public String sendMail(String body, Object recipient) {
return "Email sent to: " + recipient.toString();
}
}

Finally, let's write a method that accepts a body and recipients list and sends them the body, notifying us of the result:

public static String sendMail(String body, List<? super ValidEmail> recipients) {
MailSender mailSender = new MailSender();
StringBuilder sb = new StringBuilder();
for (Object o : recipients) {
String result = mailSender.sendMail(body, o);
sb.append(result+"\n");
}
return sb.toString();
}

Here, we've used a lower-bounded generic type of ValidEmail, which extends Email. So, we're free to create Email instances, and chuck them into this method:

List<Email> recipients = new ArrayList<>(List.of(
new Email("[email protected]"),
new Email("[email protected]")));

String result = sendMail("Hello World!", recipients);
System.out.println(result);

This results in:

Email sent to: Email{email='[email protected]'}
Email sent to: Email{email='[email protected]'}

#### Unbounded Wildcards

Unbounded wildcards are wildcards without any form of binding. Simply put, they are wildcards that extend every single class starting from the base Object class.

Unbounded wildcards are used when the Object class is the one being accessed or manipulated or if the method it's being used on does not access or manipulate using a type parameter. Otherwise, using unbounded wildcards will compromise the type safety of the method.

To declare an unbounded wildcard, simply use the question mark operator encapsulated within angle brackets <?>.

For example, we can have a List of any element:

public void print(List<?> elements) {
for(Object element : elements) {
System.out.println(element);
}
}

System.out.println() accepts any object, so we're good to go here. If the method were to copy an existing list into a new list, then upper-bounded wildcards are more favorable.

#### Difference Between Bounded Wildcards and Bounded Type Parameters?

You may have noticed the sections for bounded wildcards and bounded type parameters are separated but more or less have the same definition, and on the surface level look like they're interchangeable:

<E extends Number>
<? extends Number>

So, what's the difference between these two approaches? There are several differences, in fact:

• Bounded type parameters accept multiple extends using the & keyword while bounded wildcards only accept one single type to extend.
• Bounded type parameters are only limited to upper-bounds. This means that you cannot use the super keyword on bounded type parameters.
• Bounded wildcards can only be used during instantiation. They can not be used for declaration (e.g. class declarations and constructor calls. A few examples of invalid use of wildcards are:
• class Example<? extends Object> {...}
• GenericObj<?> = new GenericObj<?>()
• GenericObj<? extends Object> = new GenericObj<? extends Object>()
• Bounded wildcards should not be used as return types. This will not trigger any errors or exceptions but it forces unnecessary handling and typecasting which is completely against the type safety that generics achieves.
• The operator ? can not be used as an actual parameter and can only be used as a generic parameter. For example:
• public <?> void printDisplay(? var) {} will fail during compilation, while
• public <E> void printDisplay(E var) compiles and runs successfully.

### Benefits of Using Generics

Throughout the guide, we've covered the primary benefit of generics - to provide an additional layer of type safety for your program. Apart from that, generics offer many other benefits over code that doesn't use them.

1. Runtime errors involving types and casting are caught during compile time. The reason why typecasting should be avoided is that the compiler does not recognize casting exceptions during compile time. When used correctly, generics completely avoids the use of typecasting and subsequently avoids all the runtime exceptions that it might trigger.
2. Classes and methods are more reusable. With generics, classes and methods can be reused by different types without having to override methods or create a separate class.

### Conclusion

Applying generics to your code will significantly improve code reusability, readability, and more importantly, type safety. In this guide, we've gone into what generics are, how you can apply them, the differences between approaches and when to choose which.

Last Updated: April 4th, 2021

Get tutorials, guides, and dev jobs in your inbox.


text:
# Free algebra

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

in a class \$\mathfrak K\$ of universal algebras

An algebra \$F\$ in \$\mathfrak K\$ with a free generating system (or base) \$X\$, that is, with a set \$X\$ of generators such that every mapping of \$X\$ into any algebra \$A\$ from \$\mathfrak K\$ can be extended to a homomorphism of \$F\$ into \$A\$ (see Free algebraic system). Any non-empty class of algebras that is closed under subalgebras and direct products and that contains non-singleton algebras, has free algebras. In particular, free algebras always exist in non-trivial varieties and quasi-varieties of universal algebras (see Variety of universal algebras; Algebraic systems, quasi-variety of). A free algebra in the class of all algebras of a given signature \$\Lambda\$ is called absolutely free. An algebra \$A\$ of signature \$\Lambda\$ is a free algebra in some class of universal algebras of signature \$\Lambda\$ if and only if \$A\$ is intrinsically free, that is, if it has a generating set \$X\$ such that every mapping of \$X\$ into \$A\$ can be extended to an endomorphism of \$A\$. If a free algebra has an infinite base, then all its bases have the same cardinality (see Free Abelian group; Free algebra over a ring; Free associative algebra; Free Boolean algebra; Free group; Free semi-group; Free lattice; Free groupoid; Free module; and also Free product). Clearly, every element of a free algebra with a base \$X\$ can be written as a word over the alphabet \$X\$ in the signature of the class being considered. It is natural to ask: When are different words equal as elements of the free algebra? In certain cases the answer is almost trivial (semi-groups, rings, groups, associative algebras), while in others it is fairly complicated (Lie algebras, lattices, Boolean algebras), and sometimes it does not have a recursive solution (alternative rings).

Sometimes the phrases "free algebra" and "free algebraic system" are identified in meaning. See Free algebraic system.

How to Cite This Entry:
Free algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Free_algebra&oldid=31432
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article


text:
Prioritizing structural variants and CNV
1
1
Entering edit mode
17 months ago
jan ▴ 140

Hi All,

I'm pretty new in analysing SV and CNV. We have WGS PacBio long reads germline sequencing reads that have been aligned using pbalign tool to reference sequences （GRCh37/hg19). Variants were called using the variantCaller.py from GenomicConsensus package (https://github.com/PacificBiosciences/GenomicConsensus). Variants were annotated with ANNOVAR for protein coding changes, affected genomic regions, allele frequency reported by some big projects, deleteriousness prediction, etc. The whole process were done by the sequencing company that we sent our sample to.

I am more familiar with Illumina WGS short reads sequencing and analysing SNV and small indels. I have few question regarding SV and CNV analyses.

1) I would like to do some QC to the results (eg check variant counts based on variant type) that we have obtained from the sequencing company but I am not too sure what are the accepted standards. Could you please point me to the right literatures or blogs?

2) For my previous analysis for Illumina WGS short reads sequencing, I used to use two variant different callers and get the unity of both callers, and the results are better than just using one caller. Upon reading, I found a workflow that combines multiple callers https://github.com/wdecoster/nano-snakemake that seem to perform better. Has anyone benchmarked different callers, combined, alone?

3) I am not too sure what information should I use to filter for diseased related SV and CNV. For SNV and small indels for example, I would use information such as population frequency based on gnomAD, in silico predictions eg REVEL, PROVEAN and MaxEntScan, and clinical information based on ClinVar database. Could you please suggest the information (and relevant databases) that I can use to prioritize SVs and CNVs.

Thank you.

PacBio CNV SV • 682 views
4
Entering edit mode
17 months ago

I see you separate CNV from SV in your question, while in my opinion, a CNV is a subtype of an SV. So I don't consider them separately.

1) I would like to do some QC to the results (eg check variant counts based on variant type) that we have obtained from the sequencing company but I am not too sure what are the accepted standards. Could you please point me to the right literatures or blogs?

For a human genome, you would expect ~25k-30k structural variants (defined as any variant larger than 50 bp). So you can count them. What is also useful is making a variant length histogram. For humans you expect a peak around 300 bp (SVs involing Alu elements) and 6 kb (SVs involving L1 elements). I have a tool which does this and more SV handling tasks called surpyvor. For some more complex tasks it's a convenient wrapper around SURVIVOR . surpvyor lengthplot will give you the SV length plot and variant counts per type.

There have been a couple of papers on SVs from long reads, including the one from Audano et al., which can give you some idea of what to expect.

2) For my previous analysis for Illumina WGS short reads sequencing, I used to use two variant different callers and get the unity of both callers, and the results are better than just using one caller. Upon reading, I found a workflow that combines multiple callers https://github.com/wdecoster/nano-snakemake that seem to perform better. Has anyone benchmarked different callers, combined, alone?

Sensitivity can be boosted by taking the union of calls, specificity by taking the intersection. We have done some benchmarking of callers in our paper. I welcome all feedback on our snakemake workflow.


text:
## Illinois Journal of Mathematics

### The equivariant Dold theorem mod $k$ and the Adams conjecture

#### Abstract

In this paper, we state and prove a $G$-equivariant version of the Dold Theorem mod $k$ for finite groups $G$. We then use this theorem to prove an equivariant version of the Adams Conjecture for $G$ cyclic, using the Becker-Gottlieb approach. The case for general $G$ and finite structure groups is also obtained by the methods of Quillen.

We would like to express our gratitude to Professor J. P. May for his encouragement and many useful suggestions, and to the referee for his critical reading of the manuscript, and for his improvements on several of our proofs.

#### Article information

Source
Illinois J. Math., Volume 27, Issue 1 (1983), 52-66.

Dates
First available in Project Euclid: 20 October 2009

https://projecteuclid.org/euclid.ijm/1256065410

Digital Object Identifier
doi:10.1215/ijm/1256065410

Mathematical Reviews number (MathSciNet)
MR684540

Zentralblatt MATH identifier
0522.55017

Subjects
Secondary: 55Q50: $J$-morphism [See also 19L20]
Hauschild, Henning; Waner, Stefan. The equivariant Dold theorem mod $k$ and the Adams conjecture. Illinois J. Math. 27 (1983), no. 1, 52--66. doi:10.1215/ijm/1256065410. https://projecteuclid.org/euclid.ijm/1256065410


text:
## 物理：狭义相对论中的质量增大是质量真的变大了吗？为什么不能超光速？

$m=\frac{m_0}{\sqrt{1-v^2/c^2}}$

$m=\frac{1}{\sqrt{1-v^2/c^2}}m_0=\gamma m_0$

## 物理学：Leidenfrost Phenomenon与Random Walk

Leidenfrost Phenomenon 翻译成 “莱顿弗罗斯特现象”，是指液体不会润湿炙热的表面，而仅仅在其上形成一个蒸气层的现象，由科学家莱顿弗罗斯特在1756年发现。

When Water Flows Uphill

The Inverse Leidenfrost Effect

The WALKING WATER Mystery (in SPACE and SLOW MOTION!) – Smarter Every Day 160

## 电脑技术：用TexLive和TeXstudio搭配使用写论文

TexLive 提供编译环境，也自带简易IDE，其实够用。

1. 命令设置

Options→Configure TeXstudio→Commands

…\TeXLive\2018\bin\win32\bibtex.exe

…\TeXLive\2018\bin\win32\bibtex8.exe

…\TeXLive\2018\bin\win32\biber.exe

2. 构建设置

Options→Configure TeXstudio→Build

方法1. \documentclass{ctexart}

## Candidate theories

There are a number of proposed quantum gravity theories.[33] Currently, there is still no complete and consistent quantum theory of gravity, and the candidate models still need to overcome major formal and conceptual problems. They also face the common problem that, as yet, there is no way to put quantum gravity predictions to experimental tests, although there is hope for this to change as future data from cosmological observations and particle physics experiments becomes available.[34][35]

There are a number of other approaches to quantum gravity. The approaches differ depending on which features of general relativity and quantum theory are accepted unchanged, and which features are modified.[51][52] Examples include:


text:
## The Annals of Probability

### Entrance Laws for Markov Chains

J. Theodore Cox

#### Abstract

Let $S$ be a countable set and let $Q$ be a stochastic matrix on $S \times S$. An entrance law for $Q$ is a collection $\mathbf{\mu} = \{\mu_n\}_{n\in\mathbb{Z}}$ of probability measures on $S$ such that $\mu_nQ = \mu_{n+1}$ for all $n\in\mathbb{Z}$. There is a natural correspondence between entrance laws and Markov chains $\xi_n$ with stationary transition probabilities $Q$ and time parameter set $\mathbb{Z}$. The set $\mathscr{L}(Q)$ of entrance laws is examined in the discrete and continuous time setting. Criteria are given which insure the existence of nontrivial entrance laws.

#### Article information

Source
Ann. Probab., Volume 5, Number 4 (1977), 533-549.

Dates
First available in Project Euclid: 19 April 2007

https://projecteuclid.org/euclid.aop/1176995759

Digital Object Identifier
doi:10.1214/aop/1176995759

Mathematical Reviews number (MathSciNet)
MR455128

Zentralblatt MATH identifier
0369.60079

JSTOR


text:
Derivative of a Function Raised to the Power of Another Function

Find the first derivative of $y = u^v$ showing all the steps.

Derivative of $u^v$

Note that in general that, a function of the form $y = u^v$, where $u$ and $v$ are functions, is neither a power function of the form $x^k$ nor an exponential function of the form $b^x$ > and therefore the common formulas of Differentiation may not be applied. here we suggest a method to find the first derivative a function of the form $y = u^v$ where $u$ and $v$ are functions whose derivatives exist.
Given $y = u^v$
Take the $\ln$ of both sides of the above
$\ln y = \ln (u^v)$
Use properties of logarithmic functions $\quad \ln u^v = v \ln u \;$ to the right side of the above equation and obtain
$\ln y = v \ln u$
Differentiate both sides of the above with respect to $x$, using chain rule and the product rule.
$\dfrac{dy}{dx} \dfrac{1}{y} = \dfrac{dv}{dx} \ln u + v \dfrac{du}{dx} \dfrac{1}{u}$
Multiply both sides by $y$
$\dfrac{dy}{dx} = y \left( \dfrac{dv}{dx} \ln u + v \dfrac{du}{dx} \dfrac{1}{u} \right)$
Substitute $y$ by $u^v$ to obtain the final answer
$\boxed {\dfrac{dy}{dx} = u^v \left( \dfrac{dv}{dx} \ln u + v \dfrac{du}{dx} \dfrac{1}{u} \right) }$

Exercises

Find the first derivative of

1. $y = (x+3)^{x - 2}$
2. $y = (x^2+2)^{\ln x + 1}$

1. $\dfrac{dy}{dx} = (x+3)^{x - 2} \; \left( \ln (x+3) + \dfrac{x - 2}{x+3} \right)$
2. $\dfrac{dy}{dx} = (x^2+2)^{\ln x + 1} \left( \dfrac{1}{x} \ln (x^2+2) + (\ln x + 1) \dfrac{2x}{x^2+2} \right)$


text:
Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
 Что: Лекция Когда: Воскресенье, 22 августа 2010, 11:15–12:50 Где: Слайды: csseminar_lecture_220810.pdf

#### Описание

Model Fitting and Fast Energy Minimization with Label Cost Abstract: The $$\alpha$$-expansion algorithm has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. We show how to extend α-expansion so that it can simultaneously optimize label costs as well. An energy with label costs can penalize a solution based on the set of labels that appear in it. The simplest special case is to penalize the number of labels in the solution. Our energy is quite general, and we prove optimality bounds for our algorithm. A natural application of label costs is multi-model fitting, which we discuss in detail. We demonstrate many applications in vision: homography detection, motion segmentation, and unsupervised image segmentation. Our C++/MATLAB implementation is publicly available.


text:
# Problem 14.3b6

Quick Calculation 14.4b | A First Course in String Theory

.

Massive level in the open superstring

Consider the first and second excited levels of the open superstring ($\alpha' M^2 = 1$ and $\alpha' M^2 = 2$). List the states in NS sector and the states in the R sector. Confirm that you get the same number of states.

~~~

When $\alpha' M^2 = 2$, by Equation (14.54), the possible states are

$\{ \alpha_{-2}^I, \alpha_{-1}^I \alpha_{-1}^J, d_{-1}^I d_{-1}^J \} | R_a \rangle, || ...$

$\{ \alpha_{-1}^I d_{-1}^J, d_{-2}^I \} | R_{\bar a} \rangle, || ...$

.

For $\alpha_{-2}^I | R_a \rangle$, the number of states is 8.

For $\alpha_{-1}^I \alpha_{-1}^J | R_a \rangle$, the number of states is $\frac{8 \times 7}{2} + 8 = 36$.

For $d_{-1}^I d_{-1}^J | R_a \rangle$, the number of states is $\frac{8 \times 7}{2} = 28$.

For $\alpha_{-1}^I d_{-1}^J | R_{\bar a} \rangle$, the number of states is $8 \times 8 = 64$.

For $d_{-2}^I | R_{\bar a} \rangle$, the number of states is 8.

.

However, since each of $a$ and ${\bar a}$ has 8 possible values, there is an additional multiple of 8.

The total number of states is $8 \left[ 8 + 36 + 28 + 64 + 8 \right]$.

.

You can check this answer against Equation (14.67):

$f_{NS} (x) = \frac{1}{\sqrt{x}} + 8 + 36 \sqrt{x} + 128 x + 402 x \sqrt{x} + 1152 x^2 + ...$

— Me@2018.02.20 10:57 AM

.

.


text:
accumulation points

• Sep 23rd 2010, 09:10 PM
EmmWalfer
accumulation points
how can you prove this theorem from the book?

A finite set has no accumulation points.

I know that it's true, but fail to show it mathematically :(
• Sep 24th 2010, 06:13 AM
Ackbeet
Are you working in the real numbers? What ideas have you had so far?
• Sep 24th 2010, 11:03 AM
Danneedshelp
Quote:

Originally Posted by EmmWalfer
how can you prove this theorem from the book?

A finite set has no accumulation points.

I know that it's true, but fail to show it mathematically :(

Well, if you construct an epsilon neighborhood around a proposed limit point x in your finite set, then the intersection of your set with the epsilon neighborhood of x must contain points in your finite set other than x for x to be a limit point (accumulation point). If you can show this doesn't hold, then you are done.
• Sep 25th 2010, 05:26 AM
HallsofIvy
The definition of "accumulation point" is: p is an accumulation point of set A if and only if every neighborhood of p contains at least one point of A (other than p itself). Suppose A is finite. Then the set of all distances from p to points in A (other that p itself) is finite and so contains a smallest value. Take the radius of your neighborhood to be smaller than that value.

(I notice now, that is pretty much what Danneedshelp said!)
• Sep 25th 2010, 09:44 AM
Danneedshelp
Quote:

Originally Posted by HallsofIvy
The definition of "accumulation point" is: p is an accumulation point of set A if and only if every neighborhood of p contains at least one point of A (other than p itself). Suppose A is finite. Then the set of all distances from p to points in A (other that p itself) is finite and so contains a smallest value. Take the radius of your neighborhood to be smaller than that value.

(I notice now, that is pretty much what Danneedshelp said!)

I am not a 100% this correct, but I recall a lemma from my intro to real analysis book that stated something along to lines of: a point $x$ is a limit point (accumulation point) of a set $A$ iff for every $\epsilon>0$, the neighborhood $N_{\epsilon}(x)$ contains infinitly many points of the set $A$.

I think you would have to prove this to use it, but it answers your original question rather quickly.


text:
# Train Bayesian Neural Network

This example shows how to train a Bayesian neural network (BNN) for image regression using Bayes by backpropagation [1]. You can use a BNN to predict the rotation of handwritten digits and model the uncertainty of those predictions.

A Bayesian neural network (BNN) is a type of deep learning network that uses Bayesian methods to quantify the uncertainty in the predictions of a deep learning network. This example uses Bayes by backpropagation (also known as Bayes by backprop) to estimate the distribution of the weights of a neural network. By using a distribution of weights instead of a single set of weights, you can estimate the uncertainty of the network predictions.

This figure shows an example of the predicted angles of rotation and the uncertainty regions for an estimated distribution of weights.

Load the digits data set. This data set contains synthetic images of handwritten digits together with the corresponding angles (in degrees) by which each image is rotated.

Load the training and test images as 4-D arrays using digitTrain4DArrayData and digitTest4DArrayData. The TTrain and TTest outputs are the rotation angles in degrees. The training and test data sets each contain 5000 images.

[XTrain,~,TTrain] = digitTrain4DArrayData; [XTest,~,TTest] = digitTest4DArrayData;

Create a single datastore that contains the training predictors and responses. To convert numeric arrays to datastores, use arrayDatastore. Then, use the combine function to combine these datastores into a single datastore.

dsXTrain = arrayDatastore(XTrain,IterationDimension=4); dsTTrain = arrayDatastore(TTrain); dsTrain = combine(dsXTrain,dsTTrain);

Extract the size of the responses and the number of observations.

numResponses = size(TTrain,2)
numResponses = 1
numObservations = numel(TTrain)
numObservations = 5000

Display 64 random training images.

idx = randperm(numObservations,64); I = imtile(XTrain(:,:,:,idx)); figure imshow(I)

### Define Network Architecture

To model the weights and biases using a distribution rather than a single deterministic set, you must define a probability distribution for the weights. You can define the distribution using Bayes' theorem:

$\mathit{P}\left(\mathrm{parameters}\text{\hspace{0.17em}}|\mathrm{data}\right)=\frac{\mathit{P}\left(\mathrm{data}|\mathrm{parameters}\right)×\mathit{P}\left(\mathrm{parameters}\right)}{\mathit{P}\left(\mathrm{data}\right)}\text{\hspace{0.17em}}\propto \mathrm{likelihood}×\mathrm{prior}$

where $\mathit{P}\left(\mathrm{data}|\mathrm{parameters}\right)=L\left(\mathrm{parameters}|\mathrm{data}\right)$ is the likelihood and $P\left(\mathrm{parameters}\right)$ is the prior distribution. In this example, you set the weights and biases to follow a Gaussian distribution (corresponding to squared-loss). During training, the network learns the means and variances of the Gaussian distributions, which determine the distributions of the weights and biases.

Set the prior to a Gaussian mixture model [1] with two components, each with a mean of 0 and variances sigma1 and sigma2. You can fix the variances before training or learn them during training. Both components of the mixture model have a mixing proportion of 0.5.

Define a Bayesian neural network for image regression.

• For image input, specify an image input layer with an input size matching the training data.

• Do not normalize the image input. Set the Normalization option of the input layer to "none".

• Specify three Bayes fully connected layers with ReLU activation layers between them.

A Bayes fully connected layer is a type of fully connected layer that stores the average weights and biases of the expected distribution of the weights. When computing the activations of the layer, the software shifts the mean weights and biases by random Gaussian noise and uses the shifted weights and biases to compute the outputs of the layer.

To create a Bayes fully connected layer, use the bayesFullyConnectedLayer.m custom layer, attached to this example as a supporting file. The Bayes fully connected layer takes as input the output size and the parameters of the prior probabilities of the weight distribution, sigma1 and sigma2.

Define the network.

inputSize = [28 28 1]; outputSize = 784; sigma1 = 1; sigma2 = 0.5; layers = [ imageInputLayer(inputSize,Normalization="none") bayesFullyConnectedLayer(outputSize,Sigma1=sigma1,Sigma2=sigma2) reluLayer bayesFullyConnectedLayer(outputSize/2,Sigma1=sigma1,Sigma2=sigma2) reluLayer bayesFullyConnectedLayer(1,Sigma1=sigma1,Sigma2=sigma2)];

Create a dlnetwork object from the layer array.

net = dlnetwork(layers);

Visualize the network using analyzeNetwork. You can see that the learnables for the Bayes fully connected layers include the means and variances for the weights and biases.

analyzeNetwork(net)

#### Define Learnable Parameters

The learnable parameters comprise network (layer) learnables and global learnables. During training, the algorithm updates these learnable parameters:

• The means and variances of the layer weights and biases (per layer)

• The prior probabilities for the weight distributions (per layer)

• The sampling noise (global)

#### Initialize Sampling Noise

Use sampling noise to represent the noise in the predictions of the neural network. Learn the sampling noise with the network weights and biases.

Initialize the sampling noise.

samplingNoise = dlarray(1);

#### Initialize Prior Probability

You can fix the prior variance parameters or learn them during training like the other learnable parameters. Learn the prior parameters during training using a small learn rate so that their values remain close to the initial values. Set the initial learn rate to 0.25.

doLearnPrior = true; priorLearnRate = 0.25; numLearnables = size(net.Learnables,1); for i=1:numLearnables layerName = net.Learnables.Layer(i); parameterName = net.Learnables.Parameter(i); if parameterName == "Sigma1" || parameterName == "Sigma2" if doLearnPrior net = setLearnRateFactor(net,layerName,parameterName,priorLearnRate); else net = setLearnRateFactor(net,layerName,parameterName,0); end end end

### Define Model Loss Functions

Define a function that returns the model loss and the gradients of the loss with respect to the learnable parameters. In this example, you minimize the evidence lower bound (ELBO) loss defined in the Evidence Lower Bound Loss section.

Create the function modelLoss, listed in the Model Loss Function section. The function takes as input a dlnetwork object and a mini-batch of input data with corresponding targets. The function returns these values:

• ELBO loss

• Root mean squared error (RMSE)

• Gradients of the loss with respect to the learnable parameters

• Gradients of the loss with respect to the sampling noise

• Network state

### Specify Training Options

Train for 50 epochs with a mini-batch size of 128.

numEpochs = 50; miniBatchSize = 128;

Track the ELBO loss during training. Plot the loss every 50 iterations and average the loss across five samples of the learnable parameters.

numSamplesForavgELBO = 5; averageLossComputationFrequency = 50;

### Train Model

Create a minibatchqueue object to process and manage the mini-batches of images. For each mini-batch:

• Use the custom mini-batch preprocessing function preprocessMiniBatch (defined at the end of this example) to one-hot encode the class labels.

• Format the image data with the dimension labels "SSCB" (spatial, spatial, channel, batch). By default, the minibatchqueue object converts the data to dlarray objects with underlying type single.

• Train on a GPU if one is available. By default, the minibatchqueue object converts each output to a gpuArray object if a GPU is available. Using a GPU requires a Parallel Computing Toolbox™ license and a supported GPU device. For information on supported devices, see GPU Computing Requirements (Parallel Computing Toolbox).

mbq = minibatchqueue(dsTrain, ... MiniBatchSize=miniBatchSize, ... MiniBatchFcn=@preprocessMiniBatch, ... MiniBatchFormat=["SSCB" "CB"]);

Initialize the parameters for Adam optimization.

trailingAvg = []; trailingAvgSq = []; trailingAvgNoise = []; trailingAvgNoiseSq = [];

Calculate the total number of iterations for the training progress monitor.

numIterationsPerEpoch = ceil(numObservations/miniBatchSize); numIterations = numEpochs*numIterationsPerEpoch;

Initialize the training progress monitor.

monitor = trainingProgressMonitor( ... Metrics=["RMSE","AverageELBOLoss"], ... Info="Epoch", ... XLabel="Iteration");

Train the model using a custom training loop. For each epoch, shuffle the data and loop over mini-batches of data. At the end of each iteration, display the training progress. For each mini-batch:

• Evaluate the model loss and gradients using dlfeval and the modelLoss function.

• Update the network parameters using the adamupdate function.

• Update the sampling noise parameters (global parameters) using the adamupdate function.

• Record the RMSE and the average ELBO loss.

iteration = 0; epoch = 0; % Loop over epochs. while epoch < numEpochs && ~monitor.Stop epoch = epoch + 1; miniBatchIdx = 0; % Shuffle data. shuffle(mbq); while hasdata(mbq) && ~monitor.Stop iteration = iteration + 1; miniBatchIdx = miniBatchIdx + 1; [X,T] = next(mbq); [elboLoss,rmsError,gradientsNet,gradientsNoise] = dlfeval(@modelLoss, ... net,X,T,samplingNoise,miniBatchIdx,numIterationsPerEpoch); % Update the network parameters using the Adam optimizer. [net,trailingAvg,trailingAvgSq] = adamupdate(net,gradientsNet, ... trailingAvg,trailingAvgSq,iteration); % Update the sampling noise. [samplingNoise,trailingAvgNoise,trailingAvgNoiseSq] = adamupdate(samplingNoise, ... gradientsNoise,trailingAvgNoise,trailingAvgNoiseSq,iteration); % Record the RMSE. recordMetrics(monitor,iteration,RMSE=double(rmsError)) % Record the average ELBO loss. if mod(iteration,averageLossComputationFrequency) == 0 avgELBOLoss = averageNegativeELBO(net,X,T,samplingNoise,miniBatchIdx, ... numIterationsPerEpoch,numSamplesForavgELBO); recordMetrics(monitor,iteration,AverageELBOLoss=double(avgELBOLoss)) end % Update the epoch and progress values in the monitor. updateInfo(monitor,Epoch=string(epoch) + " of " + string(numEpochs)) monitor.Progress = 100*(iteration/numIterations); end end

### Test Network

BNNs learn the probability distribution of the weights rather than optimizing a single set of weights like convolutional neural networks. Therefore, you can view a BNN as an ensemble of networks where you sample each network from the learned probability distribution of the learnable parameters.

To test the accuracy of a BNN, generate $\mathit{N}$ samples for the weights and biases and compare the average prediction across the $\mathit{N}$ samples with the true value. The standard deviation across the $\mathit{N}$ predictions is the model uncertainty. Use the modelPosteriorSample function listed in the Model Prediction Function section to generate predictions for a set of inputs. The function samples $\mathit{N}$ times from the posterior distribution of the weights and biases. For each of the $\mathit{N}$ samples, the function generates predictions for the input images. The predictions from a BNN use a sample of the weights and biases; therefore, the predictions include some variational noise.

Convert the test data to a dlarray object.

XTest = dlarray(XTest,"SSCB"); if canUseGPU XTest = gpuArray(XTest); end

#### Test Single Image

Generate 10 samples for the first test image using modelPosteriorSample. The function returns 10 predictions for the angle of rotation. The final model prediction is the average value across the 10 predictions.

idx = 1; numSamples = 10; img = XTest(:,:,:,idx); predictions = modelPosteriorSample(net,img,samplingNoise,numSamples); YTestImg = mean(predictions,1);

Plot the true angle, the predicted angles, and the mean of the predictions.

figure lineWidth = 1.5; uncertaintyColor = "#EDB120"; I = extractdata(img); imshow(I,InitialMagnification=800) hold on inputSize = size(img,1); offset = inputSize/2; thetaActual = TTest(idx); plot(offset*[1 - tand(thetaActual),1 + tand(thetaActual)],[inputSize 0], ... LineWidth=lineWidth) thetaPredAvg = YTestImg; plot(offset*[1 - tand(thetaPredAvg),1 + tand(thetaPredAvg)],[inputSize 0], ... LineWidth=lineWidth) for i=1:numSamples thetaPred = predictions(i); plot(offset*[1 - tand(thetaPred),1 + tand(thetaPred)],[inputSize 0],"--", ... Color=uncertaintyColor) end hold off title("Pred: " + round(thetaPredAvg,2)+" (Mean)" + ", True: " + round(thetaActual,2)) legend(["True","Mean Prediction","Prediction"],Location="southeast")

Increase the number of samples to 500 and plot the distribution of the predicted angles of rotation for the test image.

numSamples = 500; predictions = modelPosteriorSample(net,img,samplingNoise,numSamples); YTestImg = mean(predictions,1); uncertaintyImg = std(predictions,1); figure histogram(predictions) trueColor = "#0072BD"; predColor = "#D95319"; hold on xline(TTest(idx),Color=trueColor,LineWidth=lineWidth) xline(YTestImg,Color=predColor,LineWidth=lineWidth) xline(YTestImg - 2*uncertaintyImg,"--",Color=uncertaintyColor,LineWidth=lineWidth) xline(YTestImg + 2*uncertaintyImg,"--",Color=uncertaintyColor,LineWidth=lineWidth) hold off xlabel("Angle of Rotation") ylabel("Frequency") title("Distribution of Predictions (Number of Samples = " + numSamples + ")") legend("","True","Mean Prediction","+-" + "2\sigma (Standard Deviation)")

#### Test All Images

Predict the angle of rotation for each test image using 100 samples of the learnable parameters.

numSamples = 100; predictions = modelPosteriorSample(net,XTest,samplingNoise,numSamples); YTest = mean(predictions,1); uncertainty = std(predictions,1);

Calculate the prediction error between the true and predicted angles of rotation.

predictionError = TTest - YTest';

Use the RMSE to measure the differences between the true and predicted angles of rotation.

squares = predictionError.^2; rmse = sqrt(mean(squares))
rmse = 15.0308

#### Visualize Predicted Angles and Uncertainties

View some of the images with their predicted and true angles. Show the uncertainty in the predictions using the standard deviation of the model predictions.

numTestImages = numel(TTest); numObservationToShow = 9; idxTestSubset = randperm(numTestImages,numObservationToShow); sdToPlot = 2; tiledlayout("flow",TileSpacing="tight"); for i = 1:numObservationToShow idx = idxTestSubset(i); nexttile I = extractdata(XTest(:,:,:,idx)); imshow(I) hold on thetaActual = TTest(idx); plot(offset*[1 - tand(thetaActual),1 + tand(thetaActual)],[inputSize 0],LineWidth=lineWidth) thetaPred = YTest(idx); plot(offset*[1 - tand(thetaPred),1 + tand(thetaPred)],[inputSize 0],LineWidth=lineWidth) thetaUncertainty = [thetaPred - sdToPlot*uncertainty(idx),thetaPred + sdToPlot*uncertainty(idx)]; % Plot upper and lower bounds. lowerBound = [1 - tand(thetaUncertainty(1)),1 + tand(thetaUncertainty(1))]; upperBound = [1 - tand(thetaUncertainty(2)),1 + tand(thetaUncertainty(2))]; plot(offset*lowerBound,[inputSize 0],"--",Color=uncertaintyColor,LineWidth=lineWidth) plot(offset*upperBound,[inputSize 0],"--",Color=uncertaintyColor,LineWidth=lineWidth) hold off title({"True = " + round(thetaActual,2),"Pred: " + round(thetaPred,2)}) if i == 2 legend(["True","Mean Prediction","+-" + sdToPlot + "\sigma (Standard Deviation)"], ... Location="northoutside", ... NumColumns=3) end end

### Supporting Functions

#### Mini-Batch Preprocessing Function

The preprocessMiniBatch function preprocesses the data using these steps:

1. Extract the image data from the input cell array dataX and concatenate it into a numeric array. Concatenating the image data over the fourth dimension adds a third dimension to each image, for the network to use as a singleton channel dimension.

2. Extract angle data from the input cell arrays dataAng and concatenate it along the second dimension into a numeric array.

function [X,A] = preprocessMiniBatch(dataX,dataAng) X = cat(4,dataX{:}); A = cat(2,dataAng{:}); end

#### Model Prediction Function

The modelPosteriorSample function takes as input the dlnetwork object net, an input image X, the sampling noise samplingNoise, and the number of samples to generate numSamples. The function returns numSample predictions for the input image.

function predictions = modelPosteriorSample(net,X,samplingNoise,numSamples) predictions = zeros(numSamples,size(X,4)); for i=1:numSamples Y = predict(net,X,Acceleration="none"); sigmaY = exp(samplingNoise); predictions(i,:) = Y + sigmaY.*randn(size(Y)); end end

#### Maximum Likelihood Estimation Function

The logLikelihood function estimates the likelihood of the network prediction given the true values and the sampling noise. The function takes as input the predictions Y, true values T, and sampling noise samplingNoise and returns the log-likelihood l.

function l = logLikelihood(Y,T,samplingNoise) sigmaY = exp(samplingNoise); l = sum(logProbabilityNormal(T,Y,sigmaY),"all"); end

#### Model Loss Function

The modelLoss function takes as input the dlnetwork object net, a mini-batch of input data X with corresponding targets T, the sampling noise samplingNoise, the mini-batch index miniBatchIdx, and the number of batches numBatches. The function returns the ELBO loss, the RMSE loss, the gradients of the loss with respect to the learnable parameters, and the gradients of the loss with respect to the sampling noise.

function [elboLoss,meanError,gradientsNet,gradientsNoise] = modelLoss(net,X,T,samplingNoise,miniBatchIdx,numBatches) [elboLoss,Y] = negativeELBO(net,X,T,samplingNoise,miniBatchIdx,numBatches); [gradientsNet,gradientsNoise] = dlgradient(elboLoss,net.Learnables,samplingNoise); meanError = double(sqrt(mse(Y,T))); end

#### Evidence Lower Bound (ELBO) Loss Function

The negativeELBO function computes the ELBO loss for a given mini-batch.

The ELBO loss combines these aims:

• Maximize the likelihood of the network predictions.

• Minimize the Kullback-Leibler (KL) divergence between the variational distribution $q\left(w|\theta \right)$ and the posterior. The variational distribution $q\left(w|\theta \right)$ approximates the true posterior distribution and decreases the computational complexity during training.

The negativeELBO function takes as inputs a dlnetwork object net, a mini-batch of input data X with corresponding targets T, the sampling noise samplingNoise, the mini-batch index miniBatchIdx, and the number of batches numBatches. The function returns the ELBO loss ELBO and the result of the forward pass (network prediction) Y.

function [ELBO,Y] = negativeELBO(net,X,T,samplingNoise,miniBatchIdx,numBatches) [Y,state] = forward(net,X,Acceleration="auto"); beta = KLWeight(miniBatchIdx,numBatches); logPosterior = state.Value(state.Parameter == "LogPosterior"); logPosterior = sum([logPosterior{:}]); logPrior = state.Value(state.Parameter == "LogPrior"); logPrior = sum([logPrior{:}]); l = logLikelihood(Y,T,samplingNoise) ; ELBO = (-1*l) + ((logPosterior - logPrior)*beta); end

#### Average ELBO Loss

The averageNegativeELBO function takes as input a dlnetwork object net, a mini-batch of input data X with corresponding targets T, the sampling noise samplingNoise, the mini-batch index miniBatchIdx, the number of batches numBatches, and the number of samples numSamples. The function returns the ELBO loss averaged across numSamples samples of the ELBO loss.

function avgELBO = averageNegativeELBO(net,X,T,samplingNoise,miniBatchIdx,numBatches,numSamples) avgELBO = 0; for i=1: numSamples ELBO = negativeELBO(net,X,T,samplingNoise,miniBatchIdx,numBatches); avgELBO = avgELBO + ELBO; end avgELBO = avgELBO/numSamples; end

#### Mini-Batches and KL Reweighting

The KLWeight function takes as input the current batch index i and the total number of batches m. The function returns beta, a scalar value in the range [0, 1] that you can use to scale the current batch KL sum.

Minimize the cost for each mini-batch using this reweighting strategy:

,

where ${\beta }_{i}=\frac{{2}^{M-i}}{{2}^{M}-1}$.

$\beta$ is a scaling factor for an estimate of the posterior distribution of the weights [1].

function beta = KLWeight(i,m) beta = 2^(m - i)/(2^m - 1); end

### References

[1] Blundell, Charles, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra, “Weight Uncertainty in Neural Networks”. arXiv preprint arXiv:1505.05424 (May 2015)., https://arxiv.org/abs/1505.05424.


text:
# Non-idempotent Python [closed]

Write a few lines of Python code, X, that does not reference any global variables, such that

def method():
X
print(a)

method()

prints 1 but

def method():
X
X
print(a)

method()

prints 2.

So, I hate to be a stickler, but it seems like vars and locals are actually global variables in Python:

def test_global_1():
global vars, locals
vars = lambda: 2
locals = lambda: 3

def test_global_2():
print(vars())
print(locals())

test_global_1()
test_global_2()

Also, it looks like people would like to see objective winning criteria for puzzles like this. Code length doesn't really feel right here so perhaps we could make a system of brownie points for various novel features of the code? I'm not sure exactly what these could be but here's a start:

• +1 for really truly no globals (no vars or locals)
• +1 for being the first to post a particular technique
• +1 for the shortest solution posted
• +1 for a solution involving only a single Python statement
• +1 for interesting "hacks" like joining at lexical non-boundaries
• +1 for not using exceptions

And if you can think of more you could edit this question to add to the list.

Can this problem be solved without using exceptions and without using globals like vars and locals? I suspect it can, though I haven't figured out exactly how yet...

• Good puzzle! I made sure not to scroll down so I could solve it myself without seeing anyone's answers. :D – mbomb007 Jul 30 '15 at 21:36
• Thanks for the puzzles Owen, and welcome to the site. There is a rule on the site that all questions must have an objective winning condition, so you should probably add one. One possibility is shortest length of X, but there are other options. – isaacg Jul 31 '15 at 8:25
• "all questions must have an objective winning condition" - Stupid rule imho. Who cares about a "winner" when we all actually most enjoy the puzzling and learning from the different answers. – JimmyB Jul 31 '15 at 11:34
• Please add a code-golf or popularity-contest tag, depending on whether you want people to optimize for shortness code or for general popularity. I imagine code-golf is better for this challenge (popularity-contest is encouraged only for challenges that cannot be easily classified otherwise), but it's up to you. – apsillers Jul 31 '15 at 13:18
• You've added a scoring system, but also added the popularity contest tag, which means that a winner is decided by votes. What do you mean here? Perhaps you want votes just as a tiebreak? – xnor Aug 2 '15 at 2:13

def method():
if 'a' not in vars():a=0
a+=1
if 'a' not in vars():a=0
a+=1
print(a)

Initializes the variable a to 0 only if it's not already initialized in the variables table. Then, increments it.

More briefly (thanks to histocrat for len):

def method():
a=len(vars())+1
a=len(vars())+1
print(a)

If the two copies of X could be on the same line, we could do

a=0;a+=1;a

which doubles to

a=0;a+=1;aa=0;a+=1;a

with the "sacrificial lamb" aa eating up the second variable assignment.

• I don't want to be a spoilsport posting this so fast, so how about we try for shortest code? – xnor Jul 30 '15 at 20:03
• Slightly shorter variant: a=len(vars())+1 – histocrat Jul 30 '15 at 20:50
• @histocrat Nice one, thanks! – xnor Jul 30 '15 at 21:03

# Python

Thought of this solution, since try and except was the first way I thought of to determine if a variable existed yet or not.

def method():
try:a+=1
except:a=1
print(a)

# Python 2

def method():
exec'';locals()['a']=locals().get('a',0)+1
exec'';locals()['a']=locals().get('a',0)+1
print a

method()

Basically, when exec is encountered in Python 2, it causes a special flag (0x01) to be removed from method.func_code.co_flags, which makes locals assignments have an effect. I exploited this to implement nonlocal support in Python 2 (see line 43 for the xor that modifies the flag).

• Why not a = locals().get('a', 0) + 1? – Vincent Jul 31 '15 at 13:15
• @Vincent I was tiree. :O Fixed. – kirbyfan64sos Jul 31 '15 at 14:15
• In that case you don't need exec'' any more ;) – Vincent Jul 31 '15 at 14:20
• @Vincent Eh, maybe I should just stick with the longer version. It felt more creative. Now it just seems a lot like a clone of the top-voted answer... :/ – kirbyfan64sos Jul 31 '15 at 14:23

My first idea (and then smooshing it) was:

def method():
a=2if'a'in vars()else 1
a=2if'a'in vars()else 1
print(a)

My attempt. Uses the math module to track if X is run once or twice.

def module():
import sys
if 'math' in sys.modules:
a+=1
else:
a=1
import math

import sys
if 'math' in sys.modules:
a+=1
else:
a=1
import math

print(a)

module()

def method(a=[]):
a.append(a)
print len(a)

Edited in response to comment: a is a list of empty lists of length n, where n is the number of time you've called method. Calling this method twice prints 1 then 2.

• Putting a=[] as a parameter is outside the parameters for this challenge. – mbomb007 Jul 31 '15 at 2:57
• Sorry, this is my answer, and it's not very good. This is (arguably) a surprisingly non-idempotent operation in python, but there's no way to slot it into the format provided for the challenge without also making the challenge trivial. – WithScience Jul 31 '15 at 17:29
• Also, the challenge asks to print 1 or 2, not just two different things. – xnor Jul 31 '15 at 22:52
def method():
#### X-block
try:a
except NameError:a=1
else:a=2
####
print(a)

The try block checks if the variable a is defined.
If variable not defined,(this is only when X-block is present once) then NameError Exception is raised.
If variable is defined, (this is when X-block is present twice) then else will be entered .

• Yeah, that's the solution I found by searching Google. Then I created my current solution, which is shorter. – mbomb007 Jul 30 '15 at 21:46
• @mbomb007 Yeah :P. Your way is shorter than using else – Kamehameha Jul 30 '15 at 21:50


text:
# Diffie-Hellman key exchange

In the previous sections, we discussed symmetric-key schemes such as block ciphers and MACs. For these schemes to work, we assumed that Alice and Bob both share a secret key that no one else knows. But how would they be able to exchange a secret key if they can only communicate through an insecure channel? It turns out there is a clever way to do it, first discovered by Whit Diffie and Martin Hellman in the 1970s.

The goal of Diffie-Hellman is usually to create an ephemeral key. An ephemeral key is used for some series of encryptions and decryptions and is discarded once it is no longer needed. Thus Diffie-Hellman is effectively a way for two parties to agree on a random value in the face of an eavesdropper.

## Diffie-Hellman intuition

A useful analogy to gain some intuition about Diffie-Hellman key exchange is to think about colors. Alice and Bob want to both share a secret color of paint, but Eve can see any paint being exchanged between Alice and Bob. It doesn’t matter what the secret color is, as long as only Alice and Bob know it.

Alice and Bob each start by deciding on a secret color–for example, Alice generates amber and Bob generates blue. If Eve wasn’t present, Alice and Bob could just send their secret colors to each other and mix the two secret colors together to get the final color. However, since Eve can see any colors sent between Alice and Bob, they must somehow hide their colors when exchanging them.

To hide their secret colors, Alice and Bob agree on a publicly-known common paint color–in this example, green. They each take their secret color, mix it with the common paint color, and then send it over the insecure channel. Alice sends a green-amber mixture to Bob, and Bob sends a green-blue mixture to Alice. Here we’re assuming that given a paint mixture, Eve cannot separate the mixture into its original colors.

At this point, Alice and Bob have each other’s secret colors, mixed with the common color. All that’s left is to add their own secret. Alice receives the green-blue mixture from Bob and adds her secret amber to get green-blue-amber. Bob receives the green-amber mixture from Alice and adds his secret blue to get green-amber-blue. Alice and Bob now both have a shared secret color (green-amber-blue).

The only colors exchanged over the insecure channel were the secret mixtures green-amber and green-blue. Given green-amber, Eve would need to add blue to get the secret, but she doesn’t know Bob’s secret color, because it wasn’t sent over the channel, and she can’t separate the green-blue mixture. Eve could also try mixing the green-amber and green-blue mixtures, but you can imagine this wouldn’t result in exactly the same secret, since there would be too much green in the mix. The result would be more like green-amber-green-blue than green-amber-blue.

## Discrete logarithm problem

The secret exchange in the color analogy relied on the fact that mixing two colors is easy, but separating a mixture of two colors is practically impossible. It turns out that there is a mathematical equivalent of this. We call these one-way functions: a function $$f$$ such that given $$x$$, it is easy to compute $$f(x)$$, but given $$y$$, it is practically impossible to find a value $$x$$ such that $$f(x) = y$$.

A one-way function is also sometimes described as the computational equivalent of a process that turns a cow into hamburger: given the cow, you can produce hamburger, but there’s no way to restore the original cow from the hamburger.

There are many functions believed to be one-way functions. The simplest one is exponentiation modulo a prime: $$f(x) = g^x \pmod{p}$$, where $$p$$ is a large prime and $$g$$ is a specially-chosen generator1.

Given $$x$$, it is easy to calculate $$f(x)$$ (you may recall the repeated squaring algorithm from CS 70). However, given $$f(x) = g^x \pmod{p}$$, there is no known efficient algorithm to solve for $$x$$. This is known as the discrete logarithm problem, and it is believed to be computationally hard to solve.

Using the hardness of the discrete log problem and the analogy from above, we are now ready to construct the Diffie-Hellman key exchange protocol.

## Diffie-Hellman protocol

In high-level terms, the Diffie-Hellman key exchange works like this.

Alice and Bob first establish the public parameters $$p$$ and $$g$$. Remember that $$p$$ is a large prime and $$g$$ is a generator in the range $$1<g<p-1$$. For instance, Alice could pick $$p$$ and $$g$$ and then announce it publicly to Bob. Today, $$g$$ and $$p$$ are often hardcoded or defined in a standard so they don’t need to be chosen each time. These values don’t need to be specific to Alice or Bob in any way, and they’re not secret.

Then, Alice picks a secret value $$a$$ at random from the set $$\{0,1,\dots,p-2\}$$, and she computes $$A=g^a \bmod p$$. At the same time, Bob randomly picks a secret value $$b$$ and computes $$B=g^b \bmod p$$.

Now Alice announces the value $$A$$ (keeping $$a$$ secret), and Bob announces $$B$$ (keeping $$b$$ secret). Alice uses her knowledge of $$B$$ and $$a$$ to compute

$S = B^a = (g^b)^a = g^{ba} \pmod p.$

Symmetrically, Bob uses his knowledge of $$A$$ and $$b$$ to compute

$S = A^b = (g^a)^b = g^{ab} \pmod p.$

Note that $$g^{ba} = g^{ab} \pmod{p}$$, so both Alice and Bob end up with the same result, $$S$$.

Finally, Alice and Bob can use $$S$$ as a shared key for a symmetric-key cryptosystem (in practice, we would apply some hash function to $$S$$ first and use the result as our shared key, for technical reasons).

The amazing thing is that Alice and Bob’s conversation is entirely public, and from this public conversation, they both learn this secret value $$S$$—yet eavesdroppers who hear their entire conversation cannot learn $$S$$.

As far as we know, there is no efficient algorithm to deduce $$S=g^{ab} \bmod p$$ from the values Eve sees, namely $$A=g^a \bmod p$$, $$B=g^b \bmod p$$, $$g$$, and $$p$$. The hardness of this problem is closely related to the discrete log problem discussed above. In particular, the fastest known algorithms for solving this problem take $$2^{cn^{1/3} (\log n)^{2/3}}$$ time, if $$p$$ is a $$n$$-bit prime. For $$n=2048$$, these algorithms are far too slow to allow reasonable attacks.

Here is how this applies to secure communication among computers. In a computer network, each participant could pick a secret value $$x$$, compute $$X=g^x \bmod p$$, and publish $$X$$ for all time. Then any pair of participants who want to hold a conversation could look up each other’s public value and use the Diffie-Hellman scheme to agree on a secret key known only to those two parties. This means that the work of picking $$p$$, $$g$$, $$x$$, and $$X$$ can be done in advance, and each time a new pair of parties want to communicate, they each perform only one modular exponentiation. Thus, this can be an efficient way to set up shared keys.

Here is a summary of Diffie-Hellman key exchange:

• System parameters: a 2048-bit prime $$p$$, a value $$g$$ in the range $$2\ldots p-2$$. Both are arbitrary, fixed, and public.

• Key agreement protocol: Alice randomly picks $$a$$ in the range $$0\ldots p-2$$ and sends $$A=g^a \bmod p$$ to Bob. Bob randomly picks $$b$$ in the range $$0\ldots p-2$$ and sends $$B=g^b \bmod p$$ to Alice. Alice computes $$K=B^a \bmod p$$. Bob computes $$K=A^b \bmod p$$. Alice and Bob both end up with the same random secret key $$K$$, yet as far as we know no eavesdropper can recover $$K$$ in any reasonable amount of time.

## Elliptic-curve Diffie-Hellman

In the section above, we used the discrete log problem to construct a Diffie-Hellman protocol, but we can generalize Diffie-Hellman key exchange to other one-way functions. One commonly used variant of Diffie-Hellman relies on the elliptic curve discrete logarithm problem, which is based on the math around elliptic curves instead of modular arithmetic. Although the underlying number theory is more complicated, elliptic-curve Diffie-Hellman can use smaller keys than modular arithmetic Diffie-Hellman and still provide the same security, so it has many useful applications.

For this class, you don’t need to understand the underlying math that makes elliptic-curve Diffie-Hellman work, but you should know that the idea behind the protocol is the same.

Alice and Bob start with a publicly known point on the elliptic curve $$G$$. Alice chooses a secret integer $$a$$ and Bob chooses a secret integer $$b$$.

Alice computes $$A = a \cdot G$$ (this is a point on the curve $$A$$, obtained by adding the point $$G$$ to itself $$a$$ times), and Bob computes $$B = b \cdot G$$. Alice sends $$A$$ to Bob, and Bob sends $$B$$ to Alice.

Alice computes

$S = a \cdot B = a \cdot b \cdot G$

and Bob computes

$S = b \cdot A = b \cdot a \cdot G$

Because of the properties of the elliptic curve, Alice and Bob will derive the same point $$S$$, so they now have a shared secret. Also, the elliptic-curve Diffie-Hellman problem states that given $$A = a \cdot G$$ and $$B = b \cdot G$$, there is no known efficient method for Eve to calculate $$S$$.

## Difficulty in Bits

It is generally believed that the discrete log problem is hard, but how hard? In practice, it is generally believed that computing the discrete log modulo a 2048b prime, computing the elliptic curve discrete log on a 256b curve, and brute forcing a 128b symmetric key algorithm are all roughly the same difficulty. (Brute-forcing the 128b key is believed to be slightly harder than the other two.)

Thus, if we are using Diffie-Hellman key exchange with other cryptoschemes, we try to relate the difficulty of the schemes so that it is equally difficult for an attacker to break any scheme. For example, 128b AES tends to be used with SHA-256 and either 256b elliptic curves or 2048b primes for Diffie-Hellman. Similarly, for top-secret use, the NSA uses 256b AES, 384b Elliptic Curves, SHA-384, and 3096b Diffie-Hellman and RSA.

## Attacks on Diffie-Hellman

As we’ve seen, Diffie-Hellman is secure against an eavesdropper Eve, who observes the messages sent between Alice and Bob, but does not tamper with them. What if we replace Eve with Mallory, an active adversary (man-in-the-middle) who can tamper with messages?

It turns out the Diffie-Hellman key exchange protocol is only secure against a passive adversary and not an active adversary. If Mallory can tamper with the communication between Alice and Bob, she can fool them into thinking that they’ve agreed with a shared key, when they have actually generated two different keys that Mallory knows.

The following figure demonstrates how an active attacker (Mallory) can agree on a key ($$K_1=g^{am} \pmod{p}$$) with Alice and another key ($$K_2=g^{bm} \pmod{p}$$) with Bob in order to man-in-the-middle (MITM) their communications.

When Alice sends $$g^a \pmod{p}$$ to Bob, Mallory intercepts the message and replaces it with $$g^m \pmod{p}$$, where $$m$$ is Mallory’s secret. Bob now receives $$g^m \pmod{p}$$ instead of $$g^a \pmod{p}$$. Now, when Bob wants to calculate his shared key, he will calculate $$K = A^b \pmod{p}$$, where $$A$$ is the value he received from Alice. Since he received a tampered value from Mallory, Bob will actually calculate $$K = (g^m)^b = g^{mb} \pmod{p}$$.

Likewise, when Bob sends $$g^b \pmod{p}$$ to Alice, Mallory intercepts the message and replaces it with $$g^m \pmod{p}$$. Alice receives $$g^m \pmod{p}$$. To calculate her shared key, she calculates $$K = B^a \pmod{p}$$, where $$B$$ is the value she received from Bob. Since Alice received a tampered value, she will actually calculate $$K = (g^m)^a = g^{ma} \pmod{p}$$.

After the exchange, Alice thinks the shared key is $$g^{ma} \pmod{p}$$ and Bob thinks the shared key is $$g^{mb} \pmod{p}$$. They no longer have the same shared secret.

Even worse, Mallory knows both of these values too. Mallory intercepted Alice sending $$g^a \pmod{p}$$, which means Mallory knows the value of $$g^a \pmod{p}$$. She also knows her own chosen secret $$m$$. Thus she can calculate $$(g^a)^m = g^{am} \pmod{p}$$, which is what Alice thinks her shared secret is. Likewise, Mallory intercepted $$g^b \pmod{p}$$ from Bob and can calculate $$(g^b)^m = g^{bm} \pmod{p}$$, which is what Bob thinks his shared secret is.

If Alice and Bob fall victim to this attack, Mallory can now decrypt any messages sent from Alice with Alice’s key $$g^{ma} \pmod{p}$$, make any changes to the message, re-encrypt the message with Bob’s key $$g^{mb} \pmod{p}$$, and send it to Bob. In other words, Mallory would pretend to Alice that she is Bob, and pretend to Bob that she is Alice. This would not only allow Mallory to eavesdrop on the entire conversation but also make changes to the messages without Alice and Bob ever noticing that they are under attack.

The main reason why the Diffie-Hellman protocol is vulnerable to this attack is that the messages exchanged between Alice and Bob have no integrity or authenticity. To defend against this attack, Alice and Bob will need to additionally use a cryptoscheme that provides integrity and authenticity, such as digital signatures. If the messages sent during the Diffie-Hellman exchange have integrity and authenticity, then Alice and Bob would be able to detect Mallory’s tampering with the messages.

1. You don’t need to worry about how to choose $$g$$, just know that it satisfies some special number theory properties. In short, $$g$$ must satisfy the following properties: $$1 < g < p-1$$, and there exists a $$k$$ where $$g^k = a$$ for all $$1 \leq a \leq p-1$$.


text:
# 9. Using Miller–Orr The variance of the daily cash flows for the Pele Bicycle Shop is $890,000.... 1 answer below » 9. Using Miller–Orr The variance of the daily cash flows for the Pele Bicycle Shop is$890,000. The opportunity cost to the firm of holding cash is 4.1 percent per year. What should the target cash level and the upper limit be if the tolerable lower limit has been established as $160,000? The fixed cost of buying and selling securities is$300 per transaction.

Answe...

## Related Questions in Financial Accounting - Others

• ### 7. Using Miller–Orr Slap Shot Corporation has a fixed cost associated with buying and selling...

(Solved) November 07, 2015

7. Using Miller–Orr Slap Shot Corporation has a fixed cost associated with buying and selling marketable securities of $40. The interest rate is currently .013 percent per day, and the firm has estimated that the standard deviation of its daily net cash flows is$80. Management has set

SPread = 3 * (3/4 * (Transaction cost * Variance) / Interest)^(1/3) = 3 * (3/4 * (40 * 80^2) / .013)^(1/3) = 736
• ### The management of the Book Warehouse Company wishes to apply the Miller-Orr model to manage its cash...

(Solved) November 07, 2016

that the variance of daily cash flows is $20,000. Book Warehouse’s opportunity cost of cash , per day, is estimated to be 0.03%. Based on experience, management has determined that the cash balance should never fall below$10,000. Calculate the lower limit , the return point, and the upper limit...

Calculate the lower limit, the return point, and the upper limit based on the Miller-Orr model of cash management. As per Miller-Orr model : Spread between the control limits =...
• ### Accounting - Exon Mobil

(Solved) June 28, 2015

stock were authorized and issued at the end of 2013? 2. How many shares of common stock were authorized and issued at the end of 2013? What is the par value per share? 3. How many shares of treasury stock did the company hold at the end of 2013? What was the average cost per share? 4. How many...

Using the annual report, answer the questions under the following sections. Complete your assignment in a Microsoft Word document. Part of your grade will be based on the structure and...
• ### 1. The following information is for MaScare Company. Physical Units Percent Completed Beginning work

(Solved) August 01, 2015

1. The following information is for MaScare Company. Physical Units Percent Completed Beginning work in process 102 units 65% Started and completed 793 units 100% Ending work in process 84 units 45% For the beginning inventory, the percentage given is the percentage that was already completed

1. The following information is for MaScare Company. Physical Units Percent Completed Beginning work in process 102 units 65% Started and completed 793 units 100% Ending work in process 84...
• ### Assignments 9-12

(Solved) February 26, 2014

sending attachment of assignments 9 -12 and an attachment of financial reports


text:
# The relationship between the complex exponential and trig functions?

I was reading this primer not the Fourier transform and it discusses an intuitive way to think about way to think about the $e^{-i\omega t}$ function. By picking a series of inputs for $\omega t$ and using Euler's formula to calculate the $\sin x$ function on the complex plane. Why is this?

• Because $e^{it}=\cos(t)+i\sin(t)$??? – David C. Ullrich Dec 26 '17 at 1:17

It comes from power series:

\begin{align} e^{i\theta} &{}= 1 + i\theta + \frac{(i\theta)^2}{2!} + \frac{(i\theta)^3}{3!} + \frac{(i\theta)^4}{4!} + \frac{(i\theta)^5}{5!} + \frac{(i\theta)^6}{6!} + \frac{(i\theta)^7}{7!} + \frac{(i\theta)^8}{8!} + \cdots \\[8pt] &{}= 1 + i\theta - \frac{\theta^2}{2!} - \frac{i\theta^3}{3!} + \frac{\theta^4}{4!} + \frac{i\theta^5}{5!} - \frac{\theta^6}{6!} - \frac{i\theta^7}{7!} + \frac{\theta^8}{8!} + \cdots \\[8pt] &{}= \left( 1 - \frac{\theta^2}{2!} + \frac{\theta^4}{4!} - \frac{\theta^6}{6!} + \frac{\theta^8}{8!} - \cdots \right) + i\left( \theta- \frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \frac{\theta^7}{7!} + \cdots \right) \\[8pt] &{}= \cos \theta + i\sin \theta . \end{align}

Why: you use the complex representation because it is more natural by an objective measure: the number of written operations in involved expressions becomes significantly less than if you were to do the dual component $\Bbb{R}^2$ rep.

So it's as if in elementary school they should be teaching us arithmetic in $\Bbb{C}$ at times because of its many applications.

Another reason: it's easier to work with exponentials than $\sin/\cos$. Nearly all trig identities are 10x easier to prove knowing some basic properties of $e^{it}$. Therefore the shortest path of proof to a lot of problems is by using the complex numbers.

The supposed mysteriousness of Euler's formula is overrated, and actually harmful if you want to get through the light and smoke and actually learn the basic math.

Euler's formula relates exponentials to periodic functions. Although the two kinds of functions look superficially very different (exponentials diverge really quickly, periodic functions keep oscillating back and forth), any serious math student would have noted a curious relation between the two -- periodic functions arise whenever you do some negative number-ish stuff with exponentials.

For instance --

• Simple harmonic motion -- the differential equation $F=kx$ represents exponential motion when $k>0$, periodic motion when $k<0$. This is just a special case of the idea that the derivatives of the trigonometric functions match up with what you'd expect from $e^{ix}$
• Negative exponential bases -- although exponential functions like $e^x$ and $a^x$ for any positive $a$ would seem to diverge nuttily at some infinity, it turns out that $(-1)^x$ is actually a periodic function, at least for integer $x$ (other negative integers give you a periodic function times a crazy diverging function).
• Conic sections -- Trigonometric functions are defined on the unit circle, if you defined similar functions on the unit rectangular hyperbola, you'll get linear combinations of exponentials.

There are others, based on trigonometric identities (I wrote a blog post covering some examples recently, see "Making sense of Euler's formula"), but the point is that this relationship is really natural, something you should expect, not some bizarre coincidence that arises from manipulating Taylor series around.


text:
# Chapter 1.2, Problem 1PQ

### Ciccarelli: Psychology_5 (5th Edit...

5th Edition
Saundra K. Ciccarelli + 1 other
ISBN: 9780134477961

Chapter
Section

### Ciccarelli: Psychology_5 (5th Edit...

5th Edition
Saundra K. Ciccarelli + 1 other
ISBN: 9780134477961
Summary Introduction

Introduction:

The science of general psychology is something beyond the intuitions and common sense. The study and the research of the human brain, mind as well as their behaviors are defined as the psychological science. Psychology by some people is believed to be the study of people and their behavior. Psychology is the scientific method of studying mental and behavior processes.

## Explanation

### Still sussing out bartleby?

Check out a sample textbook solution.

See a sample solution

Solve them all with bartleby. Boost your grades with guidance from subject experts covering thousands of textbooks. All for just $2.99 for your first month and only$4.99/month after? Done and done.

Get A's ASAP