Boyer-Moor Exact Pattern Matching Algorithm

https://www.youtube.com/watch?v=4Xyhb72LCX4

Boyer–Moore string-search algorithm - Wikipedia

O(n + m) where n and m are lengths of p (search pattern) and t (text to search)

advantages

1. skip alignments
2. doesn't compare all the characters

Try alignments from left-to-right and compare characters in the alignment from right-to-left 

Bad character rule - if a mismatched character is found going from right-to-left then shift the pattern to the right until a matching character in the pattern is found

Good suffix rule - shift until the good matching suffix matches

Try both rules and shift by the largest amount of shift

number of characters to shift is stored in a lookup table which is created using only the search pattern

 The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.

Randomly sample files

From https://unix.stackexchange.com/questions/108581/how-to-randomly-sample-a-subset-of-a-file 

perl -ne 'print if (rand() < .01)' huge_file.csv > sample.csv

BOTORCH: A Framework for Efficient Monte-Carlo Bayesian Optimization

 BOTORCH: A Framework for Efficient Monte-Carlo Bayesian Optimization

To address these problems, we developed BoTorch, a framework for Bayesian optimization research, and Ax, a robust platform for adaptive experimentation. BoTorch follows the same modular design philosophy as PyTorch, which makes it very easy for users to swap out or rearrange individual components in order to customize all aspects of their algorithm, thereby empowering researchers to do state-of-the art research on modern Bayesian optimization methods. By exploiting modern parallel computing paradigms on both CPUs and GPUs, it is also fast.

Core Data Science researchers discuss research award opportunity in adaptive experimentation

SQL Challenge

 https://www.hackerrank.com/challenges/revising-the-select-query/problem

Easy

1. Query all columns for all American cities in the CITY table with populations larger than 100000. The CountryCode for America is USA.

select * from City where population > 100000 and CountryCode='USA'

2. Query the NAME field for all American cities in the CITY table with populations larger than 120000. The CountryCode for America is USA.

The CITY table is described as follows:

select Name from City where population > 120000 and CountryCode='USA' 

3. Query a list of CITY names from STATION for cities that have an even ID number. Print the results in any order, but exclude duplicates from the answer.

select distinct City from Station where mod(id,2)=0 

Medium 

1. Query an alphabetically ordered list of all names in OCCUPATIONS, immediately followed by the first letter of each profession as a parenthetical (i.e.: enclosed in parentheses). For example: AnActorName(A), ADoctorName(D), AProfessorName(P), and ASingerName(S).

select * from (select concat('There are a total of ',count(occupation),' ',lower(occupation),'s.') as stat from occupations group by occupation) as innertable order by innertable.stat;

2.  Pivot the Occupation column in OCCUPATIONS so that each Name is sorted alphabetically and displayed underneath its corresponding Occupation. The output column headers should be Doctor, Professor, Singer, and Actor, respectively.

Note: Print NULL when there are no more names corresponding to an occupation.

https://codingsight.com/pivot-tables-in-mysql/

User nobuh:

select  
    max(if(occupation='Doctor', name, null)) as docname,
    max(case when occupation='Professor' then name else null end) as profname,
    max(case when occupation='Singer' then name else null end) as singername,
    max(case when occupation='Actor' then name else null end) as actorname
    from (
    select 
        a.occupation, 
        a.name,
        (select count(name) from occupations b where a.occupation=b.occupation and a.name > b.name) as name_rank
    from occupations a
) as rank_summary
group by name_rank
order by name_rank

name_rank:

select 

        a.occupation, 

        a.name,

--         get the name rank by comparing the names

        (select count(name) from occupations b where a.occupation=b.occupation and a.name > b.name) as name_rank

from occupations a

order by name_rank;

Output:

Doctor Aamina 0

Actor Eve 0

Singer Christeen 0

Professor Ashley 0

Doctor Julia 1

Singer Jane 1

Professor Belvet 1

Actor Jennifer 1

Actor Ketty 2

Singer Jenny 2

Doctor Priya 2

Professor Britney 2

Singer Kristeen 3

Professor Maria 3

Actor Samantha 3

Professor Meera 4

Professor Naomi 5

Professor Priyanka 6

3. You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node:

Root: If node is root node.

Leaf: If node is leaf node.

Inner: If node is neither root nor leaf node.

Answer

select * from bst;

select distinct '------' from bst;

select * from (

select n,'Root' from bst bo where bo.p is null

union all

select n,'Inner' from bst bo where bo.p is not null and bo.n in (select bi.p from bst bi where p is not null)

union all

select n,'Leaf' from bst bo where bo.p is not null and bo.n not in (select bi.p from bst bi where p is not null)

) tmp

order by n;

Output

