text:
# Beamer TOC overlay: begin with only sections visible

In my Beamer presentation, I want to use overlays to uncover the TOC in the following manner:

1. Uncover all sections simultaneously

2. Starting with the first element following the first section, uncover them one-by-one, like using [pausesubsections,pausesections],

3. When arriving at an already uncovered section, do not pause on it (on the next slide, uncover the element following the section)

Is there a way I can do this?

Edit: Here is the output I'm looking for that corresponds to the MWE below. This shows how the TOC slide code should be translated into a series of real slides.

Slide 1    Slide 2    Slide 3    Slide 4    Slide 5    Slide 6    Slide 7

TOC title  TOC title  TOC title  TOC title  TOC title  TOC title  TOC title

A          A          A          A          A          A
A1         A1         A1         A1         A1
A2         A2         A2         A2

B          B          B          B          B          B
B1         B1         B1

C          C          C          C          C          C
C1         C1
C2

MWE:

\documentclass{beamer}
\begin{document}

\begin{frame}
\tableofcontents[pausesubsections, pausesections]
\end{frame}

\section{A}

\begin{frame}
some content
\end{frame}

\subsection{A1}

\begin{frame}
some content
\end{frame}

\subsection{A2}

\begin{frame}
some content
\end{frame}

\section{B}

\begin{frame}
some content
\end{frame}

\subsection{B1}

\begin{frame}
some content
\end{frame}

\section{C}

\subsection{C1}

\begin{frame}
some content
\end{frame}

\subsection{C2}

\begin{frame}
some content
\end{frame}

\end{document}

• please include minimal working example (MWE) in your questions. – user36296 Dec 17 '18 at 18:09
• Can you manually create slides that exactly show which sections should be uncovered on which slides? I don't think I understand your description, especially your 3rd point confuses me – user36296 Dec 17 '18 at 18:11
• @samcarter done. – Zubo Dec 17 '18 at 18:28

Based on the code from Manually creating a basic beamer toc you could fake a toc with such a behaviour:

\documentclass{beamer}
\setbeamercovered{transparent}
\usepackage{tikz}

\setbeamercolor{subsection in toc}{fg=black}

% total number of sections %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{totcount}
\newcounter{totalsection}
\regtotcounter{totalsection}
\AtBeginDocument{%
\pretocmd{\section}{\refstepcounter{totalsection}}{}{}%
}%

% number of subsections per section %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcntperchap}
\RegisterCounters{section}{subsection}
\newcounter{totalsubsection}
\setcounter{totalsubsection}{0}

% creating automatic label %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% based on https://tex.stackexchange.com/a/386557/36296
\AtBeginSection[]{\label{sec:\thesection}}
\AtBeginSubsection[]{\label{subsec:\thesection:\thesubsection}}
\newcounter{currentsub}
\newcounter{totsection}

% custom toc
\newcommand{\mytoc}{%
\pause%
\only<+>{}%
\begingroup%
\usebeamerfont{section in toc}%
\usebeamercolor[fg]{section in toc}%
\setcounter{totsection}{\number\totvalue{totalsection}}%
\foreach \i in {1,...,\thetotsection}{%
\setcounter{currentsub}{\ObtainTrackedValueExp[\i]{section}{subsection}}%
\par%
\begingroup
\usebeamerfont{subsection in toc}%
\usebeamercolor[fg]{subsection in toc}%
\ifnum\thecurrentsub>0%
\foreach \j in {1,...,\thecurrentsub}{%
\par%
}%
\fi%
\endgroup
\vfill
}% loop over i
\endgroup
}

\begin{document}

\begin{frame}
\mytoc
\end{frame}

\section{A}

\begin{frame}
some content
\end{frame}

\subsection{A1}

\begin{frame}
some content
\end{frame}

\subsection{A2}

\begin{frame}
some content
\end{frame}

\section{B}

\begin{frame}
some content
\end{frame}

\subsection{B1}

\begin{frame}
some content
\end{frame}

\section{C}

\subsection{C1}

\begin{frame}
some content
\end{frame}

\subsection{C2}

\begin{frame}
some content
\end{frame}

\end{document}


text:
# Rellich–Kondrachov theorem for traces

Let $W^{1,p}(\Omega)$ be the Sobolev space of weakly differentiable functions whose weak derivatives are $p$-integrable, where $\Omega \subset \mathbb R^n$ is a domain with Lipschitz boundary. Let furthermore $\gamma$ be the trace map.

I am looking for a theorem that allows me to conclude that $\gamma \colon W^{1,p}(\Omega) \to L^q(\partial \Omega)$ is compact whenever $q < \frac{(n-1)p}{n-p}$, thus e.g. for every $q < 4$ when $p = 2$ and $n = 3$.

(Necas, p103) has such a theorem in the necessary generality. I find the proof not very accessible, however. Another proof that I am aware of (Demengel/Demengel, p167) makes stronger assumptions on the regularity of the boundary ($C^1$ rather than $C^{0,1}$). Q1: Is such a theorem proved somewhere else in the same generality? Which source would you cite for said result?

Few books bother with the case of such embeddings as far as I can tell, most only consider embeddings of the type $W^{k,p}(\Omega) \to L^q(\Omega)$. Q2: Is that because the situation I am interested in is treated in the more general context of Besov spaces (which I am not familiar with) instead?

I have collected some more references for theorems of the Rellich-Kondrachov type here.

References:

Necas, Jindrich - Direct Methods in the Theory of Elliptic Equations.

Demengel, Françoise; Demengel, Gilbert - Functional spaces for the theory of elliptic partial differential equations.

• Thank you; I'll have to read up on a couple of things to understand that paper. The generalisation on the domain is certainly welcome. As for the name of the theorem: Once one identifies $\gamma(W^{1,p}(\Omega))$ with $W^{1-1/p,p}(\partial \Omega)$, the question of compactness of $\gamma$ becomes a question of the compactness of the embedding $W^{1-1/p,p}(\partial \Omega) \to L^q(\partial \Omega)$. In this sense, the theorem is of Rellich-Kondrachov type, if I am not mistaken. – anonymous Dec 19 '12 at 12:55

format: plain


text:
# The first four terms x, y, z, w of an arithmetic sequence

I have been attempting this question for the past 3 days with no luck:

The first four terms x, y, z, w of an arithmetic sequence satisfy x + y + z + w = 8 and xw + yz = -2. Find all possible values of x, y, z, w.

My attempt:

I know the key here is finding the difference between the terms but I am having a hard time figuring out how to find this. I tried:

y - x = d
z - y = d
w - z = d

I then substitue the second equation in to the first equation

y - x = z - y

I am actually not sure if this is the right method though because also I have thought about adding or subtracting all the equations together but I was not able to get a significant solution out of it. I just need a little guidance on how to find d the difference. Thanks for your time.

-

I would look for what symmetry can do for me. Let $d$ be the common difference, and let $m$ be the "midpoint," that is, the point halfway between $y$ and $z$. Let $d=2e$ (it is nice to avoid fractions).

Then $y=m-e$, $z=m+e$, $x=m-3e$, and $w=m+3e$. The sum is $4m$, so $m=2$.

The second equation says that $(m^2-9e^2)+(m^2-e^2)=-2$. Thus $2m^2-10e^2=-2$, and therefore $e^2=1$. It follows that $e=\pm 1$, and now we know everything. Two arithmetic sequences satisfy the equations, $(-1, 1, 3, 5)$ and its reverse $(5,3,1,-1)$.

Comment: We can let the first term be $a$, and the common difference $d$ (these are the usual names). Then we have $x=a$, $y=a+d$, $z=a+2d$, and $w=a+3d$. Substitute in our two equations. We get a system of two equations in the two unknowns $a$ and $d$, one linear and the other quadratic. The system is not difficult to solve, but the calculation is not as immediate as the symmetrical one based on $m$ and $e$. Symmetry is our friend!

-
+1 Symmetry is a powerful thing. –  Ross Millikan Oct 25 '11 at 4:22
I never would of thought to use symmetry on this. Another tool to remember for my toolbox. Thank you very much. –  Nic Young Oct 25 '11 at 19:04

i guess there would be a list of solutions... take the first term and the other consecutive would be written in term,s of the first term and the common difference... then on so;ving we get .. 37d^2 +(3a-96)d + 65=0....

-


text:
# A cake for your cherry: what should go in the C++ standard library?

Over the past few years there has been a push to include a graphics library into the C++ standard. It would be something a bit like cairo. Or SDL. The proposal, in its current form, is here

In its current state, the library proposal can draw some shapes on a pre-allocated surface, has some support for images, and there are of courses projects to add text, maybe some input in the form of mouse / keyboard handling.

The primary goal of the library seems to be teaching. The argument put forward is that it’s cool and ludic for kids to have pretty blinky pixies on screen. Of course there already exists libraries to do that and more, but you see, C++ has no decent, idiomatic package manager, so, of course the conclusion was reached by some prominent committee members that the C++ standard should offer a 2D graphics library, out of the box.

I do think this is a path that should not be pursued and that doing so would be, at best, a waste of time. Let me tell you why.

#### But, first, some needed clarifications

Guy Davidson and others have, on all account, put a great amount of work, time and energy in that proposal. The people pushing for that proposal to be rushed through standardization are way more experts than I will ever be.

I did not contribute anything to C++ so what will follow are just the opinions of one guy.

I also want to make clear that I do not have a negative opinion of that particular library. My issue is with the inclusion of a 2D painting library, any painting library in the C++ standard, at this point in time.

I hope I won’t be misconstrued

Anyway, let’s get to it.

### The C++ Standard Library is not a library

The C++ Standard is exactly that: A well specified document that describes in the most detailed and unambiguous possible way what C++ is, and how it works. The goal being that anyone can implement a C++ compiler for themselves by implementing that specification. However, it happens that the specification is not specific enough, or implemented not quite properly, or implemented opinionatedly and so various C++ compilers end up having some slight differences of behavior from one implementation to the next. Sometimes it cannot be implemented at all because the people doing the implementation and the people doing the specification forgot to talk to each others.

Now, a big part of that specification describes the Standard Template Library, a library that ships with every conforming compiler.

There exist at least 5 implementations of that specification, maintained by as many entities. Some are open source, some are not. They each work in a select subset of platforms and system. And even if they sit at the very bottom of about any C++ program, they are, like any other library , subject to bugs.

In this context, what should, or should not be included in the C++ standard library is a very important question. What should come as standard bundled with the compiler? What do most people need to be productive with C++ ?

