Starting from:
$30
CS20B: Homework 5 Binary Search Trees and Graphs Solved
This homework covers some questions about binary search trees and graphs.
1 Questions
1. Answer the questions below about the following tree, using the letters that label the nodes:
(a) Which node is the root?
(b) Which node is the parent of F?
(c) Which node(s) are the children of H?
(d) Which node(s) are the ancestors of M?
(e) Which node(s) are the descendants of T?
(f) Which node(s) are the siblings of S? And of H?
(g) What is the height of the tree?
(h) Write the order in which the nodes are visited by a breadthfirst traversal. Use the following format when specifying the order: [node1 node2 ... nodeN]
(i) Write the order in which the nodes are visited by a depthfirst traversal. Use the following format when specifying the order: [node1 node2 ... nodeN]
2. Answer the following questions about the binary search tree (in Figure 1).
(a) What is the height of the tree?
Figure 1: A binary search tree
(b) Which nodes are on level 3?
(c) Which levels have the maximum number of nodes that they could contain?
(d) What is the maximum height of a binary search tree containing these nodes (counting level 0 as well)?
(e) What is the minimum height of a binary search tree containing these nodes (counting level 0 as well)?
(f) What is the order in which nodes are visited by a preorder traversal?
(g) What is the order in which nodes are visited by an inorder traversal?
(h) What is the order in which nodes are visited by a postorder traversal?
(i) What is the order in which nodes are visited by a depthfirst traversal?
(j) What is the order in which nodes are visited by a breadthfirst traversal?
3. (Hashing from Chapter 8) Critique the following hash functions for a domain consisting of people with attributes firstName, lastName, number (used to resolve identical first and last names, e.g., “John Smith 0,” “John Smith 1,” etc.), and age. The names are of class String and the other two attributes are of type int.
(a) hash function returns (age)2
(b) hash function returns (age)2 + lastName.hashCode()
(c) hash function returns lastName.hashCode() + firstName.hashCode()
(d) hash function returns lastName.hashCode() + firstName.hashCode() + number
Note: answer the question in terms of how good the hashcode is for avoiding collisions (different entries having the same hashcode) and uniquely identifyng the objects.
4. (Hashing from Chapter 8) Critique the following code which is intended to print out whether or not a key value k1 is used in a map named relationships:
1 if (relationships.get(k1) != null)
2
3 System.out.println("yes it does");
4
5 else
6
7 System.out.println("no it does not");
Now rewrite the code so that it works correctly
5. (Graphs) Use the following description of an undirected graph for Questions a) and b) below:
EmployeeGraph = (V, E)
V(EmployeeGraph) = {Susan, Darlene, Mike, Fred, John, Sander, Lance, Jean, Brent, Fran}
E(EmployeeGraph) = {(Susan, Darlene), (Fred, Brent), (Sander, Susan), (Lance, Fran),
(Sander, Fran), (Fran, John), (Lance, Jean), (Jean, Susan), (Mike, Darlene), (Brent, Lance), (Susan, John)}
(a) Draw a picture of EmployeeGraph (draw it the way graphs look like - see the book or slides)
(b) Which one of the following phrases best describes the relationship represented by the edges between the vertices in EmployeeGraph and why?
i. “works for”
ii. “is the supervisor of ”
iii. “is senior to” iv. “works with”
6. (Graphs) Draw the adjacency matrix for the graph in Figure 2. Store the vertices in alphabetical order.
2 Programming exercises
Please do these with your partner. The assignments are not precisely defined (as in the real-world) and you will have to figure out the details. You will need to
Figure 2: Graph example
show the concepts you learned in this class (OOP design) as much as possible. You will present your solution to the class in the final class of the semester. You will run your code and demonstrate how it works and then we will discuss the structure of your solution. I will ask each of you to write a report on your partner describing how much your partner contributed to this homework. Make sure you comment your code.
2.1 Problem 1: Logical Circuits
In this assignment using Java’s OOP design you need to represent the following logic gates: AND, OR, NOT and XOR. The basic functionality of your code should be the following:
1. For each gate, given some inputs, get the calculated output. For example (this is pseudocode): AND(True, True) should give me True, XOR(True, False) should give me True. Make the application that makes sure each of your gate operates correctly with all combinations of binary inputs.
2. (Bonus for A+) Go for the glory! This one is a bit more complicated but fun. Given a logic circuit calculate the output of the circuit. For example, for the circuit in Figure 3 and inputs A = TRUE, B = FALSE, C = FALSE, D = TRUE the circuit outputs FALSE. Don’t try to solve everything. Just make a solution for these simpler examples. Use the circuit in Figure 3 to test your code.
You can always do more. Amaze us.
Figure 3: Example circuit
2.2 Problem 1: Social Network
You are provided with the following two files: users.csv and edges.csv. The files contain the following:
1. users.csv has the following attributes:
• user id: is a unique identifier of a user
• community: is one of the following values {science, sport, art}.
• age: is the age of a user
• posts: is a list of post types users most frequently share (to simply it for you I set maximum possible per user to 10). It can be one of the following values: {video, image, article}.
2. edges.csv has the following attributes:
• user id, user id : represents the edge between two user ids
2.2.1 What should I do?
To solve this task use and adapt the WeightedGraph implementation from the book (ch10). Represent this data as a graph and perform some interesting analysis of the data. You should demonstrate at least three questions asked about the graph. Some of these will require adding methods and new attributes to WeightedGraph.java file or performing it in the driver code.
2.2.2 What is a CSV file?
CSV stands for “comma-separated values”. You can load these files in Excel or Libre Office Calc and view them. However, for this project you will need to load it in Java.
2.2.3 Visualisation
If you would like to visualize your graph (or a part of it) I suggest using the following library for representing graphs: http://graphstreamproject.org/download/ Go to the Website and download all the three jars from the 1.3 release (gs-core, gs-algo, gs-ui). Make sure to download them somewhere you can find them. I suggest putting all three jars in a folder on the same level as your src folder, and call it lib. In your IDE make sure you add all three jars to your library list (Congifure Build Path -¿ Add external jars). You have to figure out how to use the library. :)
2.2.4 Timely report errors or issues
If you find an inconsistency in the data, code or similar, report immediately. It’s also part of the process and could bring you even more glory
1 Questions
1. Answer the questions below about the following tree, using the letters that label the nodes:
(a) Which node is the root?
(b) Which node is the parent of F?
(c) Which node(s) are the children of H?
(d) Which node(s) are the ancestors of M?
(e) Which node(s) are the descendants of T?
(f) Which node(s) are the siblings of S? And of H?
(g) What is the height of the tree?
(h) Write the order in which the nodes are visited by a breadthfirst traversal. Use the following format when specifying the order: [node1 node2 ... nodeN]
(i) Write the order in which the nodes are visited by a depthfirst traversal. Use the following format when specifying the order: [node1 node2 ... nodeN]
2. Answer the following questions about the binary search tree (in Figure 1).
(a) What is the height of the tree?
Figure 1: A binary search tree
(b) Which nodes are on level 3?
(c) Which levels have the maximum number of nodes that they could contain?
(d) What is the maximum height of a binary search tree containing these nodes (counting level 0 as well)?
(e) What is the minimum height of a binary search tree containing these nodes (counting level 0 as well)?
(f) What is the order in which nodes are visited by a preorder traversal?
(g) What is the order in which nodes are visited by an inorder traversal?
(h) What is the order in which nodes are visited by a postorder traversal?
(i) What is the order in which nodes are visited by a depthfirst traversal?
(j) What is the order in which nodes are visited by a breadthfirst traversal?
3. (Hashing from Chapter 8) Critique the following hash functions for a domain consisting of people with attributes firstName, lastName, number (used to resolve identical first and last names, e.g., “John Smith 0,” “John Smith 1,” etc.), and age. The names are of class String and the other two attributes are of type int.
(a) hash function returns (age)2
(b) hash function returns (age)2 + lastName.hashCode()
(c) hash function returns lastName.hashCode() + firstName.hashCode()
(d) hash function returns lastName.hashCode() + firstName.hashCode() + number
Note: answer the question in terms of how good the hashcode is for avoiding collisions (different entries having the same hashcode) and uniquely identifyng the objects.
4. (Hashing from Chapter 8) Critique the following code which is intended to print out whether or not a key value k1 is used in a map named relationships:
1 if (relationships.get(k1) != null)
2
3 System.out.println("yes it does");
4
5 else
6
7 System.out.println("no it does not");
Now rewrite the code so that it works correctly
5. (Graphs) Use the following description of an undirected graph for Questions a) and b) below:
EmployeeGraph = (V, E)
V(EmployeeGraph) = {Susan, Darlene, Mike, Fred, John, Sander, Lance, Jean, Brent, Fran}
E(EmployeeGraph) = {(Susan, Darlene), (Fred, Brent), (Sander, Susan), (Lance, Fran),
(Sander, Fran), (Fran, John), (Lance, Jean), (Jean, Susan), (Mike, Darlene), (Brent, Lance), (Susan, John)}
(a) Draw a picture of EmployeeGraph (draw it the way graphs look like - see the book or slides)
(b) Which one of the following phrases best describes the relationship represented by the edges between the vertices in EmployeeGraph and why?
i. “works for”
ii. “is the supervisor of ”
iii. “is senior to” iv. “works with”
6. (Graphs) Draw the adjacency matrix for the graph in Figure 2. Store the vertices in alphabetical order.
2 Programming exercises
Please do these with your partner. The assignments are not precisely defined (as in the real-world) and you will have to figure out the details. You will need to
Figure 2: Graph example
show the concepts you learned in this class (OOP design) as much as possible. You will present your solution to the class in the final class of the semester. You will run your code and demonstrate how it works and then we will discuss the structure of your solution. I will ask each of you to write a report on your partner describing how much your partner contributed to this homework. Make sure you comment your code.
2.1 Problem 1: Logical Circuits
In this assignment using Java’s OOP design you need to represent the following logic gates: AND, OR, NOT and XOR. The basic functionality of your code should be the following:
1. For each gate, given some inputs, get the calculated output. For example (this is pseudocode): AND(True, True) should give me True, XOR(True, False) should give me True. Make the application that makes sure each of your gate operates correctly with all combinations of binary inputs.
2. (Bonus for A+) Go for the glory! This one is a bit more complicated but fun. Given a logic circuit calculate the output of the circuit. For example, for the circuit in Figure 3 and inputs A = TRUE, B = FALSE, C = FALSE, D = TRUE the circuit outputs FALSE. Don’t try to solve everything. Just make a solution for these simpler examples. Use the circuit in Figure 3 to test your code.
You can always do more. Amaze us.
Figure 3: Example circuit
2.2 Problem 1: Social Network
You are provided with the following two files: users.csv and edges.csv. The files contain the following:
1. users.csv has the following attributes:
• user id: is a unique identifier of a user
• community: is one of the following values {science, sport, art}.
• age: is the age of a user
• posts: is a list of post types users most frequently share (to simply it for you I set maximum possible per user to 10). It can be one of the following values: {video, image, article}.
2. edges.csv has the following attributes:
• user id, user id : represents the edge between two user ids
2.2.1 What should I do?
To solve this task use and adapt the WeightedGraph implementation from the book (ch10). Represent this data as a graph and perform some interesting analysis of the data. You should demonstrate at least three questions asked about the graph. Some of these will require adding methods and new attributes to WeightedGraph.java file or performing it in the driver code.
2.2.2 What is a CSV file?
CSV stands for “comma-separated values”. You can load these files in Excel or Libre Office Calc and view them. However, for this project you will need to load it in Java.
2.2.3 Visualisation
If you would like to visualize your graph (or a part of it) I suggest using the following library for representing graphs: http://graphstreamproject.org/download/ Go to the Website and download all the three jars from the 1.3 release (gs-core, gs-algo, gs-ui). Make sure to download them somewhere you can find them. I suggest putting all three jars in a folder on the same level as your src folder, and call it lib. In your IDE make sure you add all three jars to your library list (Congifure Build Path -¿ Add external jars). You have to figure out how to use the library. :)
2.2.4 Timely report errors or issues
If you find an inconsistency in the data, code or similar, report immediately. It’s also part of the process and could bring you even more glory
1 file (0.0bytes)