1 2

3 2

5 6

7 6

2 4

6 4

4 15

8 9

10 9

12 13

14 13

9 11

13 11

11 15

15 NULL

------

1 Leaf

2 Inner

3 Leaf

4 Inner

5 Leaf

6 Inner

7 Leaf

8 Leaf

9 Inner

10 Leaf

11 Inner

12 Leaf

13 Inner

14 Leaf

15 Root

 4. Given the table schemas below, write a query to print the company_code, founder name, total number of lead managers, total number of senior managers, total number of managers, and total number of employees. Order your output by ascending company_code.

https://www.hackerrank.com/challenges/the-company/problem

SQL

select c.company_code,founder
,count(distinct lead_manager_code)
,count(distinct senior_manager_code)
,count(distinct manager_code)
,count(distinct employee_code)
from company c left join employee e on c.company_code=e.company_code group by c.company_code,founder
order by cast(substr(c.company_code,2,5) as UNSIGNED);

Output

C1 Monika 1 2 1 2
C2 Samantha 1 1 2 2

5. /*
https://www.hackerrank.com/challenges/weather-observation-station-20/problem
A median is defined as a number separating the higher half of a data set from the lower half. Query the median of the Northern Latitudes (LAT_N) from STATION and round your answer to  decimal places.
*/

SQL

select format(lat_n,4) from (

select s1.id,s1.lat_n,(select count(*) from station),(select cast(count(id)/2 as unsigned) from station) as mid_rank,(select count(s2.id) from station s2 where s1.lat_n > s2.lat_n) as latn_rank from station s1 order by s1.lat_n    

) as rank_table

where (latn_rank +1 )= mid_rank; 

or from 

user vinaychinni1998

select round(s.lat_n,4) from station s where (select round(count(s.id)/2)-1 from station) = (select count(s1.id) from station s1 where s1.lat_n > s.lat_n);

Output

83.8913

6. https://www.hackerrank.com/challenges/interviews/problem

/*

Samantha interviews many candidates from different colleges using coding challenges and contests. Write a query to print the contest_id, hacker_id, name, and the sums of total_submissions, total_accepted_submissions, total_views, and total_unique_views for each contest sorted by contest_id. Exclude the contest from the result if all four sums are .

Note: A specific contest can be used to screen candidates at more than one college, but each college only holds  screening contest.

Sample output

66406 17973 Rose 111 39 156 56

66556 79153 Angela 0 0 11 10

94828 80275 Frank 150 38 41 15

*/

Note: View_Stats and Submission_Stats have duplicate challenge_id's !

from user  dongyuzhang

select con.contest_id,

        con.hacker_id, 

        con.name, 

        sum(total_submissions), 

        sum(total_accepted_submissions), 

        sum(total_views), sum(total_unique_views)

from contests con 

join colleges col on con.contest_id = col.contest_id 

join challenges cha on  col.college_id = cha.college_id 

left join

(select challenge_id, sum(total_views) as total_views, sum(total_unique_views) as total_unique_views

from view_stats group by challenge_id) vs on cha.challenge_id = vs.challenge_id 

left join

(select challenge_id, sum(total_submissions) as total_submissions, sum(total_accepted_submissions) as total_accepted_submissions from submission_stats group by challenge_id) ss on cha.challenge_id = ss.challenge_id

    group by con.contest_id, con.hacker_id, con.name

        -- having sum(total_submissions)!=0 or 

        --         sum(total_accepted_submissions)!=0 or

        --         sum(total_views)!=0 or

        --         sum(total_unique_views)!=0

having ( sum(total_submissions) + sum(total_accepted_submissions) + sum(total_views) + sum(total_unique_views)) > 0

            order by contest_id;

Output

845 579 Rose 1987 580 1635 566 

858 1053 Angela 703 160 1002 384 

883 1055 Frank 1121 319 1217 338 

1793 2655 Patrick 1337 360 1216 412 

https://www.w3schools.com/sql/func_mysql_date_add.asp

SELECT DATE_ADD("2017-06-15", INTERVAL 10 DAY);  # returns 2017-06-25

I'm back!

Having persistent / intermittent / sporadic Wifi disconnections with Windows 10?

It may be due to Window's Wifi sense.

How to disable Wifi sense

 

https://dowser.org/wifi-frequently-disconnects-windows-10-wifi-sense-fix/

Go to Manage Wifi settings 

Once there, find and disable the following settings: Connect to suggested open hotspots and Connect to networks shared by my friends. This should fix the annoying issue and you should no longer have any problem with unwanted disconnection from the network you’re using. Just remember to save the changes you’ve just made by clicking on OK/Save.

 

Turn these OFF

 

Good luck!

Percona Bash and GNU Tools