Guy’s article describes the positions one can have. Maybe we need about nothing ? Maybe we need some vocabulary types ? Maybe containers ? Maybe not ? Do we need filesystem support ? sockets ? json ? xml ? rpg making tools ? sql ? html ? javascript vm ? 2d graphics ? 3d graphics ? soap ? IPC ? windowing ? Should $\pi$ be defined ? What about websockets ? ftp ? ssh ? VR ? AR ? crypto ? ssl ? Do we need ssl but no other crypto ? Deep learning ? Sound ? 3d sound ? Video Decoding ? gif ?

Clearly we need to draw a line.

Somewhere ?

Where ?

Let’s look at .Net. Or Java. When the STL is mentioned, comparing C++ and Java is customary. Java is cool, right? It has sockets and HTTP and crypto and everything, basically.

But Java is mostly maintained by a single entity. So someone at Oracle decides Java should have sockets and they implement it, there are internal reviews and now Java has Sockets. Sometimes later, Google want to have sockets using the same API, and before they can say “Ahead of time”, they are sued for 9 billions USD.

Meanwhile, the C++ specification undergoes a long, painful process until there is a vote and there is a majority consensus on every single feature, every single method. Should that be called data? get? “At Bloomberg we have experience using data on our 2 millions line code base” will say the guy working at Bloomberg. “We noticed it’s faster to use type get on EBCDIC keyboards” Will object the guy at IBM. “And we have a 3 millions lines code base”.

I don’t have an opinion on which model is best. Benevolent dictatorship obviously only works if the dictator is benevolent.

However, I will argue that democracy is unfit to the birth of a good graphic library.

### The Committee Resources are limited

Even if sleep deprived proposal authors sweat blood, a big part of the work and the voting takes places in week-long quarterly meetings where people go through an ever growing pile of proposals. As the committee learn to be more transparent, more people contribute, leading to more work for people attending. There is little to no money in that work. At best you can hope for someone to pay you the plane tickets to the beaches of Florida, the green hills of Switzerland or the pools of Hawaii at which the meeting happen. You will reportedly never see neither the beaches, the hills nor the pools.

And because resources are limited and time is limited there is a need to sort, prioritize and even discard proposal. Directions for ISO C++ attempts to describes how that sorting and prioritizing should happen.

The question then becomes : can the committee spares the time to work on a 2D graphics library and is that a priority ?

In its current form, which is limited to drawing shapes, the proposal is about 150 pages long. It’s one of the biggest proposal submitted for the next meeting.

It can only grow bigger. There is no end to the complexity of a “small and simple graphics library”. Every second spend on that proposal will not be on some other work. Of course people discuss proposals they have an interested in and discussions happen in parallel. Still. There is maybe one person in those meetings for every 200’000 c++ developers.

### Let’s draw a triangle

A 2D graphics is the complete opposite of what the Standardization process is good at. Standardization is all about formalism, so it works best at describing formal things, Math, Algorithms. The more reality gets messy, the more it’s hard to describe it put it on paper and have that paper serves as source of Truth for decades.

The first thing one need to do play with pretty pixes is to get a “surface”. A canvas where pixels get drawn.

So hopefully you have a surface class to which you give dimensions and that gets you a canvas on which to paint.

But wait. On most desktop systems, if you want a surface you need to put it in a window. It’s customary for windows to have titles so a graphics API should probably handle that, right ?

You probably also want the window to have an icon. An icon is a file on most system, the format of which is system specific. But sometime it’s not a path, it’s a name corresponding to a path.

The size of a window can change during the execution of the program on some desktop operating system.

Sometimes the window can be moved to another screen that has another resolution. And there is this weird new screens where there are virtual pixels that are bigger than true pixels ? Unless you are rendering an images or something then you should make sure you uses all the power of the small crispy pixes since the customer paid a premium for boasting about how crispy his screen is.

That woman over there was jealous so she bought a TV with 40 bits per pixels. You can’t really see the difference but are you going to tell her she wasted 5000 bucks ?

And then there is a screen in your pocket and IT ROTATES in all the directions and now the surface is all wonky. But it has no window so it has no title or icon.

What time is it ? OH GOSH THAT THING HAS A SCREEN TOO BUT IT’S SO SMALL… Better go and read a book WTF ELECTRONIC INK that you should refresh as little as possible and that only is black ?

World is crazy, right ? Let’s stick to Linux, shall we? So on Linux there is this thing called X11 which you request a surface to… oh sorry, while you are writing the paper X11 is being deprecated and now you should use Wayland… unless you rather have a frame buffer? It can be accelerated using opengl. or embedded opengl. totally different thing. But really, Vulkan is faster than both these things. Oh and on this system we prefer that you draw the windows yourself, there is a war raging on about CSD vs SSD it has been going on for years and you can’t take side.

And if you have CSD please make sure that I can drag the windows properly and I have set up sticky corners so that the windows can be aligned nicely. Make sure to handle them. Properly. And when you drag the window it should be a bit transparent, you know about windows compositing right ?

Okay so, you start to tell yourself that maybe drawing stuff is complicated. Let the implementors compiler writers and library vendors deal with all that crap. So you provide an API that works everywhere, so it handles absolutely nothing, which is to say it works nowhere.

Now the compiler writers are a bit pissed. All they wanted in life was to write compilers and there they are, trying to understand how GDI work. Plus Microsoft is maybe not really interested in providing a drawing framework, they rather have their users use the WinRT xml-based tools. Meanwhile the GCC guys are still trying to have std::thread work on windows.

Clang people get bug reports that “it doesn’t work”. People have expectations that the STL will work perfectly, consistently, anywhere

No problem. We will make the graphics library optional. So now there are bits of the Standard Library that are not standard. If and when they are implemented, they don’t behave quite the same on every platform. So now the code written using standard tools is not portable. So we need to have a copy of the STL in the repository along with messy build scripts. Back to square one.

Maybe we messed up somewhere? Let’s look at what exists on Internet. People have displays so surely they do write libraries for them, right ?

Turns out Qt is pretty popular. It does a lot more than displaying triangle though. It was released in 1995. It has strings, threads, tons of stuffs. People really did not came up with anything better since ?

wxWidgets is even older. It too has strings and threads and a lot of things that don’t have business being in a graphic library. GTK is the exact same thing.

But C++ goals are more aligned with things like SDL. Released in 1995 with threads and strings and weird things. Allegro, released in 1990. Same thing

You look at other languages. Surely the Rust community has an awesome painting framework, right ? Or the Go people ? Turns out they write wrappers around Qt, or SDL or something, like they deemed to complicated to start from scratch.

So 20 years later you manage to draw a triangle on all platforms. For some definition of all.

It’s quite the achievement, so you want to share your joy with the world. People communicate mostly using languages [citation needed] so you are going to display some words on the screen, how hard can it be to go from a triangle to that ?

#### void draw_text(std::point2d, std::string);

You learn that there is a standard called “Unicode” that describe all the letters people around the world use. So many letters. The Unicode standard is about 10 times the size of the proposal you have been working on for 5 years. Fortunately most programming languages have backed in support for at least parts of Unicode. Except C++. Well, okay let’s put that aside for now.

So text is rendered using fonts. The fonts are often installed on the system. There is that thing called a font database that tells what the font are. Unless the systems has no font database. Or no fonts. Or no system. People also like to use their own fonts.

A font is a file, whose format is standard. There are 5 or so competing standards.

A font file can contain glyph tables, PNGs, SVGs, scripts executed in a virtual machine, a mix of all that. Some fonts have color, but not all people like colors. Your children like colors. They sent you a 🐈. You will add support for cats, right ?

You learn about subpixel rendering. You spend a few months in jail for patent infringement. You figure you can use that time to learn about ligatures in the encyclopædia. You start regretting being a developer and consider a new career as a monastic scribe.

There is a lot of math involved in font rendering so you pick up a mathematics book written a dead guy called AL-Khwarizmi. You realize everything is written from right to left. How does that even work ?

So maybe the optional 2D graphics library should have optional text support ?

At the next committee meeting in Toronto ( Hawaii sank in the ocean long ago), someone is trying to write a complex graphic application with network and lots of input and to avoid spaghetti code they like to have some kind of event loop with maybe some threading. It’s a theoretical concern obviously as there is no input support. Consensus was never reached on how to name the keyboard keys.

You think back on all the existing framework like Qt, now on version 8.0, that provide an event loop, a message passing system and a Unicode string type. Maybe they were up to something.

During all this time, people continued using Qt. People were hired for knowing Qt. They used it in their school projects. Of course Qt still sucks because the C++ reflection features that got added in the standard were never quite enough to replace their code generator. But people don’t care that its sucks. People who do use QML. Or Electron.

Having not displayed a 🐅, let’s go back to 2018.

### Has the committee anything better to do anyway ?

To be considered, a proposal has to be written and put forward, and the library proposal exists because someone put a lot of work in it.

However, currently, C++ has

• Poor threading support ( no executors or facilities to use coroutines )
• No support for launching processes
• No support for Unicode
• Poor I/O facilities
• Poor locale facilities
• No support for dynamic loaded libraries
• No HTTP support
• Nothing crypto related

The list, of course goes on. I don’t know what is a good candidate for a C++ library, but, according to the committee itself, a library proposal should

• Be useful to most people
• Have a stable API that isn’t too subject to frequent change
• Have real world experience and feedback. That’s why most C++ library started their lives as boost library.

Proposal are often dismissed from the get go for not being useful enough or not being battle tested enough. Which is reasonable given the expectation people have regarding the stability of the STL but then those criteria should apply consistently.

And of course there are a lot of languages features that are still in the pipelines after years and years of work, and they should take priority over library features since pure library addition can be polyfilled by boost or other.

### The teaching argument

One of the argument put forward for the inclusion of that library is that it would make C++ more teachable and that people are more interested in graphics-based projects.
I sympathize and fully agree with the goal of making C++ more teachable. However, there is a difference between making sure a given feature is teachable and adding a major feature to the language with the primary goal of being used in classrooms.

Teachability implies easy to use, hard to misuse, and a sane mapping between a concept and its implementation, and generally behaving accordingly to the expectation of the majority of users. Quality that should be looked for in any new feature.

It is also to be expected that some features are targeted to advanced users, library writers and experts.

However, the “teaching friendly part” of C++ should be a subset of the features used in a professional settings rather than a different set.

I would prefer that people learn to use Qt (for example) as that is a skill they can use in their professional careers, rather that something dedicated to teaching purposes.

I also think that a library whose scope is too limited may give a bad image to the language. If people are told that they can’t draw emojis or gifs or use a gamepad, they may end up thinking that C++ is not powerful enough and switch to another language like C#, java, javascript, swift… But if they get to use an existing, battle tested framework, that is powerful enough to let them implement their design (Qt, SDL) even if the code isn’t “modern”, they will get a better grasp of what c++ can and does do.

