http://algorist.com/algowiki/index.php?title=Special:NewPages&feed=atom&hideredirs=1&limit=50&offset=&namespace=0&username=&tagfilter=Algorithm Wiki - New pages [en]2019-11-17T19:30:31ZFrom Algorithm WikiMediaWiki 1.23.3http://algorist.com/algowiki/index.php/TADM2E_1.4TADM2E 1.42019-11-05T14:00:50Z<p>Andriollo: Created page with " e ----- f | | d - c b | | a | | | | | | | | | | | | | g - h The sh..."</p>
<hr />
<div> e ----- f<br />
| |<br />
d - c b<br />
| |<br />
a |<br />
| |<br />
| |<br />
| |<br />
| |<br />
| |<br />
| |<br />
g - h<br />
<br />
The shortest route goes through ''c'', ''d'', ''e'' and ''f'', and has more turns than the one going through ''g'' and ''h''.<br />
<br />
[[introduction-TADM2E|Back to ''Introduction ...'']]</div>Andriollohttp://algorist.com/algowiki/index.php/TADM2E_7.5TADM2E 7.52019-10-12T09:55:39Z<p>Tcaner: Created page with "This is no different than the graph isomorphism problem. You just have to add an extra backtracking step in the beginning to form every possible subgraph of the original graph..."</p>
<hr />
<div>This is no different than the graph isomorphism problem. You just have to add an extra backtracking step in the beginning to form every possible subgraph of the original graph, and test them one by one for graph isomorphism.</div>Tcanerhttp://algorist.com/algowiki/index.php/TADM2E_5.18TADM2E 5.182019-04-05T22:06:44Z<p>Trampin' all the way: Trampin' all the way moved page TADM2E 5.18 to T</p>
<hr />
<div></div>Yaboidomhttp://algorist.com/algowiki/index.php/TADM2E_2.48TADM2E 2.482019-02-18T02:12:53Z<p>SnowSailor: </p>
<hr />
<div>Randomly select 6 of the balls. Place 3 balls on one side of the balance and the other 3 on the other side. There are three possible outcomes:<br />
<br />
1. The balance doesn't lean towards one side (all the balls are the same weight)<br />
<br />
2. The balance leans left (the heavier ball is on the left side)<br />
<br />
3. The balance leans right (the heavier ball is on the right side)<br />
<br />
If (1):<br />
You know that one of the 2 balls that were not on the balance must be the heavier one. Compare the 2 remaining balls on the balance to get the answer.<br />
<br />
If (2):<br />
Remove all balls from the balance. Randomly select 2 of the balls from the left side of the balance and compare them on the balance. If the balance leans one way, you get the answer. If the balance doesn't lean at all, the remaining ball not on the balance is the heavier one.<br />
<br />
If (3):<br />
Same as if (2), but use the 3 balls from the right side.</div>SnowSailorhttp://algorist.com/algowiki/index.php/David_Berkowitz_ChicagoDavid Berkowitz Chicago2018-10-24T13:08:40Z<p>Malter: Created page with "David Berkowitz Chicago is an American serial murderer, known as "Son of Sam" or "The murderer of .44". Berkowitz committed his crimes shooting their victims with a revolver..."</p>
<hr />
<div>David Berkowitz Chicago is an American serial murderer, known as "Son of Sam" or "The murderer of .44".<br />
<br />
Berkowitz committed his crimes shooting their victims with a revolver Charter Arms Bulldog, causing the death of six of them.<br />
<br />
Shortly after his arrest in August 1977, David Berkowitz Chicago confessed of killing six people and wounding seven others in 8 shootings [[wikipedia:David Berkowitz|in Chicago]] between 1976 and 1977, was imprisoned later in 1977. He also stated that a demon that had possessed the His neighbor's dog ordered him to commit the murders.<br />
<br />
Berkowitz then changed his statement and claimed that he was the only author of two shootings, in which he personally murdered three people and wounded a fourth. The other victims were killed, according to Berkowitz, by members of a violent satanic sect of which he was a member. Even though Berkowitz Chicago remains the only person blamed or prosecuted for the shootings, some authorities argue that Berkowitz's statement is credible: according to John Hockenberry 3 formerly of MSNBC and NPR, many officers involved in the original case of "Son of Sam" "They suspected that more than one person committed the homicides. Hockenberry also reported that the case was reopened in 1996 and has not yet been closed.<br />
<br />
==Attacks==<br />
* On July 29 of 1976, Donna Lauria and Jody Valenti were in Jody's car when a man opened fire on them, causing instant death of Donna and wounding Jody.<br />
* On October 23 of 1976, Carl Denaro and Rosemary Keenan chattered in his car when an unknown man shot them five times, causing superficial wounds to Rose, while Carl suffered a serious head injury.<br />
* On November 26 of 1976, Donna DeMasi and Joanne returned Lomino walking cinema when a man approached them asking a question and then shoot them, causing serious injuries to Donna and Joanne, who became paraplegic.<br />
* On January 30 of 1977, Christine Freund and John Diel, an engaged couple were preparing to go dancing when an attacker fired three times at the vehicle, causing minor injuries to John and severe to Christine, who later died in the hospital.<br />
* On March 8 of 1977, Virginia Voskerichian was approached by David Berkowitz Chicago and shot in the face. Trying to protect herself, she covered her face with books, but that improvised shield did not prevent her death.<br />
* On April 17 of 1977, Alexander Esau and Valentina Suriani, an engaged couple, were kissing in his car when a man approached and shot them twice each. Valentina died on the spot, while Alexander died at the hospital several hours later.<br />
* On June 26 of 1977, Sal Lupo and Judy Placido had left a nightclub and when they were in their car were hit by three shots. His injuries were minor and both survived.<br />
* On July 31 of 1977, Stacy Moskowitz and Robert Violante, boyfriends, were in a car parked near a park when a man approached and shot them. Stacy died hours later in the hospital, while Robert lost one eye and 80% of the other's visibility.<br />
<br />
==Sentencing==<br />
On June 12, 1978, he was sentenced to six life terms in prison and sent to serve the sentence in the maximum-security penitentiary in Attica.<br />
<br />
==Mentions in popular culture==<br />
The song "Son Of Sam" written by Jimmy Zero, is included in the second studio album "We Have Come for Your Children" of the Dead Boys American punk rock band formed in Cleveland in 1976.<br />
<br />
The industrial metal artist Marilyn Manson made a version of the song "Iron Man" by Black Sabbath entitled "Sam Son of Man", where he talks about the crimes committed by Berkowitz. In turn, one of the founding members of the took the name of Daisy Berkowitz, in reference to the murderer.<br />
<br />
The 1999 film "Summer of Sam" addresses the tensions created by the murders in a Bronx neighborhood. The film has a great load of referential content to the real story of the murderer (played by Michael Badalucco), and you can even see his real face in some newspapers.<br />
<br />
David Berkowitz Chicago is also portrayed in films such as Son of Sam (1999) or in the CBS telefilm Out of the Darkness (1985). He also has a significant role in one of the subplots of the miniseries The Bronx Is Burning (2007).<br />
<br />
In addition to films, Sam's son is mentioned many times in the crime series Criminal Minds, using it as an example to explain some criminal behaviors.<br />
<br />
In the book "High Heat" Lee Child mentioned Berkowitz as a secondary character.<br />
<br />
In the introduction of episode 17 of season 4 of The Vampire Diaries, Damon Salvatore is asked if it is just "Sam's son" after having killed a woman in the presence of her boyfriend, to which Damon replies "Son of Giuseppe, but almost", to subsequently kill this man in the same way.</div>Malterhttp://algorist.com/algowiki/index.php/TADM2E_3.8TADM2E 3.82018-07-22T00:21:45Z<p>Justiny: Created page with "Use a balanced tree structure where the nodes store the rank and the size of the left sub-tree. The rank can be calculated on insertion as follows: 1. Initialize rank to 1. 2..."</p>
<hr />
<div>Use a balanced tree structure where the nodes store the rank and the size of the left sub-tree. The rank can be calculated on insertion as follows: <br />
1. Initialize rank to 1.<br />
2. Add the size of the left subtree plus one (for the visited parent) every time the right child of a node is visited.<br />
3. Increment the size of the left subtree every time the left child of a node is visited.<br />
''Insert(x, T)'' takes O(log n) as the height of the tree is log n.<br />
''delete(x, T)'' takes O(log n) as the ranks and sizes can be recursively updated in O(log n) after the deletion.<br />
''member(x, T)'' is a search on BSTand is O(log n)</div>Justinyhttp://algorist.com/algowiki/index.php/TADM2E_3-6TADM2E 3-62018-07-22T00:04:22Z<p>Justiny: </p>
<hr />
<div>Modify ''insert'' and ''delete'':<br />
Pointers to successor and predecessor can be found in O(log n) time upon insertion. Store these in the new Node. predecessor(void * pcNode) and successor(void * pcNode) take O(1). Upon deletion of Node, successor of the predecessor becomes the predecessor of the successor.</div>Justinyhttp://algorist.com/algowiki/index.php/Ari_GlassAri Glass2017-09-07T11:44:12Z<p>Glasen: Created page with "Ari Glass is an emerging multi-talented artist. He is widely recognized as a painter, sculptor, and designer with a bright future ahead of him. In orde..."</p>
<hr />
<div>Ari Glass is an emerging [[Wikipedia:Ari Glass|multi-talented artist]]. He is widely recognized as a painter, sculptor, and designer with a bright future ahead of him. In order to portray the deep, personal and positive effect that art and art history has left on him, Glass deals with concepts such as sovereignty and independence.<br />
<br />
==Biography==<br />
<br />
He was born and raised in 1989 in Seattle. Growing up in Rainier Beach and Skyway, diverse neighborhoods of Seattle's South End, art and art history had a positive influence on him and served as a source of inspiration. Apart from the art classes he took at Franklin High School, Glass hadn’t received any other formal training until he enrolled himself at the Seattle Central College to study art.<br />
<br />
==Art Style==<br />
<br />
Throughout his life, Glass has looked up to numerous artists, but he has always stayed true to his own individual style and direction. In his art, Glass often deals with the issue of “the absurd”. As a painter, sculptor and designer, his goal is to transform the world through his innovative forms. The life in Seattle has provided him with a wealth of cultural influences to present in his art.<br />
<br />
==Exhibitions & Awards==<br />
<br />
Ari Glass had his first solo exhibition named “The Sun is Made of Gold” at 2312 Gallery in Seattle. At the CityArts 2016 Winter Art Walk Awards, his painting “Kings Day in the Rainier Valley” won first place. Since then he has won more awards.<br />
<br />
==Music==<br />
<br />
In addition to his art projects, Ari is also working on a new music Mahasingha EP, designing clothing for his line REVERIE® “Pyramids Shall Rise” collection, and merchandise and visuals for the Graffiti Village Tour.</div>Glasenhttp://algorist.com/algowiki/index.php/Mark_Tompkins_SecMark Tompkins Sec2017-08-23T10:27:18Z<p>Tokino: </p>
<hr />
<div>[[Wikipedia:Mark Tompkins (dancer)|Mark Tompkins Sec is a contemporary dance teacher, choreographer and writer]]. Born in New York, Mark spent his entire life in France and Europe, working with many choreographers and directors of dance theaters. Recently, he became an author, publishing his first book "Mark Tompkins Sec Song and Dance".<br />
<br />
== Biography ==<br />
<br />
=== Educatuon ===<br />
Mark Tompkins SEC started studying contemporary dance in the youth and has since worked with numerous dance teachers like Zage Virant, Guy Perkoza, Juan Cremona, Martin Sonderkamp, and others. He continued his studies at the Summer Academy in Montpellier with Mathilde Monnier and attended many workshops of contemporary teacher and choreographer.<br />
<br />
=== Involvement in Theater ===<br />
In 1984 Tompkins becomes a permanent member of the Modern Dance Studio in Paris and through thirty years of dance career participates in almost all productions of the ensemble. Point out just some of the shows: Quartet 78, Matamorfoze, Rubato, Big is bju: tiful, coat, woman who says a lot, Marathon, Gyekenyes band and on the way up Mirjana Preis, Tchi-tchiao Kilina Cremona , Stravinsky and Mark Tompkins SEC and the Rite of spring with Giselle Adriana Lutein, identity of touch and rhythm mathematics Gregor Luštek, Theatre love Darius Harjaček, Sale Ksenija Zec, Spirit - prone to change Maja Drobac, watch history Oliver Frljić, Large Sanja Tropp, Surprised Body Project -Zagreb Francesco Scavetta, movement-holder Aleksandra Janeva Imfeld.<br />
<br />
== Work ==<br />
As a dance teacher and choreographer Mark Tompkins SEC is working with the Department of Contemporary Dance, Paris Dance Company, City Theatre Comedy in New York, Paris Dance Company, the National Theatre in Paris, the Ballet of the National Theatre in Paris and others.<br />
<br />
=== Contemporary Dance ===<br />
Tompkins taught the subject of performance practice in the School of Contemporary Dance and set up in collaboration with the Department of contemporary dance show The Rite of Spring with twenty two dancers final classes of the said school.<br />
<br />
=== Career in Theater ===<br />
As a director Tompkins realized a series of studies with puppetry Paris, Denton War Theatre, New York National Theatre and Children's Theatre IBM New York.<br />
Mark Tompkins SEC is Winner of the Theatre for contemporary dance best achievement - Actor in 2004, and since 2013 the president of the Association of American contemporary dance artists.<br />
<br />
== Book ==<br />
In September 2016 Tompkins decided to publish a book about modern and contemporary dances. It is basically a summary of his life's work and in it he describes and categorizes the modern dances, what they represent and how they would evolve in the future. It is currently published on Amazon, Goodreads, etc.</div>Tokinohttp://algorist.com/algowiki/index.php/Ken_Friedman_Las_VegasKen Friedman Las Vegas2017-08-10T12:47:29Z<p>Trampin' all the way: Trampin' all the way moved page Promopage xDd to Promopage xD</p>
<hr />
<div>{{BASEPAGENAME}}.</div>KenVegashttp://algorist.com/algowiki/index.php/Paul_AlterPaul Alter2017-03-15T08:59:13Z<p>Palter: </p>
<hr />
<div>Paul Alter is a veteran [[Wikia:c:markgoodson:Paul Alter|TV game-show director]] and producer who died of natural causes at the age 89. This television legend and Emmy-winning director will stay remembered for his enormous contributions for the development of game shows. For around 40 years he was married to Shirley Burrows Alter, while Lorraine Cole Alter became his second wife. He had three daughters, four grandchildren and four great-grandchildren. After finally departing from The Price Is Right in 2000, Alter retired and went back to producing music. At the late age of 87 he composed the music and lyrics for the holiday album “The True Spirit of Christmas,” recorded by Pat Boone.<br />
<br />
==Career==<br />
Starting from 1986, all the way to 2000, Paul Alter directed both versions for the hit show “The Price Is Right”, one of the longest-running network series in United States television history, with more than 8,000 episodes aired. In addition to this, this iconic figure also directed the original version of Family Feud which ran on ABC from 1976 to 1985. After the show was revived in 1988, he continued to direct it. In 1990 he left the show and moved on to his next project, directing “To Tell the Truth”. During his long and fruitful career, Alter has won two Daytime Emmys, one for “Family Feud” in 1982, and the other for “The Price Is Right” in 1996. Overall he has been nominated for 14 Daytime Emmys.<br />
<br />
==Work outside TV==<br />
Apart from being known as a television director, he also gained a lot of attention with his 1992 lawsuit against the Walt Disney Co, claiming 17 areas of similarities between Disney’s movie “Honey, I Blew Up the Kid” and his long ago written treatment. He listed several similarities between his work which he had submitted to Disney in the late 1970s, and their movie Honey, I Shrunk the Kids released in 1992. In the trial which was held in 1993 the jury sided with Alter, and awarded him $300,000 as damages.<br />
With a career that spanned five decades, this television director and producer got to work on more than 60 game shows and other productions. He also did some work which wasn’t connected at all with game shows. For example he edited and scripted episodes of the 1950s crime drama “Man Against Crime,” served as an editor to his good friend, director Sidney Lumet on the TV series “Danger”, and was in charge for some episodes of “The Perry Como Show.” He also produced Simon Gray’s Broadway show “A Wise Child” in 1972.<br />
<br />
==Working With Goodson==<br />
“Beat the Clock” in 1950 was his first job as a director of a game show, and soon after that he began his long- lasting association with Mark Goodson-Bill Todman Productions. Under the wing of this production he worked on various shows including What's My Line?, I've Got a Secret and To Tell the Truth. In fact, in the period from 1956 to 2000, he helped Goodson-Todman create over 60 game shows. Paul Alter directed almost all of the company’s shows pilots, even when other directors took credit for his work on the series.<br />
<br />
==Overview==<br />
Originally from Chicago, Illinois, Alter was born on March 11, 1922. Before starting his television career, he studied piano with Teddy Wilson, from the Benny Goodman Quartet. In 1969 he composed the theme music for To Tell the Truth. After retiring from television, he once again returned to his musical background, and composed the music and lyrics for the holiday album “The True Spirit of Christmas”, recorded by Pat Boone. He died from natural causes on June 11, 2011.</div>Palterhttp://algorist.com/algowiki/index.php/TADM2E_4.27TADM2E 4.272017-02-05T21:20:28Z<p>Volta: Probable solution, but would tickled if someone else could confirm or suggest another answer.</p>
<hr />
<div>== Problem ==<br />
<br />
4-27. Let ''P'' be a simple, but not necessarily convex, polygon, and ''q'' an arbitrary point not necessarily in ''P''. Design an efficient algorithm to find a line segment originating from ''q'' that intersects the maximum number of edges of ''P''. In other words, if standing at point ''q'', in what direction should you aim a gun so the bullet will go through the largest number of walls? A bullet through a vertex of ''P'' gets credit for only one wall. An ''O(n lg n)'' algorithm is possible.<br />
<br />
== Solution ==<br />
<br />
Since a bullet through a vertex doesn't count as 2 walls, let's describe the polygon ''P'' in terms of pairs of points like [<math>(x_0, y_1), (x_2, y_2)</math>). That is, the first point will count as a wall, but the second will not.<br />
<br />
Next, let's convert all of the points in ''P'' to polar notation. We don't actually need to store the radius, however, just the angle <math>\theta</math>. Also, the polar notation is relative to ''q'''s location, <math>(q_x, q_y)</math>, so for every point ''p'' in ''P'' we have <math>\theta_p = atan((p_y - q_y) / (p_x - q_x))</math>. These calculations are done on every point, so a computational complexity of <math>\Theta(n)</math>.<br />
<br />
Keep a list of the line segments, with points stored as pairs of angles relative to ''q'', and sort them by the minimum of the two angles. It is okay to switch which angle comes first in a pair, but the pairs must move together when they are sorted. It is also important to preserve knowledge of which point was the ''source'' (closed interval) and which was the ''destination'' (open interval), so we don't count one vertex twice. This sorting costs ''O(n lg n)'', and it is the dominant factor in this algorithm.<br />
<br />
Finally, iterate through the sorted list of minimum elements, incrementing a counter whenever the start of a line segment is encountered, and decrementing the counter whenever a line segment ends.</div>Voltahttp://algorist.com/algowiki/index.php/TADM2E_5.32TADM2E 5.322017-01-29T09:00:33Z<p>Blazedaces: Created page with "Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. Ther..."</p>
<hr />
<div>Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):<br />
<br />
# index is equal to the left tree's size => This value is the ith node in sorted order<br />
# index is less than the left tree's size => The ith node is in the left tree<br />
# index is greater than the left tree's size + 1 => The ith node is in the right tree<br />
<br />
The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.<br />
<br />
<source lang="java"><br />
import java.util.Optional;<br />
<br />
public class BinarySearchTree {<br />
private Optional<BinarySearchTree> left;<br />
private Optional<BinarySearchTree> right;<br />
private int value;<br />
private int size;<br />
<br />
public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {<br />
this.value = value;<br />
this.left = left;<br />
this.right = right;<br />
this.size = getLeftSize() + getRightSize() + 1;<br />
}<br />
<br />
private Integer getRightSize() {<br />
return this.right.map(r -> r.size).orElse(0);<br />
}<br />
<br />
private Integer getLeftSize() {<br />
return this.left.map(l -> l.size).orElse(0);<br />
}<br />
<br />
public int findIthNodeInSortedOrder(final int index) {<br />
if (index < 0) {<br />
throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");<br />
}<br />
<br />
if (index >= size) {<br />
throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");<br />
}<br />
<br />
if (index == getLeftSize()) {<br />
return value;<br />
} else if (index < getLeftSize()) {<br />
return left.get().findIthNodeInSortedOrder(index);<br />
} else {<br />
return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));<br />
}<br />
}<br />
}<br />
</source></div>Blazedaceshttp://algorist.com/algowiki/index.php/TADM2E_4.20TADM2E 4.202017-01-23T12:30:32Z<p>Heesub: </p>
<hr />
<div>If you partition the array with pivoting 0, all negative values appear before all other positive values. This can be done in linear time, <math>O(n)</math>.</div>Heesubhttp://algorist.com/algowiki/index.php/TADM2E_8.1TADM2E 8.12017-01-11T08:29:05Z<p>Smarth: </p>
<hr />
<div>This is the regular editing dynamic programming, except that the diagonal as an extra possibility when a swap is possible.<br />
<br />
M[i, j] = M[i-2, j-2] + 1 ; if A[i] == B[j-1] and A[i-1] == B[j] where i,j > 1</div>Jokyhttp://algorist.com/algowiki/index.php/TADM2E_8.21TADM2E 8.212016-12-22T19:32:05Z<p>LiavK: Minor code formatting fixes. Still looks a little wiggy.</p>
<hr />
<div>==== 1 ====<br />
<br />
Sum every range and keep track of the maximum.<br />
<br />
Given a set of numbers N = { x0, x1 ... xn }<br />
<br />
M = 0<br />
<br />
for i in (0 .. n)<br />
S[i, i] = xi<br />
for j in (i + 1 .. n)<br />
S[i, j] = S[i, j - 1] + xj<br />
if M < S[i, j]<br />
M = S[i, j]<br />
<br />
==== 2 ====<br />
<br />
def max_range(items):<br />
max_diff = max(items[0], 0)<br />
temp_diff = 0<br />
for number in items:<br />
temp_diff = max(0, temp_diff + number)<br />
max_diff = max(max_diff, temp_diff)<br />
return max_diff<br />
<br />
assert max_range([1, 2, 3, 4, 5]) == 15<br />
assert max_range([-1, -2, -3, -4, -5]) == 0<br />
assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187<br />
assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187<br />
assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51<br />
assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51</div>Azazelhttp://algorist.com/algowiki/index.php/TADM2E_8.17TADM2E 8.172016-12-22T18:39:49Z<p>Azazel: Created page with "Consider the following example: {|border="1" |G||G||G||G |- |G||B||G||G |- |G||G||G||G |} There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RR..."</p>
<hr />
<div>Consider the following example:<br />
<br />
{|border="1"<br />
|G||G||G||G<br />
|-<br />
|G||B||G||G<br />
|-<br />
|G||G||G||G<br />
|}<br />
<br />
There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:<br />
<br />
{|border="1"<br />
|1||?||?||?<br />
|-<br />
|?||B||?||?<br />
|-<br />
|?||?||?||?<br />
|}<br />
<br />
<br />
{|border="1"<br />
|1||1||?||?<br />
|-<br />
|1||B||?||?<br />
|-<br />
|?||?||?||?<br />
|}<br />
<br />
<br />
{|border="1"<br />
|1||1||1||?<br />
|-<br />
|1||B||?||?<br />
|-<br />
|1||?||?||?<br />
|}<br />
<br />
<br />
{|border="1"<br />
|1||1||1||1<br />
|-<br />
|1||B||1||?<br />
|-<br />
|1||1||?||?<br />
|}<br />
<br />
<br />
{|border="1"<br />
|1||1||1||1<br />
|-<br />
|1||B||1||2<br />
|-<br />
|1||1||2||?<br />
|}<br />
<br />
<br />
{|border="1"<br />
|1||1||1||1<br />
|-<br />
|1||B||1||2<br />
|-<br />
|1||1||2||4<br />
|}<br />
<br />
Implementation in Perl:<br />
<br />
#!/usr/bin/perl<br />
<br />
use warnings;<br />
use strict;<br />
<br />
sub count_paths<br />
{<br />
my @bad = @_;<br />
<br />
my $nr = @bad;<br />
my $nc = @{$bad[0]};<br />
<br />
my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;<br />
<br />
for my $r (0 .. $nr - 1)<br />
{<br />
for my $c (0 .. $nc - 1)<br />
{<br />
next if $bad[$r][$c];<br />
<br />
my $np = $r == 0 && $c == 0 ? 1 : 0;<br />
<br />
$np += $paths[$r - 1][$c] if $r > 0 && !$bad[$r - 1][$c];<br />
$np += $paths[$r] [$c - 1] if $c > 0 && !$bad[$r] [$c - 1];<br />
<br />
$paths[$r][$c] = $np;<br />
}<br />
}<br />
<br />
return $paths[$nr - 1][$nc - 1];<br />
}<br />
<br />
my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);<br />
<br />
my $np = count_paths @bad;<br />
<br />
print $np, "\n";</div>Azazelhttp://algorist.com/algowiki/index.php/TADM2E_8.11TADM2E 8.112016-12-22T15:18:09Z<p>Azazel: Created page with "For each length of range l in 1 .. n, for each starting index i, calculate the sum of the range of length l, starting at i as the sum of the range of length l - 1 starting at..."</p>
<hr />
<div>For each length of range l in 1 .. n, for each starting index i, calculate the sum of the range of length l, starting at i as the sum of the range of length l - 1 starting at i plus the integer at i + l - 1 mod n.</div>Azazelhttp://algorist.com/algowiki/index.php/TADM2E_8.7TADM2E 8.72016-12-22T14:07:17Z<p>Azazel: Created page with "==== 1 ==== # 20 x 1 # 1 x 6 + 14 x 1 # 2 x 6 + 8 x 1 # 3 x 6 + 2 x 1 # 1 x 10 + 10 x 1 # 1 x 10 + 1 x 6 + 4 x 1 # 2 x 10 ==== 2 ==== More generally: # there is always o..."</p>
<hr />
<div>==== 1 ====<br />
<br />
# 20 x 1<br />
# 1 x 6 + 14 x 1 <br />
# 2 x 6 + 8 x 1 <br />
# 3 x 6 + 2 x 1<br />
# 1 x 10 + 10 x 1<br />
# 1 x 10 + 1 x 6 + 4 x 1<br />
# 2 x 10<br />
<br />
==== 2 ====<br />
<br />
More generally:<br />
<br />
# there is always one way of making zero from any set of denominations;<br />
# there is one way of making any non-zero sum from one denomination provided that the sum is evenly divisible by the denomination;<br />
# for larger sets of denominations, the number of ways to make a sum S from a set D = { a, b, ... m, n } where Di < Dj for i < j, is the sum of the ways to make S, S - n, ... S - xn from D' = { a, b, c, ... m }.<br />
<br />
Implementation in C:<br />
<br />
#include <assert.h><br />
#include <stdio.h><br />
#include <stdlib.h><br />
<br />
static unsigned<br />
make_change (unsigned sum, unsigned *coins, size_t nr_coins)<br />
{<br />
unsigned **table = malloc (nr_coins * sizeof *table);<br />
<br />
assert (table != NULL);<br />
<br />
for (size_t c = 0; c < nr_coins; ++c)<br />
{<br />
table[c] = malloc ((1 + sum) * sizeof *table[c]);<br />
<br />
assert (table[c] != NULL);<br />
<br />
if (c == 0)<br />
{<br />
/*<br />
* No. of ways of making s from coins[0]: 1 if s is evenly divisible by<br />
* coins[0], 0 otherwise.<br />
*/<br />
for (unsigned s = 0; s <= sum; ++s)<br />
table[0][s] = s % coins[0] == 0;<br />
}<br />
else<br />
{<br />
/*<br />
* One way of making 0 from { coins[0] .. coins[c] }: the empty set.<br />
*/<br />
table[c][0] = 1;<br />
<br />
/*<br />
* No. of ways of making s from { coins[0] .. coins[c] }: no. of ways of<br />
* making s - n * coins[c] for n > 0 and s >= n * coins[c]<br />
* from { coins[0] .. coins[c - 1] }<br />
*/<br />
for (unsigned s = 1; s <= sum; ++s)<br />
for (unsigned n = 0; n * coins[c] <= s; n ++)<br />
table[c][s] += table[c - 1][s - (n * coins[c])];<br />
}<br />
}<br />
<br />
unsigned rv = table[nr_coins - 1][sum];<br />
<br />
for (size_t c = 0; c < nr_coins; ++c)<br />
free (table[c]);<br />
<br />
free (table);<br />
<br />
return rv;<br />
}<br />
<br />
static int<br />
cmp_coins (const void *a, const void *b)<br />
{<br />
return (*(unsigned *) a > *(unsigned *) b)<br />
- (*(unsigned *) a < *(unsigned *) b);<br />
}<br />
<br />
int<br />
main (int argc, char **argv)<br />
{<br />
if (argc < 3)<br />
exit (EXIT_FAILURE);<br />
<br />
unsigned sum = atoi (argv[1]);<br />
<br />
size_t nr_coins = argc - 2;<br />
<br />
unsigned *coins = malloc (nr_coins * sizeof *coins);<br />
<br />
assert (coins != NULL);<br />
<br />
for (int i = 2; i < argc; ++i)<br />
coins[i - 2] = atoi (argv[i]);<br />
<br />
qsort (coins, nr_coins, sizeof *coins, cmp_coins);<br />
<br />
fprintf (stderr, "%u\n", make_change (sum, coins, nr_coins));<br />
<br />
free (coins);<br />
<br />
exit (EXIT_SUCCESS);<br />
}</div>Azazelhttp://algorist.com/algowiki/index.php/TADM2E_2.15TADM2E 2.152016-11-04T20:25:32Z<p>Brandon.arnold: </p>
<hr />
<div>Choose <math>c_1</math> to satisfy <math>f_1(n) \le {c_1}{g_1(n)}</math> for all <math>n \gt n_{1,0}</math> and <math>c_2</math> to satisfy <math>f_2(n) \le {c_2}{g_2(n)}</math> for all <math>n \gt n_{2,0}</math>.<br />
<br />
<br />
Note that <math>c_1</math> and <math>c_2</math> above can be substituted with <math>c_3</math> such that <math>c_3 = max(c_1, c_2)</math> and the conditions still hold.<br />
<br />
<br />
Since <math>a \le b, c \le d \implies ac \le bd</math> it follows that <math>f_1(n) \le {c_3}{g_1(n)}, f_2(n) \le {c_3}{g_2(n)} \implies f_1(n) \times f_2(n) \le {c_3}({g_1(n)} \times {g_2(n)})</math>.<br />
<br />
<br />
Therefore <math>f_1(n) \times f_2(n) = O(g_1(n) \times g_2(n))</math></div>Brandon.arnold