text:
# Majority Element

## Appearing more than N / 2 times

This type of majority element problem is a classical problem. There are two algorithm is know can solve this problem in a time cost of .

The first is that we find the median number in the array, it must be the majority element. The simplest way to get a median number is to sort the array, but its time cost is . There is a way to find the median number in based on array partition.

public class Solution {
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

private int partition(int[] nums, int l, int r) {
int pivot = nums[l];
int i = r + 1;
int m = r + 1;
do {
while (nums[--i] < pivot);
swap(nums, --m, i);
} while (i > l);
return m;
}

private int median(int[] nums, int l, int r, int k) {
int p = partition(nums, l, r);
if (p == k) return nums[k];
else if (p < k) return median(nums, p + 1, r, k);
else return median(nums, l, p - 1, k);
}

public int majorityElement(int[] nums) {
return median(nums, 0, nums.length - 1, nums.length / 2);
}
}

Although its time complexity is , but it uses a space of . It is also not fast in enough on LeetCode.

There are also several other solutions such as Using a HashTable to count element numbers, divide and conquer and so on. But the best solusion is commonly thought to be Moore Voting algorithm. Moore voting algorithm's time cost is and space cost is .

public class Solution {
public int majorityElement(int[] nums) {
int majority = nums[0];
int sameCount = 1;

for (int i = 1; i < nums.length; i++) {

if (nums[i] != majority) {
sameCount--;
if (sameCount == 0) {
majority = nums[i];
sameCount++;
}
} else {
sameCount++;
}

}
return majority;
}
}

More description on Moore voting algorithm and other algorithms please refer to the solution page on LeetCode.

## Appearing more than N / 3 times

One step harder, how to find elements that appears more than times? At first we know, there are at most two element which can appear more than times and as to make use of the Moore voting algorithm described above we need a tweak that let one type of elements appears more than times.

Thus we maintain a set which contains two items, apply Moore algorithm on elements in the set against all other elements. That is, if a element is in the set, increase its vote count by 1. Otherwise, we decrease vote count of every element by 1. The total vote of all elements in the set will exceed so that Moore voting algorithm will give a result that contains all such majority elements, but it is possible that there are numbers not are mojority elements left in the set. So we have to check each element to make sure it appears more than times.

Obviously, we can easily generalize this method to cases.