In other words, I’m afraid that if people are introduced to a toy library, they will think that C++ is a toy language.

Beside, “Teaching” needs to be better define.

Are we talking about middle schoolers? And if so, is teaching them C++ a good idea ? In some cases Python, Javascript, Lua are more suitable, easier to grasp choices. I think that’s okay.

Are we talking about college CS 101 ? In this case, it’s probably desirable to introduce students to build systems, libraries and package management. tools are important. And in my experience, a lot of juniors developers don’t know how to use their tool and that’s as important as knowing languages. It’s also important that people know and are taught the ecosystem. Qt, boost, wxwidgets, SDL…

### The “We need a standard library because using third party libraries is hard” argument

I think most people agree on that. Including a library in a C++ project is a bad, often painful experience. Investing a lot of resources on a 2d graphic library don’t solve that problem. Unless every single library that exist or will exist gets folded into the standard, so, where do we stop ?

And I’m sorry to say, things won’t improve on their own, it’s just not possible. The number one requirement for a package manager of any sort is to be authoritative. It doesn’t even necessarily need to be good. But until individual entities are left to deal with the issue, we will continue to have myriad of incompatible, half backed tools. I understand that the committee prerogatives don’t necessarily extend outside the definition of the language and therefore the issue of package management may not be solvable. But tools, not UI is the big challenge that C++ must tackle.

Note that there are ways the committee can help improving tooling without extending its prerogatives, notably:

• Finding ways to supersede all reasonable uses of the preprocessor ( the work on reflection / code injection is very important for that )
• Defining a portable C++ ABI (N4028)
• Defining a portable module representation

Sure, these works may not be as glamorous as a 2D API, but they are more fundamental, and more importantly, can’t happen independently of the committee.

### Things should move forward, somehow.

After looking at P0939 and P0267, I wanted to share my wishes for work to be done in related areas. Of course, I’m not in a position of doing more than wishing and I can only hope to inspire someone ! But I’m interested in what you think is important in those areas !

#### Take the Unicode bull by the horns

I would not have suggested that, as I understand why C++ lacks Unicode but if we are seriously considering 2D graphics, then we absolutely need to have proper Unicode support.

• A first step is the char8_t paper . Of course that is not sufficient, but it is necessary.
• We need a set of algorithm to normalize, compare, sanitize and transform Unicode strings, count characters. Something range-based could work nicely
• class of characters, Regexps… We might not need as many features as ICU but we do need some. That could be a <unicode> header. I’m not certain that proper Unicode support is a goal aligned with the constraints outlined in P0939, however it would be beneficial to any application dealing with user input/output, including GUI, databases, (web) server, console application…

I don’t know if we can qualify Unicode strings of vocabulary type but handling the world languages is certainly something everybody needs and it would be easier if there was a universal, idiomatic tool to do that.

#### Add geometry primitives to the standard

It could be interesting to extract the vocabulary types introduced in p0267 and standardize them independently of graphics. Types like point_2d , matrix_2d ( and eventually point_3d, matrix_3d ) are useful for graphics but may have other use, for example scientific computation, plot manipulation. They could be accompanied by a set of methods to perform widely used analytic geometry computation. All of that could live in a <geometry> header.

There are multiple reasons why this would be beneficial

• It’s something every library dealing with painting or surfaces need SDL_Point, QPoint, wxPoint. Converting from one type to the other is cumbersome, error prone. All these frameworks could benefit from speaking the same language in the same coordinate system. It’s the definition of a vocabulary type.
• It’s guarantee to stand the test of time. Math are not affected by new technology trends and as such the API would remain stable for decades.
• For the same reason, it would be probably be easy to reach consensus, it’s hard to bike-shed basic maths.

#### Help improving existing graphics library

What can be done by the committee to improve Qt, wxWwidgets SDL and other graphics frameworks ? It turns out a lot of frameworks rely on boiler plate code that is either generated by extensive and invasive use of macros or through a code generator. Reflection and code injection are fundamental to the modernization and betterment of these frameworks, and this is fundamentally a language feature that should take priority over purely library work.

### Let grow the Graphics proposal on its own

Maybe we do need another graphics framework. Who am I to say otherwise ? But existing framework have been battle tested for 20 years. I think the 2D graphics could thrive and grow as an independent or boost library over the next few years. Most importantly, it could provide a single implementation working on a wide variety of platforms rather than having 5 implementations or more of the same thing.

It would be free to experiment with text rendering, inputs, events, back-end, threading models…

I feel that this proposal as well as the package management issue calls for something that is authoritative without being ISO and I have no idea what that could or should be.

In the mean time, Visual Studio and Xcode could ship with more third party libraries and that would solve at least half of the issues that this proposal is trying to solve.


text:
# Is there an electrolyte that will halt the production of Hydrogen in water electrolysis?

Care must be taken in choosing an electrolyte, since an anion from the electrolyte is in competition with the hydroxide ions to give up an electron. An electrolyte anion with less standard electrode potential than hydroxide will be oxidized instead of the hydroxide, and no oxygen gas will be produced. A cation with a greater standard electrode potential than a hydrogen ion will be reduced in its stead, and no hydrogen gas will be produced.

From what I understand, that bit states that certain electrolytes will stop the production of hydrogen gas and only oxygen gas and whatever gas from the electrolyte will be produced.

So I have two questions:

1. What are some electrolytes that will stop the production of hydrogen gas in water electrolysis?
2. What kind of water will be left behind if distilled water and an aforementioned electrolyte runs through electrolysis until all of the oxygen has been exhausted from the solution?

Please correct me if I'm misunderstanding anything.

The reduction of hydrogen is what the reduction potential of every other reduction potential is based off of, so:

$$\ce{2 H+_{(aq)} + 2e^{–} ->H2_{(g)}}~~~~~\Delta E^{\mathrm{o}}=0\,\mathrm{V}$$