http://www.percona.com/blog/2015/03/17/mysql-qa-linux-upskill-bash-gnu-tools-scripting-fun/?mkt_tok=3RkMMJWWfF9wsRojuqnBZKXonjHpfsX%2F6O0oX6K3lMI%2F0ER3fOvrPUfGjI4CSMBjI%2BSLDwEYGJlv6SgFQrLNMadt3rgNWxI%3D

gnuwin32.sourceforge.net/

Points of Significance in Biology - Nature column

http://www.nature.com/nmeth/journal/v10/n9/full/nmeth.2613.html

http://www.nature.com/collections/qghhqm

Since September 2013 Nature Methods has been publishing a monthly column on statistics aimed at providing reseachers in biology with a basic introduction to core statistical concepts and methods, including experimental design. Although targeted at biologists, the articles are useful guides for researchers in other disciplines as well. A continuously updated list of these articles is provided below.

Importance of being uncertain - How samples are used to estimate population statistics and what this means in terms of uncertainty.

Error Bars - The use of error bars to represent uncertainty and advice on how to interpret them.

Significance, P values and t-tests - Introduction to the concept of statistical significance and the one-sample t-test.

Power and sample size - Using statistical power to optimize study design and sample numbers.

Visualizing samples with box plots - Introduction to box plots and their use to illustrate the spread and differences of samples. See also: Kick the bar chart habit and BoxPlotR: a web tool for generation of box plots

Comparing samples—part I - How to use the two-sample t-test to compare either uncorrelated or correlated samples.

Comparing samples—part II - Adjustment and reinterpretation of P values when large numbers of tests are performed.

Nonparametric tests - Use of nonparametric tests to robustly compare skewed or ranked data.

Designing comparative experiments - The first of a series of columns that tackle experimental design shows how a paired design achieves sensitivity and specificity requirements despite biological and technical variability.

Analysis of variance and blocking - Introduction to ANOVA and the importance of blocking in good experimental design to mitigate experimental error and the impact of factors not under study.

Replication - Technical replication reveals technical variation while biological replication is required for biological inference.

Nested designs - Use the relative noise contribution of each layer in nested experimental designs to optimally allocate experimental resources using ANOVA.

Two-factor designs - It is common in biological systems for multiple experimental factors to produce interacting effects on a system. A study design that allows these interactions can increase sensitivity.

Sources of variation - To generalize experimental conclusions to a population, it is critical to sample its variation while using experimental control, randomization, blocking and replication to collect replicable and meaningful results.

Matrix factorization - R-bloggers

http://www.r-bloggers.com/testing-recommender-systems-in-r/

http://www.r-bloggers.com/matrix-factorization/?utm_source=feedburner&utm_medium=email&utm_campaign=Feed%3A+RBloggers+%28R+bloggers%29

Latent Factor Matrix Factorization.
Singular value decomposition 
optim() function in R for optimization

http://www.r-bloggers.com/in-depth-introduction-to-machine-learning-in-15-hours-of-expert-videos/ 
In-depth introduction to machine learning in 15 hours of expert videos 

The Elements of Programming Style

http://en.wikipedia.org/wiki/The_Elements_of_Programming_Style

1. Write clearly -- don't be too clever.
2. Say what you mean, simply and directly.
3. Use library functions whenever feasible.
4. Avoid too many temporary variables.
5. Write clearly -- don't sacrifice clarity for efficiency.
6. Let the machine do the dirty work.
7. Replace repetitive expressions by calls to common functions.
8. Parenthesize to avoid ambiguity.
9. Choose variable names that won't be confused.
10. Avoid unnecessary branches.
11. If a logical expression is hard to understand, try transforming it.
12. Choose a data representation that makes the program simple.
13. Write first in easy-to-understand pseudo language; then translate into whatever language you have to use.
14. Modularize. Use procedures and functions.
15. Avoid gotos completely if you can keep the program readable.
16. Don't patch bad code -- rewrite it.
17. Write and test a big program in small pieces.
18. Use recursive procedures for recursively-defined data structures.
19. Test input for plausibility and validity.
20. Make sure input doesn't violate the limits of the program.
21. Terminate input by end-of-file marker, not by count.
22. Identify bad input; recover if possible.
23. Make input easy to prepare and output self-explanatory.
24. Use uniform input formats.
25. Make input easy to proofread.
26. Use self-identifying input. Allow defaults. Echo both on output.
27. Make sure all variables are initialized before use.
28. Don't stop at one bug.
29. Use debugging compilers.
30. Watch out for off-by-one errors.
31. Take care to branch the right way on equality.
32. Be careful if a loop exits to the same place from the middle and the bottom.
33. Make sure your code does "nothing" gracefully.
34. Test programs at their boundary values.
35. Check some answers by hand.
36. 10.0 times 0.1 is hardly ever 1.0.
37. 7/8 is zero while 7.0/8.0 is not zero.
38. Don't compare floating point numbers solely for equality.
39. Make it right before you make it faster.
40. Make it fail-safe before you make it faster.
41. Make it clear before you make it faster.
42. Don't sacrifice clarity for small gains in efficiency.
43. Let your compiler do the simple optimizations.
44. Don't strain to re-use code; reorganize instead.
45. Make sure special cases are truly special.
46. Keep it simple to make it faster.
47. Don't diddle code to make it faster -- find a better algorithm.
48. Instrument your programs. Measure before making efficiency changes.
49. Make sure comments and code agree.
50. Don't just echo the code with comments -- make every comment count.
51. Don't comment bad code -- rewrite it.
52. Use variable names that mean something.
53. Use statement labels that mean something.
54. Format a program to help the reader understand it.
55. Document your data layouts.
56. Don't over-comment

