SUMMARY / RELATED TOPICS

8th millennium BC

The 8th millennium BC spanned the years 8000 BC to 7001 BC. It is impossible to date events that happened around the time of this millennium and all dates mentioned here are estimates based on geological and anthropological analysis. Neolithic culture and technology had become widespread in the Near East by 8000 BC, it was spreading westward but is not believed to have reached Europe, still Palaeolithic, until about the end of this millennium. Planting and harvesting techniques were transferred through Asia Minor and across the Aegean Sea to Greece and the Balkans; the techniques were, in the main, cultivation of barleys. Though the Neolithic was now established throughout much of the Fertile Crescent, most people around the world still lived in scattered hunter-gatherer communities which remained in the Palaeolithic; the world population was stable and increasing. It has been estimated that there were some five million people c. 10,000 BC growing to forty million by 5000 BC and 100 million by 1600 BC.

That is an average growth rate of 0.027% p.a. from the beginning of the Neolithic to the Middle Bronze Age. By c. 7500 BC, important sites in or near the Fertile Crescent included Jericho,'Ain Ghazal, Tell Aswad, Tell Abu Hureyra, Tell Qaramel, Tell Mureibit, Jerf el Ahmar, Göbekli Tepe, Nevalı Çori, Hacilar, Çatalhöyük, Hallan Çemi Tepesi, Çayönü Tepesi, Jarmo, Ganj Dareh and Ali Kosh. Jericho in the Jordan Valley continued to be the world's most significant site through this millennium.Çatalhöyük was a large Neolithic and Chalcolithic proto-city settlement in southern Anatolia which flourished from c. 7500 BC until it was abandoned c. 5700 BC. See image above right. Pottery found in the Near East at this time is classified as Pre-Pottery Neolithic B until c. 6500 BC. The Natufian culture co-existed with PPNB; the potter's wheel had not yet been invented and pottery was still hand-built by means of coiling, pit fired. It was from c. 8000 BC that agriculture developed throughout the Americas in modern Mexico.

There were numerous New World crops, as they are now termed, domestication began with the potato and the cucurbita about this time. Other crops began to be harvested over the next 7,500 years including chili peppers, peanut, beans, sunflower and tomato; the date of c. 7640 BC has been theorised for the impact of Tollmann's hypothetical bolide with Earth and the resultant global cataclysm. The date for construction of a round-house near Howick, Northumberland is calculated c. 7600 BC by radiocarbon dating. The site is believed to have been occupied for about 100 years; the homo sapiens fossil from Combe-Capelle in southern France, discovered in 1909, is estimated to be 9,500 years old. Bronowski, Jacob; the Ascent of Man. London: BBC. ISBN 978-1-849-90115-4. Roberts, J. M.. Shorter Illustrated History of the World. Abingdon: Helicon Publishing Ltd. ISBN 0-1951-1504-X

Bermagui River

Bermagui River is an open and trained semi-mature wave dominated barrier estuary or perennial river located in the South Coast region of New South Wales, Australia. Formed by the confluence of the Coolagolite Creek and Nutleys Creek, near Bermagui South, the Bermagui River flows east, before reaching its mouth into the Tasman Sea of the South Pacific Ocean near Bermagui; the river descends 26 metres over its 7 kilometres course. The catchment area of the river is 83 square kilometres with a volume of 2,160 megalitres over a surface area of 2.2 square kilometres, at an average depth of 1.1 metres. The name of the river is derived from the Aboriginal Dyirringanj word, spelled variously as permageua and bermaguee, meaning a canoe with paddles. Rivers of New South Wales List of rivers of New South Wales List of rivers of Australia "Bega River catchment". Office of Environment and Heritage. Government of New South Wales

Longest common substring problem

In computer science, the longest common substring problem is to find the longest string, a substring of two or more strings. The longest common substring of the strings "ABABC", "BABCA" and "ABCBA" is string "ABC" of length 3. Other common substrings are "A", "AB", "B", "BA", "BC" and "C". ABABC ||| BABCA ||| ABCBA Given two strings, S of length m and T of length n, find the longest string, substring of both S and T. A generalization is the k-common substring problem. Given the set of strings S =, where | S i | = n i and Σ n i = N. Find for each 2 ≤ k ≤ K, the longest strings which occur as substrings of at least k strings. One can find the lengths and starting positions of the longest common substrings of S and T in Θ time with the help of a generalized suffix tree. Finding them by dynamic programming costs Θ; the solutions to the generalized problem take Θ space and Θ } time with dynamic programming and take Θ time with generalized suffix tree. The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings, finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

The figure on the right is the suffix tree for the strings "ABAB", "BABA" and "ABBA", padded with unique string terminators, to become "ABAB$0", "BABA$1" and "ABBA$2". The nodes representing "A", "B", "AB" and "BA" all have descendant leaves from all of the strings, numbered 0, 1 and 2. Building the suffix tree takes Θ time. If the tree is traversed from the bottom up with a bit vector telling which strings are seen below each node, the k-common substring problem can be solved in Θ time. If the suffix tree is prepared for constant time lowest common ancestor retrieval, it can be solved in Θ time; the following pseudocode finds the set of longest common substrings between two strings with dynamic programming: function LCSubstr L:= array z:= 0 ret:= for i:= 1..r for j:= 1..n if S = T if i = 1 or j = 1 L:= 1 else L:= L + 1 if L > z z:= L ret:= else if L = z ret:= ret ∪ else L:= 0 return ret This algorithm runs in O time. The variable z is used to hold the length of the longest common substring found so far.

The set ret is used to hold the set of strings. The set ret can be saved efficiently by just storing the index i, the last character of the longest common substring instead of S, thus all the longest common substrings would be, for each i in ret, S. The following tricks can be used to reduce the memory usage of an implementation: Keep only the last and current row of the DP table to save memory Store only non-zero values in the rows; this can be done using hash tables instead of arrays. This is useful for large alphabets. Data deduplication Longest palindromic substring n-gram, all the possible substrings of length n that are contained in a string Plagiarism detection Dictionary of Algorithms and Data Structures: longest common substring Perl/XS implementation of the dynamic programming algorithm Perl/XS implementation of the suffix tree algorithm Dynamic programming implementations in various languages on wikibooks working AS3 implementation of the dynamic programming algorithm Suffix Tree based C implementation of Longest common substring for two strings