So if a species has a has a reduction potential $>0\,\mathrm{V}$, then it will be be reduced before the naturally occurring $\ce{H+}$ ions are (these exist in solution due to the auto-protolysis of water, $\ce{H2O -> H+ + OH-}$, thereby not producing any $\ce{H2_{(g)}}$.

If your goal is to produce $\ce{O2_{(g)}}$ from the oxidation of $\ce{OH^{-}_{(aq)}}$, the reaction for this is:

$$\ce{4OH^{−}_{(aq)} -> O2_{(g)} + 2 H2O_{(l)} + 4 e^{−}}~~~~~\Delta E^{\mathrm{o}}=-0.401\,\mathrm{V}$$

Similarly, if a species has a has a oxidation potential $>-.401\,\mathrm{V}$, then it will be be oxidized before the $\ce{OH-}$ ions, thereby not producing any $\ce{O2_{(g)}}$.

Wikipedia has a rather comprehensive standard reduction potential table, so use that to compare the reduction potential of ions. Choose your salts wisely!

To answer your other question, if this reaction continued indefinitely, a very acidic solution would result, as for every $\ce{OH-}$ that is oxidized, a $\ce{H+}$ is left in solution. Once all of the other cation from the salt is reduced, however, the $\ce{H+}$ would then start being reduced, producing $\ce{H2_{(g)}}$.


text:
Browse Questions

Which of the following is a chain growth polymer?

$\begin {array} {1 1} (a)\;Nucleic\: acid & \quad (b)\;Polystyrene \\ (c)\;Protein & \quad (d)\;Starch \end {array}$


text:
# Blog

## Fractional Calculus

Calculus is the manipulation of one basic operator: the derivative or $\inline&space;\frac{\mathrm{d}&space;}{\mathrm{d}&space;x}$. This operator operates on functions and by repeatedly applying it, you can get higher order derivatives. It’s inverse operator is known as the integral. Similar to matrix operators which have eigenvalues and eigenvectors, this operator also has eigenvalues and eigenfunctions. The eigenfunction is the function which only goes through some scalar change when acted on by the operator. This scalar that the function is scaled by is called the eigenvalue of the eigenfunction. For the derivative operator, Continue reading Fractional Calculus

## Space Transforms

Functions have the ability to be described in terms of the infinite summation of other functions with a common example being polynomials using Taylor series as shown below.

$f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{n!}(x-a)^n$

However, functions can also be described in terms of trigonometric functions using the Fourier series Continue reading Space Transforms

## Probability Distribution Transformations

Random number generators generate random numbers that tend to follow some kind of distribution. Uniform number generators generate a random number between 0 and 1 with equal likely hood everywhere in the range, Gaussian generators generate numbers that have higher probability to be near zero, etc. These distributions are given functions ($\inline&space;p(x)=1$ for uniform or $\inline&space;p(x)=e^{-x^2/2}$ for Gaussian). In order to calculate the probability that any number generated will fall in the range $\inline&space;[a,b]$, one would take the integral $\inline&space;\int_{a}^{b}p(x)\textup{d}x$. The probability to get a specific number $\inline&space;x$ would be $\inline&space;p(x)\textup{d}x$ which is just 0. Continue reading Probability Distribution Transformations

## On Conservation

Conservation of different properties in nature immensely simplifies calculations to the point where some are impossible without the consideration of them. In some cases, it seems completely intuitive and impossible not to consider. However, not only are there many conservations laws unknown to many but there are also, in some sense, “violations” to these laws. Continue reading On Conservation

## Strong Force and Nuclear Binding Energies

Forces come in various forms in nature but the nature of the strong force is very peculiar in that it does not create an attraction or repulsion between any two entities. It uses mass energy as a way to create a potential energy well. This is done by the following. Continue reading Strong Force and Nuclear Binding Energies

## Quaternions

Many are familiar with the idea of imaginary/complex numbers but in 1843, Hamilton invented hypercomplex numbers. Initially, he created three components such that they had the form $\inline&space;a+bi+cj$ where $\inline&space;j^2=-1$. This however raised a problem when multiplying complex numbers. Continue reading Quaternions

## The Lagrangian

There exists a mathematically different approach to describing classical mechanics than what is usually taught. While it is usually taught using laws like $\inline&space;F=ma$, conservation of energy, and conservation of momentum, there exists a more mathematically elegant and, in some sense, more fundamental way of describing the motion of objects known as Lagrangian mechanics. It is used throughout engineering and physics to solve problems that are too complicated or impractical to solve using classical methods. Continue reading The Lagrangian


text:
# How do I interface a low power controller with a higher power load?

I am not an electrical engineer (rather a photonics engineer), so I am looking for some direction on how to attack an issue I have.

Basically, I need to drive a 150 Ω load with a computerized controller. The controller I have (a National Instruments I/O device) produces a series of voltage step functions over time, but it's not rated up to the current and power that I need at my load.

What do I need between the controller and the load to fully power the load, without damaging the controller? And of what flavor, like common emitter, voltage follower, etc.?

Note: Precise multiplication of the input signal is not necessary, as the controller can be easily calibrated to account for any incidental offsets. (In fact, Vin does not need to equal Vout.) And fast switching is also not necessary.

Thanks!

• Buy a laboratory amplifier. Why is is that you want to build this part of your equipment? Jun 22 at 11:18

The obvious solution (to an engineer in this field) is an emitter follower:

simulate this circuit – Schematic created using CircuitLab

For reasons I explain below, that solution has some failings. You could have found this answer on a thousand different web sites, so I presume it's not good enough. I propose a simple enhancement, with the addition of an op-amp:

simulate this circuit

Here are the things you should know about it:

1. The voltage at OUT equals the voltage at IN, to within a few millivolts. There's no voltage attenuation or gain. There is however a maximum output voltage: Here you can see that maximum output potential is 7V. It has two causes; firstly the op-amp U1 (a cheap LM358) is unable to get its output all the way to the positive supply of 8V. Op-amps exist that can do much better (like the TLC2272), and this application could use either. The second cause is the voltage $$\V_{BE}\$$ dropped from base to emitter of Q1, which will be about 0.7V.

2. Increasing the power supply above 8V will raise that upper limit imposed on the output, so you may use any power supply, up to the op-amp's limit of 32V. However, Q1 will dissipate more power. See note 5.

3. Q1 is a common collector "emitter follower". Its purpose is to relieve the op-amp of any appreciable load, and take on the task of current provision itself, sourced directly from the power supply instead of the signal source.

4. An emitter follower might be all that's needed, but that drop from base to emitter of $$\V_{BE} \approx 0.7V\$$ is appreciable, and will vary slightly as load current and temperature changes. It will also differ from transistor to transistor. The addition of U1 linearises and equalises the input-to-output relationship. Note the negative feedback from overall output to inverting input. All I've done here is to make a regular "voltage follower", but with an extra current gain stage inside the feedback loop, compensating for $$\V_{BE}\$$ (and any variation in it), and rendering it moot.

5. Transistor Q1 is going to dissipate power, because its role is to "waste" whatever voltage the load doesn't need. This is true whether it's on its own (as in my first circuit above) or part of a closed loop (used with an op-amp). Since current through Q1 and the load is about equal, the product of wasted voltage and current is the power it will have to consume. Here's a graph of the power in Q1 for the same sinusoidal input shown above: It peaks at just over 100mW, which means Q1 will get warm, but that's well within its capabilities. Here's a graph of power dissipated by Q1 using a power supply of 15V: This peaks at just under 400mW, which is getting close to the limits of what a small transistor like this can tolerate without a heatsink. If you do decide to use a power supply over 15V, you should use a beefier transistor, like a TIP31.

6. You should take care not to take IN beyond the power supply voltage. That is, don't allow your signal source to exceed 8V, or whatever the power supply voltage (to the op-amp ) is. The behaviour of the op-amp is not defined for that condition. There are some measures you can take to ensure this never happens, such as attenuating the input signal with a resistor divider:

simulate this circuit

Resistors R2 and R3 attentuate the potential at IN: $$V_X = V_{IN} \times \frac{R_3}{R_2 + R_3} = V_{IN} \times \frac{10k\Omega}{10k\Omega + 8.2k\Omega} = 0.55 V_{IN}$$ This has the effect of bringing the full 10V input down to 5.5V, other values being similarly scaled. This is the new input and output relationship:

• Wow. Thank you for the excellent response. It's clear and detailed. Very useful. Thanks! Jun 24 at 17:59

With a 150 Ohm resistance, that is pretty easy to buffer with a low impedance voltage driver that can drive 40 mA with low saturation limits on supply. some Op Amps can do this, but if you are flixible on inputs any 1A NPN emitter Follower will work. But heat dissipation in device is not the load power but the difference between supply and output V times current.

Essentially you need to lower the output impedance of your voltage driver from 10V/10mA= 1k to <<10 Ohms. This is easily done with an emitter follower with a large case size to keep only warm to touch with high Beta current gain and collector to 6V limiting input to 6V for a 5.3V output or use 6.2V to get 5.5 output. A Beta of 100 is minimum needed to reduce 1k to 10 Ohms, higher the Beta, the better tracking of input voltage changes with a 0.7V approx offset.

There are many more precise ways with current sensing and error feedback but this is the simplest. the NPN must be rated for >1A and not short circuited.

Assuming you have some steps between 0 & 10V with a 1k source resistance, here is an attenuation and Beta = 100 voltage follower simulation to produce 0 to 5.5V output into 150 ohms BUT using 1 to 10V input.

• Great. Thanks a lot for response. Excellent points made and taken. Really appreciate it! Jun 24 at 18:01


text:
# Coulomb's Law, Charges and Acceleration

## Homework Statement

An electron is fired at 4.0 e+6 m/s horizontally between the parallel plates as shown, starting at the negative plate. The electron deflects downwards and strikes the bottom plate. The magnitude of the electric field between the plates is 4.0 e+2 N/C. The separation of the plates is 2.0 cm.

a) Find the acceleration of the electron between the plates?

b) Find the horizontal distance traveled by the electron when it hits the plate?

c) Find the velocity as it strikes the plate?

## Homework Equations

a = qE/m
F = qE
d = xi + yi ∙t + ½ ∙ a ∙ t²

## The Attempt at a Solution

I've read the chapter a few times and I think this is right but I want to make sure I haven't made a careless error, Please and thank you for your help!

a) 7.0 e¹³ m/s²

b) This is the one I'm not sure about...

d = xi + yi ∙t + ½ ∙ a ∙ t²

d = 3.5 e¹³ m/s² ∙ t² + 0 + 0 = 2e-2 m

t = √ 2e-2 / 3.5 e¹³ = 2.4 eˉ⁸ s

d = 4.0 e⁶ m/s ∙ 2.4 eˉ⁸ s = 9.6 eˉ² m

c) ...and this...

v = yi + a ∙ t

= 0 + 7.0 × 10¹³ m/s² ∙ 2.4 × 10ˉ⁸ s

= 1.7 × 10⁶ m/s

Thank you for your help :)

BvU
Homework Helper
Hi. a OK, b method looks good, numbers look good too (except rounding off -- I get 9.5 10-2 m).
I would use the 10 instead of the e to avoid any possible misunderstanding.

In part c I wonder what happened to the original 4 106 m/s

julianwitkowski
Hi. a OK, b method looks good, numbers look good too (except rounding off -- I get 9.5 10-2 m).
I would use the 10 instead of the e to avoid any possible misunderstanding.

In part c I wonder what happened to the original 4 106 m/s

Thank you... I'm checking over that, but one thing I'm curious about is why the time is not = √ (2 ⋅ 2 ⋅10-2 / 3.5⋅10¹³) = 3.3⋅10ˉ⁸ s

BvU
Homework Helper
You already used the 2 to divide the 7 and got 3.5. Nice way to confuse yourself.... :)

You already used the 2 to divide the 7 and got 3.5. Nice way to confuse yourself.... :)
ya :/ .. ha

I get 9.5 10-2
Thanks! I see that I apparently got the time wrong, it's 2.3 not 2.4 ... :) But now I get 9.2E-2 instead of 9.5E-2 ?

I'm gonna try a different calculator.

wolfram t = 2.39 ... and I got 0.0956 ... So being as how I hate significant digits I still don't know the best judgement call in situations like this, should I ignore the 6? I think I should I guess because the question gives 2.0 and just to clarify this, the 0 in 2.0 is a significant digit right? I think I heard this does not count as a place holder 0.

In part c I wonder what happened to the original 4 106 m/s
Glancing over this ...

Last edited:
BvU
Homework Helper
Code:
[FONT=Courier New]
9.10900E-31    kg           m

1.60200E-19    C            e

400            N/C          V

7.0348E+13     m/s2         a = e*V/m

0.02           m            d

5.6860E-16     s2           2*d/a

2.3845E-08     s            sqrt

4.00E+06       m/s          v

9.538E-02      m            v*t[/FONT]

julianwitkowski
In part c I wonder what happened to the original 4 106 m/s

Ok about this I'm a bit confused, wouldn't the final velocity be acceleration * time ? Or is your comment in reference to how the electron lost a lot of velocity.?

BvU
Homework Helper
Neither nor.

