Phase 3 Discussion Board Richard Libeau MATH215-1301B-01 March 4, 2013

Task Type: Discussion Board Deliverable Length: 3 Parts: See Assignment Details
Points Possible: 75
Graphs and Trees
Task Background: Graphs and trees provide you with ways to visualize data sets, and the opportunity to do analysis on the data (e.g., shortest path). Knowing the structure of a database enables you to choose a proper algorithm for searching for data within a database.
Primary Task Response: Within the Discussion Board area, write up to 3 paragraphs that respond to the following questions with your thoughts, ideas, and comments. This will be the foundation for future discussions by your classmates. Be substantive and clear, and use examples to reinforce your ideas.
Part I (25 points – distributed as follows)
Trees are somewhat less complicated than graphs, which makes things like data searching easier, when a data has the structure of a tree. However, not all data can be represented by a tree.
Give an example of a data set that cannot be represented by a tree, but that can be represented by a more general graph.

1) Create, show, and describe your data set. (5 points)

V = {Bill, John, Kim, James, Chris, Destiny, Noah, Paul}
E = {(Bill, John), (Kim, James), (Chris, Destiny), (Noah, Paul), (Bill, Kim), (John, Chris), (Destiny, Noah)}
These are people that are employees at a store. Some work on the same shift together and associate with each other.

2) Then, show by building a graph, how your data is represented by a graph. (5 points)
Bill
Bill

John
John
Chris
Chris

Kim
Kim

Destiny
Destiny

James
James

Noah
Noah

Paul
Paul

3) Explain exactly why YOUR data can be represented by a graph, but not a tree. Clearly explain. (15 points)

My data can only be represented by a graph and not a tree because it has disjointed sets. A tree cannot have disjointed sets. This data can only be displayed in a graph. It is not possible to display it in a tree because it does not have one simple path and some nodes are not reachable or connected to each other.

Part II (35 points – distributed as follows)
The set of all possible sequences of moves in a chess game can be represented by a tree (decision tree). If you were to write a chess-playing computer program that can determine the best move at each step, would you use a depth-first or a breadth-first search for the best move at each step in the game? Why? 1) What is a graph? (5 points)
Graphs are generalizations of trees. They have nodes and edges like trees but they are basically more general than trees. A graph can have any number of edges and can be undirected or directed. In directed graphs you can only go node to node. Undirected graphs have no direction. You must follow the arrows in a directed graph but in a undirected graph you can go either way along an edge.

2) What is a Tree and how is a tree different from a graph – give at least 2 reasons? (5 points) A tree is a undirected graph. It is connected with no cycles and is connected by any two vertices with one simple path. There are also directed trees which is a directed graph if the direction of the edges were not acknowledged. Trees have direction and do not contain cycles.Trees cannot have disjointed nodes like graphs either. 3) What is a Depth First Search of a tree? (5 points)

Depth First Search explores a path all the way to the edges before backtracking and exploring another path. It will process the vertices first deep and then widen. Afterwards it processes a vertex it recursively processes all of its descendants. The object of a Depth First Search is to search deeper into a graph wherever possible.

4) What is a Breadth First Search of a tree and how is it different from a Depth First Search? (5 points)
Breadth First Search is a search that explores the nodes nearest to the root before exploring nodes further away. It goes level by level through searching node by node. It is the shortest path from the root and no path can skip a level. Difference in Depth First and Breadth First searching are Breadth begins at the root and searches all neighboring nodes and Depth explores as far as possible before backtracking.

5) What is a Decision Tree? (5 points)
Decision Tree is a schematic tree shaped diagram used to determine a course of action or to show a statistical probability. Every branch of a Decision Tree stands for a decision or occurrence. The structure of the tree shows how one choice leads to the next. The Decision Tree can be used to find an answer to a complex problem. The structure of the tree can be displayed in an easy format to show relationships between events or decisions. The branches the furthest away indicate the possible end results.

6) Choose either Depth First Search or Breadth First Search and explain why you would prefer to use that method to write a chess-playing game that determines the best next move using a decision tree. (10 points)

I think I would choose Breadth First Search because it explores nodes closest to the root and goes from there one node at a time. Therefore, It does a thorough job of exploring every possible scenario that could happen along the way during the game. I feel it would be more effective than a Depth First approach which takes one path and then backtracks. With the Breadth approach backtracking is not needed as it goes through every possible node hence it does not miss anything along the way.

Responses to Other Students: Due by Sunday (10 points: 5 points for each response)
Respond to at least 2 of your fellow classmates with a reply of at least 1 paragraph about their primary task response regarding items you found to be compelling and enlightening. To help you with your discussion, please consider the following questions: * What did you learn from your classmate's posting? * What additional questions do you have after reading the posting? * What clarification do you need regarding the posting?

Spelling, grammar, professionalism: (5 points)