public class MajorityElementII {
private int count(int[] nums, int value) {
int count = 0;
for (int e : nums) {
count += (e == value) ? 1 : 0;
}
return count;
}

public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> result = new ArrayList<Integer>(2);
int firstCount = 0;
int secondCount = 0;
int first = 0;
int second = 0;

for (int e : nums) {
if (firstCount == 0 || e == first) {
firstCount++;
first = e;
} else if (secondCount == 0 || e == second) {
secondCount++;
second = e;
} else {
firstCount--;
secondCount--;
}
}

if (count(nums, first) > nums.length / 3) result.add(first);
if (count(nums, second) > nums.length / 3) {
if (result.size() == 0 || (result.size() > 0 && result.get(0) != second)) {


text:
mscroggs.co.uk
mscroggs.co.uk

subscribe

# Blog

2019-12-27
In tonight's Royal Institution Christmas lecture, Hannah Fry and Matt Parker demonstrated how machine learning works using MENACE.
The copy of MENACE that appeared in the lecture was build and trained by me. During the training, I logged all the moved made by MENACE and the humans playing against them, and using this data I have created some visualisations of the machine's learning.
First up, here's a visualisation of the likelihood of MENACE choosing different moves as they play games. The thickness of each arrow represented the number of beads in the box corresponding to that move, so thicker arrows represent more likely moves.
The likelihood that MENACE will play each move.
There's an awful lot of arrows in this diagram, so it's clearer if we just visualise a few boxes. This animation shows how the number of beads in the first box changes over time.
The beads in the first box.
You can see that MENACE learnt that they should always play in the centre first, an ends up with a large number of green beads and almost none of the other colours. The following animations show the number of beads changing in some other boxes.
MENACE learns that the top left is a good move.
MENACE learns that the middle right is a good move.
MENACE is very likely to draw from this position so learns that almost all the possible moves are good moves.
The numbers in these change less often, as they are not used in every game: they are only used when the game reached the positions shown on the boxes.
We can visualise MENACE's learning progress by plotting how the number of beads in the first box changes over time.
The number of beads in MENACE's first box.
Alternatively, we could plot how the number of wins, loses and draws changes over time or view this as an animated bar chart.
The number of games MENACE wins, loses and draws.
The number of games MENACE has won, lost and drawn.
If you have any ideas for other interesting ways to present this data, let me know in the comments below.

### Similar posts

 Building MENACEs for other games MENACE at Manchester Science Festival MENACE MENACE in fiction

Comments in green were written by me. Comments in blue were not written by me.
@(anonymous): Have you been refreshing the page? Every time you refresh it resets MENACE to before it has learnt anything.

It takes around 80 games for MENACE to learn against the perfect AI. So it could be you've not left it playing for long enough? (Try turning the speed up to watch MENACE get better.)
Matthew

I have played around menace a bit and frankly it doesnt seem to be learning i occasionally play with it and it draws but againt the perfect ai you dont see as many draws, the perfect ai wins alot more
(anonymous)

@Colin: You can set MENACE playing against MENACE2 (MENACE that plays second) on the interactive MENACE. MENACE2's starting numbers of beads and incentives may need some tweaking to give it a chance though; I've been meaning to look into this in more detail at some point...
Matthew

Idle pondering (and something you may have covered elsewhere): what's the evolution as MENACE plays against itself? (Assuming MENACE can play both sides.)
Colin

Allowed HTML tags:
     <s>    <spoiler>

To prove you are not a spam bot, please type "x" then "-" then "a" then "x" then "i" then "s" in the box below (case sensitive):
2018-07-07
So you've calculated how much you should expect the World Cup sticker book to cost and recorded how much it actually cost. You might be wondering what else you can do with your sticker book. If so, look no further: this post contains 5 mathematical things involvolving your sticker book and stickers.

Stickers 354 and 369: Alisson and Roberto Firmino
In a group of 23 people, there is a more than 50% chance that two of them will share a birthday. This is often called the birthday paradox, as the number 23 is surprisingly small.
Back in 2014 when Alex Bellos suggested testing the birthday paradox on World Cup squads, as there are 23 players in a World Cup squad. I recently discovered that even further back in 2012, James Grime made a video about the birthday paradox in football games, using the players on both teams plus the referee to make 23 people.
In this year's sticker book, each player's date of birth is given above their name, so you can use your sticker book to test it out yourself.

One of the cities in which games are taking place in this World Cup is Kaliningrad. Before 1945, Kaliningrad was called Königsberg. In Königsburg, there were seven bridges connecting four islands. The arrangement of these bridges is shown below.
The people of Königsburg would try to walk around the city in a route that crossed each bridge exactly one. If you've not tried this puzzle before, try to find such a route now before reading on...
In 1736, mathematician Leonhard Euler proved that it is in fact impossible to find such a route. He realised that for such a route to exist, you need to be able to pair up the bridges on each island so that you can enter the island on one of each pair and leave on the other. The islands in Königsburg all have an odd number of bridges, so there cannot be a route crossing each bridge only once.
In Kaliningrad, however, there are eight bridges: two of the original bridges were destroyed during World War II, and three more have been built. Because of this, it's now possible to walk around the city crossing each bridge exactly once.
A route around Kaliningrad crossing each bridge exactly once.
I wrote more about this puzzle, and using similar ideas to find the shortest possible route to complete a level of Pac-Man, in this blog post.

### Sorting algorithms

If you didn't convince many of your friends to join you in collecting stickers, you'll have lots of swaps. You can use these to practice performing your favourite sorting algorithms.

#### Bubble sort

In the bubble sort, you work from left to right comparing pairs of stickers. If the stickers are in the wrong order, you swap them. After a few passes along the line of stickers, they will be in order.
Bubble sort

#### Insertion sort

In the insertion sort, you take the next sticker in the line and insert it into its correct position in the list.
Insertion sort

#### Quick sort

In the quick sort, you pick the middle sticker of the group and put the other stickers on the correct side of it. You then repeat the process with the smaller groups of stickers you have just formed.
Quick sort

### The football

Sticker 007: The official ball
Sticker 007 shows the official tournament ball. If you look closely (click to enlarge), you can see that the ball is made of a mixture of pentagons and hexagons. The ball is not made of only hexagons, as road signs in the UK show.
Stand up mathematician Matt Parker started a petition to get the symbol on the signs changed, but the idea was rejected.
If you have a swap of sticker 007, why not stick it to a letter to your MP about the incorrect signs as an example of what an actual football looks like.

### Psychic pets

Speaking of Matt Parker, during this World Cup, he's looking for psychic pets that are able to predict World Cup results. Why not use your swaps to label two pieces of food that your pet can choose between to predict the results of the remaining matches?
Timber using my swaps to wrongly predict the first match

### Similar posts

 World Cup stickers 2018, pt. 2 World Cup stickers 2018 World Cup stickers Euro 2016 stickers

Comments in green were written by me. Comments in blue were not written by me.
@Matthew: Thank you for the calculations. Good job I ordered the stickers I wanted #IRN. 2453 stickers - that's more than the number you bought (1781) to collect all stickers!

@Matthew: Here is how I calculated it:

You want a specific set of 20 stickers. Imagine you have already $$n$$ of these. The probability that the next sticker you buy is one that you want is
$$\frac{20-n}{682}.$$
The probability that the second sticker you buy is the next new sticker is
$$\mathbb{P}(\text{next sticker is not wanted})\times\mathbb{P}(\text{sticker after next is wanted})$$
$$=\frac{662+n}{682}\times\frac{20-n}{682}.$$
Following the same method, we can see that the probability that the $$i$$th sticker you buy is the next wanted sticker is
$$\left(\frac{662+n}{682}\right)^{i-1}\times\frac{20-n}{682}.$$
Using this, we can calculate the expected number of stickers you will need to buy until you find the next wanted one:
$$\sum_{i=1}^{\infty}i \left(\frac{20-n}{682}\right) \left(\frac{662+n}{682}\right)^{i-1} = \frac{682}{20-n}$$
Therefore, to get all 682 stickers, you should expect to buy
$$\sum_{n=0}^{19}\frac{682}{20-n} = 2453 \text{ stickers}.$$
Matthew

@Matthew: Yes, I would like to know how you work it out please. I believe I have left my email address in my comment. It seems like a lot of stickers if you are just interested in one team.

@Milad: Following a similiar method to this blog post, I reckon you'd expect to buy 2453 stickers (491 packs) to get a fixed set of 20 stickers. Drop me an email if you want me to explain how I worked this out.
Matthew

Thanks for the maths, but I have one probability question. How many packs would I have to buy, on average, to obtain a fixed set of 20 stickers?

Allowed HTML tags:
     <s>    <spoiler>

To prove you are not a spam bot, please type "rotcaf" backwards in the box below (case sensitive):
2017-11-14
A few weeks ago, I took the copy of MENACE that I built to Manchester Science Festival, where it played around 300 games against the public while learning to play Noughts and Crosses. The group of us operating MENACE for the weekend included Matt Parker, who made two videos about it. Special thanks go to Matt, plus Katie Steckles, Alison Clarke, Andrew Taylor, Ashley Frankland, David Williams, Paul Taylor, Sam Headleand, Trent Burton, and Zoe Griffiths for helping to operate MENACE for the weekend.
As my original post about MENACE explains in more detail, MENACE is a machine built from 304 matchboxes that learns to play Noughts and Crosses. Each box displays a possible position that the machine can face and contains coloured beads that correspond to the moves it could make. At the end of each game, beads are added or removed depending on the outcome to teach MENACE to play better.

### Saturday

On Saturday, MENACE was set up with 8 beads of each colour in the first move box; 3 of each colour in the second move boxes; 2 of each colour in third move boxes; and 1 of each colour in the fourth move boxes. I had only included one copy of moves that are the same due to symmetry.
The plot below shows the number of beads in MENACE's first box as the day progressed.

### Sunday

Originally, we were planning to let MENACE learn over the course of both days, but it learned more quickly than we had expected on Saturday, so we reset is on Sunday, but set it up slightly differently. On Sunday, MENACE was set up with 4 beads of each colour in the first move box; 3 of each colour in the second move boxes; 2 of each colour in third move boxes; and 1 of each colour in the fourth move boxes. This time, we left all the beads in the boxes and didn't remove any due to symmetry.
The plot below shows the number of beads in MENACE's first box as the day progressed.

### The data

You can download the full set of data that we collected over the weekend here. This includes the first two moves and outcomes of all the games over the two days, plus the number of beads in each box at the end of each day. If you do something interesting (or non-interesting) with the data, let me know!

### Similar posts

 MENACE Visualising MENACE's learning Building MENACEs for other games MENACE in fiction

Comments in green were written by me. Comments in blue were not written by me.
WRT the comment 2017-11-17, and exactly one year later, I had the same thing happen whilst running MENACE in a 'Resign' loop for a few hours, unattended. When I returned, the orange overlay had appeared, making the screen quite difficult to read on an iPad.
g0mrb

On the JavaScript version, MENACE2 (a second version of MENACE which learns in the same way, to play against the original) keeps setting the 6th move as NaN, meaning it cannot function. Is there a fix for this?
Lambert

what would happen if you loaded the boxes slightly differently. if you started with one bead corresponding to each move in each box. if the bead caused the machine to lose you remove only that bead. if the game draws you leave the bead in play if the bead causes a win you put an extra bead in each of the boxes that led to the win. if the box becomes empty you remove the bead that lead to that result from the box before
Ian

Hi, I was playing with MENACE, and after a while the page redrew with a Dragon Curves design over the top. MENACE was still working alright but it was difficult to see what I was doing due to the overlay. I did a screen capture of it if you want to see it.
Russ

Allowed HTML tags:
     <s>    <spoiler>

To prove you are not a spam bot, please type "tneitouq" backwards in the box below (case sensitive):
2015-03-24
 This is the fourth post in a series of posts about tube map folding.
A while ago, I made this (a stellated rhombicuboctahedron):
Here are some hastily typed instructions for Matt Parker, who is making one at this month's Maths Jam. Other people are welcome to follow these instructions too.

• 48 tube maps
• glue

### Making a module

First, take a tube map and fold the cover over. This will ensure that your shape will have tube (map and not index) on the outside and you will have pages to tuck your tabs between later.
Now fold one corner diagonally across to another corner. It does not matter which diagonal you chose for the first piece but after this all following pieces must be the same as the first.
Now fold the overlapping bit back over the top.
Turn it over and fold this overlap over too.
You will need 48 of these and some glue.

### Putting it together

By slotting three or four of these modules together, you can make a pyramid with a triangle or square as its base.
A stellated rhombicuboctahedron is a rhombicuboctahedron with a pyramid, or stellation on each face. In other words, you now need to build a rhombicuboctahedron with the bases of pyramids like these. A rhombicuboctahedron looks like this:
en.wiki User Cyp, CC BY-SA 3.0
More usefully, its net looks like this:
To build a stellated rhombicuboctahedron, make this net, but with each shape as the base of a pyramid. This is what it will look like 6/48 tube maps in:
If you make on of these, please tweet me a photo so I can see it!
Edit: Proof that these instructions can be followed:
Previous post in series
 Tube map Platonic solids, pt. 3
This is the fourth post in a series of posts about tube map folding.
Next post in series
 Tube map kaleidocycles

### Similar posts

 Tube map Platonic solids, pt. 2 Tube map kaleidocycles Tube map Platonic solids, pt. 3 Electromagnetic Field talk

Comments in green were written by me. Comments in blue were not written by me.
I wish you'd make the final stellation of the rhombicuboctahedron! And show us! I know the shapes of the faces but have been stuck two years on the assembly!
Roberts, David

format: plain


text:
# Chapter 4 - Probability - 4-6 Counting - Basic Skills and Concepts: 29

$10$

#### Work Step by Step

Because the order is not important, we can use the combination rule to determine the number of possibilities: $\frac{5!}{(5-2)!2!}=10$.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
3 views

Common Data for Questions 71,72,73:
The figure shows the high-frequency capacitance-voltage (C-V) characteristics of a $\mathrm{Metal} / \mathrm{SiO}_{2} / \text{silicon (MOS)}$ capacitor having an area of $1 \times 10^{-4} \mathrm{~cm}^{2}$. Assume that the permittivities $\left(\varepsilon_{0} \varepsilon_{r}\right)$ of silicon and $\mathrm{SiO}_{2}$ are $1 \times 10^{-12} \mathrm{~F/cm}$ and $3.5 \times 10^{-13} \mathrm{~F/cm}$ respectively.

Consider the following statements about the $\mathrm{C}-\mathrm{V}$ characteristics plot:

$\text{S1:}$ The MOS capacitor has an $n$-type substrate.
$\text{S2:}$ If positive charges are introduced in the oxide, the $\mathrm{C}-\mathrm{V}$ plot will shift to the left.

Then which of the following is true?

1. Both $\mathrm{S} 1$ and $\mathrm{S} 2$ are true
2. $\mathrm{S} 1$ is true and $\mathrm{S} 2$ is false
3. $\mathrm{S} 1$ is false and $\mathrm{S} 2$ is true
4. Both $\text{S1}$ and $\text{S2}$ are false


text:
# [texhax] Sectionining and referencing question

Peter Flom Flom at ndri.org
Mon Nov 6 23:54:39 CET 2006

```Hello

I am writing a book, and would like a more casual style than is typical
of what I write or what LaTeX produces.  One thing I wanted to do is
avoid the 'academic' style of section numbers (when I showed a draft to
some friends, they commented that this was overly formal).

(It's a book about being learning disabled, and intended for a more or
less general audience)

Per the advice in the LaTeX Companion, I started with

\setcounter{secnumdepth}{-2}

in the preamble, but on typesetting it (pdflatex in WinEdt), all the
chapters, sections and subsections were still numbered.  I looked
through the log, but saw no problems.

How does one produce such a book?
And what is a good method of referring to sections in a more casual
'friendly' way?


text:
The current GATK version is 3.7-0
Examples: Monday, today, last week, Mar 26, 3/26/04

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### ☞ Get notifications!

You can opt in to receive email notifications, for example when your questions get answered or when there are new announcements, by following the instructions given here.

#### ☞ Did you remember to?

1. Search using the upper-right search box, e.g. using the error message.
2. Try the latest version of tools.
3. Include tool and Java versions.
4. Tell us whether you are following GATK Best Practices.
5. Include relevant details, e.g. platform, DNA- or RNA-Seq, WES (+capture kit) or WGS (PCR-free or PCR+), paired- or single-end, read length, expected average coverage, somatic data, etc.
6. For tool errors, include the error stacktrace as well as the exact command.
7. For format issues, include the result of running ValidateSamFile for BAMs or ValidateVariants for VCFs.
8. For weird results, include an illustrative example, e.g. attach IGV screenshots according to Article#5484.
9. For a seeming variant that is uncalled, include results of following Article#1235.

#### ☞ Did we ask for a bug report?

Then follow instructions in Article#1894.

#### ☞ Formatting tip!

Wrap blocks of code, error messages and BAM/VCF snippets--especially content with hashes (#)--with lines with three backticks (  ) each to make a code block as demonstrated here.

Picard 2.9.0 is now available. Download and read release notes here.
GATK 3.7 is here! Be sure to read the Version Highlights and optionally the full Release Notes.

# Rare variants from annotated vcf file

New YorkMember Posts: 5
edited February 2014

Hi,

I have annotated my vcf file of 20 samples from Unified genotyper using the following steps.

Unified genotyper->Variantrecalibration->Applyrecalibration->VariantAnnotator

My question is how should I proceed if I have to select rare variants (MAF<1%) for the candidate genes that I have,for each of these 20 samples?

Post edited by rohan1925 on
Tagged:

edited February 2014

Hi there,

If you're asking how you should design your analysis, I'm afraid this question is beyond our current scope of support. I can only point you to the variant manipulation tools (e.g. SelectVariants) and answer specific questions about how to use them.

Geraldine Van der Auwera, PhD

• New YorkMember Posts: 5
edited February 2014

I want to use SelectVariants only since I have used all the tools from GATK until Variant Annotator for variants.So in this how should I get MAF (minor allele frequency) to be less than 1%,using -AF parameter?

Also,I need to select variants only for candidate genes that I have.

Ah, sorry to get back to you so late. I believe you should be able to do that simply using -select "AF < 0.01"`. Let me know if that doesn't work for you.

Geraldine Van der Auwera, PhD

• New YorkMember Posts: 5

Hi,

Thanks for your response! I am using this command,and getting some error.

java -Xmx2g -jar /GenomeAnalysisTK-2.7-4-g6f46d11/GenomeAnalysisTK.jar -T SelectVariants -R human_g1k_v37.fasta --variant annotated.vcf -o annotated.select.vcf -select "AF<0.01"

##### ERROR stack trace

java.lang.IllegalArgumentException: Invalid JEXL expression detected for select-0 with message ![0,9]: 'AF < 0.01;' < error

In my VariantRecalibration,I had asked for following parameters to be included:
-an DP -an QD -an FS -an MQRankSum -an ReadPosRankSum

Do I have to include -an AF as well?


text:
# Study of the near-barrier scattering of $^{8}$He on $^{208}$Pb

Abstract : The structure and dynamics of 8He have been studied through the collision process with a 208Pb target at energies of 22 and 16 MeV, above and below the Coulomb barrier, respectively. The energy and angular distributions of the elastically scattered 8He and the 6;4He fragments were measured. In this paper, we discuss the method used to determine the effective position of the beam spot on the reaction target and the scattering and solid angles of each pixel of the detector array.
Type de document :
Communication dans un congrès
XXXIV Mazurian Lakes Conference on Physics, Sep 2015, Piaski, Poland. Acta Physica Polonica B, 47 (3), pp.841-846, 2016, 〈10.5506/APhysPolB.47.841〉

http://hal.in2p3.fr/in2p3-01294414
Contributeur : Michel Lion <>
Soumis le : mardi 29 mars 2016 - 11:34:42
Dernière modification le : jeudi 11 janvier 2018 - 06:28:19

### Citation

G. Marquínez-Duran, A.M. Sanchez-Benítez, I. Martel, L. Acosta, K. Rusek, et al.. Study of the near-barrier scattering of $^{8}$He on $^{208}$Pb. XXXIV Mazurian Lakes Conference on Physics, Sep 2015, Piaski, Poland. Acta Physica Polonica B, 47 (3), pp.841-846, 2016, 〈10.5506/APhysPolB.47.841〉. 〈in2p3-01294414〉

### Métriques

Consultations de la notice