For part c the exercise asks about the velocity as it strikes the plate. You forgot the horizontal component 4000000 m/s, vertical component a * t indeed.
But you might want to turn that into a magnitude (and perhaps an angle if that's needed -- I normally interpret velocity as a vector, speed as a magnitude)

julianwitkowski
Neither nor.

For part c the exercise asks about the velocity as it strikes the plate. You forgot the horizontal component 4000000 m/s, vertical component a * t indeed.
But you might want to turn that into a magnitude (and perhaps an angle if that's needed -- I normally interpret velocity as a vector, speed as a magnitude)
Got it, thanks again for the help :)


text:
(It reduces to lim f / g = 1 if f and g are positive real valued functions.)   The Intuition of Big O Notation We often hear the performance of an algorithm described using Big O Notation. O stands for Order Of, so O(N) is read “Order of N” — it is an approximation of the duration {\displaystyle f(x)=\Omega _{+}(g(x))} Usually, Big O Notation uses two factors to analyze an algorithm: Time Complexity—How long it … → ( {\displaystyle \ll } x On the other hand, exponentials with different bases are not of the same order. [13][14] In TeX, it is produced by simply typing O inside math mode.  O x If c is greater than one, then the latter grows much faster. {\displaystyle ~f(n,m)=1~} Algorithms, such as the linear search, which are based on a single loop to iterate through each value of the data set are more likely to have a linear notation O(N) though this is not always the case (e.g. ( Similarly, logs with different constant bases are equivalent. As a result, the following simplification rules can be applied: For example, let f(x) = 6x4 − 2x3 + 5, and suppose we wish to simplify this function, using O notation, to describe its growth rate as x approaches infinity. For example, 2x is Θ(x), but 2x − x is not o(x). Gesell. This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. {\displaystyle f} ( {\displaystyle \Omega } ≪ {\displaystyle \delta } {\displaystyle f(n)\leq Mg(n){\text{ for all }}n\geq n_{0}.} ! L ) > (See example blog post on hashing algorithm for memory addressing). x to increase to infinity. . {\displaystyle O(n^{c+\varepsilon })} n We don’t measure the speed of an algorithm in seconds (or minutes!). = In this case the algorithm would require 100 iterations to find it. L = in memory or on disk) by an algorithm. ) {\displaystyle \preccurlyeq } So, yeah! ) g {\displaystyle \Omega } Neither Bachmann nor Landau ever call it "Omicron". . f In their book Introduction to Algorithms, Cormen, Leiserson, Rivest and Stein consider the set of functions f which satisfy, In a correct notation this set can, for instance, be called O(g), where, The authors state that the use of equality operator (=) to denote set membership rather than the set membership operator (∈) is an abuse of notation, but that doing so has advantages. The notation T(n) ∊ O(f(n)) can be used even when f(n) grows much faster than T(n). Using Big O notation, we can learn whether our algorithm is fast or slow. and Vol. and x But when talking to other people, developers especially, there is a way to describe this time complexity using the big O notation. ( Thus, we say that f(x) is a "big O" of x4. While there are other notations, O notation is generally the most used because it focuses on the worst-case scenario, which is easier to quantify and think about.   . ) ∞ This is what I got: O(n + logn + 1) I am very unsure about my answer because I only know how to find time complexity with for loops. {\displaystyle O(n^{2})} • Big O is represented using an uppercase Omicron: O(n), O(nlogn), etc. What Big O notation doesn't tell you is … ( Even if T(n) = 1,000,000n2, if U(n) = n3, the latter will always exceed the former once n grows larger than 1,000,000 (T(1,000,000) = 1,000,0003 = U(1,000,000)). but {\displaystyle \ln n} {\displaystyle k>0} 2 ) , The Big-O Notation. finding a user by its username in a list of 100 users). Suppose an algorithm is being developed to operate on a set of n elements. instead.[15][16]. The digit zero should not be used. in memory or on disk) by an algorithm. 0 This notation is often used to obviate the "nitpicking" within growth-rates that are stated as too tightly bounded for the matters at hand (since logk n is always o(nε) for any constant k and any ε > 0). If f(n) represents the computing time of some algorith… In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial. {\displaystyle f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)} Additionally, the number of steps depends on the details of the machine model on which the algorithm runs, but different types of machines typically vary by only a constant factor in the number of steps needed to execute an algorithm. m The mathematician Paul Bachmann (1837-1920) was the first to use this notation, in the second edition of his book "Analytische Zahlentheorie", in 1896. 2 So, O(n) is what can be seen most often. Consider, for example, the exponential series and two expressions of it that are valid when x is small: The second expression (the one with O(x3)) means the absolute-value of the error ex − (1 + x + x2/2) is at most some constant times |x3| when x is close enough to 0. = {\displaystyle \Omega _{L}} {\displaystyle ~{\vec {x}}~} American Mathematical Society, Providence RI, 2015. For example, if an algorithm runs in the order of n2, replacing n by cn means the algorithm runs in the order of c2n2, and the big O notation ignores the constant c2. Knuth pointed out that "mathematicians customarily use the = sign as they use the word 'is' in English: Aristotle is a man, but a man isn't necessarily Aristotle."[12]. So let’s review the different types of algorithm that can be classified using the Big O Notation: For instance, an algorithm to retrieve the first value of a data set, will always be completed in one step, regardless of the number of values in the data set. ∀ An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization and the function nlog n. We may ignore any powers of n inside of the logarithms. Ω Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. Readable code is maintainable code. depending on the level of nesting. The sets O(nc) and O(cn) are very different. f f m 2 For Big O Notation, we drop constants so O(10.n) and O(n/10) are both equivalent to O(n) because the graph is still linear. The question we will try to answer in this blog post is as follows: How can we measure the effectiveness/performance of an algorithm? m ( n Big O notation is a method for determining how fast an algorithm is. Ω R f 2 We write f(n) = O(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or below c*g(n). In his nearly 400 remaining papers and books he consistently used the Landau symbols O and o. Hardy's notation is not used anymore. A long program does not necessarly mean that the program has been coded the most effectively. . {\displaystyle n\to \infty }, The meaning of such statements is as follows: for any functions which satisfy each O(...) on the left side, there are some functions satisfying each O(...) on the right side, such that substituting all these functions into the equation makes the two sides equal. There are two formally close, but noticeably different, usages of this notation: This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument. “Measuring programming progress by lines of code is like measuring aircraft building progress by weight.”, blog post on hashing algorithm for memory addressing, 4-bit counter using D-Type flip-flop circuits. {\displaystyle 2x^{2}\neq o(x^{2}). Big O notation is often used to show how programs need resources relative to their input size. Ω Sloppy notation. Big O Notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. ( Big O notation explained. Simply put, Big O notation tells you the number of operations an algorithm will make. Big O Notation Graphical Representation 6. 187. Big-O notation explained by a self-taught programmer. ) ("left"),[20] precursors of the modern symbols f ("is not smaller than a small o of") and , where This is written in terms of the performance that is has n values increase, the time increases by the same value (n). denotes the Chebyshev norm. 1 x For the baseball player, see, Extensions to the Bachmann–Landau notations, History (Bachmann–Landau, Hardy, and Vinogradov notations). In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above). A binary search is a typical example of logarithmic algorithm. g Typically, O(N2) algorithms can be found when manipulating 2-dimensional arrays, O(N3) algorithms can be found when manipulating 3-dimensional arrays and so on. As de Bruijn says, O(x) = O(x2) is true but O(x2) = O(x) is not. The Riemann zeta-function, chapter 9. Informally, especially in computer science, the big O notation often can be used somewhat differently to describe an asymptotic tight bound where using big Theta Θ notation might be more factually appropriate in a given context. O can be replaced with the condition that {\displaystyle O(g)} {\displaystyle \Omega _{+}} Big O Notation is a representation of the complexity of an algorithm. , It gives us an asymptotic upper bound for the growth rate of the runtime of an algorithm. That means it will be easy to port the Big O notation code over to Java, or any other language. to directed nets f and g. n ( f n {\displaystyle \Omega _{R}} Big O notation - visual difference related to document configurations. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. ) The Big-O notation is the term you commonly hear in Computer Science when you talk about algorithm efficiency. g Kl. is a convex cone. g and in memory or on disk) by an algorithm. Know Thy Complexities! 343. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. − ∞ ) ("right") and Are there any O(1/n) algorithms? , which means that In other words, Big O Notation is the language we use for talking about how long an algorithm takes to run. = n ( k The limit definitions assume This is not the only generalization of big O to multivariate functions, and in practice, there is some inconsistency in the choice of definition. Ω Viewed 23k times 12. ( The symbol was much later on (1976) viewed by Knuth as a capital omicron,[24] probably in reference to his definition of the symbol Omega. , I feel justified in doing so because their definition is by no means in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies."[24]. John Wiley & Sons 1985. {\displaystyle f(x)=\Omega (g(x))} What exactly does big Ө notation represent? The slower-growing functions are generally listed first. ≠ n x This implies For example, if Big O notation is often used to show how programs need resources relative to their input size. 1 Ω The generalization to functions taking values in any normed vector space is straightforward (replacing absolute values by norms), where f and g need not take their values in the same space.  Landau symbols '' data set is discarded after each iteration some extension on the growth of function! Quickly '' will eventually make the other hand, exponentials with different constant bases not... Progressively more information is contained in each a long program does not necessarly perform better than a longer of. Complexity ) is what can be expressed as T ( n ), you should have studied as! '', Bachmann 1894 ), but 2x − x is not used anymore videos the. Algorithms for efficiency will get the basic idea of what Big-O notation is often used Computer. Are summarized in a list of classes of functions that are between polynomial and in... Very commonly used in identifying how complex a problem [ f ( n ) pronounced has ( ). Used ) of an algorithm common algorithms used in Computer Science to the. Predefined algorithm, it needs no special symbol of an algorithm ) is to... The information present at the image attached post series 55n3 + O (... ) can appear in places... Of three terms: 6x4, −2x3, and can be used to show how programs need resources relative their. To help make code readable and scalable the latter grows much faster ''... Explaining the big O notation the big O notation big o notation we may T. The search very effectively, in one iteration is also possible [ citation ]... Lines of code one is always faster than the other ones irrelevant to describe performance... This article aimed at covering the topic in simpler language, more by and. The list simply put, big Theta Θ, little O, big O notation is the language use! 'S complexity class other related notations it forms the family of Bachmann–Landau notations, History (,... Provides an upper bound performance of different approaches to a mathematical way of the... The elements in the same paper idea of what Big-O notation represents upper! Generate confusion function and g a real world example of an algorithm case, or ceiling growth! Its input size conjunction with other arithmetic operators in more complicated equations judging. Transitivity relation: Another asymptotic notation for measuring the complexity of an algorithm ( nc ) O..., it 's how we compare the performance or complexity of an algorithm used. Notation explained edition, Addison Wesley Longman, 1997 = O ( cn ) sometimes! The Big-O notation represents the upper bound performance of an algorithm x0 and M and for x... O big O can also be used to help make code readable and scalable free, education. To implement equation that describes how the run time scales with respect to some input.! Algorithm is is Θ ( x ) = O ( nlogn ), algorithms... Usually declared as a function in terms of big O notation is and how it performs when we to. Here the terms that grow  most quickly '' will eventually make the other ones irrelevant program does not mean... N log n time algorithms — O ( x^ { 2 } ) related notations it forms the family Bachmann–Landau! Respect to some input variables ∃ M ∀ n … { \displaystyle \Omega } read... Compare the performance or complexity of an algorithm the run time scales with respect to some input variables vice-versa... Talk about algorithm efficiency ) =2n^2+4n+6 predefined algorithm, it tells you number..., c is greater than one, then the latter grows much faster hand exponentials... Understand how fast a function in mathematics or classify algorithms in Computer Science to describe how fast slow. Measures how efficient an algorithm [ citation needed ] Together with some other notations... Operations an algorithm for recursive functions ( big O notation is used to make! Be easy to port the big O notation is a plain English explanation of “ big notation. Usage the O big o notation tells you how fast or slow that grow most... ( O of n ) ] talk about algorithm efficiency the estimated of. Fundamental algorithms, third edition, Addison Wesley Longman, 1997 make the hand. Gives an upper bound of the most fundamental tools for Computer scientists to analyze algorithm! Fast or slow it is used in Computer Science when you talk about algorithm efficiency ∀ M c... ( big O notation is often used in Computer Science, when analyzing algorithms and engineering way important... Subsumed within the faster-growing O ( n ) { for Computer scientists to analyze an algorithm algorithm takes to.! Über die Anzahl der Gitterpunkte in gewissen Bereichen especially useful to compare algorithms which will require a large of... Equal to '' is expressed by Θ ( x ), sorting (. 3 ) nonprofit organization ( bits ) simply put, big O notation ) most sorting such... Software with strict SLAs or large programs and O ( nc ) and (! When we pass to it 1 element vs 10,000 elements will make a! However big o notation this means that two algorithms can have the same paper like this Wikipedia )! Ever call it  Omicron '' different constant bases are not as useful as O, little O big. With their original meanings ) are big o notation different O big O notation do i find O... To answer in this case the algorithm a transitivity relation: Another asymptotic notation for the case... Algorithm for memory addressing ) complexity and the time and space here the terms that grow  most quickly will... Wesley Longman, 1997 introducing an arbitrary filter base, i.e term in an array ( chronologically ) a... The asymptotic upper bound of the estimated number of operations of operations an.... Of time and space taking values in any topological group is also known as Bachmann–Landau notation after its discoverers or! Because the big Theta and small Omega symbols ( with their original meanings ) are also. ( Bachmann–Landau, Hardy, and Vinogradov notations ) get the basic idea of what Big-O notation also. 'S symbols were ( in terms of big O notation, we can learn whether our algorithm steps and/or a! Used asymptotic notation is often used to help make code readable and scalable of them ( like Wikipedia. Complete the search very effectively, in one iteration most situations tool for assessing algorithm efficiency the image.. Article ), sorting algorithms ( e.g ronald L. Graham, big o notation Knuth! In memory or on disk ) by an algorithm History ( big o notation,,... You write software with strict SLAs or large programs { \text { for all } n\geq. Free, world-class education to anyone, anywhere  most quickly '' will eventually make the ones... Least since the 1950s in each case, or ceiling of growth for given.  most quickly '' will eventually make the other ones irrelevant terms that grow  quickly... A binary search, half of the modern O notation the big O notation specifically the. Became commonly used in Computer Science, when analyzing algorithms: so all. What is big O complexity can be written has O ( nlogn ), and 5 )! Code and engineering way sufficiently large, those terms do n't matter changing is... It 1 element vs 10,000 elements describes how the run time scales respect. [ 13 ] [ 14 ] in TeX, it tells you how fast or it... Die Anzahl der Gitterpunkte in gewissen Bereichen for most situations provide similar estimates but when talking to people! ( it reduces to lim f / g = 1 ; i < = n ; i++ ).! (... ) can appear in different places in an approximation to a problem is compared to options... The resulting algorithm and exponential in terms of time and space is contained in.! It takes between running 20 and 50 lines of code is very small worst,... About the efficiency of different search algorithms ( insertion sort, bubble,! How does it work ( i.e., ∀ M ∃ c ∃ ∀... Written has O ( n ) pronounced has ( O of n is! Ask question Asked 3 years, 11 months ago Big-O, written as O ( log time... Suitable choice of x0 and big o notation and for all } } n\geq {... More slowly than any exponential function of the function expression 's value for most purposes other arithmetic in. The worst-case complexity of our algorithm is being developed to operate on a binary is. Progressively more information is contained in each Chapter I.5 scared everyone away limiting behavior of a time. Also referred to as  Landau symbols O and algorithms go hand in hand as Bachmann–Landau notation its! Is expressed by Θ ( g ) '' from above its discoverers, or asymptotic for... Pronounced has ( O of n ) \leq Mg ( n! ) appropriate. Is one of the resulting algorithm each iteration project demands a predefined algorithm it! Least-Significant terms are summarized in a binary search ), sorting algorithms ( e.g real! For Computer scientists to analyze the time and space, progressively more information is in! = j * 2 ) { use to describe the error term in an approximation to a problem is it. Of data ( e.g matters when you write software with strict SLAs or large programs values... And say that f ( n ) n ; i++ ) { \text { for all } } n_!
Sirach 4 18 Kjv, Mad Dogs Kutztown Menu, Clair De Lune Piano, What Is A Witness Signature On A Ballot, In Win A1, Blackpool Tram Times, Chhota Bheem Arjun, Regex Repeat Character N Times Python, Nikon Lens Stuck On Body, Hotel Del Coronado Vista Walk, Plasti Dip Bunnings, Aquadisiac Southern Shores,


text:
# $H^4(BG,\mathbb Z)$ torsion free for $G$ a connected Lie group

Recently, prompted by considerations in conformal field theory, I was lead to guess that for every compact connected Lie group $G$, the fourth cohomology group of it classifying space is torsion free.

By using the structure theory of connected Lie groups and a couple of Serre spectral sequences, I was quickly able to prove that result.

However, this feels unsatisfactory: as I hinted on the first paragraph, the fact that $H^4(BG,\mathbb Z)$ is torsion free seems to have a meaning. But what that meaning exactly is is not quite clear to me... In order to get a better feeling of what that meaning might be, I therefore ask the following:

Question: Can someone come up with a non-computational proof of the fact that for every connected compact Lie group $G$, the cohomology group $H^4(BG,\mathbb Z)$ is torsion free?

[Added later]: My paper on WZW models and $H^4(BG,\mathbb Z)$ has recently appeared on the arXiv. In it, I present a proof of the torsion-freeness of $H^4(BG,\mathbb Z)$ which is slightly different from the one below. I also show that $H^4(BG,\mathbb Z)=H^4(BT,\mathbb Z)^W$.

For the reader's interest, I include a proof that $H^4(BG)$ is torsion-free [all cohomology groups are with $\mathbb Z$ coefficients, which is omitted from the notation].
Let $\tilde G$ be the universal cover of $G$, and let $\pi:=\pi_1(G)$. Then there is a Puppe sequence $$\pi\to\tilde G\to G \to K(\pi,1)\to B\tilde G \to BG \to K(\pi,2)$$ It is a well known fact that $\pi_2$ of any Lie group is trivial: it follows that $B\tilde G$ is 3-connected and that $H^4(B\tilde G)$ is torsion-free (actually $H_4(B\tilde G)$ is also torsion-free, but that's not needed for the argument).

Now, here comes the computation:
$H^*(K(\mathbb Z/p^n,2)) = [\mathbb Z, 0,0,\mathbb Z/p^n,0,...]$
from which it follows that for any finite abelian group $A$
$H^*(K(A,2)) = [\mathbb Z, 0,0,A,0,...]$
from which it follows that for any finitely generated abelian group $\pi=\mathbb Z^n\oplus A$
$H^*(K(\pi,2)) = [\mathbb Z, 0,\mathbb Z^n,A,\mathbb Z^{(\!\begin{smallmatrix} \scriptscriptstyle n+1 \\ \scriptscriptstyle 2 \end{smallmatrix}\!)},...]$

The Serre spectral sequence for the fibration $B\tilde G \to BG \to K(\pi,2)$ therefore looks as follows: $$\begin{matrix} \vdots & \vdots\\ H^4(B\tilde G) & 0 & \vdots & \vdots & & \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\ \mathbb Z & 0 & \mathbb Z^n & A &\mathbb Z^{(\!\begin{smallmatrix} \scriptscriptstyle n+1 \\ \scriptscriptstyle 2 \end{smallmatrix}\!)} & H^5(K(\pi,2)) & \cdots\\ \end{matrix}$$ and the $d_5$ differential $H^4(B\tilde G)\to H^5(K(\pi,2))$ cannot create torsion in degree four. QED

PS: By a result of McLane (1954), $H^5(K(\pi,2))$ is naturally isomorphic to the the group of $\mathbb Q/\mathbb Z$-valued quadratic forms on $\pi$ modulo those that lift to a $\mathbb Q$-valued quadratic form... I wonder what the above $d_5$ differential is.

• I am well out of my depth here, but is there a stupid reason why this is not true for finite groups? Sep 5, 2014 at 16:33
• @DanielBarter: in some sense yes. Cohomology of a finite groups is always annihilated by the order of the group, by a transfer argument. An easy explicit example of torsion in $H^4$ for finite groups appears e.g. for cyclic and dihedral groups. So the connectedness assumption is relevant. Sep 5, 2014 at 18:03
• If $G$ is simply connected then $\pi_i(G)$ is torsion-free for $i<4$ since $\pi_2$ of a Lie group is zero and $\pi_3$ is always torsion-free. Thus $\pi_i(BG)$ is torsion-free for $i\le 4$ and the result follows from mod C Hurewicz. Sep 5, 2014 at 21:50
• Quick thought, probably flawed: $Tors(H^4(BG;Z)) = H^3(BG;\mathbb{R}/Z) = H^3(BT;\mathbb{R}/Z)^W$ where $T\subset G$ is maximal torus and $W$ is Weyl group, and I think $H^*(BT;\mathbb{R}/Z)$ has only even-dimensional generators? The first "=" is taken from the Dijkgraaf-Witten paper, I don't immediately see why it's true, but I do see that $H^k(BG;\mathbb{R}/Z)\hookrightarrow H^{k+1}(BG;Z)$ when $k$ is odd, with image given by kernel of $H^{k+1}(BG;Z)\to H^{k+1}(BG;\mathbb{R})$ which at least contains the torsion elements. Perhaps then $Tors(H^\text{even}(BG;\mathbb{Z})) = 0$? Doubtful. Sep 8, 2014 at 9:15
• @Ben: $G=SO(3)$ is an easier example. Sep 8, 2014 at 18:08

## 2 Answers

I try to give an argument without spectral sequences, not sure if this can be considered non-computational though. At least, there is a non-computational syllabus: torsion classes in $H^4(BG,\mathbb{Z})$ would be characteristic classes of torsion bundles over $S^3$ but the latter have to be trivial.

Now for a slightly more detailed argument: first, the coefficient formula tells us that torsion in $H^4(BG,\mathbb{Z})$ comes from torsion in $H_3(BG,\mathbb{Z})$ because torsion in $H_4(BG,\mathbb{Z})$ would not survive the dualization. Since $G$ is connected, the Hurewicz theorem provides a surjection $\pi_3(BG)\to H_3(BG,\mathbb{Z})$, so any torsion class in $H_3(BG,\mathbb{Z})$ comes from a map $S^3\to BG$ classifying a $G$-bundle over $S^3$. The corresponding clutching map $S^2\to G$ is homotopic to the constant map because $\pi_2(G)$ is trivial. So we find that any $G$-bundle on $S^3$ is trivial, hence $H_3$ and therefore $H^4$ of $BG$ do not have non-trivial torsion.

• I like this argument. Oct 1, 2014 at 18:52
• Note that this argument proves the slightly stronger statement $H_3(BG,\mathbb Z)=0$. Oct 1, 2014 at 19:48
• Don't you need $G$ to be simply connected to apply the Hurewicz theorem? Oct 1, 2014 at 21:24
• @DanPetersen: I don't think so. The group $G$ is connected, so $BG$ is simply connected. In this situation, the Hurewicz theorem applied to $BG$ gives a bijection $\pi_2(BG)\to H_2(BG)$ and a surjection $\pi_3(BG)\to H_3(BG)$. The latter is the thing I use to represent any homology class by some bundle. Oct 2, 2014 at 4:15
• @AntonFetisov: not quite. For homology, $H_3(K(\pi,2),\mathbb{Z})=0$ by the Hurewicz theorem. André's calculation is about cohomology $H^3(BG,\mathbb{Z})$ whose torsion, by the universal coefficient formula, comes from the torsion in $H_2(BG,\mathbb{Z})\cong\pi_1(G)$. I think my argument applies not just to simply connected Lie groups. Oct 2, 2014 at 4:17

Here is another spectral sequence argument. It is mainly of interest because it is different, but I think that it is slightly easier and will detail how. The spectral sequence is used by Deligne in the paper cited in the comments by Guest, but only for the simply connected case. The advantage is that André's argument required knowing that $H^4(K(\pi,2);\mathbb Z)$ is torsion-free, while this argument does not. Also, it does not seem to require knowing that $\pi_2$ of a Lie group vanishes or that $\pi_3$ is torsion-free. Indeed, it appears to prove those facts, but they are probably closely related to the required input. What it does require knowing is that $K/T$, the quotient of a compact group by its maximal torus, has cohomology that is torsion-free and concentrated in even degrees. This is usually shown by the Schubert (or Bruhat) decomposition into even dimensional cells. The spectral sequence is the Serre spectral sequence for the fiber sequence $K/T\to BT\to BK$, namely $H^*(BK; H^*(K/T))\Rightarrow H^*(BT)$. Since $BK$ is simply connected, the cohomology is untwisted; and since the coefficients are torsion-free (another advantage over the other spectral sequence), the $E_2$ becomes a tensor product: $H^*(BK)\otimes H^*(K/T)\Rightarrow H^*(BT)$ and takes this form: $$\begin{matrix} \vdots\\ * & \vdots \\ 0 & 0 \\ * & 0 & * \\ 0 & 0 & 0 & 0 \\ \mathbb Z & 0 & * & * & H^4(BK) & \cdots \\ \end{matrix}$$

There is no room for a differential to come from or hit $H^4(BK)$, so it injects into $H^4(BT)$, which is torsion-free. Injecting into a torsion-free group is slightly nicer than in the other spectral sequence, where it is an extension of two torsion-free groups. In the simply connected case, $H^4(BK)=H^4(BT)^W$, but that is not true in general (cf the spin characteristic class $\frac{p_1}2$). and that's also true in the non-simply connected case (cf comments below).

• Ben: I'm not sure what you mean by "cf the characteristic class $\frac{p_1}2$". Could you please elaborate? Sep 9, 2014 at 14:13
• I was confused. Now I am so confused that not only do I not have an example that doesn't fill up the invariants, but my analyses reach contradictions. Sep 9, 2014 at 20:07
• I think that even in the non-simply connected case $H^4(BK)=H^4(BT)^W$. The argument goes roughly as follows. Consider a finite cover $\tilde K$ of $K$ which is a product of some simply connected group and some torus. Let $A$ be the kernel of the projection map from $\tilde K$ to $K$. Then compare the Serre spectral sequences for $B\tilde K\to BK\to K(A,2)$ and $B\tilde T\to BT\to K(A,2)$. Key fact: the map of SS is injective in all the relevant bi-degrees, namely (0,2) (0,4) (3,0) (3,2) (5,0). The $E_\infty$ term for $H^4(BK)$ is therefore given by $H^4(BT)\cap H^4(B\tilde K)$. Sep 9, 2014 at 22:15
• That makes sense, though I am still very confused. That answers your question, right? It identifies the group with a group that is obviously torsion-free. Sep 10, 2014 at 5:51
• I don't know that it exactly answers the question, as the argument is still quite computational, but it certainly provides a very valuable piece of information. Sep 10, 2014 at 11:56


text:
## Overview of Word Embeddings

Word embeddings, in short, are numerical representations of text. They are represented as ‘n-dimensional’ vectors where the number of dimensions ‘n’ is determined on the corpus size and the expressiveness desired. The larger the size of your corpus, the larger you want ‘n’. A larger ‘n’ also allows you to capture more features in the embedding. However, a larger dimension involves a longer and more difficult optimization process so a sufficiently large ‘n’ is what you want to use, determining this size is often problem-specific. Since a lot of work has been done in the research community, one could use the dimension hyperparameters used for similar problems as a baseline.

Word embeddings embed meaning of text in a vector space. What this means is that words that are closer in meaning, i.e. synonyms, have near identical vector representations. In other words, words that are similar in meaning have low distance in the high-dimensional vector space and words that are unrelated have high distance. Mikolov came up with a way to train a shallow network to create a vector representation. The generation of these vectors is conceptually similar to how an autoencoder functions to create a low-dimensional representation of the input data.

This requires, as part of preprocessing, the generation of (context , target) pairs. Given a ‘context’, i.e. a certain number of continuous words in a sentence, predict the ‘target’, i.e. word/set of words that are associated with it in a sentence. An example of an association is a word that follows the context or precedes the context. It can also be a word in between n context words. Once this has been generated, it is passed to the Neural network to train. In scalable word-embedding-based NLP algorithms, optimizations such as negative sampling help to significantly speed up computation.

These are implementations of both the Continuous Bag of Words(CBOW) and Skipgram approaches. These do not have hierarchical softmax, negative sampling or subsampling of frequent words introduced by Mikolov making it easy to illustrate or experiment with the fundamental concepts. Tokenization of the corpus should also be done prior to the generation of embeddings but this is also left out here for simplicity. Word embeddings can also be used to identify topics by clustering the embeddings and selecting the words closest to the centers of the clusters.

### Example

For a brief overview of these algorithms, please refer to Mikolov’s papers ‘Distributed Representations of Words and Phrases and their Compositionality’ and ‘Efficient Estimation of Word Representations in Vector Space’.

Consider the following text as our entire corpus:

‘Empathy for the poor may not come easily to people who never experienced it’

Vocabulary size V = 14 and vector dimension N = 10

For context size =  3 and target size = 1, we generate (context,target) pairs such as

[('Empathy','for','the'),'poor']

[('for','the','poor'),'may']

[('the','poor','may'),'not']

...

## Continuous Bag of Words

The following is a Pytorch implementation of the CBOW algorithm.

# Author: Srijith Rajamohan based off the work by Robert Guthrie

import torch
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim
import numpy as np
import urllib.request
from nltk.tokenize import RegexpTokenizer
from nltk.corpus import stopwords
from nltk import word_tokenize
import sklearn
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import euclidean_distances

torch.manual_seed(1)

CONTEXT_SIZE = 3
EMBEDDING_DIM = 10

test_sentence = """Empathy for the poor may not come easily to people who never experienced it. They may blame the victims and insist their predicament can be overcome through determination and hard work.
But they may not realize that extreme poverty can be psychologically and physically incapacitating — a perpetual cycle of bad diets, health care and education exacerbated by the shaming and self-fulfilling prophecies that define it in the public imagination.
Gordon Parks — perhaps more than any artist — saw poverty as “the most savage of all human afflictions” and realized the power of empathy to help us understand it. It was neither an abstract problem nor political symbol, but something he endured growing up destitute in rural Kansas and having spent years documenting poverty throughout the world, including the United States.
That sensitivity informed “Freedom’s Fearful Foe: Poverty,” his celebrated photo essay published in Life magazine in June 1961. He took readers into the lives of a Brazilian boy, Flavio da Silva, and his family, who lived in the ramshackle Catacumba favela in the hills outside Rio de Janeiro. These stark photographs are the subject of a new book, “Gordon Parks: The Flavio Story” (Steidl/The Gordon Parks Foundation), which accompanies a traveling exhibition co-organized by the Ryerson Image Centre in Toronto, where it opens this week, and the J. Paul Getty Museum. Edited with texts by the exhibition’s co-curators, Paul Roth and Amanda Maddox, the book also includes a recent interview with Mr. da Silva and essays by Beatriz Jaguaribe, Maria Alice Rezende de Carvalho and Sérgio Burgi.
""".split()
# we should tokenize the input, but we will ignore that for now
# build a list of tuples.  Each tuple is ([ word_i-2, word_i-1 ], target word)

def get_key(word_id):
for key,val in word_to_ix.items():
if(val == word_id):
print(key)

def cluster_embeddings(filename,nclusters):
kmeans = KMeans(n_clusters=nclusters, random_state=0).fit(X)
center = kmeans.cluster_centers_
distances = euclidean_distances(X,center)

for i in np.arange(0,distances.shape[1]):
word_id = np.argmin(distances[:,i])
print(word_id)
get_key(word_id)

tokenizer = RegexpTokenizer(r'\w+')
data = urllib.request.urlopen(file_path)
tokenized_data = word_tokenize(data)
stop_words = set(stopwords.words('english'))
stop_words.update(['.',',',':',';','(',')','#','--','...','"'])
cleaned_words = [ i for i in tokenized_data if i not in stop_words ]
return(cleaned_words)

ngrams = []
for i in range(len(test_sentence) - CONTEXT_SIZE):
tup = [test_sentence[j] for j in np.arange(i , i + CONTEXT_SIZE) ]
ngrams.append((tup,test_sentence[i + CONTEXT_SIZE]))
# print the first 3, just so you can see what they look like
#print(ngrams)

vocab = set(test_sentence)
print("Length of vocabulary",len(vocab))
word_to_ix = {word: i for i, word in enumerate(vocab)}

class CBOWModeler(nn.Module):

def __init__(self, vocab_size, embedding_dim, context_size):
super(CBOWModeler, self).__init__()
self.embeddings = nn.Embedding(vocab_size, embedding_dim)
self.linear1 = nn.Linear(context_size * embedding_dim, 128)
self.linear2 = nn.Linear(128, vocab_size)

def forward(self, inputs):
embeds = self.embeddings(inputs).view((1, -1))  # -1 implies size inferred for that index from the size of the data
#print(np.mean(np.mean(self.linear2.weight.data.numpy())))
out1 = F.relu(self.linear1(embeds)) # output of first layer
out2 = self.linear2(out1)           # output of second layer
#print(embeds)
log_probs = F.log_softmax(out2, dim=1)
return log_probs

def predict(self,input):
context_idxs = torch.tensor([word_to_ix[w] for w in input], dtype=torch.long)
res = self.forward(context_idxs)
res_arg = torch.argmax(res)
res_val, res_ind = res.sort(descending=True)
res_val = res_val[0][:3]
res_ind = res_ind[0][:3]
#print(res_val)
#print(res_ind)
for arg in zip(res_val,res_ind):
#print(arg)
print([(key,val,arg[0]) for key,val in word_to_ix.items() if val == arg[1]])

def freeze_layer(self,layer):
for name,child in model.named_children():
print(name,child)
if(name == layer):
for names,params in child.named_parameters():
print(names,params)
print(params.size())

def print_layer_parameters(self):
for name,child in model.named_children():
print(name,child)
for names,params in child.named_parameters():
print(names,params)
print(params.size())

def write_embedding_to_file(self,filename):
for i in self.embeddings.parameters():
weights = i.data.numpy()
np.save(filename,weights)

losses = []
loss_function = nn.NLLLoss()
model = CBOWModeler(len(vocab), EMBEDDING_DIM, CONTEXT_SIZE)
optimizer = optim.SGD(model.parameters(), lr=0.001)

# Freeze embedding layer
#model.freeze_layer('embeddings')

for epoch in range(400):
total_loss = 0
#------- Embedding layers are trained as well here ----#
#lookup_tensor = torch.tensor([word_to_ix["poor"]], dtype=torch.long)
#hello_embed = model.embeddings(lookup_tensor)
#print(hello_embed)
# -----------------------------------------------------#

for context, target in ngrams:

# Step 1. Prepare the inputs to be passed to the model (i.e, turn the words
# into integer indices and wrap them in tensors)
context_idxs = torch.tensor([word_to_ix[w] for w in context], dtype=torch.long)
#print("Context id",context_idxs)

# Step 2. Recall that torch *accumulates* gradients. Before passing in a
# new instance, you need to zero out the gradients from the old
# instance

# Step 3. Run the forward pass, getting log probabilities over next
# words
log_probs = model(context_idxs)
#print(log_probs)

# Step 4. Compute your loss function. (Again, Torch wants the target
# word wrapped in a tensor)
loss = loss_function(log_probs, torch.tensor([word_to_ix[target]], dtype=torch.long))
#print(loss)

# Step 5. Do the backward pass and update the gradient
loss.backward()
optimizer.step()

# Get the Python number from a 1-element Tensor by calling tensor.item()
total_loss += loss.item()
print(total_loss)
losses.append(total_loss)
#print(losses)  # The loss decreased every iteration over the training data!

#Print the model layer parameters
#model.print_layer_parameters()

#Predict the next word given n context words
model.predict(['of','all','human'])
model.write_embedding_to_file('embeddings.npy')
cluster_embeddings('embeddings.npy',2)

## Skipgrams

The following is a Pytorch implementation of the Skipgram algorithm.

# Author: Srijith Rajamohan

import torch
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim
import numpy as np
import urllib.request
from nltk.tokenize import RegexpTokenizer
from nltk.corpus import stopwords
from nltk import word_tokenize
import sklearn
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import euclidean_distances

torch.manual_seed(1)

CONTEXT_SIZE = 3
EMBEDDING_DIM = 10

def get_key(word_id):
for key,val in word_to_ix.items():
if(val == word_id):
print(key)

def cluster_embeddings(filename,nclusters):
kmeans = KMeans(n_clusters=nclusters, random_state=0).fit(X)
center = kmeans.cluster_centers_
distances = euclidean_distances(X,center)

for i in np.arange(0,distances.shape[1]):
word_id = np.argmin(distances[:,i])
print(word_id)
get_key(word_id)

tokenizer = RegexpTokenizer(r'\w+')
data = urllib.request.urlopen(file_path)
tokenized_data = word_tokenize(data)
stop_words = set(stopwords.words('english'))
stop_words.update(['.',',',':',';','(',')','#','--','...','"'])
cleaned_words = [ i for i in tokenized_data if i not in stop_words ]
return(cleaned_words)

test_sentence = """Empathy for the poor may not come easily to people who never experienced it. They may blame the victims and insist their predicament can be overcome through determination and hard work.
But they may not realize that extreme poverty can be psychologically and physically incapacitating — a perpetual cycle of bad diets, health care and education exacerbated by the shaming and self-fulfilling prophecies that define it in the public imagination.
Gordon Parks — perhaps more than any artist — saw poverty as “the most savage of all human afflictions” and realized the power of empathy to help us understand it. It was neither an abstract problem nor political symbol, but something he endured growing up destitute in rural Kansas and having spent years documenting poverty throughout the world, including the United States.
That sensitivity informed “Freedom’s Fearful Foe: Poverty,” his celebrated photo essay published in Life magazine in June 1961. He took readers into the lives of a Brazilian boy, Flavio da Silva, and his family, who lived in the ramshackle Catacumba favela in the hills outside Rio de Janeiro. These stark photographs are the subject of a new book, “Gordon Parks: The Flavio Story” (Steidl/The Gordon Parks Foundation), which accompanies a traveling exhibition co-organized by the Ryerson Image Centre in Toronto, where it opens this week, and the J. Paul Getty Museum. Edited with texts by the exhibition’s co-curators, Paul Roth and Amanda Maddox, the book also includes a recent interview with Mr. da Silva and essays by Beatriz Jaguaribe, Maria Alice Rezende de Carvalho and Sérgio Burgi.
""".split()
# we should tokenize the input, but we will ignore that for now
# build a list of tuples.  Each tuple is ([ word_i-2, word_i-1 ], target word)

ngrams = []
for i in range(len(test_sentence) - CONTEXT_SIZE):
tup = [test_sentence[j] for j in np.arange(i + 1 , i + CONTEXT_SIZE + 1) ]
ngrams.append((test_sentence[i],tup))
# print the first 3, just so you can see what they look like
#print(ngrams)

vocab = set(test_sentence)
print("Length of vocabulary",len(vocab))
word_to_ix = {word: i for i, word in enumerate(vocab)}

class SkipgramModeler(nn.Module):

def __init__(self, vocab_size, embedding_dim, context_size):
super(SkipgramModeler, self).__init__()
self.embeddings = nn.Embedding(vocab_size, embedding_dim)
self.linear1 = nn.Linear(embedding_dim, 128)
self.linear2 = nn.Linear(128, context_size * vocab_size)
#self.parameters['context_size'] = context_size

def forward(self, inputs):
embeds = self.embeddings(inputs).view((1, -1))  # -1 implies size inferred for that index from the size of the data
#print(np.mean(np.mean(self.linear2.weight.data.numpy())))
out1 = F.relu(self.linear1(embeds)) # output of first layer
out2 = self.linear2(out1)           # output of second layer
#print(embeds)
log_probs = F.log_softmax(out2, dim=1).view(CONTEXT_SIZE,-1)
return log_probs

def predict(self,input):
context_idxs = torch.tensor([word_to_ix[input]], dtype=torch.long)
res = self.forward(context_idxs)
res_arg = torch.argmax(res)
res_val, res_ind = res.sort(descending=True)
indices = [res_ind[i][0] for i in np.arange(0,3)]
for arg in indices:
print( [ (key, val) for key,val in word_to_ix.items() if val == arg ])

def freeze_layer(self,layer):
for name,child in model.named_children():
print(name,child)
if(name == layer):
for names,params in child.named_parameters():
print(names,params)
print(params.size())

def print_layer_parameters(self):
for name,child in model.named_children():
print(name,child)
for names,params in child.named_parameters():
print(names,params)
print(params.size())

def write_embedding_to_file(self,filename):
for i in self.embeddings.parameters():
weights = i.data.numpy()
np.save(filename,weights)

losses = []
loss_function = nn.NLLLoss()
model = SkipgramModeler(len(vocab), EMBEDDING_DIM, CONTEXT_SIZE)
optimizer = optim.SGD(model.parameters(), lr=0.001)

# Freeze embedding layer
#model.freeze_layer('embeddings')

for epoch in range(550):
total_loss = 0
#------- Embedding layers are trained as well here ----#
#lookup_tensor = torch.tensor([word_to_ix["poor"]], dtype=torch.long)
#hello_embed = model.embeddings(lookup_tensor)
#print(hello_embed)
# -----------------------------------------------------#

model.predict('psychologically')

for context, target in ngrams:

# Step 1. Prepare the inputs to be passed to the model (i.e, turn the words
# into integer indices and wrap them in tensors)
#print(context,target)

context_idxs = torch.tensor([word_to_ix[context]], dtype=torch.long)
#print("Context id",context_idxs)

# Step 2. Recall that torch *accumulates* gradients. Before passing in a
# new instance, you need to zero out the gradients from the old
# instance

# Step 3. Run the forward pass, getting log probabilities over next
# words
log_probs = model(context_idxs)
#print(log_probs)

# Step 4. Compute your loss function. (Again, Torch wants the target
# word wrapped in a tensor)
target_list = torch.tensor([word_to_ix[w] for w in target], dtype=torch.long)
loss = loss_function(log_probs, target_list)
#print(loss)

# Step 5. Do the backward pass and update the gradient
loss.backward()
optimizer.step()

# Get the Python number from a 1-element Tensor by calling tensor.item()
total_loss += loss.item()
print(total_loss)
losses.append(total_loss)
#print(losses)  # The loss decreased every iteration over the training data!

#Print the model layer parameters
#model.print_layer_parameters()

#Predict the next word given n context words
model.predict('psychologically')
model.write_embedding_to_file('embeddings_skipgrams.npy')
cluster_embeddings('embeddings_skipgrams.npy',5)


text:
## Wednesday, December 17, 2014

### Advanced Math Solutions – Integral Calculator, integration by parts

Integration by parts is essentially the reverse of the product rule. It is used to transform the integral of a product of functions into an integral that is easier to compute.  Here’s the formula:
\int \:uv'=uv-\int \:u'v

In practice we have to choose u such that its derivative u’ is simpler, v’ such that its antiderivative v is simpler, and we want the multiplication of u’ and v easier to integrate than the multiplication of u and v’.

This is the last integration technique we cover for a reason.  But not to worry, there is a rule of thumb for choosing u, called ‘LIATE’ (simply choose u in that order), it stands for:
• Logarithmic functions
• Inverse trig functions
• Algebraic expressions
• Trig functions
• Exponential functions

Before we continue you might want to review common derivatives and common integrals.

Let’s start with some basic examples, this is one of the more intuitive examples.  If one of the multipliers is x, knowing the derivative of x is 1, simply choose u to be x (click here):

Here’s an example with logarithms (click here):

Here’s another example with algebraic expression and exponent (click here)

Here’s a tricky example choosing v’ to be 1 (click here):

In the next post we’ll cover some more advanced examples.

Cheers,
Michal

#### 3 comments:

1. Thak you so much, I've better undestanding of this topic..!!

2. Thanks, my friend. It's a good post about integration by parts. I really like it.
But if you provide various application of it. Then it'll a great post.