//No Comment - The Blockchain, Technology Beats Algorithms & Bridges in Complex Networks
Written by Alex Armstrong   
Tuesday, 20 December 2016

• The Blockchain: A Gentle Four Page Introduction

• Technology Beats Algorithms (in Exact String Matching) 

• Bridges in Complex Networks

nocomment

Sometimes the news is reported well enough elsewhere and we have little to add other than to bring it to your attention.

No Comment is a format where we present original source information, lightly edited, so that you can decide if you want to follow it up. 

 

The Blockchain: A Gentle Four Page Introduction

Just about everyone is convinced that the blockchain, as introduced and used by Bitcoin, is a key technology of the future. So knowing how it works might be a good investment:

Blockchain is a distributed database that keeps a chronologicallygrowing list (chain) of records (blocks) secure from tampering and revision. While computerisation has changed the nature of a ledger from clay tables in the old days to digital records in modern days, blockchain technology is the first true innovation in record keeping that could potentially revolutionise the basic principles of information keeping. In this note, we provide a brief self contained introduction to how the blockchain works.

And the good news is that this is another story of Alice and Bob.

Also see:   Inside Bitcoin - The Block Chain 

 

Technology Beats Algorithms (in Exact String Matching)

We all love thinking about non-obvious algorithms that do things so much faster than the obvious approach. This is almost what computer science at its best is all about but what if we were misguided and the way to do things faster isn't to invent better algorithms but improve the hardware. It seems that this is indeed the case in the all important area of string matching:

More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naive algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets.

The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols and the increasing order of their probabilities in the text was the best.

nocomment

 

Bridges in Complex Networks

Graphs are both fun to study and sometimes important. Graphs in theory come in all sorts but what about the ones we find in the real world are just random. An edge i.e. a connection in a graph that, if removed breaks the graph into two disconnected parts, i.e. there isn't an alternative connection, is obviously important - its called a bridge.

 

bridges

 

The question is to real networks have random bridges?: 

A bridge in a graph is an edge whose removal disconnects the graph and increases the number of connected components. We calculate the fraction of bridges in a wide range of real-world networks and their randomized counterparts.

We find that real networks typically have more bridges than their completely randomized counterparts, but very similar fraction of bridges as their degree-preserving randomizations.

We define a new edge centrality measure, called bridgeness, to quantify the importance of a bridge in damaging a network. We find that certain real networks have very large average and variance of bridgeness compared to their degree-preserving randomizations and other real networks.

Finally, we offer an analytical framework to calculate the bridge fraction , the average and variance of bridgeness for uncorrelated random networks with arbitrary degree distributions.

 

nocomment

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter,subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin.

Banner

nocommentTheory


Chainguard Joins Docker Verified Publisher Program
15/03/2024

Chainguard has joined the Docker Verified Publisher (DVP) program, meaning its Chainguard Developer Images are now officially available on Docker's container image registry.



Couchbase's Coding Assistant Goes GA
11/03/2024

Capella iQ, the AI coding assistant for developers that makes interacting with Couchbase using natural language possible, has gone from private beta to being generally available.


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

 

Last Updated ( Wednesday, 21 December 2016 )