The Elements of Style

Vigorous writing is concise. A sentence should contain no unnecessary words, a paragraph no unnecessary sentences, for the same reason that a drawing should have no unnecessary lines and a machine no unnecessary parts. This requires not that the writer make all his sentences short, or that he avoid all detail and treat his subjects only in outline, but that he make every word tell.

—"Elementary Principles of Composition", The Elements of Style^[10]

Research methods: Know when your numbers are significant

http://www.nature.com/nature/journal/v492/n7428/fig_tab/492180a_T1.html  

When N is only 2 or 3, it would be more transparent to just plot the independent data points, and let the readers interpret the data for themselves, rather than showing possibly misleading P values or error bars and drawing statistical inferences. 

All experimental biologists and all those who review their papers should know what sort of sampling errors are to be expected in common experiments, such as determining the percentages of live and dead cells or counting the number of colonies on a plate or cells in a microscope field. Otherwise, they will not be able to judge their own data critically, or anyone else's.   Table 1: Statistics glossary: Some common statistical concepts and their uses in analysing experimental results.

Term	Meaning	Common uses
N, number of independent samples; t, the t-statistic; p, probability.
Standard deviation (s.d.)	The typical difference between each value and the mean value.	Describing how broadly the sample values are distributed.  s.d. = √−(∑ (x − mean)2/(N − 1))
Standard error of the mean (s.e.m.)	An estimate of how variable the means will be if the experiment is repeated multiple times.	Inferring where the population mean is likely to lie, or whether sets of samples are likely to come from the same population.  s.e.m. = s.d./√−N
Confidence interval (CI; 95%)	With 95% confidence, the population mean will lie in this interval.	To infer where the population mean lies, and to compare two populations.  CI = mean ± s.e.m. × t(N−1)
Independent data	Values from separate experiments of the same type that are not linked.	Testing hypotheses about the population.
Replicate data	Values from experiments where everything is linked as much as possible.	Serves as an internal check on performance of an experiment.
Sampling error	Variation caused by sampling part of a population rather than measuring the whole population.	Can reveal bias in the data (if it is too small) or problems with conduct of the experiment (if it is too big). In binomial distributions (such as live and dead cell counts) the expected s.d. is √−(N × p × (1 − p)); in Poisson dist

Points of significance: Power and sample size

Points of significance: Power and sample size

    Martin Krzywinski  
    & Naomi Altman  

    Nature Methods
    10,
    1139–1140
    (2013)
    doi:10.1038/nmeth.2738

http://www.nature.com/nmeth/journal/v10/n12/full/nmeth.2738.html

Figure 3: Decreasing specificity increases power.

(a) Observations are assumed to be from the null distribution (H₀) with mean μ₀. We reject H₀ for values larger than x^* with an error rate α (red area). (b) The alternative hypothesis (H_A) is the competing scenario with a different mean μ_A. Values sampled from H_A smaller than x^* do not trigger rejection of H₀ and occur at a rate β. Power (sensitivity) is 1 − β (blue area). (c) Relationship of inference errors to x^*. The color key is same as in Figure 1.

Figure 4: Impact of sample (n) and effect size (d) on power.
 

H₀ and H_A are assumed normal with σ = 1. (a) Increasing n decreases the spread of the distribution of sample averages in proportion to 1/√n. Shown are scenarios at n = 1, 3 and 7 for d = 1 and α = 0.05. Right, power as function of n at four different α values for d = 1. The circles correspond to the three scenarios. (b) Power increases with d, making it easier to detect larger effects. The distributions show effect sizes d = 1, 1.5 and 2 for n = 3 and α = 0.05. Right, power as function of d at four different a values for n = 3.