Re: trees?

From: Alex Hall <mehgcap@xxxxxxxxx>
To: programmingblind@xxxxxxxxxxxxx
Date: Mon, 1 Nov 2010 21:57:10 -0400
Thanks to all for the explanations and offers of further help. The
professor eventually explained the whole thing in terms of a
one-dimensional array and explained the pseudocode in terms of said
array. That made more sense, and I turned the thing in today and got
100% on it. Next will be implementing a recursive substring finding
algorithm (this is, after all, an algorithms class) but I think I have
that one down...

On 10/22/10, black ares <matematicianu2003@xxxxxxxxxxx> wrote:
> more simple is the father representation.
> So let say that all nodes in a tree has an index.
> so we have node 1 node 2 node 3.
> Let say that node 1 is the root.
> In this conditions a reprezentation of an tree is an array with the
> relation:
> f[nodei]=parentj;
> So foreach I in the row i retain the index of the parrent in that array.
>
> ----- Original Message -----
> From: "Dave" <davidct1209@xxxxxxxxx>
> To: <programmingblind@xxxxxxxxxxxxx>
> Sent: Friday, October 22, 2010 9:23 AM
> Subject: Re: trees?
>
>
>> Also, in addition to my previous comments, serialization helps because
>> you can write something like:
>>
>> 1.  [ (root1, children1) ].  This is sometimes called pre order.  You
>> can view a tree as a list of nodes; the first item is the root of the
>> subtree and the rest of the nodes are its children.  Thus, you can
>> expand out this representation by:
>> [ (root1, (root2, children2), children1 - 1)...
>>
>> or, you can view a list of nodes with the children first and then root
>> at the end:
>> [ (children1, root1)]
>> = [(children1 - 1, (children2, root2), root1]
>>
>> etc...
>>
>>
>>
>> On 10/21/10, Dave <davidct1209@xxxxxxxxx> wrote:
>>> The potentially difficult part of the algorithm described by others
>>> above is that it involves a depth first traversal of the possible
>>> states and also backtracking.
>>>
>>> With an 8 by 8 board, you can think of each square on the first row of
>>> the board each as a root to a tree.  That makes 8 trees.  Each "tree"
>>> then has 8 children; these children are the squares of row two.  Each
>>> of those children then have 8 more children each (taken from row
>>> three) ... and so on.
>>>
>>> The job of the algorithm then is to do a depth first search of each of
>>> these 8 trees and find a path in which every square on the path don't
>>> lie on the same diagonal, column, or row.  If you find a "conflict"
>>> then you know the path you're traveling down the tree is *wrong* and
>>> you move *up* the tree by one node and continue traversing the tree
>>> depth first.  Or in other words, you move back to the parent when a
>>> conflict occurs.
>>>
>>> Once you find that path (i.e. you reach a leaf node), then you have a
>>> possible placement of the 8 queens.
>>>
>>> Short of speaking to a person, you may want to review basic tree
>>> traversals like depth first search and ways to serialize trees.  I had
>>> the best luck understanding trees when I also could "flatten" them
>>> into a form that made them easy to write down on a single line.  So,
>>> make sure you really grock DFS on simple trees and then start tackling
>>> the specific tree representation of this problem; then, throw in
>>> backtracking...
>>>  hth.
>>>
>>> On 10/21/10, black ares <matematicianu2003@xxxxxxxxxxx> wrote:
>>>> I don't know, but the computer is used only where the human mind does
>>>> not
>>>> give results on an average.
>>>> The n-queens problem commes from reality.
>>>> The real problem in chess sounds like:
>>>> Put 8 queens on the same collor on a chess board in a such manner that
>>>> they
>>>> can not capture each other.
>>>> The fun thing about this thing is that only great chess players can find
>>>> one
>>>> or two solution for this.
>>>> The average users/player don't succeed in such chalenge.
>>>> More over the computer, for the n=8 case finds how many solution do you
>>>> thing?
>>>> Well it finds 92 solutions.
>>>> This is funy, the fact that even there are 92 solutions out there, men
>>>> can
>>>> only find one or two with out computers.
>>>> Another problem for backtracking is a knight movements problem.
>>>> It sounds like this:
>>>> Giving a knight in a chess board square, move that knight such as it
>>>> covers
>>>> every square of the board, but only once.
>>>> You will see, read 2 - 3 - 4 problems in back tracking and you quickly
>>>> observe that the code is the same.
>>>>
>>>> ----- Original Message -----
>>>> From: "Homme, James" <james.homme@xxxxxxxxxxxx>
>>>> To: <programmingblind@xxxxxxxxxxxxx>
>>>> Sent: Thursday, October 21, 2010 10:57 PM
>>>> Subject: RE: trees?
>>>>
>>>>
>>>> Hi, I have a feeling that the answer to this is Yes. Would this kind of
>>>> thing also work for pieces that have limited movement? For example, a
>>>> pawn
>>>> can only move forward, but it can move two spaces on its first move. But
>>>> a
>>>> special case is that it captures by moving diagonally. Is this the same
>>>> kind
>>>> of thing or different?
>>>>
>>>> Thanks.
>>>>
>>>> Jim
>>>>
>>>> Jim Homme,
>>>> Usability Services,
>>>> Phone: 412-544-1810. Skype: jim.homme
>>>> Internal recipients,  Read my accessibility blog. Discuss accessibility
>>>> here. Accessibility Wiki: Breaking news and accessibility advice
>>>>
>>>>
>>>> -----Original Message-----
>>>> From: programmingblind-bounce@xxxxxxxxxxxxx
>>>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of black ares
>>>> Sent: Thursday, October 21, 2010 2:14 PM
>>>> To: programmingblind@xxxxxxxxxxxxx
>>>> Subject: Re: trees?
>>>>
>>>> this is yet another individual representing the class of stupid
>>>> professors.
>>>> Please, for the N-queens problem
>>>> read about backtracking and you will get the point.
>>>> If you read about recursive back tracking you will even get the point
>>>> regarding the tree representation of this problem.
>>>> How ever, the backtracking programing algorithm
>>>> is a static one, by static I mean, that
>>>> it has a fixed form where you only change data and a little operation
>>>> and
>>>> from a problem you get another.
>>>> For example if you have a solution for another problem in backtracking,
>>>> you
>>>> can simply change somthing little there and you will get the n-queens
>>>> problem.
>>>> The recursive backtracking is easier to understand than iterative one,
>>>> but
>>>> this is just my point of view.
>>>> So your problem now is not to understand what a tree is, or how this
>>>> problem
>>>> is represented on a tree,
>>>> now your problem is to learn about back tracking and how to solve that
>>>> problems.
>>>> Sighted professors often tend to graphicaly represent all the things
>>>> even
>>>> they didn't need to!
>>>> And also often the graphical representation is most disturbing than
>>>> explaining.
>>>> When you will realy need a tree like a abstract data structure, you will
>>>> understand it very well.
>>>>
>>>>
>>>> ----- Original Message -----
>>>> From: "Ken Perry" <whistler@xxxxxxxxxxxxx>
>>>> To: <programmingblind@xxxxxxxxxxxxx>
>>>> Sent: Wednesday, October 20, 2010 7:46 PM
>>>> Subject: RE: trees?
>>>>
>>>>
>>>>> You know how I did it in my software engineering class before I did the
>>>>> file
>>>>> and outline?  I wrote an asm black white tree and followed it in a
>>>>> debugger.
>>>>> Hmm is that a little nuts?
>>>>>
>>>>> Ken
>>>>>
>>>>> -----Original Message-----
>>>>> From: programmingblind-bounce@xxxxxxxxxxxxx
>>>>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Sina Bahram
>>>>> Sent: Wednesday, October 20, 2010 11:42 AM
>>>>> To: programmingblind@xxxxxxxxxxxxx
>>>>> Subject: RE: trees?
>>>>>
>>>>> I think that you should sit down with either her or someone  else who
>>>>> fully
>>>>> understands the concept, and concentrate on
>>>>> understanding how trees work, rather than being hung up on the
>>>>> representation.
>>>>>
>>>>> I'll volunteer to offer some info over skype or phone, and there should
>>>>> be
>>>>> some good websites on this, but concepts like this need
>>>>> to be explained in person/voice, not just by reading about them,
>>>>> although
>>>>> you can get a lot that way too.
>>>>>
>>>>> Take care,
>>>>> Sina
>>>>>
>>>>> -----Original Message-----
>>>>> From: programmingblind-bounce@xxxxxxxxxxxxx
>>>>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Alex Hall
>>>>> Sent: Wednesday, October 20, 2010 10:33 AM
>>>>> To: programmingblind
>>>>> Subject: trees?
>>>>>
>>>>> Hi all,
>>>>> We are doing trees in an algorithms class I am taking. The assignment
>>>>> coming
>>>>> up is the "n queens" problem, where you have an n by n
>>>>> board and must place n queens on the board such that no two queens
>>>>> share
>>>>> the
>>>>> same row, column, or diagonal line. To "help" explain
>>>>> this, the professor is using a tree on the board. I am completely
>>>>> confused!
>>>>> She says I do not need to think of it in terms of trees,
>>>>> yet the only way she explains it is in tree terms, so I am not sure
>>>>> what
>>>>> she
>>>>> is talking about. Of course I know about trees, but
>>>>> when she tries to explain how the code we are looking at relates to the
>>>>> tree
>>>>> in terms of what the code is supposed to do, I haven't
>>>>> a clue as to what she is trying to say. Does anyone have any thoughts
>>>>> on
>>>>> how
>>>>> to represent trees, whether in braille or speech, or a
>>>>> good notation/substitute for a tree? TIA.
>>>>>
>>>>> --
>>>>> Have a great day,
>>>>> Alex (msg sent from GMail website)
>>>>> mehgcap@xxxxxxxxx; http://www.facebook.com/mehgcap __________ View the
>>>>> list's information and change your settings at
>>>>> //www.freelists.org/list/programmingblind
>>>>>
>>>>> __________
>>>>> View the list's information and change your settings at
>>>>> //www.freelists.org/list/programmingblind
>>>>>
>>>>> __________
>>>>> View the list's information and change your settings at
>>>>> //www.freelists.org/list/programmingblind
>>>>>
>>>>
>>>> __________
>>>> View the list's information and change your settings at
>>>> //www.freelists.org/list/programmingblind
>>>>
>>>>
>>>> This e-mail and any attachments to it are confidential and are intended
>>>> solely for use of the individual or entity to whom they are addressed.
>>>> If
>>>> you have received this e-mail in error, please notify the sender
>>>> immediately
>>>> and then delete it.  If you are not the intended recipient, you must not
>>>> keep, use, disclose, copy or distribute this e-mail without the author's
>>>> prior permission.  The views expressed in this e-mail message do not
>>>> necessarily represent the views of Highmark Inc., its subsidiaries, or
>>>> affiliates.
>>>> __________
>>>> View the list's information and change your settings at
>>>> //www.freelists.org/list/programmingblind
>>>>
>>>> __________
>>>> View the list's information and change your settings at
>>>> //www.freelists.org/list/programmingblind
>>>>
>>>>
>>>
>> __________
>> View the list's information and change your settings at
>> //www.freelists.org/list/programmingblind
>>
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
>


-- 
Have a great day,
Alex (msg sent from GMail website)
mehgcap@xxxxxxxxx; http://www.facebook.com/mehgcap
__________
View the list's information and change your settings at 
//www.freelists.org/list/programmingblind
Follow-Ups:
- RE: trees?
  - From: Homme, James
Re: trees?

Other related posts:
