1. Generating Random Networks 1. Create random networks using Erd¨os-R´enyi (ER) model (a) Create undirected random networks with n = 900 nodes, and the probability p for drawing an edge between two arbitrary vertices 0.002, 0.006, 0.012, 0.045, and 0.1. Plot the degree distributions. What distribution (linear/exponential/gaussian/binomial or something else) is observed? Explain why. Also, report the mean and variance of the degree distributions and compare them to the theoretical values. Hint Useful function(s): samplegnp (erdos.renyi.game) , degree , degreedistribution , plot (b) For each p and n = 900, answer the following questions: Are all random realizations of the ER network connected? Numerically estimate the probability that a generated network is connected. For one instance of the networks with that p, find the giant connected component (GCC) if not connected. What is the diameter of the GCC? Hint Useful function(s): isconnected , clusters , diameter (c) It turns out that the normalized GCC size (i.e., the size of the GCC as a fraction of the total network size) is a highly nonlinear function of p, with interesting properties occurring for values where p = O( 1 n ) and p = O( ln n n ). For n = 900, sweep over values of p from 0 to a pmax that makes the network almost surely connected and create 100 random networks for each p. pmax should be roughly determined by yourself. Then scatter plot the normalized GCC sizes vs p. Plot a line of the average normalized GCC sizes for each p along with the scatter plot. i. Empirically estimate the value of p where a giant connected component starts to emerge (define your criterion of “emergence”)? Do they match with theoretical values mentioned or derived in lectures? ii. Empirically estimate the value of p where the giant connected component takes up over 99% of the nodes in almost every experiment. (d) i. Define the average degree of nodes c = n × p = 0.5. Sweep over the number of nodes, n, ranging from 100 to 10000. Plot the expected size of the GCC of ER networks with n nodes and edge-formation probabilities p = c/n, as a function of n. What trend is observed? ii. Repeat the same for c = 1. iii. Repeat the same for values of c = 1.15, 1.25, 1.35, and show the results for these three values in a single plot. iv. What is the relation between the expected GCC size and n in each case? 2. Create networks using preferential attachment model (a) Create an undirected network with n = 1050 nodes, with preferential attachment model, where each new node attaches to m = 1 old nodes. Is such a network always connected? Hint Useful function(s): samplepa (barabasi.game) (b) Use fast greedy method to find the community structure. Measure modularity. Define Assortativity. Compute Assortativity. Hint Useful function(s): clusterfastgreedy , modularity (c) Try to generate a larger network with 10500 nodes using the same model. Compute modularity and assortativity. How is it compared to the smaller network’s modularity? 2 (d) Plot the degree distribution in a log-log scale for both n = 1050, 10500, then estimate the slope of the plot using linear regression. (e) In the two networks generated in 2(a) and 2(c), perform the following: Randomly pick a node i, and then randomly pick a neighbor j of that node. Plot the degree distribution of nodes j that are picked with this process, in the log-log scale. Is the distribution linear in the log-log scale? If so, what is the slope? How does this differ from the node degree distribution? Hint Useful function(s): sample (f) Estimate the expected degree of a node that is added at time step i for 1 ≤ i ≤ 1050. Show the relationship between the age of nodes and their expected degree through an appropriate plot. Note that the newest added node is the youngest. (g) Repeat the previous parts (a-f) for m = 2, and m = 6. Compare the results of each part for different values of m. (h) Again, generate a preferential attachment network with n = 1050, m = 1. Take its degree sequence and create a new network with the same degree sequence, through stub-matching procedure. Plot both networks, mark communities on their plots, and measure their modularity. Compare the two procedures for creating random power-law networks. Hint In case that fastgreedy community detection fails because of self-loops, you may use “walktrap” community detection. Useful function(s): sampledegseq 3. Create a modified preferential attachment model that penalizes the age of a node (a) Each time a new vertex is added, it creates m links to old vertices and the probability that an old vertex is cited depends on its degree (preferential attachment) and age. In particular, the probability that a newly added vertex connects to an old vertex is proportional to: P[i] ∼ (ckα i + a)(dlβ i + b), where ki is the degree of vertex i in the current time step, and li is the age of vertex i. Produce such an undirected network with 1050 nodes and parameters m = 1, α = 1, β = −1, and a = c = d = 1, b = 0. Plot the degree distribution. What is the power law exponent? Hint Useful function(s): samplepaage (b) Use fast greedy method to find the community structure. What is the modularity? 3 2. Random Walk on Networks 1. Random walk on Erd¨os-R´enyi networks (a) Create an undirected random network with 900 nodes, and the probability p for drawing an edge between any pair of nodes equal to 0.015. (b) Let a random walker start from a randomly selected node (no teleportation). We use t to denote the number of steps that the walker has taken. Measure the average distance (defined as the shortest path length) ⟨s(t)⟩ of the walker from his starting point at step t. Also, measure the variance σ 2 (t) = ⟨(s(t) − ⟨s(t)⟩) 2 ⟩ of this distance. Plot ⟨s(t)⟩ v.s. t and σ 2 (t) v.s. t. Here, the average ⟨·⟩ is over random choices of the starting nodes. (c) Measure the degree distribution of the nodes reached at the end of the random walk. How does it compare to the degree distribution of graph? (d) Repeat 1(b) for undirected random networks with 9000 nodes. Compare the results and explain qualitatively. Does the diameter of the network play a role? 2. Random walk on networks with fat-tailed degree distribution (a) Generate an undirected preferential attachment network with 900 nodes, where each new node attaches to m = 1 old nodes. (b) Let a random walker start from a randomly selected node. Measure and plot ⟨s(t)⟩ v.s. t and σ 2 (t) v.s. t. (c) Measure the degree distribution of the nodes reached at the end of the random walk on this network. How does it compare with the degree distribution of the graph? (d) Repeat 2(b) for preferential attachment networks with 90 and 9000 nodes, and m = 1. Compare the results and explain qualitatively. Does the diameter of the network play a role? 3. PageRank The PageRank algorithm, as used by the Google search engine, exploits the linkage structure of the web to compute global “importance” scores that can be used to influence the ranking of search results. Here, we use random walk to simulate PageRank. (a) We are going to create a directed random network with 900 nodes, using the preferential attachment model. Note that in a directed preferential attachment network, the out-degree of every node is m, while the in-degrees follow a power law distribution. One problem of performing random walk in such a network is that, the very first node will have no outbounding edges, and be a “black hole” which a random walker can never “escape” from. To address that, let’s generate another 900-node random network with preferential attachment model, and merge the two networks by adding the edges of the second graph to the first graph with a shuffling of the indices of the nodes. For example, 1 → 2 2 → 3 3 → 4 Initial edge list of the second network 4 → 3 3 → 1 1 → 2 Edge list after node idx shuffling (the edges that should be added to the first network) shuffled to 1,2,3,4 4,3,1,2 4 Create such a network using m = 4. Measure the probability that the walker visits each node. Is this probability related to the degree of the nodes? Hint Useful function(s): asedgelist , sample , permute , addedges (b) In all previous questions, we didn’t have any teleportation. Now, we use a teleportation probability of α = 0.2 (teleport out of a node with prob=0.2 instead of going to its neighbor). By performing random walks on the network created in 3(a), measure the probability that the walker visits each node. How is this probability related to the degree of the node and α ? 4. Personalized PageRank While the use of PageRank has proven very effective, the web’s rapid growth in size and diversity drives an increasing demand for greater flexibility in ranking. Ideally, each user should be able to define their own notion of importance for each individual query. (a) Suppose you have your own notion of importance. Your interest in a node is proportional to the node’s PageRank, because you totally rely upon Google to decide which website to visit (assume that these nodes represent websites). Again, use random walk on network generated in question 3 to simulate this personalized PageRank. Here the teleportation probability to each node is proportional to its PageRank (as opposed to the regular PageRank, where at teleportation, the chance of visiting all nodes are the same and equal to 1 N ). Again, let the teleportation probability be equal to α = 0.2. Compare the results with 3(a). (b) Find two nodes in the network with median PageRanks. Repeat part 4(a) if teleportations land only on those two nodes (with probabilities 1/2, 1/2). How are the PageRank values affected? (c) More or less, 4(b) is what happens in the real world, in that a user browsing the web only teleports to a set of trusted web pages. However, this is against the assumption of normal PageRank, where we assume that people’s interest in all nodes are the same. Can you take into account the effect of this self-reinforcement and adjust the PageRank equation? 5 Final Remarks The following functions from igraph library are useful for this project: • degree, degree.distribution, diameter, clusters, vcount, ecount • random.graph.game, barabasi.game, aging.prefatt.game, degree.sequence.game • page rank For part 2 of the project, you can start off with the Jupyter notebook provided to you.In this project, we will study the various properties of social networks. In the first part of the project, we will study an undirected social network (Facebook). In the second part of the project, we will study a directed social network (Google +). You can complete the Project using R or Python. 1. Facebook network In this project, we will be using the dataset given below: http://snap.stanford.edu/data/egonets-Facebook.html The Facebook network can be created from the edgelist file (facebook combined.txt) 1. Structural properties of the Facebook network Having created the Facebook network, we will study some of the structural properties of the network. To be specific, we will study • Connectivity • Degree distribution QUESTION 1: A first look at the network: QUESTION 1.1: Report the number of nodes and number of edges of the Facebook network. QUESTION 1.2: Is the Facebook network connected? If not, find the giant connected component (GCC) of the network and report the size of the GCC. QUESTION 2: Find the diameter of the network. If the network is not connected, then find the diameter of the GCC. QUESTION 3: Plot the degree distribution of the facebook network and report the average degree. QUESTION 4: Plot the degree distribution of Question 3 in a log-log scale. Try to fit a line to the plot and estimate the slope of the line. 1 2. Personalized network A personalized network of an user vi is defined as the subgraph induced by vi and it’s neighbors. In this part, we will study some of the structural properties of the personalized network of the user whose graph node ID is 1 (node ID in edgelist is 0). From this point onwards, whenever we are refering to a node ID we mean the graph node ID which is 1 + node ID in edgelist. QUESTION 5: Create a personalized network of the user whose ID is 1. How many nodes and edges does this personalized network have? Hint Useful function(s): makeegograph QUESTION 6: What is the diameter of the personalized network? Please state a trivial upper and lower bound for the diameter of the personalized network. QUESTION 7: In the context of the personalized network, what is the meaning of the diameter of the personalized network to be equal to the upper bound you derived in Question 6. What is the meaning of the diameter of the personalized network to be equal to the lower bound you derived in Question 6 (assuming there are more than 3 nodes in the personalized network)? 3. Core node’s personalized network A core node is defined as the nodes that have more than 200 neighbors. For visualization purpose, we have displayed the personalized network of a core node below. An example of a personal network. The core node is shown in black. In this part, we will study various properties of the personalized network of the core nodes. QUESTION 8: How many core nodes are there in the Facebook network. What is the average degree of the core nodes? 3.1. Community structure of core node’s personalized network In this part, we study the community structure of the core node’s personalized network. To be specific, we will study the community structure of the personalized network of the following core nodes: 2 • Node ID 1 • Node ID 108 • Node ID 349 • Node ID 484 • Node ID 1087 QUESTION 9: For each of the above core node’s personalized network, find the community structure using Fast-Greedy, Edge-Betweenness, and Infomap community detection algorithms. Compare the modularity scores of the algorithms. For visualization purpose, display the community structure of the core node’s personalized networks using colors. Nodes belonging to the same community should have the same color and nodes belonging to different communities should have different color. In this question, you should have 15 plots in total. Hint Useful function(s): clusterfastgreedy , clusteredgebetweenness , clusterinfomap 3.2. Community structure with the core node removed In this part, we will explore the effect on the community structure of a core node’s personalized network when the core node itself is removed from the personalized network. QUESTION 10: For each of the core node’s personalized network (use same core nodes as Question 9), remove the core node from the personalized network and find the community structure of the modified personalized network. Use the same community detection algorithm as Question 9. Compare the modularity score of the community structure of the modified personalized network with the modularity score of the community structure of the personalized network of Question 9. For visualization purpose, display the community structure of the modified personalized network using colors. In this question, you should have 15 plots in total. 3.3. Characteristic of nodes in the personalized network In this part, we will explore characteristics of nodes in the personalized network using two measures. These two measures are stated and defined below: • Embeddedness of a node is defined as the number of mutual friends a node shares with the core node. • Dispersion of a node is defined as the sum of distances between every pair of the mutual friends the node shares with the core node. The distances should be calculated in a modified graph where the node (whose dispersion is being computed) and the core node are removed. For further details on the above characteristics, you can read the paper below: http://arxiv.org/abs/1310.6753 QUESTION 11: Write an expression relating the Embeddedness between the core node and a non-core node to the degree of the non-core node in the personalized network of the core node. 3 QUESTION 12: For each of the core node’s personalized network (use the same core nodes as Question 9), plot the distribution histogram of embeddedness and dispersion. In this question, you will have 10 plots. Hint Useful function(s): neighbors , intersection , distances QUESTION 13: For each of the core node’s personalized network, plot the community structure of the personalized network using colors and highlight the node with maximum dispersion. Also, highlight the edges incident to this node. To detect the community structure, use Fast-Greedy algorithm. In this question, you will have 5 plots. QUESTION 14: Repeat Question 13, but now highlight the node with maximum embeddedness and the node with maximum dispersion embeddedness (excluding the nodes having zero embeddedness if there are any). Also, highlight the edges incident to these nodes. Report the id of those nodes. QUESTION 15: Use the plots from Question 13 and 14 to explain the characteristics of a node revealed by each of this measure. 4. Friend recommendation in personalized networks In many social networks, it is desirable to predict future links between pairs of nodes in the network. In the context of this Facebook network it is equivalent to recommending friends to users. In this part of the project, we will explore some neighborhood-based measures for friend recommendation. The network that we will be using for this part is the personalized network of node with ID 415. 4.1. Neighborhood based measure In this project, we will be exploring three different neighborhood-based measures. Before we define these measures, let’s introduce some notation: • Si is the neighbor set of node i in the network • Sj is the neighbor set of node j in the network Then, with the above notation we define the three measures below: • Common neighbor measure between node i and node j is defined as Common Neighbors(i, j) = |Si ∩ Sj | • Jaccard measure between node i and node j is defined as Jaccard(i, j) = |Si ∩ Sj | |Si ∪ Sj | • Adamic-Adar measure between node i and node j is defined as Adamic Adar(i, j) = X k∈Si∩Sj 1 log(|Sk|) 4 4.2. Friend recommendation using neighborhood based measures We can use the neighborhood based measures defined in the previous section to recommend new friends to users in the network. Suppose we want to recommend t new friends to some user i in the network using Jaccard measure. We follow the steps listed below: 1. For each node in the network that is not a neighbor of i, compute the jaccard measure between the node i and the node not in the neighborhood of i Compute Jaccard(i, j) ∀j ∈ S C i 2. Then pick t nodes that have the highest Jaccard measure with node i and recommend these nodes as friends to node i 4.3. Creating the list of users Having defined the friend recommendation procedure, we can now apply it to the personalized network of node ID 415. Before we apply the algorithm, we need to create the list of users who we want to recommend new friends to. We create this list by picking all nodes with degree 24. We will denote this list as Nr. QUESTION 16: What is |Nr|, i.e. the length of the list Nr? 4.4. Average accuracy of friend recommendation algorithm In this part, we will apply the 3 different types of friend recommendation algorithms to recommend friends to the users in the list Nr. We will define an average accuracy measure to compare the performances of the friend recommendation algorithms. Suppose we want to compute the average accuracy of the friend recommendation algorithm. This task is completed in two steps: 1. Compute the average accuracy for each user in the list Nr 2. Compute the average accuracy of the algorithm by averaging across the accuracies of the users in the list Nr Let’s describe the procedure for accomplishing the step 1 of the task. Suppose we want to compute the average accuracy for user i in the list Nr. We can compute it by iterating over the following steps 10 times and then taking the average: 1. Remove each edge of node i at random with probability 0.25. In this context, it is equivalent to deleting some friends of node i. Let’s denote the list of friends deleted as Ri 2. Use one of the three neighborhood based measures to recommend |Ri | new friends to the user i. Let’s denote the list of friends recommended as Pi 3. The accuracy for the user i for this iteration is given by |Pi∩Ri| |Ri| By iterating over the above steps for 10 times and then taking the average gives us the average accuracy of user i. In this manner, we compute the average accuracy for each user in the list 5 Nr. Once we have computed them, then we can take the mean of the average accuracies of the users in the list Nr. The mean value will be the average accuracy of the friend recommendation algorithm. QUESTION 17: Compute the average accuracy of the friend recommendation algorithm that uses: • Common Neighbors measure • Jaccard measure • Adamic Adar measure Based on the average accuracy values, which friend recommendation algorithm is the best? Hint Useful function(s): similarity 2. Google+ network In this part, we will explore the structure of the Google+ network. The dataset for creating the network can be found in the link below: http://snap.stanford.edu/data/egonets-Gplus.html Create directed personal networks for users who have more than 2 circles. The data required to create such personal networks can be found in the file named gplus.tar.gz. QUESTION 18: How many personal networks are there? QUESTION 19: For the 3 personal networks (node ID given below), plot the in-degree and outdegree distribution of these personal networks. Do the personal networks have a similar in and out degree distribution? In this question, you should have 6 plots. • 109327480479767108490 • 115625564993990145546 • 101373961279443806744 1. Community structure of personal networks In this part of the project, we will explore the community structure of the personal networks that we created and explore the connections between communities and user circles. QUESTION 20: For the 3 personal networks picked in Question 19, extract the community structure of each personal network using Walktrap community detection algorithm. Report the modularity scores and plot the communities using colors. Are the modularity scores similar? In this question, you should have 3 plots. Having found the communities, now we will explore the relationship between circles and communities. In order to explore the relationship, we define two measures: 6 • Homogeneity • Completeness Before, we state the expression for homogeneity and completeness, let’s introduce some notation: • C is the set of circles, C = {C1, C2, C3, · · · } • K is the set of communities, K = {K1, K2, K3, · · · } • ai is the number of people in circle Ci • bi is the number of people in community Ki with circle information • N is the total number of people with circle information • Aji is the number of people belonging to community j and circle i Then, with the above notation, we have the following expressions for the entropy H(C) = − X |C| i=1 ai N log( ai N ) (1) H(K) = − X |K| i=1 bi N log( bi N ) (2) and conditional entropy H(C|K) = − X |K| j=1 X |C| i=1 Aji N log(Aji bj ) (3) H(K|C) = − X |C| i=1 X |K| j=1 Aji N log(Aji ai ) (4) Now we can state the expression for homogeneity, h as h = 1 − H(C|K) H(C) (5) and the expression for completeness, c as c = 1 − H(K|C) H(K) (6) QUESTION 21: Based on the expression for h and c, explain the meaning of homogeneity and completeness in words. QUESTION 22: Compute the h and c values for the community structures of the 3 personal network (same nodes as Question 19). Interpret the values and provide a detailed explanation. Are there negative values? Why? 7 3. Cora dataset One of the well-known categories of machine learning problems is “supervised learning”. In supervised learning, we are given some information called “input” features about certain objects. For each object, we are also given an “output” or target variable that we are trying to predict about. Our goal is to learn the mapping between the features and the target variable. Typically, there is a portion of data where both input features and target variables are available. This portion of the dataset is called the training set. There is also typically another portion of the dataset where the target variable is missing and we want to predict it. This portion is called the “test set”. When the target variable can take on a finite number of discrete values, we call the problem at hand a “classification” problem. In this project, we are trying to solve a classification problem in settings where some additional information is provided in the form of “graph structure”. In this project we work with “Cora” dataset. Cora consists of a set of 2708 documents that are Machine Learning related papers. Each documents is labeled with one of the following seven classes: Case Based, Genetic Algorithms, Neural Networks, Probabilistic Methods, Reinforcement Learning, Rule Learning, Theory. For each class, only 20 documents are labeled (a total of 140 for the seven classes). We refer to them as “seed” documents. Each document comes with a set of features about its text content. These features are occurrences of a selection of 1433 words in the vocabulary. We are also given an undirected graph where each node is a document and each edge represents a citation. There are a total of 5429 edges. Our goal is to use the hints from text features as well as from graph connections to classify (assign labels to) these documents. To solve this problem for Cora dataset, we pursue three parallel ideas. Implement each idea and compare. QUESTION 23: Idea 1 Use Graph Convolutional Networks [1]. What hyperparameters do you choose to get the optimal performance? How many layers did you choose? QUESTION 24: Idea 2 Extract structure-based node features using Node2Vec [2]. Briefly describe how Node2Vec finds node features. Choose your desired classifier (one of SVM, Neural Network, or Random Forest) and classify the documents using only Node2Vec (graph structure) features. Now classify the documents using only the 1433-dimensional text features. Which one outperforms? Why do you think this is the case? Combine the Node2Vec and text features and train your classifier on the combined features. What is the best classification accuracy you get (in terms of the percentage of test documents correctly classified)? QUESTION 25: Idea 3 We can find the personalized PageRank of each document in seven different runs, one per class. In each run, select one of the classes and take the 20 seed documents of that class. Then, perform a random walk with the following customized properties: (a) teleportation takes the random walker to one of the seed documents of that class (with a uniform probability of 1/20 per seed document). Vary the teleportation probability in {0, 0.1, 0.2}. (b) the probability of transitioning to neighbors is not uniform among the neighbors. Rather, it is proportional to the cosine similarity between the text features of the current node and the next neighboring node. Particularly, assume we are currently visiting a document x0 which has neighbors x1, x2, x3. 8 Then the probability of transitioning to each neighbor is: pi = exp(x0 · xi) exp(x0 · x1) + exp(x0 · x2) + exp(x0 · x3) ; for i = 1, 2, 3. (7) Repeat part b for every teleportation probability in part a. Run the PageRank only on the GCC. for each seed node, do 1000 random walks. Maintain a class-wise visited frequency count for every unlabeled node. The predicted class for that unlabeled node is the class which lead to maximum visits to that node. Report accuracy and f1 scores. For example if node ’n’ was visited by 7 random walks from class A, 6 random walks from class B… 1 random walk from class G, then the predicted label of node of ’n’ is class A. Submission Please submit the report to Gradescope. Meanwhile, please submit a zip file containing your codes and report to BruinLearn. The zip file should be named as “Project2 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. If you have any questions please feel free to ask them over email or piazza. References [1] Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” arXiv preprint arXiv:1609.02907 (2016).1 Introduction Reinforcement Learning (RL) is the task of learning from interaction to achieve a goal. The learner and the decision maker is called the agent. The thing it interacts with, comprising everything outside the agent, is called the environment. These interact continually, the agent selecting actions and the environment responding to those actions by presenting rewards and new states. In the first part of the project, we will learn the optimal policy of an agent navigating in a 2-D environment. We will implement the Value iteration algorithm to learn the optimal policy. Inverse Reinforcement Learning (IRL) is the task of extracting an expert’s reward function by observing the optimal policy of the expert. In the second part of the project, we will explore the application of IRL in the context of apprenticeship learning. 2 Reinforcement learning (RL) The two main objects in Reinforcement learning are: • Agent • Environment In this project, we will learn the optimal policy of a single agent navigating in a 2-D environment. 2.1 Environment In this project, we assume that the environment of the agent is modeled by a Markov Decision Process (MDP). In a MDP, agents occupy a state of the environment and perform actions to change the state they are in. After taking an action, they are given some representation of the new state and some reward value associated with the new state. An MDP formally is a tuple (S, A,P a ss′, Ra ss′, γ) where: 1 • S is a set of states • A is a set of actions • P a ss′ is a set of transition probabilities, where P a ss′ is the probability of transitioning from state s ∈ S to state s ′ ∈ S after taking action a ∈ A – P a ss′ = P(st+1 = s ′ |st = s, at = a) • Given any current state and action, s and a, together with any next state, s ′ , the expected value of the next reward is Ra ss′ – Ra ss′ = E(rt+1|st = s, at = a, st+1 = s ′ ) • γ ∈ [0, 1) is the discount factor, and it is used to compute the present value of future reward – If γ is close to 1 then the future rewards are discounted less – If γ is close to 0 then the future rewards are discounted more In the next few subsections, we will discuss the parameters that will be used to generate the environment for the project. 2.1.1 State space In this project, we consider the state space to be a 2-D square grid with 100 states. The 2-D square grid along with the numbering of the states is shown in figure 1 Figure 1: 2-D square grid with state numbering 2.1.2 Action set In this project, we consider the action set(A) to contain the 4 following actions: • Move Right 2 • Move Left • Move Up • Move Down The 4 types of actions are displayed in figure 2 Figure 2: 4 types of action From the above figure, we can see that the agent can take 4 actions from the state marked with a dot. 2.1.3 Transition probabilities In this project, we define the transition probabilities in the following manner: 1. If state s ′ and s are not neighboring states in the 2-D grid, then P(st+1 = s ′ |st = s, at = a) = 0 s ′ and s are neighbors in the 2-D grid if you can move to s ′ from s by taking an action a from the action set A. We will consider a state s to be a neighbor of itself. For example, from figure 1 we can observe that states 1 and 11 are neighbors (we can transition from 1 to 11 by moving right) but states 1 and 12 are not neighbors. 2. Each action corresponds to a movement in the intended direction with probability 1 − w, but has a probability of w of moving in a random direction instead due to wind. To illustrate this, let’s consider the states shown in figure 3 3 Figure 3: Inner grid states (Non-boundary states) The transition probabilities for the non-boundary states shown in figure 3 are given below: P(st+1 = 43|st = 44, at =↑) = 1 − w + w 4 P(st+1 = 34|st = 44, at =↑) = w 4 P(st+1 = 54|st = 44, at =↑) = w 4 P(st+1 = 45|st = 44, at =↑) = w 4 From the above calculation it can be observed that if the agent is at a non-boundary state then it has 4 neighbors excluding itself and the probability w is uniformly distributed over the 4 neighbors. Also, if the agent is at a non-boundary state then it transitions to a new state after taking an action (P(st+1 = 44|st = 44, at =↑) = 0) 3. If the agent is at one of the four corner states (0,9,90,99), the agent stays at the current state if it takes an action to move off the grid or is blown off the grid by wind. The actions can be divided into two categories: • Action to move off the grid • Action to stay in the grid To illustrate this, let’s consider the states shown in figure 4 4 Figure 4: Corner states The transition probabilities for taking an action to move off the grid are given below: P(st+1 = 10|st = 0, at =↑) = w 4 P(st+1 = 1|st = 0, at =↑) = w 4 P(st+1 = 0|st = 0, at =↑) = 1 − w + w 4 + w 4 The transition probabilities for taking an action to stay in the grid are given below: P(st+1 = 10|st = 0, at =→) = 1 − w + w 4 P(st+1 = 1|st = 0, at =→) = w 4 P(st+1 = 0|st = 0, at =→) = w 4 + w 4 At a corner state, you can be blown off the grid in two directions. As a result, we have P(st+1 = 0|st = 0, at =→) = w 4 + w 4 since we can be blown off the grid in two directions and in both the cases we stay at the current state. 4. If the agent is at one of the edge states, the agent stays at the current state if it takes an action to move off the grid or is blown off the grid by wind. The actions can be divided into two categories: • Action to move off the grid • Action to stay in the grid To illustrate this, let’s consider the states shown in figure 5 5 Figure 5: Edge states The transition probabilities for taking an action to move off the grid are given below: P(st+1 = 0|st = 1, at =←) = w 4 P(st+1 = 11|st = 1, at =←) = w 4 P(st+1 = 2|st = 1, at =←) = w 4 P(st+1 = 1|st = 1, at =←) = 1 − w + w 4 The transition probabilities for taking an action to stay in the grid are given below: P(st+1 = 0|st = 1, at =↑) = 1 − w + w 4 P(st+1 = 11|st = 1, at =↑) = w 4 P(st+1 = 2|st = 1, at =↑) = w 4 P(st+1 = 1|st = 1, at =↑) = w 4 At an edge state, you can be blown off the grid in one direction. As a result, we have P(st+1 = 1|st = 1, at =↑) = w 4 since we can be blown off the grid in one direction and in that case we stay at the current state. The main difference between a corner state and an edge state is that a corner state has 2 neighbors and an edge state has 3 neighbors. 2.1.4 Reward function To simplify the project, we will assume that the reward function is independent of the current state (s) and the action that you take at the current state (a). To be specific, reward 6 function only depends on the state that you transition to (s ′ ). With this simplification, we have Ra ss′ = R(s ′ ) In this project, we will learn the optimal policy of an agent for two different reward functions: • Reward function 1 • Reward function 2 The two different reward functions are displayed in figures 6 and 7 respectively Figure 6: Reward function 1 7 Figure 7: Reward function 2 Question 1: (10 points) For visualization purpose, generate heat maps of Reward function 1 and Reward function 2. For the heat maps, make sure you display the coloring scale. You will have 2 plots for this question For solving question 1, you might find the following function useful: https://matplotlib.org/api/_as_gen/matplotlib.pyplot.pcolor.html 3 Optimal policy learning using RL algorithms In this part of the project, we will use reinforcement learning (RL) algorithm to find the optimal policy. The main steps in RL algorithm are: • Find optimal state-value or action-value • Use the optimal state-value or action-value to determine the deterministic optimal policy There are a couple of RL algorithms, but we will use the Value iteration algorithm since it was discussed in detail in the lecture. We will skip the derivation of the algorithm here because it was covered in the lecture (for the derivation details please refer to the lecture slides on Reinforcement learning). We will just reproduce the algorithm below for the ease of implementation: 8 1: procedure Value Iteration(P a ss′ , Ra ss′ , S, A, γ): 2: for all s ∈ S do ▷ Initialization 3: V (s) ← 0 4: end for 5: ∆ ← ∞ 6: while ∆ > ϵ do ▷ Estimation 7: ∆ ← 0 8: for all s ∈ S do 9: v ← V (s); 10: V (s) ← max a∈A X s ′∈S P a ss′ [Ra ss′ + γV (s ′ )]; 11: ∆ ← max(∆, |v − V (s)|); 12: end for 13: end while 14: for all s ∈ S do ▷ Computation 15: π(s) ← arg max a∈A X s ′∈S P a ss′ [Ra ss′ + γV (s ′ )]; 16: end for 17: end procedure return π Question 2: (40 points) Create the environment of the agent using the information provided in section 2. To be specific, create the MDP by setting up the state-space, action set, transition probabilities, discount factor, and reward function. For creating the environment, use the following set of parameters: • Number of states = 100 (state space is a 10 by 10 square grid as displayed in figure 1) • Number of actions = 4 (set of possible actions is displayed in figure 2) • w = 0.1 • Discount factor = 0.8 • Reward function 1 After you have created the environment, then write an optimal state-value function that takes as input the environment of the agent and outputs the optimal value of each state in the grid. For the optimal state-value function, you have to implement the Initialization (lines 2-4) and Estimation (lines 5-13) steps of the Value Iteration algorithm. For the estimation step, use ϵ = 0.01. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal value of that state. In this part of question, you should have 1 plot. Let’s assume that your value iteration algorithm converges in N steps. Plot snapshots of state values in 5 different steps linearly distributed from 1 to N. Report N and your step numbers. What observations do you have from the plots? Question 3: (5 points) Generate a heat map of the optimal state values across the 2- D grid. For generating the heat map, you can use the same function provided in the hint earlier (see the hint after question 1). Question 4: (15 points) Explain the distribution of the optimal state values across the 2-D grid. (Hint: Use the figure generated in question 3 to explain) Question 5: (20 points) Implement the computation step of the value iteration algorithm 9 (lines 14-17) to compute the optimal policy of the agent navigating the 2-D state-space. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The optimal actions should be displayed using arrows. Does the optimal policy of the agent match your intuition? Please provide a brief explanation. Is it possible for the agent to compute the optimal action to take at each state by observing the optimal values of it’s neighboring states? In this question, you should have 1 plot. Question 6: (10 points) Modify the environment of the agent by replacing Reward function 1 with Reward function 2. Use the optimal state-value function implemented in question 2 to compute the optimal value of each state in the grid. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal value of that state. In this question, you should have 1 plot. Question 7: (20 points) Generate a heat map of the optimal state values (found in question 6) across the 2-D grid. For generating the heat map, you can use the same function provided in the hint earlier. Explain the distribution of the optimal state values across the 2-D grid. (Hint: Use the figure generated in this question to explain) Question 8: (20 points) Implement the computation step of the value iteration algorithm (lines 14-17) to compute the optimal policy of the agent navigating the 2-D state-space. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The optimal actions should be displayed using arrows. Does the optimal policy of the agent match your intuition? Please provide a brief explanation. In this question, you should have 1 plot. Question 9:(20 points) Change the hyper parameter w to 0.6 and find the optimal policy map similar to previous question for reward functions. Explain the differences you observe. What do you think about value of new w compared to previous value? Choose the w that you think give rise to better optimal policy and use that w for the next stages of the project. 4 Inverse Reinforcement learning (IRL) Inverse Reinforcement learning (IRL) is the task of learning an expert’s reward function by observing the optimal behavior of the expert. The motivation for IRL comes from apprenticeship learning. In apprenticeship learning, the goal of the agent is to learn a policy by observing the behavior of an expert. This task can be accomplished in two ways: 1. Learn the policy directly from expert behavior 2. Learn the expert’s reward function and use it to generate the optimal policy The second way is preferred because the reward function provides a much more parsimonious description of behavior. Reward function, rather than the policy, is the most succinct, robust, and transferable definition of the task. Therefore, extracting the reward function of an expert would help design more robust agents. In this part of the project, we will use IRL algorithm to extract the reward function. 10 We will use the optimal policy computed in the previous section as the expert behavior and use the algorithm to extract the reward function of the expert. Then, we will use the extracted reward function to compute the optimal policy of the agent. We will compare the optimal policy of the agent to the optimal policy of the expert and use some similarity metric between the two to measure the performance of the IRL algorithm. 4.1 IRL algorithm For finite state spaces, there are a couple of IRL algorithms for extracting the reward function: • Linear Programming (LP) formulation • Maximum Entropy formulation Since we covered the LP formulation of inverse reinforcement learning in lecture—and it is simpler than the original quadratic-program approach—we adopt that version here [?]. A step-by-step derivation can be found in our course slides [?]. The LP formulation of the IRL is given by equation 1 maximize R,ti,ui P|S| i=1(ti − λui) subject to [(Pa1 (i) − Pa(i))(I − γPa1 ) −1R] ≥ ti , ∀a ∈ A a1, ∀i (Pa1 − Pa)(I − γPa1 ) −1R ⪰ 0, ∀a ∈ A a1 −u ⪯ R ⪯ u |Ri | ≤ Rmax, i = 1, 2, · · · , |S| (1) In the LP given by equation 1, R is the reward vector (R(i) = R(si)), Pa is the transition probability matrix corresponding to the action a, λ is the adjustable penalty coefficient, and ti ’s and ui ’s are the extra optimization variables (please note that u(i) = ui). Throughout IRL section we fix the discount factor to γ = 0.9. Use the maximum absolute value of the ground-truth reward as Rmax. For the ease of implementation, we can recast the LP in equation 1 into an equivalent form given by equation 2 using block matrices. maximize x c T x subject to Dx ⪯ b, ∀a ∈ A a1 (2) Question 10: (10 points) Express c, x, D, b in terms of R, Pa, Pa1 , ti , u, λ and Rmax 4.2 Performance measure In this project, we use a very simple measure to evaluate the performance of the IRL algorithm. Before we state the performance measure, let’s introduce some notation: • OA(s): Optimal action of the agent at state s • OE(s): Optimal action of the expert at state s • m(s) = ( 1, OA(s) = OE(s) 0, else 11 Then with the above notation, accuracy is given by equation 3 Accuracy = P s∈S m(s) |S| (3) Since we are using the optimal policy found in the previous section as the expert behavior, so we will use the optimal policy found in the previous section to fill the OE(s) values. Please note that these values will be different depending on whether we used Reward Function 1 or Reward Function 2 to create the environment. To compute OA(s), we will solve the linear program given by equation 2 to extract the reward function of the expert. For solving the linear program you can use the LP solver in python (from cvxopt import solvers and then use solvers.lp). Then, we will use the extracted reward function to compute the optimal policy of the agent using the value iteration algorithm you implemented in the previous section. The optimal policy of the agent found in this manner will be used to fill the OA(s) values. Please note that these values will depend on the adjustable penalty coefficient λ. We will tune λ to maximize the accuracy. Implementation Guide Constants γ = 0.8 Rmax = maxi |Rtrue(si)| CVXOPT options from cvxopt import s o l v e r s s o l v e r s . o p ti o n s . update ({ ’ a b s t o l ’ : 1 e−7, ’ r e l t o l ’ : 1 e −6, ’ f e a s t o l ’ : 1 e −7, ’ s ho w p rog r e s s ’ : Fal s e }) Question 11: (30 points) Sweep λ from 0 to 5 to get 500 evenly spaced values for λ. For each value of λ compute OA(s) by following the process described above. For this problem, use the optimal policy of the agent found in question 5 to fill in the OE(s) values. Then use equation 3 to compute the accuracy of the IRL algorithm for this value of λ. You need to repeat the above process for all 500 values of λ to get 500 data points. Plot λ (x-axis) against Accuracy (y-axis). In this question, you should have 1 plot. Question 12: (5 points) Use the plot in question 11 to compute the value of λ for which accuracy is maximum. For future reference we will denote this value as λ (1) max. Please report λ (1) max Question 13: (15 points) For λ (1) max, generate heat maps of the ground truth reward and the extracted reward. Please note that the ground truth reward is the Reward function 1 and the extracted reward is computed by solving the linear program given by equation 2 with the λ parameter set to λ (1) max. In this question, you should have 2 plots. Question 14: (10 points) Use the extracted reward function computed in question 13, to compute the optimal values of the states in the 2-D grid. For computing the optimal values you need to use the optimal state-value function that you wrote in question 2. For visualization purpose, generate a heat map of the optimal state values across the 2-D grid (similar to the figure generated in question 3). In this question, you should have 1 plot. 12 Question 15: (10 points) Compare the heat maps of Question 3 and Question 14 and provide a brief explanation on their similarities and differences. Question 16: (10 points) Use the extracted reward function found in question 13 to compute the optimal policy of the agent. For computing the optimal policy of the agent you need to use the function that you wrote in question 5. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The actions should be displayed using arrows. In this question, you should have 1 plot. Question 17: (10 points) Compare the figures of Question 5 and Question 16 and provide a brief explanation on their similarities and differences. Question 18: (30 points) Sweep λ from 0 to 5 to get 500 evenly spaced values for λ. For each value of λ compute OA(s) by following the process described above. For this problem, use the optimal policy of the agent found in question 8 to fill in the OE(s) values. Then use equation 3 to compute the accuracy of the IRL algorithm for this value of λ. You need to repeat the above process for all 500 values of λ to get 500 data points. Plot λ (x-axis) against Accuracy (y-axis). In this question, you should have 1 plot. Question 19: (5 points) Use the plot in question 18 to compute the value of λ for which accuracy is maximum. For future reference we will denote this value as λ (2) max. Please report λ (2) max Question 20: (15 points) For λ (2) max, generate heat maps of the ground truth reward and the extracted reward. Please note that the ground truth reward is the Reward function 2 and the extracted reward is computed by solving the linear program given by equation 2 with the λ parameter set to λ (2) max. In this question, you should have 2 plots. Question 21: (10 points) Use the extracted reward function computed in question 20, to compute the optimal values of the states in the 2-D grid. For computing the optimal values you need to use the optimal state-value function that you wrote in question 2. For visualization purpose, generate a heat map of the optimal state values across the 2-D grid (similar to the figure generated in question 7). In this question, you should have 1 plot. Question 22: (10 points) Compare the heat maps of Question 7 and Question 21 and provide a brief explanation on their similarities and differences. Question 23: (10 points) Use the extracted reward function found in question 20 to compute the optimal policy of the agent. For computing the optimal policy of the agent you need to use the function that you wrote in question 9. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The actions should be displayed using arrows. In this question, you should have 1 plot. Question 24: (10 points) Compare the figures of Question 9 and Question 23 and provide a brief explanation on their similarities and differences. 13 Question 25: (50 points) From the figure in question 23, you should observe that the optimal policy of the agent has two major discrepancies. Please identify and provide the causes for these two discrepancies. One of the discrepancy can be fixed easily by a slight modification to the value iteration algorithm. Perform this modification and re-run the modified value iteration algorithm to compute the optimal policy of the agent. Also, recompute the maximum accuracy after this modification. Is there a change in maximum accuracy? The second discrepancy is harder to fix and is a limitation of the simple IRL algorithm. 5 Submission Please submit your report to Gradescope. Also submit a zip file containing your codes and report to bruinlearn. The zip file should be named as “Project3 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. ReferencesIntroduction In this project we will explore graph theory theorems and algorithms, by applying them on real data. In the first part of the project, we consider a particular graph modeling correlations between stock price time series. In the second part, we analyse traffic data on a dataset provided by Uber. 1. Stock Market In this part of the project, we study data from stock market. The data is available on this Dropbox Link. The goal of this part is to study correlation structures among fluctuation patterns of stock prices using tools from graph theory. The intuition is that investors will have similar strategies of investment for stocks that are effected by the same economic factors. For example, the stocks belonging to the transportation sector may have different absolute prices, but if for example fuel prices change or are expected to change significantly in the near future, then you would expect the investors to buy or sell all stocks similarly and maximize their returns. Towards that goal, we construct different graphs based on similarities among the time series of returns on different stocks at different time scales (day vs a week). Then, we study properties of such graphs. The data is obtained from Yahoo Finance website for 3 years. You’re provided with a number of csv tables, each containing several fields: Date, Open, High, Low, Close, Volume, and Adj Close price. The files are named according to Ticker Symbol of each stock. You may find the market sector for each company in Name sector.csv. We recommend doing this part of the project (Q1 – Q8) in R. 1. Return correlation In this part of the project, we will compute the correlation among log-normalized stock-return time series data. Before giving the expression for correlation, we introduce the following notation: • pi(t) is the closing price of stock i at the t th day • qi(t) is the return of stock i over a period of [t − 1, t] qi(t) = pi(t) − pi(t − 1) pi(t − 1) 1 • ri(t) is the log-normalized return stock i over a period of [t − 1, t] ri(t) = log(1 + qi(t)) Then with the above notation, we define the correlation between the log-normalized stock-return time series data of stocks i and j as ρij = ⟨ri(t)rj (t)⟩ − ⟨ri(t)⟩⟨rj (t)⟩ p (⟨ri(t) 2⟩ − ⟨ri(t)⟩ 2 )(⟨rj (t) 2⟩ − ⟨rj (t)⟩ 2 ) where ⟨·⟩ is a temporal average on the investigated time regime (for our data set it is over 3 years). QUESTION 1: What are upper and lower bounds on ρij? Provide a justification for using lognormalized return (ri(t)) instead of regular return (qi(t)). 2. Constructing correlation graphs In this part,we construct a correlation graph using the correlation coefficient computed in the previous section. The correlation graph has the stocks as the nodes and the edge weights are given by the following expression wij = q 2(1 − ρij ) Compute the edge weights using the above expression and construct the correlation graph. QUESTION 2: Plot a histogram showing the un-normalized distribution of edge weights. 3. Minimum spanning tree (MST) In this part of the project, we will extract the MST of the correlation graph and interpret it. QUESTION 3: Extract the MST of the correlation graph. Each stock can be categorized into a sector, which can be found in Name sector.csv file. Plot the MST and color-code the nodes based on sectors. Do you see any pattern in the MST? The structures that you find in MST are called Vine clusters. Provide a detailed explanation about the pattern you observe. QUESTION 4: Run a community detection algorithm (for example walktrap) on the MST obtained above. Plot the communities formed. Compute the homogeneity and completeness of the clustering. (you can use the ’clevr’ library in r to compute homogeneity and completeness). 4. Sector clustering in MST’s In this part, we want to predict the market sector of an unknown stock. We will explore two methods for performing the task. In order to evaluate the performance of the methods we define the following metric α = 1 |V | X vi∈V P(vi ∈ Si) 2 where Si is the sector of node i. Define P(vi ∈ Si) = |Qi | |Ni | where Qi is the set of neighbors of node i that belong to the same sector as node i and Ni is the set of neighbors of node i. Compare α with the case where P(vi ∈ Si) = |Si | |V | QUESTION 5: Report the value of α for the above two cases and provide an interpretation for the difference. 5. Correlation graphs for weekly data In the previous parts, we constructed the correlation graph based on daily data. In this part of the project, we will construct a correlation graph based on WEEKLY data. To create the graph, sample the stock data weekly on Mondays and then calculate ρij using the sampled data. If there is a holiday on a Monday, we ignore that week. Create the correlation graph based on weekly data. QUESTION 6: Repeat questions 2,3,4,5 on the WEEKLY data. 6. Correlation graphs for MONTHLY data In this part of the project, we will construct a correlation graph based on MONTHLY data. To create the graph, sample the stock data Monthly on 15th and then calculate ρij using the sampled data. If there is a holiday on the 15th, we ignore that month. Create the correlation graph based on MONTHLY data. QUESTION 7: Repeat questions 2,3,4,5 on the MONTHLY data. QUESTION 8: Compare and analyze all the results of daily data vs weekly data vs monthly data. What trends do you find? What changes? What remains similar? Give reason for your observations. Which granularity gives the best results when predicting the sector of an unknown stock and why? 2. Let’s Help Santa! Companies like Google and Uber have a vast amount of statistics about transportation dynamics. Santa has decided to use network theory to facilitate his gift delivery for the next Christmas. When we learned about his decision, we designed this part of the project to help him. We will send him your results for this part! 1. Download the Data Normally we use the last winter data but this year the latest available data is Winter 2019. Go to “Uber Movement” website and download data of Travel Times by Month (All Days), 3 2019 Quarter 4, for Los Angeles area1 . The dataset contains pairwise traveling time statistics between most pairs of points in the Los Angeles area. Points on the map are represented by unique IDs. To understand the correspondence between map IDs and areas, download Geo Boundaries file from the same website2 . This file contains latitudes and longitudes of the corners of the polygons circumscribing each area. To be specific, if an area is represented by a polygon with 5 corners, then you have a 5 × 2 matrix of the latitudes and longitudes, each row of which represents latitude and longitude of one corner. We recommend doing this part of the project (Q9 – Q18) in Python. 2. Build Your Graph Read the dataset at hand, and build a graph in which nodes correspond to locations, and undirected weighted edges correspond to the mean traveling times between each pair of locations (only December). Add the centroid coordinates of each polygon region (a 2-D vector) as an attribute to the corresponding vertex. The graph will contain some isolated nodes (extra nodes existing in the Geo Boundaries JSON file) and a few small connected components. Remove such nodes and just keep the largest connected component of the graph. In addition, merge duplicate edges by averaging their weights 3 . We will refer to this cleaned graph as G afterwards. QUESTION 9: Report the number of nodes and edges in G. 3. Traveling Salesman Problem QUESTION 10: Build a minimum spanning tree (MST) of graph G. Report the street addresses near the two endpoints (the centroid locations) of a few edges. Are the results intuitive? QUESTION 11: Determine what percentage of triangles in the graph (sets of 3 points on the map) satisfy the triangle inequality. You do not need to inspect all triangles, you can just estimate by random sampling of 1000 triangles. Now, we want to find an approximation solution for the traveling salesman problem (TSP) on G. Apply the 1-approximate algorithm described in the class4 . Inspect the sequence of street addresses visited on the map and see if the results are intuitive. QUESTION 12: Find an upper bound on the empirical performance of the approximate algorithm: ρ = Approximate TSP Cost Optimal TSP Cost QUESTION 13: Plot the trajectory that Santa has to travel! 1 If you download the dataset correctly, it should be named as los angeles-censustracts-2019-4-All-MonthlyAggregate.csv 2The file should be named los angeles censustracts.json 3Duplicate edges may exist when the dataset provides you with the statistic of a road in both directions. We remove duplicate edges for the sake of simplicity. 4You can find the algorithm in: Papadimitriou and Steiglitz, “Combinatorial optimization: algorithms and complexity”, Chapter 17, page 414 4 4. Analysing Traffic Flow Next December, there is going to be a large group of visitors travelling between a location near Malibu to a location near Long Beach. We would like to analyse the maximum traffic that can flow between the two locations. 5. Estimate the Roads We want to estimate the map of roads without using actual road datasets. Educate yourself about Delaunay triangulation algorithm and then apply it to the nodes coordinates5 . QUESTION 14: Plot the road mesh that you obtain and explain the result. Create a graph G∆ whose nodes are different locations and its edges are produced by triangulation. 6. Calculate Road Traffic Flows QUESTION 15: Using simple math, calculate the traffic flow for each road in terms of cars/hour. Report your derivation. Hint: Consider the following assumptions: • Each degree of latitude and longitude ≈ 69 miles • Car length ≈ 5 m = 0.003 mile • Cars maintain a safety distance of 2 seconds to the next car • Each road has 2 lanes in each direction Assuming no traffic jam, consider the calculated traffic flow as the max capacity of each road. 7. Calculate Max Flow Consider the following locations in terms of latitude and longitude: • Source coordinates (in Malibu): [34.04, -118.56] • Destination coordinates (in Long Beach): [33.77, -118.18] QUESTION 16: Calculate the maximum number of cars that can commute per hour from Malibu to Long Beach. Also calculate the number of edge-disjoint paths between the two spots. Does the number of edge-disjoint paths match what you see on your road map? 5You can use scipy.spatial.Delaunay in Python, or RTriangle package in R. 5 8. Prune Your Graph In G∆, there are a number of unreal roads that could be removed. For instance, you might notice some unreal links along the concavities of the beach, as well as in the hills of Topanga. Apply a threshold on the travel time of the roads in G∆ to remove the fake edges. Call the resulting graph G˜∆. QUESTION 17: Plot G˜∆ on actual coordinates. Do you think the thresholding method worked? QUESTION 18: Now, repeat question 13 for G˜∆ and report the results. Do you see any changes? Why? Submission Please submit your report to Gradescope. In addition, please submit a zip file containing your codes and report to BruinLearn. The zip file should be named as “Project4 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. If you have any questions you can post on piazza.
5/5 - (1 vote)
Problem 1: Problem 7.4 in R1 (Proakis 4th Edition)Problem 2: Problem 7.8 in R1Problem 3: Problem 7.9 in R1Problem 4: Problem 8.13 in R1Problem 5: Problem 8.17 in R1Problem 6: Problem 3.2 ((b) and (h) only) in R1Problem 7: Problem 3.4 ((b) only) in R1Problem 8: Problem 3.8 in R1Problem 9: Problem 3.9 in R1
Problem 1: Problem 3.14 ((d) and (g) only) in R1 (Proakis 4th Edition)Problem 2: Problem 3.16 ((d) only) in R1Problem 3: Problem 3.18 ((d) only) in R1Problem 4: Problem 3.32 in R1Problem 5: Problem 3.35 ((c) and (g) only) in R1 (Hint: In Part (c), a “,” is obviously missing between x(n-1) and x(n). For Part (g), note that x(n) does not have a Z-transform and you should instead use the fundamental property of Transfer Functions relating to how an LTI system responds to a sinusoidal sequence)Problem 6: Problem 3.38 ((b) only) in R1Problem 7: Problem 3.40 in R1Problem 8: Problem 3.42 in R1Problem 9: Problem 3.51 in R1Problem 10: Problem 5.20 in R1
Problem 1: Problem 4.3 in R1 (Proakis 4th Edition)Problem 2: Problem 4.6 (Part (b) only) in R1Problem 3: Problem 4.7 (Part (a) only) in R1Problem 4: Problem 4.9 (Part (d) only) in R1Problem 5: Problem 4.10 (Parts (c) and (d) only) in R1Problem 6: Problem 7.18 in R1Problem 7: Problem 7.23 (Part (h) only, assume N odd) in R1
Problem 1: Problem 6.4 in R1 (i.e., Proakis 4th Edition) (Note: To obtain the Fourier Transform of x(n)=x0(nT)x(n)=x0(nT) in this problem, recall the “differentiation in the frequency domain” property of FT, i.e., nx(n)↔jdX(f)2πdfnx(n)↔j2πdfdX(f))
Problem 1: Problem 2.24 in R1 (i.e., Proakis 4th Edition)Problem 2: Problem 2.32 in R1Problem 3: Problem 2.35 in R1Problem 4: Problem 2.57 in R1Problem 5: Problem 5.5 in R1Problem 6: Problem 5.24 in R1Problem 7: Problem 9.5 in R1 (In this problem, “transposed structure” refers to transposed Direct Form II).Problem 8: Problem 9.9 in R1 (Find Direct Form I, Direct Form II, and Cascade realization for Part b only. Parallel realization optional).
1.1 Classify the following signals according to whether they are (1) one- or multi-dimensional; (2) single or multichannel, (3) continuous time or discrete time, and (4) analog or digital (in amplitude). Give a brief explanation. (a) Closing prices of utility stocks on the New York Stock Exchange. (b) A color movie. (c) Position of the steering wheel of a car in motion relative to car’s reference frame. (d) Position of the steering wheel of a car in motion relative to ground reference frame. (e) Weight and height measurements of a child taken every month.
1. 1-point Extra Credit on your total score Please answer the following two questions before you submit your solutions. (a) Did you fill out the online survey? Yes, or No? (b) Approximately how many hours did you have to spend on this exam? Please try to exclude all the extra time you may spend on reviewing the lecture notes again during the exam period, or on double or triple checking your solutions again etc., and try to include the actual number of hours you think you would have to spend if, say, this were an in-person closed-book exam. 2. (10 points) Quick Review Carefully read each statement below and identify it as True or False, and briefly explain your reason in one or two sentences. 1. An anti-causal LTI system (i.e., h(n) = 0, for n ≥ 0) will be BIBO stable as long as all its poles reside inside the unit circle. True or False? Why? 2. Rational, causal, and stable all-pass filters are always non-minimum-phase systems. True or False? Why? 3. For the same filter specifications, Chebyshev IIR filters will typically lead to a lower order filter than Butterworth filters. True or False? Why? 4. Digitizing a stable analog filter using either the Impulse Invariance method or the Bilinear transformation will always lead to a stable IIR filter. True or False? Why? 5. In window-based FIR design, using a Hann window will result in a larger bandwidth for the filter transition band, when compared with a Blackman window. True or False? Why? 6. In window-based FIR design, when using a rectangular window, increasing the order of the filter will lead to increased attenuation in the filter stopband. True or False? Why? 7. Assuming N even, any real-valued finite sequence of length M ≤ N can be uniquely represented by the first N 2 + 1 samples of its N-point DFT. True or False? Why? 8. The magnitude response and the phase response of a causal filter can be designed independently. True or False? Why? 9. Any symmetric or anti-symmetric FIR filter will always have a constant group delay. True or False? Why? 10. A causal, stable, and rational IIR filter can have linear phase response as long as its impulse response is symmetric or anti-symmetric. True or False? Why?3. (18 points) LCCDE, Transfer Function, LTI System Response: Consider the LTI system shown in Figure 1 below. Figure 1: LTI System Given the following input sequence: x(n) = (1 2 ) nu(n) + 2nu(−n − 1) we have obtained the zero-state output sequence as: y(n) = 6(1 2 ) nu(n) − 6(3 4 ) nu(n) where u(n) is the unit step sequence. (a) (1 point) Obtain X(z) = Z{x(n)} and determine its Region of Convergence (ROC). (b) (2 points) Find the system Transfer Function H(z) and determine its Region of Convergence (ROC). (c) (1 point) Find the system Impulse Response h(n). (d) (2 points) Is this system BIBO stable? Is it causal? Is it minimum-phase? Please explain all your answers. (e) (2 points) Obtain the Linear Constant Coefficient Difference Equation (LCCDE) describing the time-domain input-output relationship for this system. (f) (5 points) Now, suppose the system has an initial condition y(−1) = 4 and we have applied the following input sequence: x(n) = n( 1 2 ) nu(n) Using unilateral Z-transform, obtain the system response y(n), n ≥ 0. Specifically, please identify the zero-state response yzs(n), and the zero-input response yzi(n) for this system. (Note: For Partial Fraction Expansion, you must write how you obtain the residues, even if you choose to check your result with MATLAB). (g) (2 points) In the response you obtained in Part (f), identify the forced response as well as the natural response. Moreover, identify the separate contributions of the initial condition and the input signal on the system natural response. (h) (3 points) Obtain the steady-state response of this system to the following input signal: x(n) = 1 4 + 7(−1)n + 5 sin(π 4 n + π 3 )4. (10 points) Frequency Domain Analysis: DFS, DFT, Frequency Response: Consider an ideal LTI lowpass filter with the following frequency response: H(ω) = 1 for |ω|
Introduction In this project we will explore graph theory theorems and algorithms, by applying them on real data. In the first part of the project, we consider a particular graph modeling correlations between stock price time series. In the second part, we analyse traffic data on a dataset provided by Uber. 1. Stock Market In this part of the project, we study data from stock market. The data is available on this Dropbox Link. The goal of this part is to study correlation structures among fluctuation patterns of stock prices using tools from graph theory. The intuition is that investors will have similar strategies of investment for stocks that are effected by the same economic factors. For example, the stocks belonging to the transportation sector may have different absolute prices, but if for example fuel prices change or are expected to change significantly in the near future, then you would expect the investors to buy or sell all stocks similarly and maximize their returns. Towards that goal, we construct different graphs based on similarities among the time series of returns on different stocks at different time scales (day vs a week). Then, we study properties of such graphs. The data is obtained from Yahoo Finance website for 3 years. You’re provided with a number of csv tables, each containing several fields: Date, Open, High, Low, Close, Volume, and Adj Close price. The files are named according to Ticker Symbol of each stock. You may find the market sector for each company in Name sector.csv. We recommend doing this part of the project (Q1 – Q8) in R. 1. Return correlation In this part of the project, we will compute the correlation among log-normalized stock-return time series data. Before giving the expression for correlation, we introduce the following notation: • pi(t) is the closing price of stock i at the t th day • qi(t) is the return of stock i over a period of [t − 1, t] qi(t) = pi(t) − pi(t − 1) pi(t − 1) 1 • ri(t) is the log-normalized return stock i over a period of [t − 1, t] ri(t) = log(1 + qi(t)) Then with the above notation, we define the correlation between the log-normalized stock-return time series data of stocks i and j as ρij = ⟨ri(t)rj (t)⟩ − ⟨ri(t)⟩⟨rj (t)⟩ p (⟨ri(t) 2⟩ − ⟨ri(t)⟩ 2 )(⟨rj (t) 2⟩ − ⟨rj (t)⟩ 2 ) where ⟨·⟩ is a temporal average on the investigated time regime (for our data set it is over 3 years). QUESTION 1: What are upper and lower bounds on ρij? Provide a justification for using lognormalized return (ri(t)) instead of regular return (qi(t)). 2. Constructing correlation graphs In this part,we construct a correlation graph using the correlation coefficient computed in the previous section. The correlation graph has the stocks as the nodes and the edge weights are given by the following expression wij = q 2(1 − ρij ) Compute the edge weights using the above expression and construct the correlation graph. QUESTION 2: Plot a histogram showing the un-normalized distribution of edge weights. 3. Minimum spanning tree (MST) In this part of the project, we will extract the MST of the correlation graph and interpret it. QUESTION 3: Extract the MST of the correlation graph. Each stock can be categorized into a sector, which can be found in Name sector.csv file. Plot the MST and color-code the nodes based on sectors. Do you see any pattern in the MST? The structures that you find in MST are called Vine clusters. Provide a detailed explanation about the pattern you observe. QUESTION 4: Run a community detection algorithm (for example walktrap) on the MST obtained above. Plot the communities formed. Compute the homogeneity and completeness of the clustering. (you can use the ’clevr’ library in r to compute homogeneity and completeness). 4. Sector clustering in MST’s In this part, we want to predict the market sector of an unknown stock. We will explore two methods for performing the task. In order to evaluate the performance of the methods we define the following metric α = 1 |V | X vi∈V P(vi ∈ Si) 2 where Si is the sector of node i. Define P(vi ∈ Si) = |Qi | |Ni | where Qi is the set of neighbors of node i that belong to the same sector as node i and Ni is the set of neighbors of node i. Compare α with the case where P(vi ∈ Si) = |Si | |V | QUESTION 5: Report the value of α for the above two cases and provide an interpretation for the difference. 5. Correlation graphs for weekly data In the previous parts, we constructed the correlation graph based on daily data. In this part of the project, we will construct a correlation graph based on WEEKLY data. To create the graph, sample the stock data weekly on Mondays and then calculate ρij using the sampled data. If there is a holiday on a Monday, we ignore that week. Create the correlation graph based on weekly data. QUESTION 6: Repeat questions 2,3,4,5 on the WEEKLY data. 6. Correlation graphs for MONTHLY data In this part of the project, we will construct a correlation graph based on MONTHLY data. To create the graph, sample the stock data Monthly on 15th and then calculate ρij using the sampled data. If there is a holiday on the 15th, we ignore that month. Create the correlation graph based on MONTHLY data. QUESTION 7: Repeat questions 2,3,4,5 on the MONTHLY data. QUESTION 8: Compare and analyze all the results of daily data vs weekly data vs monthly data. What trends do you find? What changes? What remains similar? Give reason for your observations. Which granularity gives the best results when predicting the sector of an unknown stock and why? 2. Let’s Help Santa! Companies like Google and Uber have a vast amount of statistics about transportation dynamics. Santa has decided to use network theory to facilitate his gift delivery for the next Christmas. When we learned about his decision, we designed this part of the project to help him. We will send him your results for this part! 1. Download the Data Normally we use the last winter data but this year the latest available data is Winter 2019. Go to “Uber Movement” website and download data of Travel Times by Month (All Days), 3 2019 Quarter 4, for Los Angeles area1 . The dataset contains pairwise traveling time statistics between most pairs of points in the Los Angeles area. Points on the map are represented by unique IDs. To understand the correspondence between map IDs and areas, download Geo Boundaries file from the same website2 . This file contains latitudes and longitudes of the corners of the polygons circumscribing each area. To be specific, if an area is represented by a polygon with 5 corners, then you have a 5 × 2 matrix of the latitudes and longitudes, each row of which represents latitude and longitude of one corner. We recommend doing this part of the project (Q9 – Q18) in Python. 2. Build Your Graph Read the dataset at hand, and build a graph in which nodes correspond to locations, and undirected weighted edges correspond to the mean traveling times between each pair of locations (only December). Add the centroid coordinates of each polygon region (a 2-D vector) as an attribute to the corresponding vertex. The graph will contain some isolated nodes (extra nodes existing in the Geo Boundaries JSON file) and a few small connected components. Remove such nodes and just keep the largest connected component of the graph. In addition, merge duplicate edges by averaging their weights 3 . We will refer to this cleaned graph as G afterwards. QUESTION 9: Report the number of nodes and edges in G. 3. Traveling Salesman Problem QUESTION 10: Build a minimum spanning tree (MST) of graph G. Report the street addresses near the two endpoints (the centroid locations) of a few edges. Are the results intuitive? QUESTION 11: Determine what percentage of triangles in the graph (sets of 3 points on the map) satisfy the triangle inequality. You do not need to inspect all triangles, you can just estimate by random sampling of 1000 triangles. Now, we want to find an approximation solution for the traveling salesman problem (TSP) on G. Apply the 1-approximate algorithm described in the class4 . Inspect the sequence of street addresses visited on the map and see if the results are intuitive. QUESTION 12: Find an upper bound on the empirical performance of the approximate algorithm: ρ = Approximate TSP Cost Optimal TSP Cost QUESTION 13: Plot the trajectory that Santa has to travel! 1 If you download the dataset correctly, it should be named as los angeles-censustracts-2019-4-All-MonthlyAggregate.csv 2The file should be named los angeles censustracts.json 3Duplicate edges may exist when the dataset provides you with the statistic of a road in both directions. We remove duplicate edges for the sake of simplicity. 4You can find the algorithm in: Papadimitriou and Steiglitz, “Combinatorial optimization: algorithms and complexity”, Chapter 17, page 414 4 4. Analysing Traffic Flow Next December, there is going to be a large group of visitors travelling between a location near Malibu to a location near Long Beach. We would like to analyse the maximum traffic that can flow between the two locations. 5. Estimate the Roads We want to estimate the map of roads without using actual road datasets. Educate yourself about Delaunay triangulation algorithm and then apply it to the nodes coordinates5 . QUESTION 14: Plot the road mesh that you obtain and explain the result. Create a graph G∆ whose nodes are different locations and its edges are produced by triangulation. 6. Calculate Road Traffic Flows QUESTION 15: Using simple math, calculate the traffic flow for each road in terms of cars/hour. Report your derivation. Hint: Consider the following assumptions: • Each degree of latitude and longitude ≈ 69 miles • Car length ≈ 5 m = 0.003 mile • Cars maintain a safety distance of 2 seconds to the next car • Each road has 2 lanes in each direction Assuming no traffic jam, consider the calculated traffic flow as the max capacity of each road. 7. Calculate Max Flow Consider the following locations in terms of latitude and longitude: • Source coordinates (in Malibu): [34.04, -118.56] • Destination coordinates (in Long Beach): [33.77, -118.18] QUESTION 16: Calculate the maximum number of cars that can commute per hour from Malibu to Long Beach. Also calculate the number of edge-disjoint paths between the two spots. Does the number of edge-disjoint paths match what you see on your road map? 5You can use scipy.spatial.Delaunay in Python, or RTriangle package in R. 5 8. Prune Your Graph In G∆, there are a number of unreal roads that could be removed. For instance, you might notice some unreal links along the concavities of the beach, as well as in the hills of Topanga. Apply a threshold on the travel time of the roads in G∆ to remove the fake edges. Call the resulting graph G˜∆. QUESTION 17: Plot G˜∆ on actual coordinates. Do you think the thresholding method worked? QUESTION 18: Now, repeat question 13 for G˜∆ and report the results. Do you see any changes? Why? Submission Please submit your report to Gradescope. In addition, please submit a zip file containing your codes and report to BruinLearn. The zip file should be named as “Project4 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. If you have any questions you can post on piazza.
1. Generating Random Networks 1. Create random networks using Erd¨os-R´enyi (ER) model (a) Create undirected random networks with n = 900 nodes, and the probability p for drawing an edge between two arbitrary vertices 0.002, 0.006, 0.012, 0.045, and 0.1. Plot the degree distributions. What distribution (linear/exponential/gaussian/binomial or something else) is observed? Explain why. Also, report the mean and variance of the degree distributions and compare them to the theoretical values. Hint Useful function(s): samplegnp (erdos.renyi.game) , degree , degreedistribution , plot (b) For each p and n = 900, answer the following questions: Are all random realizations of the ER network connected? Numerically estimate the probability that a generated network is connected. For one instance of the networks with that p, find the giant connected component (GCC) if not connected. What is the diameter of the GCC? Hint Useful function(s): isconnected , clusters , diameter (c) It turns out that the normalized GCC size (i.e., the size of the GCC as a fraction of the total network size) is a highly nonlinear function of p, with interesting properties occurring for values where p = O( 1 n ) and p = O( ln n n ). For n = 900, sweep over values of p from 0 to a pmax that makes the network almost surely connected and create 100 random networks for each p. pmax should be roughly determined by yourself. Then scatter plot the normalized GCC sizes vs p. Plot a line of the average normalized GCC sizes for each p along with the scatter plot. i. Empirically estimate the value of p where a giant connected component starts to emerge (define your criterion of “emergence”)? Do they match with theoretical values mentioned or derived in lectures? ii. Empirically estimate the value of p where the giant connected component takes up over 99% of the nodes in almost every experiment. (d) i. Define the average degree of nodes c = n × p = 0.5. Sweep over the number of nodes, n, ranging from 100 to 10000. Plot the expected size of the GCC of ER networks with n nodes and edge-formation probabilities p = c/n, as a function of n. What trend is observed? ii. Repeat the same for c = 1. iii. Repeat the same for values of c = 1.15, 1.25, 1.35, and show the results for these three values in a single plot. iv. What is the relation between the expected GCC size and n in each case? 2. Create networks using preferential attachment model (a) Create an undirected network with n = 1050 nodes, with preferential attachment model, where each new node attaches to m = 1 old nodes. Is such a network always connected? Hint Useful function(s): samplepa (barabasi.game) (b) Use fast greedy method to find the community structure. Measure modularity. Define Assortativity. Compute Assortativity. Hint Useful function(s): clusterfastgreedy , modularity (c) Try to generate a larger network with 10500 nodes using the same model. Compute modularity and assortativity. How is it compared to the smaller network’s modularity? 2 (d) Plot the degree distribution in a log-log scale for both n = 1050, 10500, then estimate the slope of the plot using linear regression. (e) In the two networks generated in 2(a) and 2(c), perform the following: Randomly pick a node i, and then randomly pick a neighbor j of that node. Plot the degree distribution of nodes j that are picked with this process, in the log-log scale. Is the distribution linear in the log-log scale? If so, what is the slope? How does this differ from the node degree distribution? Hint Useful function(s): sample (f) Estimate the expected degree of a node that is added at time step i for 1 ≤ i ≤ 1050. Show the relationship between the age of nodes and their expected degree through an appropriate plot. Note that the newest added node is the youngest. (g) Repeat the previous parts (a-f) for m = 2, and m = 6. Compare the results of each part for different values of m. (h) Again, generate a preferential attachment network with n = 1050, m = 1. Take its degree sequence and create a new network with the same degree sequence, through stub-matching procedure. Plot both networks, mark communities on their plots, and measure their modularity. Compare the two procedures for creating random power-law networks. Hint In case that fastgreedy community detection fails because of self-loops, you may use “walktrap” community detection. Useful function(s): sampledegseq 3. Create a modified preferential attachment model that penalizes the age of a node (a) Each time a new vertex is added, it creates m links to old vertices and the probability that an old vertex is cited depends on its degree (preferential attachment) and age. In particular, the probability that a newly added vertex connects to an old vertex is proportional to: P[i] ∼ (ckα i + a)(dlβ i + b), where ki is the degree of vertex i in the current time step, and li is the age of vertex i. Produce such an undirected network with 1050 nodes and parameters m = 1, α = 1, β = −1, and a = c = d = 1, b = 0. Plot the degree distribution. What is the power law exponent? Hint Useful function(s): samplepaage (b) Use fast greedy method to find the community structure. What is the modularity? 3 2. Random Walk on Networks 1. Random walk on Erd¨os-R´enyi networks (a) Create an undirected random network with 900 nodes, and the probability p for drawing an edge between any pair of nodes equal to 0.015. (b) Let a random walker start from a randomly selected node (no teleportation). We use t to denote the number of steps that the walker has taken. Measure the average distance (defined as the shortest path length) ⟨s(t)⟩ of the walker from his starting point at step t. Also, measure the variance σ 2 (t) = ⟨(s(t) − ⟨s(t)⟩) 2 ⟩ of this distance. Plot ⟨s(t)⟩ v.s. t and σ 2 (t) v.s. t. Here, the average ⟨·⟩ is over random choices of the starting nodes. (c) Measure the degree distribution of the nodes reached at the end of the random walk. How does it compare to the degree distribution of graph? (d) Repeat 1(b) for undirected random networks with 9000 nodes. Compare the results and explain qualitatively. Does the diameter of the network play a role? 2. Random walk on networks with fat-tailed degree distribution (a) Generate an undirected preferential attachment network with 900 nodes, where each new node attaches to m = 1 old nodes. (b) Let a random walker start from a randomly selected node. Measure and plot ⟨s(t)⟩ v.s. t and σ 2 (t) v.s. t. (c) Measure the degree distribution of the nodes reached at the end of the random walk on this network. How does it compare with the degree distribution of the graph? (d) Repeat 2(b) for preferential attachment networks with 90 and 9000 nodes, and m = 1. Compare the results and explain qualitatively. Does the diameter of the network play a role? 3. PageRank The PageRank algorithm, as used by the Google search engine, exploits the linkage structure of the web to compute global “importance” scores that can be used to influence the ranking of search results. Here, we use random walk to simulate PageRank. (a) We are going to create a directed random network with 900 nodes, using the preferential attachment model. Note that in a directed preferential attachment network, the out-degree of every node is m, while the in-degrees follow a power law distribution. One problem of performing random walk in such a network is that, the very first node will have no outbounding edges, and be a “black hole” which a random walker can never “escape” from. To address that, let’s generate another 900-node random network with preferential attachment model, and merge the two networks by adding the edges of the second graph to the first graph with a shuffling of the indices of the nodes. For example, 1 → 2 2 → 3 3 → 4 Initial edge list of the second network 4 → 3 3 → 1 1 → 2 Edge list after node idx shuffling (the edges that should be added to the first network) shuffled to 1,2,3,4 4,3,1,2 4 Create such a network using m = 4. Measure the probability that the walker visits each node. Is this probability related to the degree of the nodes? Hint Useful function(s): asedgelist , sample , permute , addedges (b) In all previous questions, we didn’t have any teleportation. Now, we use a teleportation probability of α = 0.2 (teleport out of a node with prob=0.2 instead of going to its neighbor). By performing random walks on the network created in 3(a), measure the probability that the walker visits each node. How is this probability related to the degree of the node and α ? 4. Personalized PageRank While the use of PageRank has proven very effective, the web’s rapid growth in size and diversity drives an increasing demand for greater flexibility in ranking. Ideally, each user should be able to define their own notion of importance for each individual query. (a) Suppose you have your own notion of importance. Your interest in a node is proportional to the node’s PageRank, because you totally rely upon Google to decide which website to visit (assume that these nodes represent websites). Again, use random walk on network generated in question 3 to simulate this personalized PageRank. Here the teleportation probability to each node is proportional to its PageRank (as opposed to the regular PageRank, where at teleportation, the chance of visiting all nodes are the same and equal to 1 N ). Again, let the teleportation probability be equal to α = 0.2. Compare the results with 3(a). (b) Find two nodes in the network with median PageRanks. Repeat part 4(a) if teleportations land only on those two nodes (with probabilities 1/2, 1/2). How are the PageRank values affected? (c) More or less, 4(b) is what happens in the real world, in that a user browsing the web only teleports to a set of trusted web pages. However, this is against the assumption of normal PageRank, where we assume that people’s interest in all nodes are the same. Can you take into account the effect of this self-reinforcement and adjust the PageRank equation? 5 Final Remarks The following functions from igraph library are useful for this project: • degree, degree.distribution, diameter, clusters, vcount, ecount • random.graph.game, barabasi.game, aging.prefatt.game, degree.sequence.game • page rank For part 2 of the project, you can start off with the Jupyter notebook provided to you.
In this project, we will study the various properties of social networks. In the first part of the project, we will study an undirected social network (Facebook). In the second part of the project, we will study a directed social network (Google +). You can complete the Project using R or Python. 1. Facebook network In this project, we will be using the dataset given below: http://snap.stanford.edu/data/egonets-Facebook.html The Facebook network can be created from the edgelist file (facebook combined.txt) 1. Structural properties of the Facebook network Having created the Facebook network, we will study some of the structural properties of the network. To be specific, we will study • Connectivity • Degree distribution QUESTION 1: A first look at the network: QUESTION 1.1: Report the number of nodes and number of edges of the Facebook network. QUESTION 1.2: Is the Facebook network connected? If not, find the giant connected component (GCC) of the network and report the size of the GCC. QUESTION 2: Find the diameter of the network. If the network is not connected, then find the diameter of the GCC. QUESTION 3: Plot the degree distribution of the facebook network and report the average degree. QUESTION 4: Plot the degree distribution of Question 3 in a log-log scale. Try to fit a line to the plot and estimate the slope of the line. 1 2. Personalized network A personalized network of an user vi is defined as the subgraph induced by vi and it’s neighbors. In this part, we will study some of the structural properties of the personalized network of the user whose graph node ID is 1 (node ID in edgelist is 0). From this point onwards, whenever we are refering to a node ID we mean the graph node ID which is 1 + node ID in edgelist. QUESTION 5: Create a personalized network of the user whose ID is 1. How many nodes and edges does this personalized network have? Hint Useful function(s): makeegograph QUESTION 6: What is the diameter of the personalized network? Please state a trivial upper and lower bound for the diameter of the personalized network. QUESTION 7: In the context of the personalized network, what is the meaning of the diameter of the personalized network to be equal to the upper bound you derived in Question 6. What is the meaning of the diameter of the personalized network to be equal to the lower bound you derived in Question 6 (assuming there are more than 3 nodes in the personalized network)? 3. Core node’s personalized network A core node is defined as the nodes that have more than 200 neighbors. For visualization purpose, we have displayed the personalized network of a core node below. An example of a personal network. The core node is shown in black. In this part, we will study various properties of the personalized network of the core nodes. QUESTION 8: How many core nodes are there in the Facebook network. What is the average degree of the core nodes? 3.1. Community structure of core node’s personalized network In this part, we study the community structure of the core node’s personalized network. To be specific, we will study the community structure of the personalized network of the following core nodes: 2 • Node ID 1 • Node ID 108 • Node ID 349 • Node ID 484 • Node ID 1087 QUESTION 9: For each of the above core node’s personalized network, find the community structure using Fast-Greedy, Edge-Betweenness, and Infomap community detection algorithms. Compare the modularity scores of the algorithms. For visualization purpose, display the community structure of the core node’s personalized networks using colors. Nodes belonging to the same community should have the same color and nodes belonging to different communities should have different color. In this question, you should have 15 plots in total. Hint Useful function(s): clusterfastgreedy , clusteredgebetweenness , clusterinfomap 3.2. Community structure with the core node removed In this part, we will explore the effect on the community structure of a core node’s personalized network when the core node itself is removed from the personalized network. QUESTION 10: For each of the core node’s personalized network (use same core nodes as Question 9), remove the core node from the personalized network and find the community structure of the modified personalized network. Use the same community detection algorithm as Question 9. Compare the modularity score of the community structure of the modified personalized network with the modularity score of the community structure of the personalized network of Question 9. For visualization purpose, display the community structure of the modified personalized network using colors. In this question, you should have 15 plots in total. 3.3. Characteristic of nodes in the personalized network In this part, we will explore characteristics of nodes in the personalized network using two measures. These two measures are stated and defined below: • Embeddedness of a node is defined as the number of mutual friends a node shares with the core node. • Dispersion of a node is defined as the sum of distances between every pair of the mutual friends the node shares with the core node. The distances should be calculated in a modified graph where the node (whose dispersion is being computed) and the core node are removed. For further details on the above characteristics, you can read the paper below: http://arxiv.org/abs/1310.6753 QUESTION 11: Write an expression relating the Embeddedness between the core node and a non-core node to the degree of the non-core node in the personalized network of the core node. 3 QUESTION 12: For each of the core node’s personalized network (use the same core nodes as Question 9), plot the distribution histogram of embeddedness and dispersion. In this question, you will have 10 plots. Hint Useful function(s): neighbors , intersection , distances QUESTION 13: For each of the core node’s personalized network, plot the community structure of the personalized network using colors and highlight the node with maximum dispersion. Also, highlight the edges incident to this node. To detect the community structure, use Fast-Greedy algorithm. In this question, you will have 5 plots. QUESTION 14: Repeat Question 13, but now highlight the node with maximum embeddedness and the node with maximum dispersion embeddedness (excluding the nodes having zero embeddedness if there are any). Also, highlight the edges incident to these nodes. Report the id of those nodes. QUESTION 15: Use the plots from Question 13 and 14 to explain the characteristics of a node revealed by each of this measure. 4. Friend recommendation in personalized networks In many social networks, it is desirable to predict future links between pairs of nodes in the network. In the context of this Facebook network it is equivalent to recommending friends to users. In this part of the project, we will explore some neighborhood-based measures for friend recommendation. The network that we will be using for this part is the personalized network of node with ID 415. 4.1. Neighborhood based measure In this project, we will be exploring three different neighborhood-based measures. Before we define these measures, let’s introduce some notation: • Si is the neighbor set of node i in the network • Sj is the neighbor set of node j in the network Then, with the above notation we define the three measures below: • Common neighbor measure between node i and node j is defined as Common Neighbors(i, j) = |Si ∩ Sj | • Jaccard measure between node i and node j is defined as Jaccard(i, j) = |Si ∩ Sj | |Si ∪ Sj | • Adamic-Adar measure between node i and node j is defined as Adamic Adar(i, j) = X k∈Si∩Sj 1 log(|Sk|) 4 4.2. Friend recommendation using neighborhood based measures We can use the neighborhood based measures defined in the previous section to recommend new friends to users in the network. Suppose we want to recommend t new friends to some user i in the network using Jaccard measure. We follow the steps listed below: 1. For each node in the network that is not a neighbor of i, compute the jaccard measure between the node i and the node not in the neighborhood of i Compute Jaccard(i, j) ∀j ∈ S C i 2. Then pick t nodes that have the highest Jaccard measure with node i and recommend these nodes as friends to node i 4.3. Creating the list of users Having defined the friend recommendation procedure, we can now apply it to the personalized network of node ID 415. Before we apply the algorithm, we need to create the list of users who we want to recommend new friends to. We create this list by picking all nodes with degree 24. We will denote this list as Nr. QUESTION 16: What is |Nr|, i.e. the length of the list Nr? 4.4. Average accuracy of friend recommendation algorithm In this part, we will apply the 3 different types of friend recommendation algorithms to recommend friends to the users in the list Nr. We will define an average accuracy measure to compare the performances of the friend recommendation algorithms. Suppose we want to compute the average accuracy of the friend recommendation algorithm. This task is completed in two steps: 1. Compute the average accuracy for each user in the list Nr 2. Compute the average accuracy of the algorithm by averaging across the accuracies of the users in the list Nr Let’s describe the procedure for accomplishing the step 1 of the task. Suppose we want to compute the average accuracy for user i in the list Nr. We can compute it by iterating over the following steps 10 times and then taking the average: 1. Remove each edge of node i at random with probability 0.25. In this context, it is equivalent to deleting some friends of node i. Let’s denote the list of friends deleted as Ri 2. Use one of the three neighborhood based measures to recommend |Ri | new friends to the user i. Let’s denote the list of friends recommended as Pi 3. The accuracy for the user i for this iteration is given by |Pi∩Ri| |Ri| By iterating over the above steps for 10 times and then taking the average gives us the average accuracy of user i. In this manner, we compute the average accuracy for each user in the list 5 Nr. Once we have computed them, then we can take the mean of the average accuracies of the users in the list Nr. The mean value will be the average accuracy of the friend recommendation algorithm. QUESTION 17: Compute the average accuracy of the friend recommendation algorithm that uses: • Common Neighbors measure • Jaccard measure • Adamic Adar measure Based on the average accuracy values, which friend recommendation algorithm is the best? Hint Useful function(s): similarity 2. Google+ network In this part, we will explore the structure of the Google+ network. The dataset for creating the network can be found in the link below: http://snap.stanford.edu/data/egonets-Gplus.html Create directed personal networks for users who have more than 2 circles. The data required to create such personal networks can be found in the file named gplus.tar.gz. QUESTION 18: How many personal networks are there? QUESTION 19: For the 3 personal networks (node ID given below), plot the in-degree and outdegree distribution of these personal networks. Do the personal networks have a similar in and out degree distribution? In this question, you should have 6 plots. • 109327480479767108490 • 115625564993990145546 • 101373961279443806744 1. Community structure of personal networks In this part of the project, we will explore the community structure of the personal networks that we created and explore the connections between communities and user circles. QUESTION 20: For the 3 personal networks picked in Question 19, extract the community structure of each personal network using Walktrap community detection algorithm. Report the modularity scores and plot the communities using colors. Are the modularity scores similar? In this question, you should have 3 plots. Having found the communities, now we will explore the relationship between circles and communities. In order to explore the relationship, we define two measures: 6 • Homogeneity • Completeness Before, we state the expression for homogeneity and completeness, let’s introduce some notation: • C is the set of circles, C = {C1, C2, C3, · · · } • K is the set of communities, K = {K1, K2, K3, · · · } • ai is the number of people in circle Ci • bi is the number of people in community Ki with circle information • N is the total number of people with circle information • Aji is the number of people belonging to community j and circle i Then, with the above notation, we have the following expressions for the entropy H(C) = − X |C| i=1 ai N log( ai N ) (1) H(K) = − X |K| i=1 bi N log( bi N ) (2) and conditional entropy H(C|K) = − X |K| j=1 X |C| i=1 Aji N log(Aji bj ) (3) H(K|C) = − X |C| i=1 X |K| j=1 Aji N log(Aji ai ) (4) Now we can state the expression for homogeneity, h as h = 1 − H(C|K) H(C) (5) and the expression for completeness, c as c = 1 − H(K|C) H(K) (6) QUESTION 21: Based on the expression for h and c, explain the meaning of homogeneity and completeness in words. QUESTION 22: Compute the h and c values for the community structures of the 3 personal network (same nodes as Question 19). Interpret the values and provide a detailed explanation. Are there negative values? Why? 7 3. Cora dataset One of the well-known categories of machine learning problems is “supervised learning”. In supervised learning, we are given some information called “input” features about certain objects. For each object, we are also given an “output” or target variable that we are trying to predict about. Our goal is to learn the mapping between the features and the target variable. Typically, there is a portion of data where both input features and target variables are available. This portion of the dataset is called the training set. There is also typically another portion of the dataset where the target variable is missing and we want to predict it. This portion is called the “test set”. When the target variable can take on a finite number of discrete values, we call the problem at hand a “classification” problem. In this project, we are trying to solve a classification problem in settings where some additional information is provided in the form of “graph structure”. In this project we work with “Cora” dataset. Cora consists of a set of 2708 documents that are Machine Learning related papers. Each documents is labeled with one of the following seven classes: Case Based, Genetic Algorithms, Neural Networks, Probabilistic Methods, Reinforcement Learning, Rule Learning, Theory. For each class, only 20 documents are labeled (a total of 140 for the seven classes). We refer to them as “seed” documents. Each document comes with a set of features about its text content. These features are occurrences of a selection of 1433 words in the vocabulary. We are also given an undirected graph where each node is a document and each edge represents a citation. There are a total of 5429 edges. Our goal is to use the hints from text features as well as from graph connections to classify (assign labels to) these documents. To solve this problem for Cora dataset, we pursue three parallel ideas. Implement each idea and compare. QUESTION 23: Idea 1 Use Graph Convolutional Networks [1]. What hyperparameters do you choose to get the optimal performance? How many layers did you choose? QUESTION 24: Idea 2 Extract structure-based node features using Node2Vec [2]. Briefly describe how Node2Vec finds node features. Choose your desired classifier (one of SVM, Neural Network, or Random Forest) and classify the documents using only Node2Vec (graph structure) features. Now classify the documents using only the 1433-dimensional text features. Which one outperforms? Why do you think this is the case? Combine the Node2Vec and text features and train your classifier on the combined features. What is the best classification accuracy you get (in terms of the percentage of test documents correctly classified)? QUESTION 25: Idea 3 We can find the personalized PageRank of each document in seven different runs, one per class. In each run, select one of the classes and take the 20 seed documents of that class. Then, perform a random walk with the following customized properties: (a) teleportation takes the random walker to one of the seed documents of that class (with a uniform probability of 1/20 per seed document). Vary the teleportation probability in {0, 0.1, 0.2}. (b) the probability of transitioning to neighbors is not uniform among the neighbors. Rather, it is proportional to the cosine similarity between the text features of the current node and the next neighboring node. Particularly, assume we are currently visiting a document x0 which has neighbors x1, x2, x3. 8 Then the probability of transitioning to each neighbor is: pi = exp(x0 · xi) exp(x0 · x1) + exp(x0 · x2) + exp(x0 · x3) ; for i = 1, 2, 3. (7) Repeat part b for every teleportation probability in part a. Run the PageRank only on the GCC. for each seed node, do 1000 random walks. Maintain a class-wise visited frequency count for every unlabeled node. The predicted class for that unlabeled node is the class which lead to maximum visits to that node. Report accuracy and f1 scores. For example if node ’n’ was visited by 7 random walks from class A, 6 random walks from class B… 1 random walk from class G, then the predicted label of node of ’n’ is class A. Submission Please submit the report to Gradescope. Meanwhile, please submit a zip file containing your codes and report to BruinLearn. The zip file should be named as “Project2 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. If you have any questions please feel free to ask them over email or piazza. References [1] Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” arXiv preprint arXiv:1609.02907 (2016).
1 Introduction Reinforcement Learning (RL) is the task of learning from interaction to achieve a goal. The learner and the decision maker is called the agent. The thing it interacts with, comprising everything outside the agent, is called the environment. These interact continually, the agent selecting actions and the environment responding to those actions by presenting rewards and new states. In the first part of the project, we will learn the optimal policy of an agent navigating in a 2-D environment. We will implement the Value iteration algorithm to learn the optimal policy. Inverse Reinforcement Learning (IRL) is the task of extracting an expert’s reward function by observing the optimal policy of the expert. In the second part of the project, we will explore the application of IRL in the context of apprenticeship learning. 2 Reinforcement learning (RL) The two main objects in Reinforcement learning are: • Agent • Environment In this project, we will learn the optimal policy of a single agent navigating in a 2-D environment. 2.1 Environment In this project, we assume that the environment of the agent is modeled by a Markov Decision Process (MDP). In a MDP, agents occupy a state of the environment and perform actions to change the state they are in. After taking an action, they are given some representation of the new state and some reward value associated with the new state. An MDP formally is a tuple (S, A,P a ss′, Ra ss′, γ) where: 1 • S is a set of states • A is a set of actions • P a ss′ is a set of transition probabilities, where P a ss′ is the probability of transitioning from state s ∈ S to state s ′ ∈ S after taking action a ∈ A – P a ss′ = P(st+1 = s ′ |st = s, at = a) • Given any current state and action, s and a, together with any next state, s ′ , the expected value of the next reward is Ra ss′ – Ra ss′ = E(rt+1|st = s, at = a, st+1 = s ′ ) • γ ∈ [0, 1) is the discount factor, and it is used to compute the present value of future reward – If γ is close to 1 then the future rewards are discounted less – If γ is close to 0 then the future rewards are discounted more In the next few subsections, we will discuss the parameters that will be used to generate the environment for the project. 2.1.1 State space In this project, we consider the state space to be a 2-D square grid with 100 states. The 2-D square grid along with the numbering of the states is shown in figure 1 Figure 1: 2-D square grid with state numbering 2.1.2 Action set In this project, we consider the action set(A) to contain the 4 following actions: • Move Right 2 • Move Left • Move Up • Move Down The 4 types of actions are displayed in figure 2 Figure 2: 4 types of action From the above figure, we can see that the agent can take 4 actions from the state marked with a dot. 2.1.3 Transition probabilities In this project, we define the transition probabilities in the following manner: 1. If state s ′ and s are not neighboring states in the 2-D grid, then P(st+1 = s ′ |st = s, at = a) = 0 s ′ and s are neighbors in the 2-D grid if you can move to s ′ from s by taking an action a from the action set A. We will consider a state s to be a neighbor of itself. For example, from figure 1 we can observe that states 1 and 11 are neighbors (we can transition from 1 to 11 by moving right) but states 1 and 12 are not neighbors. 2. Each action corresponds to a movement in the intended direction with probability 1 − w, but has a probability of w of moving in a random direction instead due to wind. To illustrate this, let’s consider the states shown in figure 3 3 Figure 3: Inner grid states (Non-boundary states) The transition probabilities for the non-boundary states shown in figure 3 are given below: P(st+1 = 43|st = 44, at =↑) = 1 − w + w 4 P(st+1 = 34|st = 44, at =↑) = w 4 P(st+1 = 54|st = 44, at =↑) = w 4 P(st+1 = 45|st = 44, at =↑) = w 4 From the above calculation it can be observed that if the agent is at a non-boundary state then it has 4 neighbors excluding itself and the probability w is uniformly distributed over the 4 neighbors. Also, if the agent is at a non-boundary state then it transitions to a new state after taking an action (P(st+1 = 44|st = 44, at =↑) = 0) 3. If the agent is at one of the four corner states (0,9,90,99), the agent stays at the current state if it takes an action to move off the grid or is blown off the grid by wind. The actions can be divided into two categories: • Action to move off the grid • Action to stay in the grid To illustrate this, let’s consider the states shown in figure 4 4 Figure 4: Corner states The transition probabilities for taking an action to move off the grid are given below: P(st+1 = 10|st = 0, at =↑) = w 4 P(st+1 = 1|st = 0, at =↑) = w 4 P(st+1 = 0|st = 0, at =↑) = 1 − w + w 4 + w 4 The transition probabilities for taking an action to stay in the grid are given below: P(st+1 = 10|st = 0, at =→) = 1 − w + w 4 P(st+1 = 1|st = 0, at =→) = w 4 P(st+1 = 0|st = 0, at =→) = w 4 + w 4 At a corner state, you can be blown off the grid in two directions. As a result, we have P(st+1 = 0|st = 0, at =→) = w 4 + w 4 since we can be blown off the grid in two directions and in both the cases we stay at the current state. 4. If the agent is at one of the edge states, the agent stays at the current state if it takes an action to move off the grid or is blown off the grid by wind. The actions can be divided into two categories: • Action to move off the grid • Action to stay in the grid To illustrate this, let’s consider the states shown in figure 5 5 Figure 5: Edge states The transition probabilities for taking an action to move off the grid are given below: P(st+1 = 0|st = 1, at =←) = w 4 P(st+1 = 11|st = 1, at =←) = w 4 P(st+1 = 2|st = 1, at =←) = w 4 P(st+1 = 1|st = 1, at =←) = 1 − w + w 4 The transition probabilities for taking an action to stay in the grid are given below: P(st+1 = 0|st = 1, at =↑) = 1 − w + w 4 P(st+1 = 11|st = 1, at =↑) = w 4 P(st+1 = 2|st = 1, at =↑) = w 4 P(st+1 = 1|st = 1, at =↑) = w 4 At an edge state, you can be blown off the grid in one direction. As a result, we have P(st+1 = 1|st = 1, at =↑) = w 4 since we can be blown off the grid in one direction and in that case we stay at the current state. The main difference between a corner state and an edge state is that a corner state has 2 neighbors and an edge state has 3 neighbors. 2.1.4 Reward function To simplify the project, we will assume that the reward function is independent of the current state (s) and the action that you take at the current state (a). To be specific, reward 6 function only depends on the state that you transition to (s ′ ). With this simplification, we have Ra ss′ = R(s ′ ) In this project, we will learn the optimal policy of an agent for two different reward functions: • Reward function 1 • Reward function 2 The two different reward functions are displayed in figures 6 and 7 respectively Figure 6: Reward function 1 7 Figure 7: Reward function 2 Question 1: (10 points) For visualization purpose, generate heat maps of Reward function 1 and Reward function 2. For the heat maps, make sure you display the coloring scale. You will have 2 plots for this question For solving question 1, you might find the following function useful: https://matplotlib.org/api/_as_gen/matplotlib.pyplot.pcolor.html 3 Optimal policy learning using RL algorithms In this part of the project, we will use reinforcement learning (RL) algorithm to find the optimal policy. The main steps in RL algorithm are: • Find optimal state-value or action-value • Use the optimal state-value or action-value to determine the deterministic optimal policy There are a couple of RL algorithms, but we will use the Value iteration algorithm since it was discussed in detail in the lecture. We will skip the derivation of the algorithm here because it was covered in the lecture (for the derivation details please refer to the lecture slides on Reinforcement learning). We will just reproduce the algorithm below for the ease of implementation: 8 1: procedure Value Iteration(P a ss′ , Ra ss′ , S, A, γ): 2: for all s ∈ S do ▷ Initialization 3: V (s) ← 0 4: end for 5: ∆ ← ∞ 6: while ∆ > ϵ do ▷ Estimation 7: ∆ ← 0 8: for all s ∈ S do 9: v ← V (s); 10: V (s) ← max a∈A X s ′∈S P a ss′ [Ra ss′ + γV (s ′ )]; 11: ∆ ← max(∆, |v − V (s)|); 12: end for 13: end while 14: for all s ∈ S do ▷ Computation 15: π(s) ← arg max a∈A X s ′∈S P a ss′ [Ra ss′ + γV (s ′ )]; 16: end for 17: end procedure return π Question 2: (40 points) Create the environment of the agent using the information provided in section 2. To be specific, create the MDP by setting up the state-space, action set, transition probabilities, discount factor, and reward function. For creating the environment, use the following set of parameters: • Number of states = 100 (state space is a 10 by 10 square grid as displayed in figure 1) • Number of actions = 4 (set of possible actions is displayed in figure 2) • w = 0.1 • Discount factor = 0.8 • Reward function 1 After you have created the environment, then write an optimal state-value function that takes as input the environment of the agent and outputs the optimal value of each state in the grid. For the optimal state-value function, you have to implement the Initialization (lines 2-4) and Estimation (lines 5-13) steps of the Value Iteration algorithm. For the estimation step, use ϵ = 0.01. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal value of that state. In this part of question, you should have 1 plot. Let’s assume that your value iteration algorithm converges in N steps. Plot snapshots of state values in 5 different steps linearly distributed from 1 to N. Report N and your step numbers. What observations do you have from the plots? Question 3: (5 points) Generate a heat map of the optimal state values across the 2- D grid. For generating the heat map, you can use the same function provided in the hint earlier (see the hint after question 1). Question 4: (15 points) Explain the distribution of the optimal state values across the 2-D grid. (Hint: Use the figure generated in question 3 to explain) Question 5: (20 points) Implement the computation step of the value iteration algorithm 9 (lines 14-17) to compute the optimal policy of the agent navigating the 2-D state-space. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The optimal actions should be displayed using arrows. Does the optimal policy of the agent match your intuition? Please provide a brief explanation. Is it possible for the agent to compute the optimal action to take at each state by observing the optimal values of it’s neighboring states? In this question, you should have 1 plot. Question 6: (10 points) Modify the environment of the agent by replacing Reward function 1 with Reward function 2. Use the optimal state-value function implemented in question 2 to compute the optimal value of each state in the grid. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal value of that state. In this question, you should have 1 plot. Question 7: (20 points) Generate a heat map of the optimal state values (found in question 6) across the 2-D grid. For generating the heat map, you can use the same function provided in the hint earlier. Explain the distribution of the optimal state values across the 2-D grid. (Hint: Use the figure generated in this question to explain) Question 8: (20 points) Implement the computation step of the value iteration algorithm (lines 14-17) to compute the optimal policy of the agent navigating the 2-D state-space. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The optimal actions should be displayed using arrows. Does the optimal policy of the agent match your intuition? Please provide a brief explanation. In this question, you should have 1 plot. Question 9:(20 points) Change the hyper parameter w to 0.6 and find the optimal policy map similar to previous question for reward functions. Explain the differences you observe. What do you think about value of new w compared to previous value? Choose the w that you think give rise to better optimal policy and use that w for the next stages of the project. 4 Inverse Reinforcement learning (IRL) Inverse Reinforcement learning (IRL) is the task of learning an expert’s reward function by observing the optimal behavior of the expert. The motivation for IRL comes from apprenticeship learning. In apprenticeship learning, the goal of the agent is to learn a policy by observing the behavior of an expert. This task can be accomplished in two ways: 1. Learn the policy directly from expert behavior 2. Learn the expert’s reward function and use it to generate the optimal policy The second way is preferred because the reward function provides a much more parsimonious description of behavior. Reward function, rather than the policy, is the most succinct, robust, and transferable definition of the task. Therefore, extracting the reward function of an expert would help design more robust agents. In this part of the project, we will use IRL algorithm to extract the reward function. 10 We will use the optimal policy computed in the previous section as the expert behavior and use the algorithm to extract the reward function of the expert. Then, we will use the extracted reward function to compute the optimal policy of the agent. We will compare the optimal policy of the agent to the optimal policy of the expert and use some similarity metric between the two to measure the performance of the IRL algorithm. 4.1 IRL algorithm For finite state spaces, there are a couple of IRL algorithms for extracting the reward function: • Linear Programming (LP) formulation • Maximum Entropy formulation Since we covered the LP formulation of inverse reinforcement learning in lecture—and it is simpler than the original quadratic-program approach—we adopt that version here [?]. A step-by-step derivation can be found in our course slides [?]. The LP formulation of the IRL is given by equation 1 maximize R,ti,ui P|S| i=1(ti − λui) subject to [(Pa1 (i) − Pa(i))(I − γPa1 ) −1R] ≥ ti , ∀a ∈ A a1, ∀i (Pa1 − Pa)(I − γPa1 ) −1R ⪰ 0, ∀a ∈ A a1 −u ⪯ R ⪯ u |Ri | ≤ Rmax, i = 1, 2, · · · , |S| (1) In the LP given by equation 1, R is the reward vector (R(i) = R(si)), Pa is the transition probability matrix corresponding to the action a, λ is the adjustable penalty coefficient, and ti ’s and ui ’s are the extra optimization variables (please note that u(i) = ui). Throughout IRL section we fix the discount factor to γ = 0.9. Use the maximum absolute value of the ground-truth reward as Rmax. For the ease of implementation, we can recast the LP in equation 1 into an equivalent form given by equation 2 using block matrices. maximize x c T x subject to Dx ⪯ b, ∀a ∈ A a1 (2) Question 10: (10 points) Express c, x, D, b in terms of R, Pa, Pa1 , ti , u, λ and Rmax 4.2 Performance measure In this project, we use a very simple measure to evaluate the performance of the IRL algorithm. Before we state the performance measure, let’s introduce some notation: • OA(s): Optimal action of the agent at state s • OE(s): Optimal action of the expert at state s • m(s) = ( 1, OA(s) = OE(s) 0, else 11 Then with the above notation, accuracy is given by equation 3 Accuracy = P s∈S m(s) |S| (3) Since we are using the optimal policy found in the previous section as the expert behavior, so we will use the optimal policy found in the previous section to fill the OE(s) values. Please note that these values will be different depending on whether we used Reward Function 1 or Reward Function 2 to create the environment. To compute OA(s), we will solve the linear program given by equation 2 to extract the reward function of the expert. For solving the linear program you can use the LP solver in python (from cvxopt import solvers and then use solvers.lp). Then, we will use the extracted reward function to compute the optimal policy of the agent using the value iteration algorithm you implemented in the previous section. The optimal policy of the agent found in this manner will be used to fill the OA(s) values. Please note that these values will depend on the adjustable penalty coefficient λ. We will tune λ to maximize the accuracy. Implementation Guide Constants γ = 0.8 Rmax = maxi |Rtrue(si)| CVXOPT options from cvxopt import s o l v e r s s o l v e r s . o p ti o n s . update ({ ’ a b s t o l ’ : 1 e−7, ’ r e l t o l ’ : 1 e −6, ’ f e a s t o l ’ : 1 e −7, ’ s ho w p rog r e s s ’ : Fal s e }) Question 11: (30 points) Sweep λ from 0 to 5 to get 500 evenly spaced values for λ. For each value of λ compute OA(s) by following the process described above. For this problem, use the optimal policy of the agent found in question 5 to fill in the OE(s) values. Then use equation 3 to compute the accuracy of the IRL algorithm for this value of λ. You need to repeat the above process for all 500 values of λ to get 500 data points. Plot λ (x-axis) against Accuracy (y-axis). In this question, you should have 1 plot. Question 12: (5 points) Use the plot in question 11 to compute the value of λ for which accuracy is maximum. For future reference we will denote this value as λ (1) max. Please report λ (1) max Question 13: (15 points) For λ (1) max, generate heat maps of the ground truth reward and the extracted reward. Please note that the ground truth reward is the Reward function 1 and the extracted reward is computed by solving the linear program given by equation 2 with the λ parameter set to λ (1) max. In this question, you should have 2 plots. Question 14: (10 points) Use the extracted reward function computed in question 13, to compute the optimal values of the states in the 2-D grid. For computing the optimal values you need to use the optimal state-value function that you wrote in question 2. For visualization purpose, generate a heat map of the optimal state values across the 2-D grid (similar to the figure generated in question 3). In this question, you should have 1 plot. 12 Question 15: (10 points) Compare the heat maps of Question 3 and Question 14 and provide a brief explanation on their similarities and differences. Question 16: (10 points) Use the extracted reward function found in question 13 to compute the optimal policy of the agent. For computing the optimal policy of the agent you need to use the function that you wrote in question 5. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The actions should be displayed using arrows. In this question, you should have 1 plot. Question 17: (10 points) Compare the figures of Question 5 and Question 16 and provide a brief explanation on their similarities and differences. Question 18: (30 points) Sweep λ from 0 to 5 to get 500 evenly spaced values for λ. For each value of λ compute OA(s) by following the process described above. For this problem, use the optimal policy of the agent found in question 8 to fill in the OE(s) values. Then use equation 3 to compute the accuracy of the IRL algorithm for this value of λ. You need to repeat the above process for all 500 values of λ to get 500 data points. Plot λ (x-axis) against Accuracy (y-axis). In this question, you should have 1 plot. Question 19: (5 points) Use the plot in question 18 to compute the value of λ for which accuracy is maximum. For future reference we will denote this value as λ (2) max. Please report λ (2) max Question 20: (15 points) For λ (2) max, generate heat maps of the ground truth reward and the extracted reward. Please note that the ground truth reward is the Reward function 2 and the extracted reward is computed by solving the linear program given by equation 2 with the λ parameter set to λ (2) max. In this question, you should have 2 plots. Question 21: (10 points) Use the extracted reward function computed in question 20, to compute the optimal values of the states in the 2-D grid. For computing the optimal values you need to use the optimal state-value function that you wrote in question 2. For visualization purpose, generate a heat map of the optimal state values across the 2-D grid (similar to the figure generated in question 7). In this question, you should have 1 plot. Question 22: (10 points) Compare the heat maps of Question 7 and Question 21 and provide a brief explanation on their similarities and differences. Question 23: (10 points) Use the extracted reward function found in question 20 to compute the optimal policy of the agent. For computing the optimal policy of the agent you need to use the function that you wrote in question 9. For visualization purpose, you should generate a figure similar to that of figure 1 but with the number of state replaced by the optimal action at that state. The actions should be displayed using arrows. In this question, you should have 1 plot. Question 24: (10 points) Compare the figures of Question 9 and Question 23 and provide a brief explanation on their similarities and differences. 13 Question 25: (50 points) From the figure in question 23, you should observe that the optimal policy of the agent has two major discrepancies. Please identify and provide the causes for these two discrepancies. One of the discrepancy can be fixed easily by a slight modification to the value iteration algorithm. Perform this modification and re-run the modified value iteration algorithm to compute the optimal policy of the agent. Also, recompute the maximum accuracy after this modification. Is there a change in maximum accuracy? The second discrepancy is harder to fix and is a limitation of the simple IRL algorithm. 5 Submission Please submit your report to Gradescope. Also submit a zip file containing your codes and report to bruinlearn. The zip file should be named as “Project3 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. References
Introduction Welcome to your first COMP 2522 assignment. Today you will apply what you have started learning as we migrate from Python to Java. You will implement the first class for a larger project. Developing software is often a highly iterative process. Iterative software development involves repeated cycles of designing, coding, testing, and integrating small sections or increments of a program. We build a little, show it to our clients, make adjustments, and continue. By deconstructing a large project into smaller, more manageable tasks, we can abstract away portions of the application and focus on separate, solvable problems. The knowledge we gain from developing and testing these smaller modules can be applied to the development of other parts of the project. Ultimately we generate correct, working, and maintainable software efficiently and quickly. You have been hired to generate some helpful software for a group of ichthyologists at the Vancouver Aquarium. A new and invasive species of Poecilia, the live-bearing aquarium fish also known as the guppy, has been discovered in some of the hot springs, pools, and streams near Skookumchuk. The owners of the land have asked the scientists to study the prolific little fish and determine, among other things, if its reproductive rate will be a threat to native aquatic fauna. Figure 1: Guppies by Per Harald Olsen (Own work) via Wikimedia Commons [GFDL (https://www.gnu.org/copyleft/fdl.html) or CC BY 3.0 (https://creativecommons.org/licenses/by/3.0)] The scientists are still studying the problem domain, and they haven’t finalized the scope of the simulations they want to conduct. But that’s okay. Object-oriented analysis, design, and programming are well suited to developing software systems whose requirements are incomplete and changing. During the first few analysis meetings with the scientists, you identified some fundamental classes in the problem domain. For the first iteration of your software project, you will abstract away much of the potentially complicated logic and design in the application. You will begin by writing one of the classes that represent the basic building blocks of the simulations the scientists will want to run. 1 1 Submission requirements This assignment must be submitted via GitHub by Sunday January 19th at or before 23:59:59 PM. Tardy submissions will not be accepted. Your code must be in the ca.bcit.comp2522.assignments.a1 package of the main COMP 2522 IntelliJ project you created in Lab 01. We will mark the code as it appears during the final commit before the due date and time. 2 Grading scheme Your assignment will be marked out of 10: 1. 5 points for code style (refer to the code style handout) 2. 5 point for code correctness (we will even provide you with some helpful JUnit tests later this week). 3 Implementation requirements You must implement a class called Guppy.java which contains the following elements: 1. The following nine public symbolic constants. Use these variable names and data types. In Java, symbolic constants are static and final. Do not use different names or data types, and do not add any other symbolic constants. Use these constants instead of magic numbers inside your code: (a) YOUNG_FISH_AGE_IN_WEEKS an integer equal to 10 (b) MATURE_FISH_AGE_IN_WEEKS an integer equal to 30 (c) MAXIMUM_AGE_IN_WEEKS an integer equal to 50 (d) MINIMUM_WATER_VOLUME_ML a double equal to 250.0 (e) DEFAULT_GENUS a String equal to “Poecilia” (f) DEFAULT_SPECIES a String equal to “reticulata” (g) DEFAULT_HEALTH_COEFFICIENT a double equal to 0.5 (h) MINIMUM_HEALTH_COEFFICIENT a double equal to 0.0 (i) MAXIMUM_HEALTH_COEFFICIENT a double equal to 1.0 2. The following eight private instance variables. Use these variable names and data types. Do not use different names or data types, and do not add any other instance variables: (a) genus (first word of the scientific binomial two-part name) a String (b) species (second word of the scientific binomial name) a String (c) ageInWeeks an integer (d) isFemale a boolean (e) generationNumber an integer (f) isAlive a boolean (g) healthCoefficient a double (h) identificationNumber an integer 3. numberOfGuppiesBorn, a private static integer that has an initial value of 0. This variable is incremented by 1 each time a new guppy is constructed, and the newly incremented value is assigned to the new guppy’s identificationNumber instance variable. Further details are provided in the section about constructors (remember that static variables are shared by all objects of a class). 4. Two (2) constructors: 2 (a) A zero-parameter constructor which sets ageInWeeks and generationNumber to zero, and sets: i. genus to DEFAULT_GENUS ii. species to DEFAULT_SPECIES iii. isFemale to true iv. isAlive to true v. healthCoefficient to DEFAULT_HEALTH_COEFFICIENT vi. identificationNumber to the newly incremented value of numberOfGuppiesBorn (b) A second constructor which accepts the following parameters in the following order: i. newGenus a String. Format the String passed in newGenus correctly (capital first letter, the rest lower case) and assign the new String to the genus instance variable. ii. newSpecies a String. Format the String passed in newSpecies correctly (lower case) and assign the new String to the species instance variable. iii. newAgeInWeeks a positive integer. Assign newAgeInWeeks to the ageInWeeks instance variable. If the parameter passed to the method is negative, assign a 0. iv. newIsFemale a boolean to assign to the isFemale instance variable. v. newGenerationNumber an integer. If the argument passed as the parameter is less than zero, set the value to one. Otherwise assign newGenerationNumber to the generationNumber instance variable. vi. newHealthCoefficient a double. If the argument passed as the parameter is less than MINIMUM_HEALTH_COEFFICIENT or greater than MAXIMUM_HEALTH_COEFFICIENT, set the value to the closest bound. Otherwise assign newHealthCoefficient to the instance variable called healthCoefficient. vii. This constructor should not accept a parameter for the isAlive instance variable. Set the isAlive variable to true. Every new Guppy is alive by default. (c) Remember that each constructor must also increment the static numberOfGuppiesBorn variable by 1 and and assign the new value to identificationNumber. 5. A method with the header public void incrementAge() which increases the value in the ageInWeeks instance variable field by 1. If the new value in ageInWeeks is greater than MAXIMUM_AGE_IN_WEEKS, set the isAlive instance variable to false. 6. An accessor (getter) for all eight instance variables, and a mutator (setter) for ageInWeeks, isAlive, and healthCoefficient: (a) Do not create mutators for genus, species, isFemale, or identificationNumber. (b) Every accessor method name must follow the pattern getVariableName. (c) Every mutator method name must follow the pattern setVariableName. (d) Also create a static accessor for the numberOfGuppiesBorn static variable. It must be called public static int getNumberOfGuppiesBorn(). (e) The mutator for ageInWeeks must ignore values below 0 and above MAXIMUM_AGE_IN_WEEKS. (f) The mutator for healthCoefficient must ignore values that would cause the healthCoefficient variable to exceed its bounds. 7. A method with the header public double getVolumeNeeded() which returns the volume of water in millilitres that the guppy needs according to the following formula: (a) If the fish is less than 10 weeks old, return MINIMUM_WATER_VOLUME_ML. (b) If the fish is 10 to 30 weeks old, return MINIMUM_WATER_VOLUME_ML * ageInWeeks / YOUNG_FISH_WEEKS. (c) If the fish is 31 to 50 weeks old, return MINIMUM_WATER_VOLUME_ML * 1.5. (d) If the fish is older than 50 weeks, return 0.0. 3 8. a method with the header public void changeHealthCoefficient(double delta) which adds the value passed in the delta parameter to the healthCoefficient instance variable. The parameter delta may be positive or negative, but if the new value of healthCoefficient would be less than or equal to MINIMUM_HEALTH_COEFFICIENT, in addition to setting the value of healthCoefficient to 0.0, set the isAlive instance variable to false. If the new value of healthCoefficient would be greater than MAXIMUM_HEALTH_COEFFICIENT, set healthCoefficient to MAXIMUM_HEALTH_COEFFICIENT. 9. a method with the header public String toString() which returns a String representation of the guppy. The version generated by IntelliJ is sufficient. 10. an equals() method. Write this one yourself from scratch. That’s it! Good luck, and have fun!Introduction Hooray! It took a few late nights, but you met your first milestone. You successfully demonstrated the first iteration of the simulation software to the ichthyologists and they are eager for you to finish. The scientists have returned from their final fact-hunting expedition. They have given you the data you need to finish the program. And it’s a rush job – they need a finished simulation in about two weeks! It’s time to complete your contract and give the whole project a little bit of polish. You are ready to begin the next iteration. Did you have any idea that you’d be writing full-fledged Java programs after only a few weeks? For assignment 2, you will implement a class that represents a hot spring Pool and ’manages’ a collection of resident Guppy objects. You will make minor additions to the Guppy class, and create one Ecosystem class to rule them all. Let’s begin! Figure 1: Guppy Simulation class diagram (Proposed design) 1 Submission requirements This assignment must be completed by Wednesday February 12th 2020 at or before 23:59:59. Your code must all be in the ca.bcit.comp2522.assignments.a2 package of your COMP 2522 IntelliJ project. We will mark the code as it appears during the final commit before the due date and time. 1 2 Grading scheme Your assignment will be marked out of 10: 1. 2 points for code style 2. 2 point the modifications to the Guppy class 3. 3 points for the Pool class 4. 3 points for the Ecosystem class 3 Implementation requirements Implement the following: 1. Copy the Guppy.java and GuppyTest.java source files to the a2 package. 2. It’s time to implement reproduction for the Guppies! You must implement a method called public ArrayList spawn() in the Guppy.java class. Here’s how it must work: (a) Only female Guppies can have babies (b) Female Guppies must be 8 weeks of age or older to spawn (c) Each week, each female Guppy who is 8 weeks old or older has a 50 percent chance of spawning (hint: use Random) (d) A spawning female has between 0 and 100 fry (Note: Guppies don’t lay eggs, they have live babies called fry! Really!) (e) Each fry is the same genus and species as its mother (f) Each fry has a 50 percent chance of being female (g) A new fry has a health coefficient equal to (1.0 + mother’s health quotient) / 2.0 (h) The generation number of a new fry is 1 + the mother’s generation number. Here’s a good way to approach this. The method should begin by checking if the Guppy is female. If not, or if the Guppy is 0 – 7 weeks old, return null immediately. Otherwise create a local ArrayList called babyGuppies. Use a Random object to generate a double between 0 and 1.0. If the random number is equal to or less than 0.50, the female will spawn some babies. If the female is going to have babies, use the Random object to generate a random int between 0 and 100 inclusive for the female. Use a loop statement to create this number of Guppies (0 – 100) with the correct attributes, and add them to the babyGuppies ArrayList. After the loop is done, return the newly created ArrayList. That’s all. 3. You must create a class called Pool.java which contains the following elements: (a) The following public symbolic constants. Use these variable names and data types. Remember symbolic constants are static and final. Do not use different names or data types. Use these constants instead of magic numbers inside your code: i. DEFAULT_POOL_NAME a String equal to “Unnamed” ii. DEFAULT_POOL_TEMP_CELSIUS a double equal to 40.0 iii. MINIMUM_POOL_TEMP_CELSIUS a double equal to 0.0 iv. MAXIMUM_POOL_TEMP_CELSIUS a double equal to 100.0 v. NEUTRAL_PH a double equal to 7.0 vi. DEFAULT_NUTRIENT_COEFFICIENT a double equal to 0.50 vii. MINIMUM_NUTRIENT_COEFFICIENT a double equal to 0.0 viii. MAXIMUM_NUTRIENT_COEFFICIENT a double equal to 1.0. (b) The following 8 private instance variables. Use these variable names and data types. Do not use different names or data types, and do not add any other instance variables: 2 i. name a String ii. volumeLitres a double iii. temperatureCelsius a double iv. pH a double that will always be between 0 and 14.0 inclusive v. nutrientCoefficient, a double that will always be between 0 and 1.0 inclusive vi. identificationNumber an int vii. guppiesInPool an ArrayList of Guppy viii. randomNumberGenerator a Random object. (c) numberOf Pools a private static variable with an initial value of 0 that is incremented by 1 each time a new Pool is constructed. Further details are provided in the section about constructors (remember that static variables are shared by all objects of a class). (d) Two (2) constructors: i. Zero-parameter constructor which sets volumeLitres to 0.0, and also sets: A. name is set to DEFAULT_POOL_NAME B. temperatureCelsius is set to DEFAULT_POOL_TEMP_CELSIUS C. pH is set to NEUTRAL_PH D. nutrientCoefficient is set to DEFAULT_NUTRIENT_COEFFICIENT E. guppiesInPool is initialized to be an empty ArrayList of Guppy, and randomNumberGenerator is initialized to be a new Random (use the zero-parameter constructor in the Random class). ii. Multi-Parameter constructor which accepts a parameter for each instance variable (except the identification number, the ArrayList of guppies, and the random number generator) and validates it: A. The parameter passed for the name field must not be null, and must not be an empty String or a String composed only of whitespace. If the argument passed as the parameter is either null or an empty/whitespace String, throw an IllegalArgumentException. Otherwise, format the value correctly (remove the whitespace, capitalize the first letter, set the rest to lower case) before storing it in the instance variable. B. The parameter passed for the volumeLitres field must be positive, otherwise set the instance variable to 0.0. C. The parameter passed for the temperatureCelsius instance variable must be greater than or equal to MINIMUM_POOL_TEMP_CELSIUS and less than or equal to MAXIMUM_POOL_TEMP_CELSIUS, else the instance variable must be set to the default temperature. D. the parameter passed for the pH field must be within the range [0, 14.0], otherwise set the instance variable to NEUTRAL_PH. E. the parameter passed for the nutrientCoefficient must be within the range [0, 1.0] (between 0 and 1.0 inclusive), otherwise set the instance variable to DEFAULT_NUTRIENT_COEFFICIENT. F. guppiesInPool is initialized to be a new ArrayList of Guppy. G. randomNumberGenerator is initialized to be a new Random (use the zero-parameter constructor in the Random class). iii. Both constructors must create and assign a unique numerical identification number to the identificationNumber instance variable. A good way to do this is to increment the static counter field from inside the constructor, and then assign that newly incremented value to the new Pool object’s identification field. (e) Implement accessors (getters) and mutators (setters). Create accessors for name, volumeLitres, temperatureCelsius, pH, nutrientCoefficient, and identificationNumber. We do not want to create an accessor for the ArrayList of Guppy because we want to keep that collection encapsulated and protected from tampering. Create mutators for volumeLitres. temperatureCelsius, pH, nutrientCoefficient. All mutators should ignore values that are unacceptable. For example. the pH 3 mutator must ignore input that does not fall within the range [0, 14], and the nutrientCoefficient mutator should ignore values that do not fall within the range [0, 1.0]. Instance variables which do not have mutators should be final. (f) a method with the header public void changeNutrientCoefficient(double delta) which adds the value passed in the delta parameter to the Pool’s nutrient coefficient. The parameter may be positive or negative, but if the new value of the nutrient coefficient would be less than the minimum, set the nutrient coefficient to the minimum. If the new value would be greater than the maximum, set the new value to the maximum. (g) a method with the header public void changeTemperature(double delta) which changes the temperature by the amount passed in the delta parameter. If the new Pool temperature would be less than the minimum, set the pool temperature to the minimum. If the new Pool temperature would be greater than the maximum, set it to the maximum. (h) a method with the header public static int getNumberCreated() which returns the total number of Pools created. (i) a method with the header public boolean addGuppy(Guppy guppy) which adds a Guppy to the Pool. If the parameter equals null, the method should return false. If the parameter is not equal to null, add the Guppy to the ArrayList of Guppy. If the Guppy is successfully added, return true, else return false. (j) a method with the header public int getPopulation() which returns the number of living Guppies in the pool. (k) a method with the header public int applyNutrientCoefficient() that calculates which Guppies in the Pool have died of malnutrition this week, and returns the number of deaths. Iterate over the ArrayList of Guppy in the Pool using the iterator returned by the ArrayList’s iterator( ) method. For each Guppy, generate a different random number between 0.0 and 1.0 inclusive using the Random method nextDouble(). If this randomly generated number is greater than the Pool’s nutrient coefficient, kill that Guppy by setting the appropriate boolean field in the Guppy. Note that this method does not remove any dead Guppies from the Pool, it just kills them. Do not do anything else. (l) a method with the header public int removeDeadGuppies() which uses an ArrayList iterator and a loop to visit each Guppy in the collection and remove the Guppies that are not alive. This method must keep track of how many Guppies are removed. Return the number of Guppies that have been removed. (m) a method with the header public double getGuppyVolumeRequirementInLitres() which returns the total number of litres required by all of the living Guppies in the Pool. Note that the Guppy class has a helpful method with returns the total number of milliLitres required per Guppy. You will need to convert this to litres (note that 1,000 mL = 1 L). (n) a method with the header public double getAverageAgeInWeeks() which returns the average age of the living Guppies in the Pool. (o) a method with the header public double getAverageHealthCoefficient() which returns the average health coefficient of the living Guppies in the Pool. (p) a method with the header public double getFemalePercentage() which returns a double representing the percentage of living Guppies in the Pool that are female. (q) a method with the header public double getMedianAge() which returns median age of the living Guppies in the Pool. (r) a method with the header public String toString() which returns a String representation of the Pool. The version generated by IntelliJ is sufficient. (s) Implement a method called public int spawn(). This method must Iterate over the Guppies in the Pool and invoke the spawn method on each one. Each Guppy will return null (if it is male, or too young to reproduce) or an ArrayList of Guppies containing the new fry. Add the new baby Guppies to the Pool’s collection of Guppies. You can add each mother’s new fry to the Pool like this: guppiesInPool.addAll(newBabies);. Count the total number of new Guppies that have been born and added to the Pool, and return the total. 4 (t) Implement a method called public int incrementAges(). This method increments the ages of every Guppy in the Pool and returns the number that have died of old age. Do not remove the dead Guppies from the collection, just kill them. The dead Guppies still need to be removed from the system. (u) Implement a method called public int adjustForCrowding( ). This Pool method extinguishes the Guppies that have suffocated due to overcrowding. If the total volume needed by a collection of Guppies exceeds the volume of their Pool, then some of the Guppies must be extinguished. If the total volume required by the Guppies in the Pool exceeds the total volume of the Pool, then we must loop through the Guppies in the Pool and terminate the weakest, e.g., the Guppy with the lowest health coefficient. We must do this again and again, and keep terminating the weakest Guppy in the Pool until the total volume requirement of the group of Guppies that remain alive is equal to or less than than the volume of the Pool. Note that the crowded out Guppies are only terminated. They are not removed from the Pool. Return the total number of Guppies that have died due to crowding. 4. Implement a new class called Ecosystem. Ecosystem contains and drives the simulation and requires the following elements: (a) One private instance variable, private ArrayList pools. Do not add any other instance variables. (b) Zero-parameter constructor that must initialize the ArrayList of Pools. Do not create a oneparameter constructor. (c) Implement a method called public void addPool(Pool newPool) which adds the Pool passed as a parameter to the Collection of Pools. Ignore null parameters, e.g., do not add any nulls to the Pool collection. (d) Implement a method called public void reset( ) that resets the Ecosystem by emptying the ArrayList of Pool (hint: check out the clear() method available to the ArrayList). (e) Implement a method called public int getGuppyPopulation( ) which returns the total number of living Guppies in the Ecosystem. Hint: use a for each loop to invoke the getPopulation() method on each pool and add the result to a local accumulator variable. (f) Implement a method called public int adjustForCrowding( ) (same name as the Pool method!) which iterates over all the Pools, invokes each Pool’s adjustForCrowding( ) method, and adds the number of Guppies that have been crowded out to a running total. Once all the Pools have been “de-crowded,” adjustForCrowding should return the total number of Guppies that have been squeezed out of the entire ecosystem. (g) Implement a method called public void setupSimulation( ). This method should create the following Ecosystem: i. The first pool is called Skookumchuk. It has a total volume of 3,000 litres. Its temperature is 42 degrees Celsius and its pH is 7.9. The nutrient coefficient is 0.9. ii. The second pool is called Squamish. It has a total volume of 15,000 litres. Its temperature is 39 degrees Celsius and its pH is 7.7. The nutrient coefficient is 0.85. iii. The third and final pool is called Semiahmoo. It has a total volume of 4,500 litres. Its temperature is 37 degrees Celsius and its pH is 7.5. The nutrient coefficient is 1.0. iv. There are 300 Guppies in Skookumchuk Pool. They are all Poecilia reticulata. Use your Random object and the multi- parameter Guppy constructor to create each new Guppy with an age between 10 and 25 weeks inclusive and a health coefficient between 0.5 and 0.8 inclusive. Each original Guppy has a 75 percent chance of being female. v. There are 100 Guppies in Squamish Pool. They are all Poecilia reticulata. Use your Random object and the multi-parameter Guppy constructor to create each new Guppy with an age be- tween 10 and 15 weeks inclusive and a health coefficient between 0.8 and 1.0 inclusive. Each original Guppy has a 75 percent chance of being female. vi. There are 200 Guppies in Semiahmoo Pool. They are all Poecilia reticulata. Use your Random object and the non-default Guppy constructor to create each new Guppy with an age between 15 and 49 weeks inclusive and a health coefficient between 0.0 and 1.0 inclusive. Each original Guppy has a 35 percent chance of being female. 5 (h) Implement a method called public void simulate(int numberOf Weeks). It uses a loop to invoke the next method, simulateOneWeek, the specified number of times. (i) Implement a method called public void simulateOneWeek( ) that runs the simulation for one week. This method must: i. Invoke incrementAges( ) on each Pool and add the return value to a local int called diedOfOldAge. ii. Invoke removeDeadGuppies( ) on each Pool and add the return value to a local int called numberRemoved. iii. Invoke applyNutrientCoefficient( ) on each Pool and add the return value to a local int called starvedToDeath. iv. Invoke removeDeadGuppies( ) again (second time) on each Pool and add the return value to the local int called numberRemoved. v. Invoke spawn( ) on each Pool and add the return value to a local int called newFry. vi. Invoke adjustForCrowding( ) and assign the return value to a local int called crowdedOut. vii. Invoke removeDeadGuppies( ) again (third time!) and add the return value to numberRemoved. viii. Check that diedOfOldAge + starvedToDeath + crowdedOut == numberRemoved. If they are not equal, you have a logic error. ix. Print in a lovely and easy-to-read format: A. Week number B. Number of deaths this week due to old age C. Number of deaths this week due to starvation D. Number of deaths this week due to overcrowding E. Number of births (new fry) this week F. List of pools and their current populations at the end of the week G. Total population of the Ecosystem at the end of the week 5. Create a Driver class. The Driver class should contain a main method, nothing else. Inside the main method, instantiate an Ecosystem object. Ask the user how many weeks they would like to run the simulation, and then invoke the Ecosystem object’s public void simulate(int numberOf Weeks) method passing in the user’s choice. 6. A bonus of up to 10% is available for submissions that do one more thing. Modify the setupSimulation method in Ecosystem. Modify the Pool temperatures, pHs, and nutritional coefficients so that the populations in the Pool eventually reach a thriving balance point. I define a thriving balance point as a combination of environmental factors that result in a steady population where the number of deaths equals the number of births and the median health coefficient of the Guppies in the Ecosystem is greater that 0.6. That’s it! Good luck, and have fun!Introduction For assignment 3, we will examine abstraction and inheritance through the lens of mathematics. In 1924, a Polish mathematician named Jan Łukasiewicz invented something called Polish notation. It was refined in the early 1960s by Edsger Dijkstra who developed Reverse Polish Notation to take advantage of the Stack data structure. We’ve already talked about binary infix operators in COMP 1510 and COMP 2522. Binary infix operators are called binary because they require two operands. They are called infix because the operator is placed between the operands: 2 + 2 = 4 4 – 2 = 2 5 / 3 = 1 (assuming we are using ints) Reverse Polish notation (RPN) is a mathematical notation where operators follow their operands. Instead of using a binary infix operator, RPN uses a binary postfix operator: 2 2 + = 4 4 2 – = 2 5 3 / = 1 Consider our usual notation. When we mix our operations using binary infix operators, we must implement rules of precedence. The use of parentheses can result in dramatically different results: 2 – 3 * 4 = -10 (2 – 3) * 4 = -4 RPN (postfix) notation removes the need for parentheses! RPN’s greatest advantage is clear when we consider expressions that contain more than one operand. If we want an operation to take precedence, we just put the operator immediately to the right of the two operands: 2 3 4 * – = -10 2 3 – 4 * = -4 RPN doesn’t just eliminate parentheses and keystrokes. It’s flexible. If we use a Stack by pushing operands onto the Stack until we reached an operator, we can pop operands off the Stack, transform them with the operator, and push the result back onto the Stack as we go, letting us calculate complex partial results without having to save them in multiple locations. That’s exactly what we’re going to do. We’ll use a bit of inheritance and abstraction to create a hierarchy of operations. Then we’ll build an RPNCalculator class that contains just a few methods. 1 Ordinarily for a project like this, we would use as many existing classes as possible. Why re-invent the wheel, right? Ordinarily we would use the java.util.Stack class to implement our Stack. Ordinarily. But not for a3. For a3, in order to gain some more experience with data structures and exceptions, you will do something extraordinary. You will implement your own Stack. You’ve already created an implementation during an exam, a seriously stressful situation, so this will surely be a cinch. Fun will be had by all. Read on, and get started now! 1 Submission requirements This assignment must be completed by Sunday March the 8th at or before 23:59:59. Your code must all be in the ca.bcit.comp2522.assignments.a3 package of your COMP 2522 IntelliJ project. We will mark the code as it appears during the final commit before the due date and time. 2 Grading scheme Your assignment will be marked out of 10. A rubric will be made available on the Learning Hub to help guide your priorities. 3 Implementation requirements Implement the following: 1. We are going to build a Reverse Polish Notation calculator. The RPNCalculator will accepts two command line arguments. The first command line argument must be an int which represents the initial size of the Stack we will use to store operands. The second command line argument must be a String in double quotes that contains a valid Reverse Polish Notation expression. We will place the main method inside a class called RPNCalculator, and we will invoke the program like this: java RPNCalculator 10 “1 2 3 4 5 6 7 8 9 10 + + + + + + + + +” The program must respond by printing the expression inside a set of square brackets followed by the result: [1 2 3 4 5 6 7 8 9 10 + + + + + + + + +] = 55 2. Start by defining an interface called Operation. An Operation is a function that has a symbol. It requires two operands. The Operation interface contains two public methods, char getSymbol(), which returns the operation symbol to the user, and int perform(int operandA, int operandB), which is a blueprint for performing a math operation. That’s all we need to put inside the Operation. 3. Note that the Operation doesn’t contain any instance variables because it’s an interface. An interface just tells us how to interact with something. It makes no demands about implementation. Since it’s an interface, it doesn’t have a constructor either. We need to create a level of abstraction, another layer of the onion if you will, that adds the instance variable that will store the actual symbol being used. 4. Define an abstract class called AbstractOperation that implements Operation. Ensure AbstractOperation is an abstract class. It must contain a single protected instance variable called operationType, a char. Add a constructor which accepts a char and assigns it to operationType. Add an 2 accessor that returns the char. The accessor must be called getSymbol() and it must be final. We don’t want any subclasses overriding it. 5. We are going to confine our exploration to the basic operations: +, -, *, and /. Create four classes that extend AbstractOperation. They must be called AdditionOperation, SubtractionOperation, MultiplicationOperation, and DivisionOperation. Each of these classes must contain a static constant char called ADDITION_CODE or SUBTRACTION_CODE or MULTIPLICATION_CODE or DIVISION_CODE, each of which is assigned the value ’+’, ’-’, ’*’, or ’/’ (I will let you decide which goes with which!). The constructor must pass the constant to the superclass constructor. Ensure each class provides a concrete implementation of perform too. That’s all you need inside each class. 6. The hierarchy we just created is really quite elegant. We defined the concept of an Operation, and we can interact with an Operation by getting its symbol and passing it two operands to operate on. We further added an abstract implementation of Operation which added an instance variable, a constructor to assign it, and an accessor to acquire it. Then we created four concrete implementations of Operation. Each one is many things at once. For example, an AdditionOperation is-an AbstractOperation and it is-an Operation, too. 7. So we have this wonderful little inheritance hierarchy. It’s easy to add more operations. In our project, any operation that can be represented as a single char can be added. Do I smell a bonus? Perhaps… 8. I’d like you to implement the Stack next. We will implement a fixed size, non-resizable Stack using an olde fashioned array of int: (a) The Stack must have two instance variables, an array of int called stackValues, and an int called count. (b) The Stack constructor must accept an integer representing the size of the array to create. If the size is less than one, throw an IllegalArgumentException. (c) Add a capacity( ) method that returns the size of the Stack. (d) Add a size( ) method that returns the number of elements in the Stack, i.e., the count. (e) Add a method called unused( ) which returns the amount of space left in the Stack. (f) Add a method called push(int value) which accepts an integer called value. This method pushes the value onto the Stack. If the Stack is already full, this method must throw a checked exception called StackOverflowException. You must create this exception. Pass the message “This stack is full!” to the StackOverflowException constructor. If, however, there is room, push the value onto the Stack. The next call to pop will remove this item( ) and return it. The next call to peek( ) will return a reference to this item without removing it. (g) Did someone say pop? Add a method called pop( ) which accepts no parameters and returns an int. If someone tries to pop a value from an empty Stack, ensure this method throws a checked exception called StackUnderflowException. You will have to add this exception to your project too. Pass the message “Cannot call Stack.pop() on an empty stack!” to the StackUnderflowException exception. (h) Finally, add a method called peek( ) which does NOT remove anything from the Stack, but does return the value on top of it. If the Stack is empty, throw a new StackUnderflowException and pass the message “Cannot call Stack.peek() on an empty stack!”. 9. The pieces are in place. We just need to create the main class. Implement a class called RPNCalculator. It’s time for the fun stuff! (a) RPNCalculator contains a single integer constant called MIN_STACK_SIZE which stores two. The smallest RPN calculation is two operands followed by a single operation. (b) RPNCalculator contains a single instance variable of type Stack called (wait for it) stack. (c) The constructor must accept an integer called stackSize. If this integer is less than MIN_STACK_SIZE the constructor must throw an IllegalArgumentException. Otherwise instantiate a Stack of that size and assign the address of this new object to the instance variable. 3 (d) Implement a method called public int processFormula(final String formula): i. This method must throw an IllegalArgumentException if formula is equal to null or if it is a string of length zero. ii. Otherwise, instantiate a Scanner object, passing the formula to its constructor. We will parse the formula using an instance of the Scanner class. iii. Here’s the algorithm I’d like you to use. While the Scanner object’s hasNext( ) method returns true, check if the hasNextInt( ) method returns true, too. If it does, we know the next token in the formula String is an operand that we can push onto the Stack. If this is the case, go ahead and push that int onto the stack with a helper method called void push(final int operand). iv. The method void push(final int operand) must check that unused( ) does not return zero. If it does, we must throw a StackOverflowException with an appropriate message. Otherwise, push the operand onto the Stack. v. Otherwise, it must be an operation. If it’s an operation, we must scan the operation and use it to instantiate the correct Operation descendant. Do this in a helper method called private Operation getOperation(final char symbol). vi. Inside private Operation getOperation(final char symbol), use a switch statement to evaluate symbol. If it’s ’+’, return a new AdditionOperation object, if it’s ’-’, return a new SubtractionOperation, etc. vii. The return value must be assigned to a variable inside the processFormula method whose data type is Operation. This makes our code flexible. Now we can use polymorphism! We can create and use any kind of Operation we like. We can define new and novel operations. All we have to do is add a line inside the switch statement in the getOperation method. viii. In the switch statement, the default case must throw a checked exception called InvalidOperationTypeException (you will need to create this). Pass the errant operation to the InvalidOperationTypeException constructor. ix. Otherwise, processFormula must pass the instance of Operation created in the helper method to a method called perform( ), and then invoke a public method called getResult( ). (e) public int getResult() must use the peek( ) method in the Stack to retrieve the current value in the Stack, i.e., the result. If the size of the Stack is zero throw a new StackUnderflowException and pass the message, “There are no operands!”. (f) Finally. The moment you’ve been waiting for. The one method that rules them all. private void perform(final Operation operation) will accept the Operation object instantiated by processFormula and its helpers. Check that operation is not null. If it is, throw an IllegalArgumentException using the message, “Operation cannot be null!”. Otherwise, pop the top two operands and pass them to the Operation’s perform method. Use the push( ) method to push the result onto the Stack. 10. In order to give you a little start, I’ve included the main method which you must insert into your RPNCalculator class. You may not change this. Not a single thing: /** * Drives the program by evaluating the RPN calculation provided as * a command line argument. * * Example usage: RPNCalculator 10 “1 2 +” * * Note that the formula MUST be placed inside of double quotes. * * @param argv – the command line arguments are the size of the Stack * to be created followed by the expression to evaluate. */ public static void main(final String[] argv) { // Checks for correct number of command line arguments. 4 if (argv.length != 2) { System.err.println(“Usage: Main “); System.exit(1); } // Initializes stack and RPNCalculator. final int stackSize = Integer.parseInt(argv[0]); final RPNCalculator calculator = new RPNCalculator(stackSize); try { System.out.println(“[” + argv[1] + “] = ” + calculator.processFormula(argv[1])); } catch (final InvalidOperationTypeException ex) { System.err.println(“formula can only contain integers, +, -, *, and /”); } catch (final StackOverflowException ex) { System.err.println(“too many operands in the formula, increase the stack size”); } catch (final StackUnderflowException ex) { System.err.println(“too few operands in the formula”); } } That’s it! I’ll furnish some unit tests later that include some formulas your RPNCalculator must be able to evaluate, and which ensure your methods are throwing the right checked Exceptions, etc. Good luck, and have fun!Introduction For your fourth assignment, you will apply what you have learned about sets in COMP 1510, and arrays, ArrayLists, generics, and inner classes in COMP 2522. You will implement a novel and simple data structure that we will call the ArraySet. There is no ArraySet in the Java Collections Framework, but you have all the tools and knowledge you need to write one. The ArraySet is a parameterized data structure just like the ArrayList – it uses an array “under the hood” to implement a data structure (in this case, a set instead of a list). Recall that a set is a collection of items without duplicates and in no particular order (i.e., unordered). A user may add items to a set, remove items from a set, and check whether an item is in a particular set. Occasionally, the elements in the set must be accessed one at a time; for instance, this is necessary to list the set elements to the standard output. A SetIterator object supports accessing each element of a set, one at a time. In Java, a set cannot contain nulls, either. 1 Submission requirements This assignment must be completed by✭✭✭✭✭✭✭✭✭✭ Friday March the 27th Sunday March the 29th at or before 23:59:59. Your code must all be in the ca.bcit.comp2522.assignments.a4 package of your COMP 2522 IntelliJ project. We will mark the code as it appears during the final commit before the due date and time. 2 Grading scheme This assignment will be marked out of 10: 1. 3 points for code style: identifiers, indentation, minimization of mutability, etc. 2. 7 points for passing our JUnit tests. 3 Implementation requirements 1. Download the “starter pack” and copy its contents to the a4 package in your COMP 2522 assignments project. 2. The ArraySet class already contains some helpful instance variables and a constant. Read the method comments to better understand what each method is supposed to do. You must implement the following methods inside the ArraySet class: 1 (a) the ArraySet constructor (b) public boolean add(E newItem) (c) public boolean contains(E item) (d) public boolean remove(E item) (e) public Object[] toArray() (f) public void clear() (g) public int size() (h) public SetIterator iterator() (i) private void resize() 3. The ArraySet must contain an inner class called SetIterator. The SetIterator class is used internally by the ArraySet class to iterate over its elements. There are two methods to implement: (a) public boolean hasNext() (b) public E next() 4. Some helpful hints: (a) An implementation of a set can be realized in more than one way. For your assignment, you must implement the set by using an array whose elements are of type E. (b) Your implementation of the ArraySet class must support initially holding 10 items, i.e., it must have a capacity of 10. If there is an attempt to add one more item than the current size allows, i.e., the current size has increased to be equal to the capacity, the size of the set (its capacity) must double. The recommended way to do this is to create a new array that is twice the size of the current array and add all of the data from the current array to the new array. (c) When an item is added to the ArraySet, you should add the item to the end of the array; do not try to keep track of null entries in the underlying array. When an item is removed from the ArraySet, another item in the ArraySet must be moved into the recently vacated slot (you should determine which item to move). Remember this is okay because the ArraySet doesn’t maintain sequence. In the case of removal, your implementation must not move more than one element to remain efficient. (d) You must strictly adhere to the specification in this document and in the ArraySet comments. (e) To allow the the items of an ArraySet to be accessed, a SetIterator is used. A SetIterator for an instance of an ArraySet called s is an object that can access the items of s. During iteration, the SetIterator “refers to” an item in s (though how it refers to the element is your implementation decision). The SetIterator allows the user to access the ArraySet item that the SetIterator points to, advance the SetIterator to the next item in the ArraySet, and check whether there is another item in the ArraySet that have not yet been accessed by the SetIterator. (f) The only object that knows how to set up a SetIterator for an ArraySet is the ArraySet itself. For this reason, the ArraySet contains a single method called iterator() that returns a SetIterator for that set. Therefore, the ArraySet you implement has to include its own SetIterator that can be returned when its method iterator() is called. The following code snippet illustrates how a client can use a SetIterator to print out the people that are stored in a fictitious ArraySet of Person: ArraySet people = new ArraySet(); SetIterator it = people.iterator(); while( it.hasNext() ) { Person nextPerson = it.next(); System.out.println( nextPerson.toString() ); } (g) An easy way to define a SetIterator for an ArraySet is to define a class inside the ArraySet class named SetIterator. Such a class is called an inner class, of course (remember a nested class is static. Don’t use a nested class). That is what our ArraySet will do. There are several advantages to implementing the SetIterator as an inner class of the ArraySet class: 2 i. The client of an ArraySet won’t know that it exists. This is a good thing. All the client needs to know is that when they call the iterator() method they get back something (they don’t care exactly what) that iterates over the ArraySet’s elements. ii. The SetIterator has direct access to the private members of the enclosing class. In other words, your SetIterator can access the private members of your ArraySet class. This is really useful as the SetIterator will need to extract data from the ArraySet. iii. Your SetIterator will have a single data member that stores the index of the next item to be returned by the iterator. That’s it! Good luck, and have fun!
Credit card numbers follows certain patterns. A credit card number must have between 13 and 16 digits. It must start with:o 4 for Visa cards o 5 for Master cards o 37 for American Express cards o 6 for Discover cards In 1954, Habs Luhn of IBM proposed an algorithm for validating credit card numbers. The algorithm is useful to determine whether a card number is entered correctly or whether a credit card is scanned correctly by a scanner. Credit card numbers are generated following this validity check, commonly known as the Luhn check or Mod 10 check, which is described as follows ( for illustration, consider the card number 4388576018402626):1. Double every second digit from right to left. If double of a digit results in a two-digit number, add up the two digits to get a single digit number.2. Now add all single-digit number from the step above (Step 1 ). 4 + 4 + 8 + 2 + 3 + 1 + 7 + 8 = 373. Add all digits in the odd places from right to left in the card number. a. 6 + 6 + 0 + 8 + 0 + 7 + 8 + 3 = 384. Sum the results from the above two step ( Step 2 and Step 3). 37 + 38 = 755. If the result from the above step ( step 4 ) is divisible by 10, the card is valid; otherwise, the card is invalid. For example, the card number 4388576018402626 is invalid, but the card number 4388576018410707 is valid.Design and Implement the above algorithm in Java Recursively. Your algorithm should prompt the user to enter a credit card number as a long integer. Display whether the number is a valid or invalid credit card number. Design your program to use the following methods: These methods should be done recursively… Make sure you have several runs, i.e. several testing conditions. //Return if the card number is valid Public static Boolean isValid(long number)//Get the result from step 2 Public static int sumOfDoubleEvenPlace( long number )//Return this number it is a single digit, otherwise, return the sum of the two //digits Public static int getDigit( int number )//Return sum of sumOfOddPlace( long number ) Public static int sumOfOddPlace( long number ) //Return the number of digits in digit Public static int getSize( long number )//Return the first k number of digits from the number. If the number of digits in number is less than k, return number Public static long getPrefix( long number, int k )Here are some runs of the programEnter a credit card number as a long integer4388576018410707 4388576018410707 is a valid credit card number.Enter a credit card number as a long integer4388576018402626 4388576018402626 is a valid credit card number.Infix to Postfix Conversion and The Evaluations of the Postfix Expression. You are to design and implement and algorithm in Java, to input an Infix expression , convert to a postfix expression and finally evaluate the postfix expression… Follow the examples done during class lectures… Problem description: 1. We are used to infix notation – ”3 + 4” – where the operator is between the operands. There is also prefix notation, where the operand comes before the operands. A Reverse Polish Notation calculator uses postfix notation, and was one of the first handheld calculators built. At first, it seems confusing, but is very logical once you think about it. Instead of doing ”2 + 3 + 4”, you may do ”2 [enter] 3 [enter] 4 [enter] + +”. 2. You will be implementing a conversion from infix to RPN and then perform an RPN calculator for this assignment.3. How does an RPN calculator work? It is quite simple in principle. The calculator keeps a stack – a list of numbers. When you type a number and hit ”enter”, it pushes, or appends the number to the stack. So you build up a stack of numbers. Whenever you click an operand, it applies the operator to the top of the stack. In the previous example, it builds a stack like [2, 3, 4]. When you hit the first ”+”, it pops off the top/most recent two elements off the list and ”pluses” them. Lastly, it pushes the result back on the stack, so it looks like [2, 7]. When you hit plus again, it pops off the two elements (so the stack is temporarily empty), adds them, and pushes it back on the stack, so you get [9] . 3 What you need to do For the first part of this assignment, think about what classes you need. Java has a Stack class for you, but write your own ( do nt use the Java Stack class). Use encapsulation, think about what methods it should have, and call it something like CalculatorStack. Add an option to ”roll” the stack; shift it left or right by one (and the end number rollls) to the other end). Other classes may include Controller, Handler, or SpecialOperationsHandler. 4 Why? • It’s one of the better assignments I can think of as a teaching tool • RPN calculators are awesome – they’re far more logical than infix calculators once you get used to them • You should learn RPN calculators; besides the historical importance, it forces you to think differently. Several example done during class lectures. The following code below is a sample on how to evaluate the RPN expression …Design and Implement an Algorithm in Java to solve the following problem in solving linear equations using the Gaussian Elimination method. Definition: A system of linear equations can be placed into matrix form. Each equation becomes a row and each variable becomes a column. An additional column is added for the right hand side. A system of linear equations and the resulting matrix are shown. Sample of linear equations … 3x + 2y – 4z = 3 2x + 3y + 3z = 15 5x – 3y + z = 14 becomes the augmented matrix … (transform the Linear Equation into Matrix form) x y z Constants 3 2 -4 3 2 3 3 15 5 -3 1 14 The goal when solving a system of equations is to place the augmented matrix into reduced row-echelon form, if possible. There are three elementary row operations that you may use to accomplish placing a matrix into reduced row-echelon form. Each of the requirements of a reduced row-echelon matrix can satisfied using the elementary row operations. • If there is a row of all zeros, then it is at the bottom of the matrix. Interchange two rows of a matrix to move the row of all zeros to the bottom. • The first non-zero element of any row is a one. That element is called the leading one. Multiply (divide) the row by a non-zero constant to make the first non-zero element into a one. • The leading one of any row is to the right of the leading one of the previous row. Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zeros. By making the numbers under the leading ones into zero, it forces the first non-zero element of any row to be to the right of the leading one of the previous row. • All elements above and below a leading one are zero. Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zero. The difference here is that you’re clearing (making zero) the elements above the leading one instead of just below the leading one. Definition of pivoting? The objective of pivoting is to make an element above or below a leading one into a zero. The “pivot” or “pivot element” is an element on the left hand side of a matrix that you want the elements above and below to be zero. Normally, this element is a one. If you can find a book that mentions pivoting, they will usually tell you that you must pivot on a one. If you restrict yourself to the three elementary row operations, then this is a true statement. However, if you are willing to combine the second and third elementary row operations, you come up with another row operation (not elementary, but still valid). • You can multiply a row by a non-zero constant and add it to a non-zero multiple of another row, replacing that row. So what? If you are required to pivot on a one, then you must sometimes use the second elementary row operation and divide a row through by the leading element to make it into a one. Division leads to fractions. While fractions are your friends, you’re less likely to make a mistake if you don’t use them. What’s the catch? If you don’t pivot on a one, you are likely to encounter larger numbers. Most people are willing to work with the larger numbers to avoid the fractions. The Pivot Process Pivoting works because a common multiple (not necessarily the least common multiple) of two numbers can always be found by multiplying the two numbers together. Let’s take the example we had before, and clear the first column. x y z Const 3 2 -4 3 2 3 3 15 5 -3 1 14 Selecting a Pivot • Pick the column with the most zeros in it. • Use a row or column only once • Pivot on a one if possible • Pivot on the main diagonal • Never pivot on a zero • Never pivot on the right hand side Since there is no one in the first row, we have two options: Either we divide the first row by three and work with fractions, or we pivot on the three and get large numbers. That is the option I’m going to use. I’ll pivot on the three in R1C1. Go ahead and circle that as the pivot element. Depending on your browser, you may see the pivot elements circled in red or just with a * in front of it. x y z Const *3 2 -4 3 2 3 3 15 5 -3 1 14 The idea is to make the boxed numbers into zero. Using the combined row operation that could be done by 3R2 – 2R1 → R2 and 3R3 – 5R1 → R3. The only row not being changed is the row containing the pivot element (the 3). The whole point of the pivot process is to make the boxed values into zero. Go ahead and rewrite the pivot row and clear (make zero) the pivot column. x y z Const *3 2 -4 3 0 0 To replace the values in row 2, each new element is obtained by multiplying the element being replaced in the second row by 3 and subtracting 2 times the element in the first row from the same column as the element being replaced. To perform the pivot, place one finger on the pivot (circled number), and one finger on the element being replaced. Multiply these two numbers together. Now, place one finger on the boxed number in the same row as the element you’re replacing and the other finger in the pivot row and the same column as the number your replacing. Multiply these two numbers together. Take the product with the pivot and subtract the product without the pivot.x y z Const *3 2 -4 3 2 3 3 15 5 -3 1 14To replace the 3 in R2C2, you would take 3(3) – 2(2) = 9 – 4 = 5. To replace the 3 in R2C3, you would take 3(3) – 2(-4) = 9 +8 = 17. To replace the 15 in R2C4, you would take 3(15) – 2(3) = 45 – 6 = 39. To replace the -3 in R3C2, you would take 3(-3) – 5(2) = -9 – 10 = -19. To replace the 1 in R3C3, you would take 3(1) – 5(-4) = 3 + 20 = 23 To replace the 14 in R3C4, you would take 3(14) – 5(3) = 42 – 15 = 27.Here’s how the process looks. x y z rhs pivot row, copy 3 pivot row, copy 2 pivot row, copy -4 pivot row, copy 3 pivot column, clear 0 3(3) – 2(2) 5 3(3) – 2(-4) 17 3(15) – 2(3) 39 pivot column, clear 0 3(-3) – 5(2) -19 3(1) – 5(-4) 23 3(14) – 5(3) 27 Or, if you remove the comments, the matrix after the first pivot looks like this. x y z rhs 3 2 -4 3 0 5 17 39 0 -19 23 27 It is now time to repeat the entire process. We go through and pick another place to pivot. We would like it to be on the main diagonal, a one, or have zeros in the column. Unfortunately, we can’t have any of those. But since we have to multiply all the other numbers by the pivot, we want it to be small, so we’ll pivot on the 5 in R2C2 and clear out the 2 and -19. x y z Const 3 2 -4 3 0 *5 17 39 0 -19 23 27Begin by copying down the pivot row (2nd row) and clearing the pivot column (2nd column). Previously cleared columns will remain cleared. x y z Const 0 0 *5 17 39 0 0 Here are the calculations to find the next interation. Pay careful attention to the 3rd row where we’re subtracting -19 times a value. Since we’re subtracting a negative, I went ahead and wrote it as plus 19. x y z rhs 5(3) – 2(0) 15 pivot column, clear 0 5(-4) – 2(17) -54 5(3) – 2(39) -63 pivot row, copy 0 pivot row, copy 5 pivot row, copy 17 pivot row, copy 39 previously cleared 0 pivot column, clear 0 5(23) + 19(17) 438 5(27) + 19(39) 876 And the resulting matrix. x y z Const 15 0 -54 -63 0 5 17 39 0 0 438 876 Notice that all the elements in the first row are multiples of 3 and all the elements in the last row are multiples of 438. We’ll divide to reduce the rows.x y z Const 5 0 -18 -21 0 5 17 39 0 0 1 2 That had the added benefit of giving us a 1, exactly where we want it to be to pivot. So, we’ll pivot on the 1 in R3C3 and clear out the -18 and 17. Circle your pivot and box the other numbers in that column to clear. x y z Const 5 0 -18 -21 0 5 17 39 0 0 *1 2 Copy down the pivot row and clear the pivot column. Previously cleared columns will remain cleared as long as you don’t pivot in a row or column twice. x y z Const 0 0 0 0 0 0 *1 2 Notice that each time, there are fewer calculations to perform. Here are the calculations for this pivot. Again, since the value in the pivot column in the first row is -18 and we’re subtracting, I wrote it as + 18.x y z rhs 1(5) +18(0) 5 previously cleared 0 pivot column, clear 0 1(-21) + 18(2) 15 previously cleared 0 1(5) – 17(0) 5 pivot column, clear 0 1(39) – 17(2) 5 pivot row, copy 0 pivot row, copy 0 pivot row, copy 1 pivot row, copy 2 And the resulting matrix. x y z Const 5 0 0 15 0 5 0 5 0 0 1 2 Notice that the first and second rows are multiples of 5, so we can reduce those rows. x y z Const 1 0 0 3 0 1 0 1 0 0 1 2 And the final answer is x = 3, y = 1, and z = 2. You can also write that as an ordered triplet {(3,1,2)}. Hopefully, you noticed that when I worked this example, I didn’t follow the hints I gave. That’s because I wanted you to see what happens if you don’t pivot on a one. There was a one, on the main diagonal, in the original matrix, and it would have been better to start there.Summary • Pick your pivot element wisely. • Picking a column with zeros in it means less pivoting. • Picking a one as the pivot makes the numbers smaller, the multiplication easier, and leaves the non-zero elements in a cleared column the same (less pivoting) • Pivoting on the main diagonal means you won’t have to switch rows to put the matrix into reduced row-echelon form. • Do not pivot on a zero. • Do not pivot on the right hand side. • Only use a row or column once • Take the product with the pivot minus the product without the pivot Special Cases If you get a row of all zeros except for the right hand side, then there is no solution to the system. If you get a row of all zeros, and the number of non-zero rows is less than the number of variables, then the system is dependent, you will have many answers, and you need to write your answer in parametric form.You will implement an algorithm developed by Edsger Dijkstra (1930-2002) to solve the network shortest path problem in this lab. In addition to the algorithm, there are several other things required to make a program that solves the shortest path problem. First, it needs an interface that a user can interact with the program so that the program is “userfriendly.” Second, you need to create a “digital” network in the computer memory that the program can access. In this lab, you will first create the GUI of the program. Then, you will read a text file that defines the network into the computer memory and finally implement the Dijkstra algorithm. You have three lab sessions to complete this lab. The learning goals for you are to learn how to read from/write to text files and to use List and HashTable to implement the Dijkstra algorithm. The Dijkstra algorithm, developed a half century ago, finds the shortest path between a vertex and every other vertex on a network graph by constructing and searching a shortest path tree. The algorithm is widely used in modern routing applications that you encounter in everyday life (e.g., on Google map). The algorithm outlined on the wikipedia website has the following steps. Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step. Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step. 1. Assign to every node a distance value: set it to zero for our initial node and to infinity for all other nodes. 2. Mark all nodes as unvisited. Set initial node as current. 3. For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance. 4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal. 5. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node, considering all nodes in graph) as the next “current node” and continue from step 3.Figure 1 and Table 1 show the network on which you will find the shortest paths.PART 2: FILE I/O 1. First you need to create a text file that defines the network depicted in Figure 1. 2. We will use a simple edge definition format for this lab. Each edge on the network is recorded as having an ID, Node1, Node2, and Length (Table 1). 3. Two-way traffic is allowed on all edges. Use an ASCII text editor (e.g., Notepad.exe) to create the file and save it with a .txt extension name. Please refer to Tuesday’s lecture slides on how to use OpenFileDialog and SaveFileDialog controls to read from/write to a text file.We can define an abstract data type for single-variable polynomials (with non-negative exponents) by using a list. Let . If most of the coefficients ai are nonzero we could use a simple array to store the coefficients and write routines to perform addition, subtraction, multiplication, differentiation, and other operations on these polynomials.An array implementation would be adequate for dense polynomials, where most of the terms are present, but if and , then the running time is likely to be unacceptable. One cans see that if arrays were used, then most of the time is spend multiplying zeros and stepping through what amounts to nonexistent parts of the input polynomials. This is always undesirable.An alternative is to use a singly linked list. Each term in the polynomial is contained int one cell, and the cells are stored in decreasing order of exponents. For instance, the AssignmentStarting with the class Skeleton, below, Implement the Polynomial ADT using linked lists. You are Not to use the Java LinkedList class, you should “roll your own” list/node data types. Your project will be graded automatically, so you must make the Polynomial ADT it’s own class. However, you must include an application that demonstrates and tests the key functionality of your implementation. Your write/documentations up should include a discussion of what you used and the documentation html files generated by javadoc.public class Literal {// various constructors & accessors (not shown)double coefficient; int exponent;//if you roll your own list, then include “Literal next;” }public class Polynomial {private List terms ; // A list of literals // if you roll your own, then “private Literal head;”public Polynomial() { // constructor to be implemented } public void insert term(double coef, int exp){ // to be implemented } public Polynomial add(Polynomial rhs) { // to be implemented } public Polynomial multiply(Polynomial rhs) { // to be implemented } public String toString(){ // to be implemented use “^” to signify exponents } }GRADING : Documentations 10% Code Style 15% Functionality 75% ( 15% for each base operation supported +.-./,*,()) Extra Credit :do not require blanks (i.e. allow users to input “5+7*2” as well as “5 + 7 * 2″ ) 5% must be documented – it’s your responsibility to point it out) Extra Credit : support negative and positive numbers – unary +/- (i.e.allow users to input ” -5 + -7 * +2″ ) 5% must be documented – it’s your responsibility to point it out) Extra Credit : exponentials (use “^” operator associating right to left) 5% must be documented – it’s your responsibility to point it out) Extra Credit : modulo (use “%” operator same association as in JAVA ) 5% must be documented – it’s your responsibility to point it out)Banks lend money to each other. In tough economic times, if a bank goes bankrupt, it may not be able to pay back the loan. A bank’s total assets are its current balance plus its loans to other banks. The diagram in Figure 8.8 shows five banks. The banks’ current balances are 25, 125, 175, 75, and 181 million dollars, respectively. The directed edge from node 1 to node 2 indicates that bank 1 lends 40 million dollars to bank 2.
This assignment is designed to make sure you can load an image, manipulate the values, produce some output; see MATLAB tutorials on the course webpage (and search the web) for additional help. Use BrightSpace to submit your assignment. This assignment is to be done individually. Try to avoid using loops, as much as possible. Traditionally, loops are notoriously slow, due to MATLAB being an interpreted language. Instead try to use vectorized operations by applying a single MATLAB command (i.e., precompiled code) to an entire array. To get documentation for a particular MATLAB function, type help and the then command name. Finally, make sure you do the appropriate typecasting (i.e., uint8 and double) when working with images. You should submit a zip file that contains the following: • the images (e.g., JPEG or some other easy to recognize format) and • and your MATLAB files for the assignment, including “a0 script.m”; see the comments in “a0 script.m” for additional details. Your assignment must run fully by invoking “a0 script.m”. 1. Input images (a) Find two interesting images to use. They should be colour. You can find some classic vision examples at https://sipi.usc.edu/database/database.php?volume= misc. Make sure they are not larger than 512 × 512. Output: Display both images; see imshow() (Tip: Always make sure to set the display range of imshow() to a reasonable range for display, such as the minimum and maximum values of the image). 2. Colour planes (a) Load image 1 and store it in the variable img; see imread(). (b) Swap the red and blue channels of image 1 Output: Display new image (c) Create a monochrome image (call it img g) by selecting the green channel of image 1 Output: Display new image (d) Create a monochrome image (call it img r) by selecting the red channel of image 1 Output: Display new image 1 (e) Convert the image to grayscale; see rgb2gray() Output: Display new image 3. Replacement of pixels (a) Take the square of 100 × 100 pixels located in the centre of image 1 (grayscale version) and insert them into image 2 (grayscale version). Output: Display new image 4. Arithmetic and geometric operations (a) What is the minimum and maximum of the pixel values of img g? What is the mean? What is the standard deviation? How did you compute these? (b) Subtract the mean from all the pixels, then divide by the standard deviation, then multiply by 10 (if your image is zero to 255) or by 0.05 (if your image ranges from 0.0 to 1.0). Now add the mean back in. Output: Display new image (c) Shift img g to the left by 2 pixels. Output: Display new image (d) Subtract the shifted version of img g from the original. (Tip: Whenever performing arithmetic operations with images make sure you convert the image to a floating point type prior to usage, otherwise issues will arise since the default type is an unsigned integer.) Output: Display new image (e) Flip horizontally img g from the original, i.e., flip image left-to-right. Output: Display new image (f) Change the intensities of img g from the original, such that the lightest values appear dark and the darkest appear light. Output: Display new image 5. Image noise (a) Take the original colour image 1 and start adding Gaussian noise to the pixels in each colour channel. (Hint: Create a three-channel image containing Gaussian noise.) Increase the variance of the noise until the noise is somewhat visible; see randn(). To increase the noise variance, multiply the Gaussian noise output by the standard deviation you desire. What value for the standard deviation did you use? Output: Display new image1 Convolution (Total 25) 1. [5 points] Fill in the empty table (below-right) with the resulting image obtained after convolution of the original image (bottom-left image) with the following approximation of the derivative filter [1, 0, −1] in the horizontal direction. Assume that the image is zero padded. The origin is located at the top-left corner with coordinates [0, 0]. This question is to be done by hand; use fprintf() in MATLAB to output your response. -5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -7 2 1 1 3 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 3 1 1 5 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2. [5 points] Compute the gradient magnitude at pixels [2, 3], [4, 3] and [4, 6] in the left image in Q1.1 (the image pixels marked in bold). Hint: Assume the same derivative filter approximation used for the horizontal direction is used for the vertical direction. Use fprintf() in MATLAB to output your response. 1 3. [5 points] Write a convolution function, call it MyConv, that takes in as input an arbitrary image and kernel. Your convolution function should only use loops (i.e., do not use any of the prebuilt MATLAB functions, e.g., imfilter). For the boundary cases, assume that the values outside the image are zero. (HINT: Pad the image prior to convolution with zeros.) Your code should appropriately flip the input kernel. 4. [5 points] Compare the output of your convolution function with the output of imfilter using a 2D Gaussian kernel with standard deviation 2 and dimensions 13 × 13. Specifically, subtract the convolution outputs and display the absolute value using reasonable scalings for imshow. Is there any difference between the outputs? Make sure that imfilter is assuming that the boundaries are zero outside the image. Use fprintf() in MATLAB to output your response. 5. [5 points] Determine the execution times between convolving a 640 × 480 image by a 2D Gaussian with a standard deviation of 8 and separably convolving the same image with two 1D Gaussians each with a standard deviation of 8. Use imfilter to perform the convolution and fspecial to generate the kernels (with the “three-sigma rule”). What do you observe? In MATLAB, if you place the command tic before your script and toc after your script, MATLAB will return the total execution time. Use fprintf() in MATLAB to output your response. 2 Canny edge detection (Total 35 for CPS843 and 45 for CP8307) 1. [30 points] Implement the Canny edge detection algorithm as a MATLAB function, call it MyCanny, up to but not including the hysteresis step, as described in class and the handout available on the course webpage. Your function should take as input a greyscale image and the edge detection parameters and return the Canny edge binary image. For this question, there are two edge detection parameters, the standard deviation, σ, of the Gaussian smoothing filter and the gradient magnitude threshold, τ. Note, if you implement the peak/ridge detection step correctly the output of your program should NOT have “thick” edges! In addition to turning in your source code for the Canny edge detector, submit a MATLAB script that runs your edge detector on the test image provided at this link and on an image of your own choosing. Your Canny output images should use the best set of parameters you find for each input image. For obvious reasons, you are excluded from using MATLAB’s edge() function in your own code but are encouraged to run the edge() function to get a sense of what the correct output should look like. 2. [5 points] Implement the Gaussian convolution as a sequence of horizontal and vertical convolutions, i.e., a separable filter. 3. [10 points] (CP8307 question, bonus for CPS843) Add the hysteresis mechanism to the function you wrote for Q2.1. For hysteresis thresholding, a high and low threshold is specified by the user beforehand. The process begins by marking all pixels with gradient magnitudes above the high threshold as a “discovered” definite edge. These pixels are placed into a queue and become the starting points for a breadth first search (BFS) algorithm. Run the BFS by iterating through the queue of pixels. The hysteresis process terminates when the queue is empty. All adjacent pixels (one of the eight neighbours) are treated as connected nodes to the current pixel removed from the queue. The criteria for adding a new pixel to the queue is given by: an adjacent pixel that has not been previously discovered and has a gradient magnitude greater than the low threshold. Adjacent pixels that meet the criteria are subsequently added to the BFS queue. Every adjacent pixel is also marked as discovered once it is checked against the criteria. 3 Seam carving (Total 20 points) 1. [20 points] Seam carving is a procedure to resize images in a manner that preserves “important” image content. A video demo is available on YouTube. The general steps for seam carving are as follows: (a) Compute the energy image, E, for the input image, e.g., the sum of the gradient magnitude images computed for each of the three colour channels of the input image. (b) Create a scoring matrix, M, with spatial image dimensions matching those of the input image. 2 (c) Set the values of the first row of the scoring matrix, M, to match those of the energy image, E. (d) Set the values of every entry in the scoring matrix to the energy value at that position and the minimum value in any of the neighbouring cells above it in the seam, i.e., M(x, y) = E(x, y) + min M(x − 1, y − 1), M(x, y − 1), M(x + 1, y − 1) , (1) where M(x, y) is the cost of the lowest cost seam crossing through that point. This minimization procedure is an instance of dynamic programming. (e) Find the minimum value in the bottom row of the scoring matrix. The corresponding position of the minimal value is the bottom of the optimal seam. (f) Using M(x, y), trace back up the seam by following the smallest value in any of the neighbouring positions above. (g) Remove the seam from the image. (h) To reach a desired resized image, you will have to repeat the above procedure. Note that you will have to recompute the energy matrix (and scoring matrix) each time to take into account changes in the resized image. Your task is to write a MATLAB function, call it MySeamCarving, that takes in an image and the desired new resolution by removing the necessary horizontal and vertical seams and returns the resized image. Implement the seam carving routine with a single helper function, call it CarvingHelper, that removes all the necessary vertical (horizontal) seams. You first call the helper function to remove the vertical (horizontal) seams, transpose the result of this function and then call the seam removal function again with the transposed image as the input to remove the horizontal (vertical) seams. In addition to submitting your code, submit resizing outputs for the Ryerson image to 640 × 480 and 720 × 320. Also submit an image of your own and its resized output. 2. [10 points] (Bonus): Implement image expansion by inserting seams, see the original paper for details.1 Least Squares Fitting of a Plane 1. [5 points] Write a MATLAB script that generates 500 data points for a plane, z = αx + βy + γ, with additive Gaussian noise. (HINT: See the MATLAB example in the lecture slides for generating points on a line with additive noise.) 2. [5 points] Write a MATLAB script to estimate the parameters for the point set in Q1.1 based on all 500 data points using least-squares fitting. You will need to rewrite the equation of a plane as a non-homogeneous matrix equation, Ax = b, where x is a vector of unknowns (α, β, γ) >. 3. [5 points] Print to the screen the absolute error you found between each parameter of the ground truth and estimated planes? 2 RANSAC-based Image Stitching The goal of this question is to write a simple mosaic/panorama application. A panorama is a wide-angle image constructed by compositing together a number of images with overlapping fields-of-views in a photographically plausible way. Part A: [30 points] In this part, you will write code to construct a mosaic based on an affine transformation. The images you will work with are shown in Fig. 1 and can be downloaded here: image 1 and image 2. An example result is shown in Fig. 2. An affine transformation is equivalent to the composed effects of translation, rotation, isotropic scaling and shear. Formally, an affine transformation of an image coordinate, x1, is given by the matrix equation x2 = Tx1 + c. The unknowns are given by the elements in the 2 × 2 matrix T and the 2 × 1 vector c. Rewrite the affine equation as a non-homogeneous matrix equation, Ax = b, where x is a vector containing the the six unknown elements of T and c. Since each point correspondence yields two equations and there are six unknowns, a minimum of three point correspondences are required. (Real mosaics are constructed with a homographic image transformation. This transformation is more general than an affine transformation. Nonetheless, the same basic robust estimation architecture you are implementing in this part of the assignment applies when constructing a homography-based mosaic in Part B. 1. Preprocessing Load both images, convert to single and to grayscale. 1 Figure 1: Images used to create the Parliament panorama using an affine transformation. 2. Detect keypoints and extract descriptors Compute image features in both images. The feature detector and descriptor you will be using is SIFT. Use the publicly available VLFeat library to compute SIFT features. The instructions for setting up VLFeat in MATLAB are available here: instructions. Also, check out the VLFeat SIFT demo. Compute SIFT feature descriptors using: [f, d] = vl sift(img); 3. Match features Compute distances between every SIFT descriptor in one image and every descriptor in the other image. You can use this code for fast computation of (squared) Euclidean distance. 4. Prune features Select the closest matches based on the matrix of pairwise descriptor distances obtained above. You can select all pairs whose descriptor distances are below a specified threshold, or select the top few hundred descriptor pairs with the smallest pairwise distances. 5. Robust transformation estimation Implement RANSAC to estimate an affine transformation mapping one image to the other. Use the minimum number of pairwise matches to estimate the affine transformation. Since you are using the minimum number of pairwise points, the transformation can be estimated using an inverse transformation rather than least-squares. Inliers are defined as the number of transformed points from image 1 that lie within a user-defined radius of ρ pixels of their pair in image 2. You will need to experiment with the matching threshold, ρ, and the required number of RANSAC iterations. For randomly sampling matches, you can use the MATLAB functions randperm or randsample functions. 6. Compute optimal transformation Using all the inliers of the best transformation found using RANSAC (i.e., the one with the most inliers), compute the final transformation with least-squares. 7. Create panorama Using the final affine transformation recovered using RANSAC, generate the final mosaic and display the color mosaic result to the screen; your result should be similar to the result in Fig. 2. Warp one image onto the other using the estimated transformation. To do this, use MATLAB’s maketform and imtransform functions. Create a new image big enough to hold the mosaic and composite the two images into it. You can create the mosaic by taking the pixel with the maximum value from each image. This tends to produce less artifacts than taking the average of warped images. To create a color mosaic, apply the same compositing step to each of the color channels separately. 2 Figure 2: An example (affine) panorama result using the Parliament images. 3 Part B: [10 points] In this part, you will write code for constructing a panorama based on a homography transformation. The images you will work with are shown in Fig. 3 and can be downloaded here: image 1 and image 2. An example result is shown in Fig. 4. You should reuse the code from Part A but swap out the parts that refer to the affine transformation with the homography. The minimum number of point correspondences to estimate a homography is four. Using a homography yields a set of homogeneous linear equations, AX = 0. The solution to both the system of homogeneous equations consisting of four point correspondences and homogeneous least squares, X ∗ = argmin X kAXk (1) subject to the constraint kXk = 1, (2) is obtained from the singular value decomposition (SVD) of A by the singular vector corresponding to the smallest singular value: [U,S,V]=svd(A); X = V(:,end); 1. Using your RANSAC-based homography code generate the mosaic using the Egerton Ryerson images and display the color mosaic result to the screen. 2. Run your code on an image pair of your own choosing and display the color mosaic result to the screen. Make sure the images you choose have significant overlap; otherwise, you will not be able to establish correspondences. Further, for a homography to be valid, the images can either be obtained from rotating in the same place OR from multiple vantage points if the scene is planar or approximately planar. Figure 3: Images used to create the Egerton Ryerson statue panorama using a homography transformation. 4 Figure 4: An example (homography) panorama result using the Egerton Ryerson statue images. 5 Bonus: 1. [10 points] Experiment with combining image pairs where establishing correspondence is rendered difficult because of widely varying images sources. These images should have a Ryerson theme. Possible ideas include: (i) combining a modern and a historical view1 of the same location, such as these ones and (ii) combining images taken from different times of day or different seasons. Display the result to the screen and indicate this is for the bonus in the MATLAB Command Window. 2. [5 points] Experiment with image blending techniques to remove salient seems between images; see Szeliski (the course textbook) Chapter 9. Display the before and after blending color mosaic results to the screen and indicate in the MATLAB command window this is for the bonus. Submission Details Submit all MATLAB files and images required for the various parts of the assignment to run. Your submission should include a MATLAB script named a2.m for the grader to run. The script should break up the assignment with pause() commands, so that the grader can press “Enter” to step through all of your figures and written answers. If your code does not run we cannot mark it. 1The Ryerson archives may be able to assist with obtaining suitable historical imagery.1 Face detection (30 points) In this part of the assignment, you will be implementing various parts of a sliding window object detector [1]. In particular, you are tasked with implementing a multi-scale face detector. You need to train an SVM to categorize 36 × 36 pixel images as “face” or “not face”, using HOG features. Use the VLFeat library (https://www.vlfeat.org/) for both HOG and the SVM. You are given: • a directory of cropped grayscale face images, called cropped training images faces, • a directory of images without faces, called images notfaces, • a skeleton script called generate cropped notfaces.m, • a skeleton script called get features.m, • a skeleton script called train svm.m, and • a helper script called report accuracy.m (do not edit this file). You need to do the following: 1. [5 points] Using the images in images notfaces, generate a set of cropped, grayscale, non-face images. Use generate cropped notfaces.m as your starting point. The images should be 36 × 36, like the face images. 2. [5 points] Split your training images into two sets: a training set, and a validation set. A good rule of thumb is to use 80% of your data for training, and 20% for validation. 3. [5 points] Generate HOG features for all of your training and validation images. Use get features.m as your starting point. You are free to experiment with the details of your HOG descriptor. A useful resource is the VLFeat tutorial on HOG: https://www.vlfeat.org/overview/hog.html 1 4. [5 points] Train an SVM on the features from your training set. Use train svm.m as your starting point. The parameter “lambda” will help you control overfitting. A useful resource is the VLFeat tutorial on SVMs: https://www.vlfeat.org/matlab/vl_svmtrain.html. Note: If you test your SVM on the training set features, you should get near perfect accuracy. 5. [5 points] Test your SVM on the validation set features. From the SVM’s performance at this step, try to refine the parameters you chose in the earlier steps (e.g., the cell size for HOG, and lambda for the SVM). Save your final SVM (weights and bias) in a mat file called my svm.mat, and include it in your submission. 6. [5 points] Write a script called recog summary.m, which prints out a brief summary of your approach (using fprintf). Be sure to include your best accuracy on the validation set, and what you did to improve performance. 2 Multi-scale face detection (35 points) In this part, you need to create a multi-scale sliding window face detector. In addition to the files from Part 1, you are given: • an image called class.jpg, • a skeleton script called detect.m, • a directory of grayscale test images, called test images, • bounding box annotations for the test images, called test images gt.txt (do not edit this file), • a helper script called look at test images gt.m, • a helper script called evaluate detections on test.m (do not edit this file), and • a helper script called VOCap.m (do not edit this file). You need to do the following: 1. Get familiar with the test set, and how bounding boxes work, by exploring look at test images gt.m. 2. [5 points] Write a single-scale sliding window face detector, using the SVM you trained in Part 1. Use detect.m as your starting point. Evaluate your detector by calling evaluate detections on test.m with the appropriate arguments. 3. [10 points] Upgrade your face detector so that it does not make overlapping predictions. This is called non-maximum suppression. Detectors typically yield multiple high scores over a region. You want to report the single best bounding box per object. Since only a single bounding box is reported in the ground truth, failure to do so will result in a reduction in the test accuracy score. You may want to inspect the code in evaluate detections on test.m to how to calculate area of intersection, and area of union. 4. [10 points] Upgrade your face detector so that it makes predictions at multiple scales. 5. [5 points] Use your face detector on class.jpg, and plot the bounding boxes on the image. 6. [5 points] Write a script called detect summary.m, which prints out a brief summary of your approach (using fprintf). Be sure to include your best accuracy on the test set, what you did to improve performance, and a brief qualitative evaluation of your performance on class.jpg. Bonus points will be awarded to the top-performing classifiers on class.jpg. Secret ground-truth labels (bounding boxes for faces) have already been generated. Do not use class.jpg in anyway to train your detector. If you would like to compete for these points, include a single script called detect class faces.m which runs the full detection pipeline. This script should: 1. load your SVM from a saved file (my svm.mat), 2 2. generate features from the image at multiple scales, 3. classify the features, 4. suppress overlapping detections, 5. generate an N × 4 matrix of bounding boxes called bboxes, where N is the number of faces you detect, 6. generate an N × 1 matrix of SVM scores called confidences, and 7. plot the bounding boxes on the image. The marker will run this script, followed by an evaluation script that will use your bboxes and confidences to generate an average precision score. The top three performing groups will get points as follows: 1st place: 30 points, 2nd place: 15 points, 3rd place: 10 points. Feel free to research ways to improve your detector’s performance, aside from inputting detections manually. For example, it may help to add new training data to the existing set (e.g., training data from another dataset or augmenting the existing set by applying image transformations to some subset of the images, such as left-right flipping), revise your training approach (e.g., use hard negative mining1 ) or add some colour cues to the feature vector. Good luck! References [1] Navneet Dalal and Bill Triggs. Histograms of oriented gradients for human detection. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 886–893, 2005. Acknowledgement: The face detection portion of this assignment is adapted from one created by Prof. James Hayes (Georgia Tech). 1Hard negative mining [1] is a training scheme to improve the performance of a detector. It begins with training a detector on a set of positive examples and an initial set of negative ones. Following this initial training stage, negative examples that are incorrectly classified by the initial model are collected to form a set of hard negatives. These hard negatives are added to the negative training set and a new model is trained. This process may be repeated several times.1 Optical flow estimation (45 points) In this part, you will implement the Lucas-Kanade optical flow algorithm that computes the pixelwise motion between two images in a sequence. Compute the optical flow fields for the three image sets labeled synth, sphere and corridor. Before running your code on the images, you should first convert your images to grayscale and map the intensity values to the range [0, 1]. 1. [20 points] Recall from lecture, to compute the optical flow at a pixel, compute the spatial derivatives (in the first frame), Ix and Iy, compute the temporal derivative, It , and then over a window centred around each pixel solve the following: P P IxIx P P P P IxIy IxIy P P IyIy ! u v ! = − P P P P IxIt IyIt ! . (1) Write a MATLAB function, call it myFlow, that takes as input two images, img1 and img2, the window length used to compute flow around a point, and a threshold, τ. The function should return three images, u and v, that contain the horizontal and vertical components of the estimated optical flow, respectively, and a binary map that indicates whether the flow is valid. To compute spatial derivatives, use the five-point derivative of Gaussian convolution filter (1/12)*[-1 8 0 -8 1] (make sure the filter is flipped correctly); the image origin is located in the top-left corner of the image, with the positive direction of the x and y axes running to the right and down, respectively. To compute the temporal derivative, apply Gaussian filtering with a small σ value (e.g., 3 × 3 filter with σ = 1) to both images and then subtract the first image from the second image. Since Lucas-Kanade only works for small displacements (roughly a pixel or less), you may have to resize the input images (use MATLAB’s imresize) to get a reasonable flow field. Hint: The (partial) derivatives can be computed once by applying the filters across the entire image. Further, to efficiently compute the component-wise summations in (1), you can apply a smoothing filter (e.g., box filter, Gaussian, etc.) on the image containing the product of the gradients. Recall, the optical flow estimate is only valid in regions where the 2×2 matrix on the left side of (1) is invertible. Matrices of this type are invertible when their smallest eigenvalue is not zero, or in practice, greater than some threshold, τ, e.g., τ = 0.01. At image points where the flow is not computable, set the flow value to zero. 2. [5 points] Visualize the flow fields using the function flowToColor. Play around with the window size and explain what effect this parameter has on the result. 1 3. [10 points] Another way to visualize the accuracy of the computed flow field is to warp img2 with the computed optical flow field and compare the result with img1. Write a function, call it myWarp, that takes img2 and the estimated flow, u and v, as input and outputs the (back)warped image. If the images are identical except for a translation and the estimated flow is correct then the warped img2 will be identical to img1 (ignoring discretization artifacts). Hint: Use MATLAB’s functions interp2 (try bicubic and bilinear interpolation) and meshgrid. Be aware that interp2 may return NaNs. In particular, this may occur around the image boundaries, since data is missing to perform the interpolation. Make sure your code handles this situation in a reasonable way. Visualize the difference between the warped img2 and img1 by: (i) take the difference between the two images and display their absolute value output (use an appropriate scale factor for imshow) and (ii) using imshow display img1 and the warped img2 consecutively in a loop for a few iterations, the output should appear approximately stationary. When running imshow in a loop, you will need to invoke the function draw now to force MATLAB to render the new image to the screen. 4. [10 points] In this question you will implement the Kanada-Lucas-Tomasi (KLT) tracker. The steps to implement are as follows: • Detect a set of keypoints in the initial frame using the Harris Corner detector. Here, you can use the code outlined in the lecture as a starting point. • Select 20 random keypoints in the initial frame and track them from one frame to the next; for each keypoint, use a window size of 15 × 15. The tracking step consists of computing the optical flow vector for each keypoint and then shifting the window, i.e., x t+1 i = x t i + u and y t+1 i = y t i + v, where i denotes the keypoint index and t the frame. This step is to be repeated for each frame using the estimated window position from the previous tracking step. • Discard any keypoints if their predicted location moves out of the frame or is near the image borders. Since the displacement values (u, v) are generally not integer value, you will need to use interpolation for subpixel values; use interp2. • Display the image sequence and overlay the 2D path of the keypoints using line segments. • Display a separate image of the first frame and overlay a plot of the keypoints which have moved out of the frame at some point in the sequence. For this question, you will use the images from the Hotel Sequence.
GoalYou will write a program in C, in the Ubuntu Linux shell environment, to translate an encrypted message into ASCII characters and print out the decrypted message to the screen. The encrypted bytes, set up as array of unsigned chars, can be found here: ciphertext.txtLearning Objectives• familiarize yourself with the Linux programming environment• write a small program in C that is modular, correctly designed and documented• manipulate values at the bit levelInstructions:1. Support Functions:• get/set/clear bitYou will implement the following bit manipulation functions, just as we saw in class:unsigned char getBit(unsigned char c, int n) returns the value of the nth bit of character cunsigned char setBit(unsigned char c, int n) returns the value of character c, with bit n set to 1unsigned char clearBit(unsigned char c, int n) returns the value of character c, with bit n set to 0• rotateYou will implement two functions that perform a circular rotation of the bits in a byte. One function is a rotation to the left, and the other is a rotation to the right. The function prototypes are the following:unsigned char rotl(unsigned char c) returns the value of c with its bits shifted left in a circular fashionunsigned char rotr(unsigned char c) returns the value of c with its bits shifted right in a circular fashion• swap two bitsYou will implement a function that swaps two bits in a byte. The function prototype is the following:unsigned char swapBits(unsigned char c, int pos1, int pos2)The function returns the value of c with its bits in positions pos1 and pos2 switched with each other.• encryptThe heart of the decryption algorithm (depicted in Figure 1) is the encrypt function, which is a permutation cipher that takes one byte and changes some of its bits depending on the value of a key. The result is the changed byte. You will implement this function, using the following prototype:unsigned char encrypt (unsigned char c, unsigned char key)The overall logic of the encrypt function is the following: start with the value of the c as the basis for the resulting byte examine each bit of the key, starting at the most significant bit if the current bit of the key has value 0, swap the following two bits of the resulting byte: the bit in the current bit position, and the bit two positions to the left (circling back to the least significant bits, if necessary) if the current bit of the key has value 1, perform a circular right shift on the resulting byteCOMP 2401 — Assignment #1 Fall 2013 2/32. Decryption algorithmThe decryption algorithm has the following structure:Figure 1 — Decryption AlgorithmThe encrypted message, known as ciphertext, is processed one byte at a time. It is shown in Figure 1 as C0 through Cn, where n is the length of the ciphertext. The plaintext is the corresponding readable, decrypted byte. It is shown as P0 through Pn. The Key and the initialization vector (IV) are initial values that are known beforehand. You can find these values in a header file located here: a1Defs.hYou will implement the decryption algorithm, as depicted in Figure 1. Your program will process the ciphertext one byte at a time, and print out the corresponding plaintext bytes.The algorithm works as follows. At every iteration i:• encrypt the value of IVi using the key• exclusive-or (XOR) the value of Ci with the encrypted IVi to compute the value of Pi• perform a circular left shift on the value of the encrypted IVi to compute the value of IVi+1Notes: You may use the XOR bitwise operator in C. The sizeof function can compute the length of the ciphertext.Constraints• you must include the given header file in your program and use the function prototypes exactly as stated• do not use any global variables• you must use all the support functions that you implemented in Part 1, and reuse functions everywhere possible• your program must be thoroughly commented• programs that do not compile, do not execute, or violate any constraint are subject to severe deductions• late assignments are never acceptedCOMP 2401 — Assignment #1 Fall 2013 3/3SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source code• all data files required for your program to execute• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation commando launching and operating instructionsGrading• Marking breakdown:ComponentMarksget/set/clear bit functions6rotate functions20swap two bits function10encrypt function35decryption algorithm24printing result5• Assignment grade: Your grade will be computed based on two criteria:o completeness of the program functionality and its executiono quality of the implementation You must familiarize yourself with the grading rules• Bonus marks: Up to 5 extra marks are available for fun and creative additional featuresGoal You will write a program in C, in the Ubuntu Linux shell environment, to simulate the use and operation of a function call stack. Every time a function is called, a new stack frame is created to contain information about that function, and the stack frame is added to the function call stack in LIFO (last-in-first-out) order. When the function returns, the corresponding frame is removed from the call stack.In this assignment, you will:• define the data types and structures required to represent the function call stack; you will use arrays to represent all collections of data• write a main function that prompts the user for a collection of integers and calls one of two given sum functions (one iterative and one recursive) to add the integers together• modify the given sum functions to call instrumentation functions upon entry and return• write two instrumentation functions: one that initializes and adds a frame to the function call stack when a sum function is entered, and one that removes a frame from the call stack when a sum function returns; both instrumentation functions output the contents of the call stackLearning Objectives• understand and modify existing code• work with arrays and perform simple pointer manipulations• get familiar with the basic operation of the function call stack mechanism• compare the operation of the call stack using iterative and recursive function calls• practice pass-by-value and pass-by-reference parameter passing• use standard I/O function calls to interact with a user• integrate basic error checking with user I/OInstructions1. Main and supporting functionsWrite a main function and supporting functions that do the following:• define the function call stack variableo there must be only one instance of the function call stack in the entire program; do not make copies!o this is not a global variable• prompt the user to input the values of an integer array; you can start by prompting for the number of integers• prompt the user to select which sum function to call (iterative or recursive)• call the appropriate sum function; you will use the code for the sum functions found here: a2Loop.c• display the resulting sum to the userYour program must use the definitions in the header file found here: a2Defs.hCOMP 2401 — Assignment #2 Fall 2013 2/32. Data typesModify the given header file to define the following data types required to simulate the function call stack:• StackType corresponds to the function call stack and holds the frames currently on the stack• FrameType holds the data for a frame corresponding to a specific function; this includes the function name and information about its parameters• VarType holds the information for a specific parameterThe data types that you define must work with the stack utility functions found here: a2Stack.c3. Instrumenting the sum functionsModify both sumIterative and sumRecursive functions (found in a2Loop.c) to call the instrumentation functions on entry and return. The sum functions must call enterSumFunc immediately upon entry to initialize a stack frame corresponding to the sum function. They must call leaveSumFunc when the sum function returns.4. Instrumentation functionsImplement the two instrumentation functions:void enterSumFunc(StackType *stkPtr, char *fname, int num, int *arr, int *sum)void leaveSumFunc(StackType *stkPtr)• enterSumFunc creates a new stack frame to store information about one of the sum functions, including its name (sumIterative or sumRecursive) and the parameters passed to it; enterSumFunc must:o initialize a new stack frameo set the frame’s function name to the value in fnameo initialize the frame’s parameter data with information about the parameters passed to the sum function num represents the number of elements to be added together by the sum function arr is the array of integers to be added together sum points to the result of the sum functiono add the new frame as the next frame in LIFO sequence on the call stack pointed to by stkPtro output the contents of the function call stack, using the given dumpStack function• leaveSumFunc prints out the contents of the function call stack when one of the sum functions returns, using the given dumpStack functionConstraints• Design:o you must separate your code into modular, reusable functionso never use global variableso compound data types must be passed by reference, not by value• Reuse:o you must include the given header file in your program and use its function prototypes exactly as definedo you must use the sum functions found here: a2Loop.co you must use, without modification, the stack utility functions found here: a2Stack.c• Implementation:o your program must perform all basic error checkingo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductionsCOMP 2401 — Assignment #2 Fall 2013 3/3SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionsGrading• Marking breakdown:ComponentMarksmain and support functions25data types20instrumenting sum functions20instrumentation functions35• Assignment grade: Your grade will be computed based on two criteria:o completeness of the program functionality and its executiono quality of the implementation You must familiarize yourself with the grading rules• Bonus marks: Up to 5 extra marks are available for fun and creative additional featuresGoal You will modify your program from Assignment #2 to simulate a function call stack, implemented as a linked list of frames, using C in the Ubuntu Linux environment.In this assignment, you will:• define the data types and structures required to represent the function call stack as a linked list of frames• write supporting functions to manage the function call stack• modify the instrumentation functions to work with the call stack implemented as a linked list• change the existing call stack output functions to print to a file instead of standard outputLearning Objectives• perform more complex pointer manipulations by implementing a linked list• work with dynamically allocated memory• practice using double pointers in pass-by-reference parameter passing• use file I/O function calls to output to a file• Note: Of course, linked lists are not the best underlying data structure for representing a stack. The use of linked lists in this assignment is for exclusively pedagogical purposes.Instructions1. Data typesModify the function call stack data type, so that the call stack is implemented as a singly linked list of frames, exactly as we saw in the “Advanced Linked Lists” section of the course notes:• StackType corresponds to the function call stack and contains a pointer to the head of the linked list of frames• FrameNodeType represents a node in the linked list• your main function must define the function call stack as dynamically allocated memoryo there must be only one instance of the function call stack in the entire program; do not make copies!o this is not a global variableNotes:• your program must use the definitions in the header file found here: a3Defs.h• the header file declares a frame number in each frame; your program must initialize this value2. Supporting stack functionsImplement the following support functions for the function call stack:• initStack allocates and initializes the stack• push adds a frame in LIFO order to the call stack• pop removes from the stack the frame that was last added• cleanupStack deallocates all the memory for the stackNote: remember to manage your memory! do not leave any memory leaksCOMP 2401 — Assignment #3 Fall 2013 2/33. Instrumentation functionsModify both enterSumFunc and leaveSumFunc functions to manipulate the function call stack as a linked list:• enterSumFunc is called when a sum function begins; it must:o create a new dynamically allocated stack frame to store information about one of the sum functionso initialize all the frame data, as you did in Assignment #2o add the new frame to the function call stacko output the contents of the call stack, using the modified dumpStack function• leaveSumFunc is called when a sum function returns; it must:o output the contents of the call stack, using the modified dumpStack functiono remove the corresponding frame from the stackNotes:• your sum functions must call the instrumentation functions defined above• the instrumentation functions must use the supporting push and pop functions4. Stack output to fileDefine, as a global variable, a pointer to the output file that will contain the contents of the call stack• remember! global variables are to be used very rarely, this is a one-time exception!Modify the call stack output functions to work with the linked list and output the contents of the stack to a file:• dumpStack traverses the linked list of frames and outputs the contents to the output fileo you must use the same output format as in Assignment #2• dumpVar and dumpBytes must be modified to print to file as wellNotes:• think about where you must open and close the output file!• you must use the stack utility functions found here: a3Stack.c• you can find some helpful sample code here: testUtil.cConstraints• Design:o you must separate your code into modular, reusable functionso never use global variables, unless otherwise instructedo compound data types must be passed by reference, not by valueo you must manage your memory! use valgrind to find memory leaks• Reuse:o you must include the given header file in your program and use its function prototypes exactly as defined• Implementation:o your program must perform all basic error checkingo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductionsCOMP 2401 — Assignment #3 Fall 2013 3/3SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionsGrading• Marking breakdown:ComponentMarksdata types15supporting stack functions50instrumentation functions25stack output to file10• Assignment grade: Your grade will be computed based on the completeness of your implementation, plus bonus marks, minus deductions.• Deductions: 100 marks if:o any files are missing from your submission, or if they are corrupt or in the wrong format 50 marks if:o the code does not compile using gcc in the Ubuntu Linux shell environmento unauthorized changes have been made to the header and/or source files provided for youo code cannot be tested because it doesn’t run 25 marks if:o your submission consists of anything other than exactly one tar fileo your program is not broken down into multiple reusable, modular functionso your code is not correctly separated into header and source fileso your program uses global variables (unless otherwise explicitly permitted)o the readme file is missing or incomplete 10 marks for missing comments or other bad style (non-standard indentation, improper identifier names, etc)• Bonus marks: Up to 5 extra marks are available for fun and creative additional featuresGoal You will write a program in C, in the Ubuntu Linux environment, to manage a movie database.In this assignment, you will:• define the data types and structures required to represent a movie collection as a doubly linked list• write code to interact with the user for the purpose of managing movie data• implement functions to manipulate the doubly linked list• create a set of input files to test a programLearning Objectives• get familiar with more complex dynamic memory operations by managing a doubly linked list• practice a wider variety of user I/O interactions using standard library functions• use redirection of standard input to test a programInstructions1. Data typesDefine the data types required for the movie database:• MovieType represents one movie; it includes the movie title, the year it was made, and the genre• MovieNodeType corresponds to a node in the doubly linked list of movies, implemented as we saw in the “Advanced Linked Lists” section of the course notes• your main function must define the movie list as a pointer to the head of the doubly linked listo there must be only one instance of the movie list in the entire program; do not make copies!o this is not a global variableNote:• your program must use the definitions in the header file found here: a4Defs.h2. Movie management user interface (UI)Write a main and a main menu function to interact with the user and provide these four options (with 0 to exit):• add movieso getMovieData prompts the user for the number of movies to be entered, then prompts for the movie data• delete a movieo the user enters the title of a movie to be removed from the list• list all movieso a list of all movies is printed to the standard output• list movies by genreo the user enters the genre of movies to be listedo a list of all movies of that genre is printed to the standard outputNote:• you can find some helpful sample code for user I/O here: testUtil.cCOMP 2401 — Assignment #4 Fall 2013 2/43. List management functionsImplement the following list management functions:• addToMovieListo adds a given movie to the movie list, alphabetically by title, then chronologically by year if titles are identical• deleteMovieo removes the given movie from the movie list• printMovieDatao prints out a list of all movies to the standard output• printMoviesByGenreo prints out a list of all movies of the given genre to the standard output you must create a new temporary list containing movies of only that genre – do not copy the movie data! you must reuse the addToMovieList and printMovieData functionsNotes:• the print functions must display all the data for each movie• remember to manage your memory! do not leave any memory leaks4. Instrumentation functionDefine, as a global variable, a pointer to an output file that will contain the contents of the movie list• the file can be opened at the beginning of the main function and closed at the end of the programWrite a dumpList function that prints to the output file the detailed contents of the movie list, including:• the value of the head, as an address• for each node:o the value of the node, as an addresso the address of the data, as well as its contentso the value of the previous node, as an addresso the value of the next node, as an addressNotes:• your program must call dumpList at the beginning and end of these functions: getMovieData, addMovieToList, deleteMovie• your output must be formatted as in Figure 1• you can reuse the convertToBytes and dumpBytes functions from previous assignments5. Test input filesDesign a suite of test cases that thoroughly exercise your program’s functionality and possible error conditions.In your readme file, list and number all the cases that must be tested. At minimum, these will include, for each feature of the program, one test case for every normal case and every error case; for the add movies feature, for example, the following must be tested:o adding a movie to an empty listo adding a movie to the beginning of the listo adding a movie to the end of the list… and many more …Create a set of test input files; each input file:• corresponds to one test case• contains the standard input data to be redirected into your program for that test caseCOMP 2401 — Assignment #4 Fall 2013 3/4Figure 1 – Sample output of instrumentation functionConstraints• Design:o you must separate your code into modular, reusable functionso never use global variables, unless otherwise instructedo compound data types must be passed by reference, not by valueo you must manage your memory! use valgrind to find memory leaks• Reuse:o you must include the given header file in your program and use its function prototypes exactly as defined• Implementation:o your program must perform all basic error checkingo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductions• Testingo submissions that do not include a list of test cases and a suite of test input files are subject to severe deductionsCOMP 2401 — Assignment #4 Fall 2013 4/4SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a Makefile• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionso a list of test cases that test your program• a set of test input filesGrading• Marking breakdown:ComponentMarksdata types10movie management UI16list management functions62instrumentation function12• Assignment grade: Your grade will be computed based on the completeness of your implementation, plus bonus marks, minus deductions.• Deductions: 100 marks if:o any files are missing from your submission, or if they are corrupt or in the wrong format 50 marks if:o the Makefile is missingo the code does not compile using gcc in the Ubuntu Linux shell environmento unauthorized changes have been made to the header and/or source files provided for youo code cannot be tested because it doesn’t run 25 marks if:o your submission consists of anything other than exactly one tar fileo your program is not broken down into multiple reusable, modular functionso your code is not correctly separated into header and source fileso your program uses global variables (unless otherwise explicitly permitted)o the readme file is missing or incomplete 10 marks for missing comments or other bad style (non-standard indentation, improper identifier names, etc)• Bonus marks: Up to 5 extra marks are available for fun and creative additional featuresGoal You will write a program in C, in the Ubuntu Linux environment, to simulate a two-player game of Twenty Questions, as a distributed system over the School of Computer Science network. One player (the oracle) chooses an object that the other player (the guesser) tries to guess by asking the oracle one question at a time. At every turn, the guesser asks a yes/no question, or tries to guess the object. The oracle responds by signalling one of three responses: yes, no, or win. If the guesser correctly guesses the object within 20 questions, s/he wins, otherwise the oracle wins. The winning player is given a choice of quitting the game, or playing another round. If s/he opts to play again, s/he becomes the oracle for the next round.In this assignment, you will:• implement a game between two users on different computers, communicating over TCP/IP sockets• modify client-server code so that a single executable program can switch between client mode and server modeInstructions1. Process startupYou are writing code for a single executable program. Both guesser and oracle players will be running their own copy of the same program, but executing on different computers that are networked together.Your program initiates a connection to another game process as follows:• the user may specify an IP address on the command line or not• if an IP address is specified, then the game process initiates a connection using TCP/IP sockets to the other game process running at the specified IP address• if no IP address is specified, then the game process waits for another game process to initiate a connection2. Game logicThe Twenty Questions game logic works as follows:• setting up a roundo the player on the game process that initiated the connection takes on the role of guessero the other player becomes the oracle• during the roundo at each turn, the guesser is prompted for a yes/no question (questions should be numbered)o the question is sent to the oracle’s game processo the oracle user enters a response using signals; do not prompt the oracle for input! the SIGINT (Ctrl-C) signal indicates a yes answer to the question the SIGTSTP (Ctrl-Z) signal indicates a no answer to the question the SIGQUIT (Ctrl-) signal is a win answer, meaning that the guesser has correctly guessed the objecto both players see all the questions asked so far, along with the answero if the guesser correctly guesses the object, s/he winso if the number of questions reaches 20 without a correct guess, the oracle wins• ending a roundo when a player wins, s/he is prompted to either play another round or quito the losing player does not get a choice and must play again if the winner chooses to do soo if the winner decides to play again, s/he becomes the oracle, and a new round starts upo if the winner decides to quit: the winner’s game process closes the connection, cleans up all its resources, and terminates the loser’s game process waits for a new connection to be initiatedCOMP 2401 — Assignment #5 Fall 2013 2/2Constraints• Design:o you must separate your code into modular, reusable functionso never use global variables, unless otherwise instructed• Implementation:o your program must perform all basic error checking and clean up resources upon terminationo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductionsSubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a Makefile• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionsGrading• Marking breakdown:ComponentMarksprocess startup40game logic60• Assignment grade: Your grade will be computed based on the completeness of your implementation, plus bonus marks, minus deductions.• Deductions: 100 marks if:o any files are missing from your submission, or if they are corrupt or in the wrong format 50 marks if:o the Makefile is missingo the code does not compile using gcc in the Ubuntu Linux shell environmento code cannot be tested because it doesn’t run 25 marks if:o your submission consists of anything other than exactly one tar fileo your program is not broken down into multiple reusable, modular functionso your code is not correctly separated into header and source fileso your program uses global variables (unless otherwise explicitly permitted)o the readme file is missing or incomplete 10 marks for missing comments or other bad style (non-standard indentation, improper identifier names, etc)• Bonus marks: Up to 5 extra marks are available for fun and creative additional features
Problem 1 (Electronics Store – Version 1) Your goal for this problem is to create a simple implementation of an electronics store. You must implement the following five classes with the defined functionality: Desktop Class: Must store the CPU speed (in Ghz as a double), amount of RAM (in GB as an integer), amount of storage (in GB as an integer), and whether or not the storage is an SSD or HDD (a Boolean, with true meaning SSD and false meaning HDD). The class must have a fourargument constructor that accepts an input parameter for each of these values in the same order they are listed above (CPU, RAM, storage, SSD). The class must have a toString method that returns a string indicating the object is a desktop PC along with the object’s properties. Two examples of what the toString method could return are included below: Desktop PC with 3.5ghz CPU, 8GB RAM, 500GB HDD drive. Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. Laptop Class: Must store the CPU speed (in Ghz as a double), amount of RAM (in GB as an integer), amount of storage (in GB as an integer), whether or not the storage is an SSD or HDD (a Boolean, with true meaning SSD and false meaning HDD), and the screen size (in inches as an integer). The class must have a five-argument constructor that accepts an input parameter for each of these values in the same order they are listed above (CPU, RAM, storage, SSD, screen size). The class must have a toString method that returns a string indicating the object is a laptop PC along with the object’s properties. Two examples of what the toString method could return are included below: 15″ Laptop PC with 3.1ghz CPU, 32GB RAM, 500GB SSD drive. 13″ Laptop PC with 2.5ghz CPU, 8GB RAM, 250GB HDD drive. Fridge Class: Must store the size of the fridge (in cubic feet, as a double), whether it includes a freezer or not (a Boolean that is true if it has a freezer), and the color (as a String). The class must have a toString method that returns a string indicating the object is a fridge along with the object’s properties. Two examples of what the toString method could return are included below: 15.6 cubic foot Fridge with Freezer (Gray) 10.5 cubic foot Fridge (White) COMP 1406 – W20 – A1 Due Friday, January 31st at 11:59 PM 2 ElectronicStore Class: Must have an instance variable called name to store the name of the store. Must have a one-argument constructor that accepts a string to specify the store name. The constructor for this class must also create three instances of each of the previous three classes (9 items in total, using the constructors defined in those classes) and store them within the ElectronicStore instance being created. For storage purposes in the ElectronicStore class, you can use one or more arrays, lists, or hash maps to store the various products (your design choice). You can hard-code the argument values for the product constructors (i.e., CPU speed, RAM, color, etc.) or use a random number generator to randomly assign them. This class should also have a void method called printStock() that will iterate over all of the store’s stock and print them to the console in a readable format. Additionally, this class should have a searchStock(String) method. The searchStock method should accept a string argument and return true if the toString() of any product in the store’s stock contains the given string argument (otherwise, the method should return false). The searchStock method should also be case insensitive. That is, searches for “desk” and “hdd” should both return true if the store contains a “Desktop PC with 3.5ghz CPU, 8GB RAM, 500GB HDD drive”. ElectronicStoreTester Class: This class should have a single main method, which will first instantiate a single ElectronicStore and call the printStock() method. The test class should then repeatedly prompt the user to enter an item to search for. If the user enters the word “quit”, this process should stop, and the program should end. Otherwise, the searchStock method of the ElectronicStore instance should be used to search for the given search term and the result should be printed out. You should use the searchStock method’s return value to determine what message should be displayed. The output from this tester class should be similar to below (user input text is highlighted): The store stock includes: Desktop PC with 3.5ghz CPU, 8GB RAM, 500GB HDD drive. Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. Desktop PC with 4.3ghz CPU, 32GB RAM, 500GB SSD drive. 15″ Laptop PC with 3.1ghz CPU, 32GB RAM, 500GB SSD drive. 13″ Laptop PC with 2.5ghz CPU, 8GB RAM, 250GB HDD drive. 15″ Laptop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. 16.5 cu. ft. Fridge with Freezer (Black) 12.0 cu. ft. Fridge (White) 23.0 cu. ft. Fridge with Freezer (Stainless Steel) Enter a term to search for: desk A matching item is contained in the store’s stock. Enter a term to search for: LaPtOP A matching item is contained in the store’s stock. Enter a term to search for: Toast No items in the store’s stock match that term. Enter a term to search for: television COMP 1406 – W20 – A1 Due Friday, January 31st at 11:59 PM 3 No items in the store’s stock match that term. Enter a term to search for: GB A matching item is contained in the store’s stock. Enter a term to search for: quitFor this assignment, you will apply the OOP principles of encapsulation and inheritance to the redesign of the electronic store classes from Assignment #1. A list of the classes that must be contained in your program are given below, along with a summary of their state and behaviour. It is up to you to decide on and implement the appropriate class hierarchy. You will likely need to add more classes to define the best class hierarchy – look for shared state/behaviour between different classes and define a parent class if you need to. Note that you will not need to define/implement all these methods/attributes in each class if you make proper use of inheritance. Additionally, you must use proper encapsulation in designing these classes. All your instance variables should be private, unless you can justify them being protected/public. You should be able to complete the assignment without creating any public/protected variables. If you include a protected/public variable, also include a comment with your justification. You can add additional methods (e.g., getter/setter methods) to the classes as you see fit. A large portion of your mark will come from the quality of your class design and proper use of encapsulation/inheritance. Two test classes are included on the assignment page. Your code should work with these test case classes. When you run the test case classes, the output should be very similar to the output included at the end of this document. The only difference may be in the formatting of the objects, though your toString() methods should closely mirror the formatting included here. You should test your code with your own additional test cases as well. The supplied test classes only provide a minimal amount of testing. Desktop Class: State: 1. double price – represents how much the desktop costs 2. int stockQuantity – represents how many units of this desktop are in stock 3. int soldQuantity – represents how many units of this desktop have been sold 4. double cpuSpeed – the CPU speed in Ghz 5. int ram – the amount of RAM in GB 6. boolean ssd – whether the hard-drive is an SSD (true) or HDD (false) 7. int storage – the size of the hard-drive in GB 8. String profile – a string describing the size of the desktop case COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 2 Behaviour: 1. Desktop(double price, int quantity, double cpuSpeed, int ram, boolean ssd, int storage, String profile) – constructor for the class 2. double sellUnits(int amount) – simulates selling amount units. If there are enough units in stock to meet the request, the quantity attributes must be updated appropriately and the total revenue (revenue = units * price) should be returned. If there are not enough units in stock, no sale should take place and 0.0 should be returned. 3. String toString() – returns a string representing the desktop. This should summarize the state of the desktop, including each attribute. See the example output included at the bottom for examples. ElectronicStore Class: State: 1. final int MAX_PRODUCTS = 10 – the maximum number of different product instances that this store can contain. This value should be set to 10 and never changed. Your class should refer to this variable so that the maximum number of products can be changed easily. 2. String name – the name of the electronics store 3. double revenue – the total revenue the store has made through sales. This should initially be 0 but should be updated as products are sold. 4. Product[ ] products – an array to store product objects that are in the store. This array should have size equal to MAX_PRODUCTS. In case you are working on this before we have finished discussing polymorphism in class, all you need to know is that you can store any class that is below Product in the class hierarchy within this array. So if you have additional classes that extend Product (or in general, are further down the hierarchy), you can store them in this array without any problems. Behaviour: 1. ElectronicStore(String name) – constructor for the class. 2. String getName() – returns the name of the store 3. boolean addProduct(Product p) – if there is space remaining in the products array, this method should add p to the products array at the next available array slot and return true. If there is no space remaining in the products array, this method should just return false. 4. void sellProducts() – this method should print out the store’s products (see example output below for an idea of how it should look), read an integer from the user representing the product to sell (i.e., what index in the products array), and read an integer from the user representing how many units of the product to sell. You may assume the user will only enter integer numbers but must verify that the values are valid (e.g., a valid item index, an amount greater than 0). If the values supplied by the user are valid, the specified COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 3 number of units of the specified product should be sold, if possible. All appropriate variables must be updated in all instances (e.g., revenue, number of units in stock, etc.). If any of the input is invalid, no sales should take place. 5. void sellProducts(int item, int amount) – should sell amount units of the product stored at index item in the products array, if possible. All appropriate variables must be updated in all instances (e.g., revenue, number of units in stock, etc.). If any of the input is invalid, no sales should take place. 6. double getRevenue() – returns the total revenue the store has made through sales. 7. void printStock() – should print out the products of the store. See the example output at the bottom of the document for examples. Fridge Class: State: 1. double price – represents how much the fridge costs 2. int stockQuantity – represents how many units of this fridge there are in stock 3. int soldQuantity – represents how many units of this fridge have been sold 4. int wattage – the wattage rating of the fridge 5. String color – the color of the fridge 6. String brand – the brand name of the fridge 7. double cubicFeet – The volume of the fridge in cubic feet 8. boolean hasFreezer – Whether the fridge has a freezer or not Behaviour: 1. Fridge(double price, int quantity, int wattage, String color, String brand, double cubicFeet, boolean freezer) – constructor for the class 2. double sellUnits(int amount) – simulates selling amount units. If there are enough units in stock to meet the request, the quantity attributes must be updated appropriately and the total revenue (revenue = units * price) should be returned. If there are not enough units in stock, no sale should take place and 0.0 should be returned. 3. String toString() – returns a string representing the fridge. This should summarize the state of the fridge, including each attribute. See the example output included at the bottom for examples. Laptop Class: State: 1. double price – represents how much the laptop costs 2. int stockQuantity – represents how many units of this laptop there are in stock 3. int soldQuantity – represents how many units of this laptop have been sold 4. double cpuSpeed – the CPU speed, in Ghz 5. int ram – the amount of RAM in GB 6. boolean ssd – whether the hard-drive is an SSD (true) or HDD (false) COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 4 7. int storage – the size of the hard-drive in GB 8. double screenSize – the size of the screen in inches Behaviour: 1. Laptop(double price, int quantity, double cpuSpeed, int ram, boolean ssd, int storage, double screenSize) – constructor for the class 2. double sellUnits(int amount) – simulates selling amount units. If there are enough units in stock to meet the request, the quantity attributes must be updated appropriately and the total revenue (revenue = units * price) should be returned. If there are not enough units in stock, no sale should take place and 0.0 should be returned. 3. String toString() – returns a string representing the laptop. This should summarize the state of the laptop, including each attribute. See the example output included at the bottom for examples. Product Class: State: 1. double price – represents how much the product costs 2. int stockQuantity – represents how many units of this product are in stock 3. int soldQuantity – represents how many units of this product have been sold Behaviour: 1. Product(double price, int quantity) – constructor for the class 2. double sellUnits(int amount) – simulates selling amount units. If there are enough units in stock to meet the request, the quantity attributes must be updated appropriately and the total revenue for selling (revenue = units * price) should be returned. If there are not enough units in stock, no sale should take place and 0.0 should be returned. ToasterOven Class: State: 1. double price – represents how much the toaster oven costs 2. int stockQuantity – represents how many units of this toaster are in stock 3. int soldQuantity – represents how many units of this toaster have been sold 4. int wattage – the wattage rating of the toaster oven 5. String color – the color of the toaster oven 6. String brand – the brand name of the toaster oven 7. int width – the width of the toaster oven 8. boolean convection – whether the toaster has convection heating or not Behaviour: 1. ToasterOven(double price, int quantity, int wattage, String color, String brand, int width, boolean convection) – constructor for the class 2. double sellUnits(int amount) – simulates selling amount units. If there are enough units in stock to meet the request, the quantity attributes must be COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 5 updated appropriately and the total revenue for selling (revenue = units * price) should be returned. If there are not enough units in stock, no sale should take place and 0.0 should be returned. 3. String toString() – returns a string representing the toaster oven. This should summarize the state of the toaster oven, including each attribute. See the example output included at the bottom for examples. ElectronicStoreStockTester Class Output If you run the ElectronicStoreStockTester class, you should get the following output (bold font added to help find specific parts of the output, your code does not need to produce bold output): Watts Up Electronics’s Stock Is: 0. Compact Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB HDD drive. (100.0 dollars each, 10 in stock, 0 sold) 1. Server Desktop PC with 4.0ghz CPU, 32GB RAM, 500GB SSD drive. (200.0 dollars each, 10 in stock, 0 sold) 2. 15.0 inch Laptop PC with 2.5ghz CPU, 16GB RAM, 250GB SSD drive. (150.0 dollars each, 10 in stock, 0 sold) 3. 16.0 inch Laptop PC with 3.5ghz CPU, 24GB RAM, 500GB SSD drive. (250.0 dollars each, 10 in stock, 0 sold) 4. 15.5 cu. ft. Sub Zero Fridge (White, 250 watts) (500.0 dollars each, 10 in stock, 0 sold) 5. 23.0 cu. ft. Sub Zero Fridge with Freezer (Stainless Steel, 125 watts) (750.0 dollars each, 10 in stock, 0 sold) 6. 8 inch Danby Toaster (Black, 50 watts) (25.0 dollars each, 10 in stock, 0 sold) 7. 12 inch Toasty Toaster with convection (Silver, 50 watts) (75.0 dollars each, 10 in stock, 0 sold) Buy-nary Computing’s Stock Is: 0. Compact Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (150.0 dollars each, 5 in stock, 0 sold) 1. Server Desktop PC with 3.5ghz CPU, 32GB RAM, 500GB SSD drive. (250.0 dollars each, 5 in stock, 0 sold) 2. 15.0 inch Laptop PC with 2.5ghz CPU, 16GB RAM, 250GB HDD drive. (100.0 dollars each, 15 in stock, 0 sold) 3. 16.0 inch Laptop PC with 3.5ghz CPU, 24GB RAM, 500GB SSD drive. (175.0 dollars each, 15 in stock, 0 sold) 4. 15.5 cu. ft. Sub Zero Fridge (Black, 250 watts) (350.0 dollars each, 10 in stock, 0 sold) COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 6 5. 23.0 cu. ft. Sub Zero Fridge with Freezer (White, 125 watts) (600.0 dollars each, 10 in stock, 0 sold) 6. 6 inch Danby Toaster (Graphite, 50 watts) (25.0 dollars each, 10 in stock, 0 sold) 7. 10 inch Toasty Toaster with convection (Red, 50 watts) (75.0 dollars each, 10 in stock, 0 sold) Ohm-y Goodness Electronics’s Stock Is: 0. Low-Profile Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (175.0 dollars each, 10 in stock, 0 sold) 1. Standard Desktop PC with 3.5ghz CPU, 32GB RAM, 1000GB HDD drive. (150.0 dollars each, 15 in stock, 0 sold) 2. 16.0 inch Laptop PC with 3.5ghz CPU, 16GB RAM, 500GB SSD drive. (350.0 dollars each, 5 in stock, 0 sold) 3. 13.0 inch Laptop PC with 2.5ghz CPU, 8GB RAM, 125GB SSD drive. (500.0 dollars each, 5 in stock, 0 sold) 4. 12.0 cu. ft. Sub Zero Fridge (Black, 250 watts) (250.0 dollars each, 5 in stock, 0 sold) 5. 15.0 cu. ft. Sub Zero Fridge (White, 125 watts) (275.0 dollars each, 5 in stock, 0 sold) 6. 8 inch Danby Toaster (Graphite, 50 watts) (30.0 dollars each, 10 in stock, 0 sold) 7. 12 inch Toasty Toaster with convection (Red, 50 watts) (80.0 dollars each, 10 in stock, 0 sold) 8. Low-Profile Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (175.0 dollars each, 10 in stock, 0 sold) 9. Standard Desktop PC with 3.5ghz CPU, 32GB RAM, 1000GB HDD drive. (150.0 dollars each, 15 in stock, 0 sold) ElectronicStoreSellingTester Class Output If you run the ElectronicStoreSellingTester class, you should get the following output (bold font added to help find specific parts of the output, your code does not need to produce bold output): Watts Up Electronics’s Starting Stock Is: 0. Compact Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB HDD drive. (100.0 dollars each, 10 in stock, 0 sold) 1. Server Desktop PC with 4.0ghz CPU, 32GB RAM, 500GB SSD drive. (200.0 dollars each, 10 in stock, 0 sold) 2. 15.0 inch Laptop PC with 2.5ghz CPU, 16GB RAM, 250GB SSD drive. (150.0 dollars each, 10 in stock, 0 sold) COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 7 3. 16.0 inch Laptop PC with 3.5ghz CPU, 24GB RAM, 500GB SSD drive. (250.0 dollars each, 10 in stock, 0 sold) 4. 15.5 cu. ft. Sub Zero Fridge (White, 250 watts) (500.0 dollars each, 10 in stock, 0 sold) 5. 23.0 cu. ft. Sub Zero Fridge with Freezer (Stainless Steel, 125 watts) (750.0 dollars each, 10 in stock, 0 sold) 6. 8 inch Danby Toaster (Black, 50 watts) (25.0 dollars each, 10 in stock, 0 sold) 7. 12 inch Toasty Toaster with convection (Silver, 50 watts) (75.0 dollars each, 10 in stock, 0 sold) Buy-nary Computing’s Starting Stock Is: 0. Compact Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (150.0 dollars each, 5 in stock, 0 sold) 1. Server Desktop PC with 3.5ghz CPU, 32GB RAM, 500GB SSD drive. (250.0 dollars each, 5 in stock, 0 sold) 2. 15.0 inch Laptop PC with 2.5ghz CPU, 16GB RAM, 250GB HDD drive. (100.0 dollars each, 15 in stock, 0 sold) 3. 16.0 inch Laptop PC with 3.5ghz CPU, 24GB RAM, 500GB SSD drive. (175.0 dollars each, 15 in stock, 0 sold) 4. 15.5 cu. ft. Sub Zero Fridge (Black, 250 watts) (350.0 dollars each, 10 in stock, 0 sold) 5. 23.0 cu. ft. Sub Zero Fridge with Freezer (White, 125 watts) (600.0 dollars each, 10 in stock, 0 sold) 6. 6 inch Danby Toaster (Graphite, 50 watts) (25.0 dollars each, 10 in stock, 0 sold) 7. 10 inch Toasty Toaster with convection (Red, 50 watts) (75.0 dollars each, 10 in stock, 0 sold) Ohm-y Goodness Electronics’s Starting Stock Is: 0. Low-Profile Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (175.0 dollars each, 10 in stock, 0 sold) 1. Standard Desktop PC with 3.5ghz CPU, 32GB RAM, 1000GB HDD drive. (150.0 dollars each, 15 in stock, 0 sold) 2. 16.0 inch Laptop PC with 3.5ghz CPU, 16GB RAM, 500GB SSD drive. (350.0 dollars each, 5 in stock, 0 sold) 3. 13.0 inch Laptop PC with 2.5ghz CPU, 8GB RAM, 125GB SSD drive. (500.0 dollars each, 5 in stock, 0 sold) 4. 12.0 cu. ft. Sub Zero Fridge (Black, 250 watts) (250.0 dollars each, 5 in stock, 0 sold) 5. 15.0 cu. ft. Sub Zero Fridge (White, 125 watts) (275.0 dollars each, 5 in stock, 0 sold) COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 8 6. 8 inch Danby Toaster (Graphite, 50 watts) (30.0 dollars each, 10 in stock, 0 sold) 7. 12 inch Toasty Toaster with convection (Red, 50 watts) (80.0 dollars each, 10 in stock, 0 sold) 8. Low-Profile Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (175.0 dollars each, 10 in stock, 0 sold) 9. Standard Desktop PC with 3.5ghz CPU, 32GB RAM, 1000GB HDD drive. (150.0 dollars each, 15 in stock, 0 sold) Watts Up Electronics’s Ending Stock Is: 0. Compact Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB HDD drive. (100.0 dollars each, 0 in stock, 10 sold) 1. Server Desktop PC with 4.0ghz CPU, 32GB RAM, 500GB SSD drive. (200.0 dollars each, 10 in stock, 0 sold) 2. 15.0 inch Laptop PC with 2.5ghz CPU, 16GB RAM, 250GB SSD drive. (150.0 dollars each, 10 in stock, 0 sold) 3. 16.0 inch Laptop PC with 3.5ghz CPU, 24GB RAM, 500GB SSD drive. (250.0 dollars each, 0 in stock, 10 sold) 4. 15.5 cu. ft. Sub Zero Fridge (White, 250 watts) (500.0 dollars each, 10 in stock, 0 sold) 5. 23.0 cu. ft. Sub Zero Fridge with Freezer (Stainless Steel, 125 watts) (750.0 dollars each, 10 in stock, 0 sold) 6. 8 inch Danby Toaster (Black, 50 watts) (25.0 dollars each, 10 in stock, 0 sold) 7. 12 inch Toasty Toaster with convection (Silver, 50 watts) (75.0 dollars each, 0 in stock, 10 sold) Buy-nary Computing’s Ending Stock Is: 0. Compact Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (150.0 dollars each, 0 in stock, 5 sold) 1. Server Desktop PC with 3.5ghz CPU, 32GB RAM, 500GB SSD drive. (250.0 dollars each, 4 in stock, 1 sold) 2. 15.0 inch Laptop PC with 2.5ghz CPU, 16GB RAM, 250GB HDD drive. (100.0 dollars each, 0 in stock, 15 sold) 3. 16.0 inch Laptop PC with 3.5ghz CPU, 24GB RAM, 500GB SSD drive. (175.0 dollars each, 15 in stock, 0 sold) 4. 15.5 cu. ft. Sub Zero Fridge (Black, 250 watts) (350.0 dollars each, 10 in stock, 0 sold) 5. 23.0 cu. ft. Sub Zero Fridge with Freezer (White, 125 watts) (600.0 dollars each, 10 in stock, 0 sold) 6. 6 inch Danby Toaster (Graphite, 50 watts) (25.0 dollars each, 10 in stock, 0 sold) COMP 1406 – W20 – A2 Due Friday, February 14th at 11:59 PM 9 7. 10 inch Toasty Toaster with convection (Red, 50 watts) (75.0 dollars each, 10 in stock, 0 sold) Ohm-y Goodness Electronics’s Ending Stock Is: 0. Low-Profile Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (175.0 dollars each, 10 in stock, 0 sold) 1. Standard Desktop PC with 3.5ghz CPU, 32GB RAM, 1000GB HDD drive. (150.0 dollars each, 0 in stock, 15 sold) 2. 16.0 inch Laptop PC with 3.5ghz CPU, 16GB RAM, 500GB SSD drive. (350.0 dollars each, 0 in stock, 5 sold) 3. 13.0 inch Laptop PC with 2.5ghz CPU, 8GB RAM, 125GB SSD drive. (500.0 dollars each, 5 in stock, 0 sold) 4. 12.0 cu. ft. Sub Zero Fridge (Black, 250 watts) (250.0 dollars each, 1 in stock, 4 sold) 5. 15.0 cu. ft. Sub Zero Fridge (White, 125 watts) (275.0 dollars each, 0 in stock, 5 sold) 6. 8 inch Danby Toaster (Graphite, 50 watts) (30.0 dollars each, 10 in stock, 0 sold) 7. 12 inch Toasty Toaster with convection (Red, 50 watts) (80.0 dollars each, 10 in stock, 0 sold) 8. Low-Profile Desktop PC with 3.0ghz CPU, 16GB RAM, 250GB SSD drive. (175.0 dollars each, 10 in stock, 0 sold) 9. Standard Desktop PC with 3.5ghz CPU, 32GB RAM, 1000GB HDD drive. (150.0 dollars each, 8 in stock, 7 sold) Watts Up Electronics’s total revenue was: 4250.0 Buy-nary Computing’s total revenue was: 2500.0 Ohm-y Goodness Electronics’s total revenue was: 7425.0For this assignment, you will build a graphical user interface to attach to the electronic store model that you have developed over the previous two assignments. You can use your own model classes from the previous assignment, or you can download the model classes included within the zip file on the assignment page and incorporate those into your IntelliJ project as a starting point (these will be posted on Tuesday February 18th). Your assignment must maintain a separation between the GUI and the underlying electronic store model. You should ensure you understand the Model/View/Controller paradigm before beginning the assignment. You must also continue to apply the principles of OOP, such as encapsulation. A recording showing a demonstration of how the GUI should work is included on the assignment page. 1) The GUI An example of what the graphical user interface window should include is given in the picture below. The code for this view should be created in a class called ElectronicStoreView. You should make the GUI window non-resizable. The ratio of the window width/height should be approximately 2:1 (e.g., 800 wide, 400 high). It does not have to look exactly as the picture but should closely match. COMP 1406 – W20 – A3 Due Friday, March 6 th at 11:59 PM 2 2) When the Application Starts Create a class called ElectronicStoreApp, which will represent the controller component of your program. This class should extend from the JavaFX Application class. When the application starts, your controller should create an instance of ElectronicStore, as well as an instance of your view defined in part 1. To create the ElectronicStore instance, you must use the static createStore() method from the ElectronicStore.java file included on the assignment page and save the returned ElectronicStore instance in a variable within the ElectronicStoreApp. If you are using your own code as a base, you can copy/paste the createStore() method from the example. The ElectronicStore instance will represent the model that the GUI application will interact with. When the application starts, the window title must include the name of the store. The ‘Add to Cart’, ‘Remove from Cart’, and ‘Complete Sale’ buttons should initially be disabled. The ‘# Sales’, ‘Revenue’, and “$ / Sale” TextFields should be initialized to default values representing the starting state of an electronic store. The store stock ListView should display all the items currently in stock within the electronic store model. The most popular items ListView should show 3 products that exist in the store’s stock. At this point, all products will have an equal popularity since no sales have taken place. The image below shows an example of what the initial window should look like: COMP 1406 – W20 – A3 Due Friday, March 6 th at 11:59 PM 3 3) Event Handling You must add event handling to the ElectronicStoreApp class to meet the requirements outlined below. Store Stock: 1) If an item has been selected inside of the Store Stock ListView, the ‘Add to Cart’ button should be enabled. If no item has been selected, the button should be disabled. 2) When an item in the Store Stock ListView has been selected and the ‘Add to Cart’ button is clicked, one unit of the selected item should be added to the current cart (see requirements for Current Cart below). 3) If a product does not have any items left in stock (i.e., they have all been sold or added to the current cart), it should not be displayed in the Store Stock ListView. Note that when a product is added to the cart, the amount of that product available in stock should decrease. Current Cart: 1) The Current Cart ListView should show the products that have been added to the cart. Additionally, if the same product has been added to the cart x times, the product should be included x times in the Current Cart ListView. 2) If no products have been added into the cart, the ‘Complete Sale’ button should be disabled. If products are in the cart, the button should be enabled. 3) The total dollar amount in brackets beside ‘Current Cart’, representing the total value of all products in the current cart, should be updated each time a product is added to the cart or removed from the cart. 4) If an item in the Current Cart ListView has been selected, the ‘Remove from Cart’ button should be enabled. Otherwise, it should be disabled. When an item is clicked in the Current Cart ListView, it is acceptable to have your ListView select ANY item that is the same as the originally clicked item (this is the default behaviour of the ListView). 5) If an item in the Current Cart ListView is selected and the ‘Remove from Cart’ button is clicked, that item should be removed from the Current Cart and placed back into the store’s stock. Complete Sale: 1) When there is at least one product in the current cart and the ‘Complete Sale’ button is clicked, those items should be sold. You must update the ‘# Sales’ (increase by 1), the ‘Revenue’ (increase by the total value of the cart), and the ‘$ / Sale’ (calculate using the other two values) fields on the GUI window and the related variables in the underlying model. 2) The total dollar amount listed in brackets beside ‘Current Cart’ should be reset to $0.00 when a sale is completed. COMP 1406 – W20 – A3 Due Friday, March 6 th at 11:59 PM 4 Most Popular Items: 1) The most popular items ListView should show the 3 products that have sold the most units. You do not need to worry about ties between products. 2) The most popular items list view should only account for products that have officially been sold (i.e., it should not account for items that are added to the cart). Reset Store: 1) When the ‘Reset Store’ button is clicked, the model should be reset to its initial state (i.e., the electronic store should be recreated). The GUI should also update to show the reset state of the store.In this assignment, you will simulate an on-line music centre called the MusicExchangeCenter where Users log in and download Songs from other users’ computers. It is a similar idea to the operation of the original Napster program that operated many years ago where users shared songs. You won’t be doing any downloading or internet programming. Instead, you will just simulate what happens in real life. The assignment will give you familiarity with ArrayLists and HashMaps. To get started with the assignment, download the Assignment4-Starting-Code.zip file from the assignment page, which contains an IntelliJ project with a number of classes that will be used in the assignment. (1) The Song/ User Classes The Song and User classes represent a song that is available at the Music Exchange Center and a user of the Music Exchange Center that logs in to download music. Do the following in the User class: Add a songList attribute which is an ArrayList of Song objects. This list will contain all the songs that this user has on his/her hard drive to be made available to the Music Exchange Center community. Adjust the 2nd constructor to ensure that this attribute is initialized properly. Write a get method for the attribute as well. Adjust the toString() method so that the XXX is replaced by the number of songs available in the user’s song list. Create a method called addSong(Song s) which adds a given song to the user’s song list. Create a method called totalSongTime() that returns an integer indicating the total duration (i.e., amount of time), in seconds, that all of the user’s songs would require if played. COMP 1406 – W20 – A4 Due Friday, March 20th at 11:59 PM Due Friday, March 20th at 11:59 PM (2) The MusicExchangeCenter Class Implement a class called MusicExchangeCenter which represents the company website that users log in and out of in order to download music. The class should have this attribute: users – an ArrayList of all registered Users (which may be either logged on or not logged on). Create the following methods: A zero-parameter constructor that sets attributes properly. An onlineUsers() method that returns an ArrayList of all Users that are currently online. Note that this method creates and returns a new ArrayList each time it is called. An allAvailableSongs() method that returns a new ArrayList of all Songs currently available for download (i.e., all songs that are available from all logged-on users). Note that this method creates and returns a new ArrayList each time it is called. A toString() method that returns a string representation of the music center showing the number of users currently online as well as the number of songs currently available. (e.g., “Music Exchange Center (3 users on line, 15 songs available)”). A userWithName(String s) method that finds and returns the user object with the given name if it is in the list of users. If not there, null should be returned. A registerUser(User x) method that adds a given User to the music center’s list of users, provided that there are no other users with the same userName. If there are other users with the same userName, then this method does nothing. Use the userWithName(String s) method above. An availableSongsByArtist(String artist) method that returns a new ArrayList of all Songs currently available for download by the specified artist. Note that this method creates and returns a new ArrayList each time it is called. Go back to the User class and add these methods: A register(MusicExchangeCenter m) that makes use of the registerUser(User x) method that you just wrote to register the user into the given MusicExchangeCenter m. (Note that this should be a one-line method). A logon() method that simulates a user going online. A logoff() method that simulates a user going offline. Now you should test your code. To do so, run the MusicExchangeTestProgram.java file and compare your results to the expected results below. COMP 1406 – W20 – A4 Due Friday, March 20th at 11:59 PM Due Friday, March 20th at 11:59 PM Here is the output that you should see: Status: Music Exchange Center (0 users on-line, 0 songs available) On-Line Users: [] Available Songs: [] Status: Music Exchange Center (2 users on-line, 8 songs available) On-Line Users: [Disco Stew: 4 songs (online), Ronnie Rocker: 4 songs (online)] Available Songs: [“Hey Jude” by The Beatles 4:35, “Barbie Girl” by Aqua 3:54, “Only You Can Rock Me” by UFO 4:59, “Paper Soup Cats” by Jaw 4:18, “Rock is Cool” by Yeah 4:17, “My Girl is Mean to Me” by Can’t Stand Up 3:29, “Only You Can Rock Me” by UFO 4:52, “We’re Not Gonna Take It” by Twisted Sister 3:9] Status: Music Exchange Center (4 users on-line, 16 songs available) On-Line Users: [Disco Stew: 4 songs (online), Ronnie Rocker: 4 songs (online), Country Candy: 3 songs (online), Peter Punk: 5 songs (online)] Available Songs: [“Hey Jude” by The Beatles 4:35, “Barbie Girl” by Aqua 3:54, “Only You Can Rock Me” by UFO 4:59, “Paper Soup Cats” by Jaw 4:18, “Rock is Cool” by Yeah 4:17, “My Girl is Mean to Me” by Can’t Stand Up 3:29, “Only You Can Rock Me” by UFO 4:52, “We’re Not Gonna Take It” by Twisted Sister 3:9, “If I Had a Hammer” by Long Road 4:15, “My Man is a 4×4 Driver” by Ms. Lonely 3:7, “This Song is for Johnny” by Lone Wolf 4:22, “Bite My Arms Off” by Jaw 4:12, “Where’s My Sweater” by The Knitters 3:41, “Is that My Toenail ?” by Clip 4:47, “Anvil Headache” by Clip 4:34, “My Hair is on Fire” by Jaw 3:55] Available Songs By Jaw: [“Paper Soup Cats” by Jaw 4:18, “Bite My Arms Off” by Jaw 4:12, “My Hair is on Fire” by Jaw 3:55] Status: Music Exchange Center (2 users on-line, 9 songs available) On-Line Users: [Ronnie Rocker: 4 songs (online), Peter Punk: 5 songs (online)] Available Songs: [“Rock is Cool” by Yeah 4:17, “My Girl is Mean to Me” by Can’t Stand Up 3:29, “Only You Can Rock Me” by UFO 4:52, “We’re Not Gonna Take It” by Twisted Sister 3:9, “Bite My Arms Off” by Jaw 4:12, “Where’s My Sweater” by The Knitters 3:41, “Is that My Toenail ?” by Clip 4:47, “Anvil Headache” by Clip 4:34, “My Hair is on Fire” by Jaw 3:55] Available Songs By Jaw: [“Bite My Arms Off” by Jaw 4:12, “My Hair is on Fire” by Jaw 3:55] Status: Music Exchange Center (0 users on-line, 0 songs available) On-Line Users: [] Available Songs: [] Available Songs By Jaw: [] (3) Downloading Music Go back to the Song class and add to it an attribute called owner which will be a User object representing the user who happens to own this copy of this song. Note that a Song object may only be owned by one User and that many users can have copies of the same song. Set it to null initially. In the User class, adjust the addSong(Song s) method so that it sets the owner properly. In the User class, add a method called requestCompleteSonglist(MusicExchangeCenter m). This method should gather the list of all available songs from all users that are online at the given music exchange center (i.e., the union of all of their local song lists), and then return an ArrayList formatted as follows (note: there should be 1 String element in the ArrayList per line): COMP 1006A/1406A – F18 – A4 Due Friday, March 20th at 11:59 PM 4 TITLE ARTIST TIME OWNER 1. Hey Jude The Beatles 4:35 Disco Stew 2. Barbie Girl Aqua 3:54 Disco Stew 3. Only You Can Rock Me UFO 4:59 Disco Stew 4. Paper Soup Cats Jaw 4:18 Disco Stew 5. Rock is Cool Yeah 4:17 Ronnie Rocker 6. My Girl is Mean to Me Can’t Stand Up 3:29 Ronnie Rocker 7. Only You Can Rock Me UFO 4:52 Ronnie Rocker 8. We’re Not Gonna Take It Twisted Sister 3:09 Ronnie Rocker Notice that the songs are numbered and that the title, artist, time and owner are all lined up nicely. You should use the String.format() method as described in the notes (Chapter 1). Recall that %-30s in the format string will allow you to display a leftjustified 30-character string. Also, %2d and %02d will allow you to display numbers so that they take 2 places, the 0 indicating that a leading zero character is desired. In the User class, add a method called requestSonglistByArtist(MusicExchangeCenter m, String artist). This method should gather the list of all available songs by the given artist from all users that are online at the given music exchange center (i.e., the union of all of their local song lists), and then return an ArrayList formatted similar to that shown above. In the MusicExchangeCenter class, add a method called getSong(String title, String ownerName) which returns the Song object with the given title owned by the user with the given ownerName, provided that the user is currently online and that the song exists. Return null otherwise. (Hint: you will need to search through the center’s users to find User with the matching ownerName and then search through that user’s songs to find the Song with the given title. It may be a good idea to write an extra helper method in the User class called songWithTitle(String title) that you can make use of). In the User class, add a downloadSong(MusicExchangeCenter m, String title, String ownerName) method that simulates the downloading of one of the songs in the catalog. It should use the getSong(String title, String ownerName) method that you just wrote, and add the downloaded song to the user’s songList (if not null). Download and execute the MusicExchangeTestProgram2.java file to test your new code. Here is the expected output: COMP 1006A/1406A – F18 – A4 Due Friday, March 20th at 11:59 PM 4 Status: Music Exchange Center (5 users on-line, 18 songs available) Complete Song List: TITLE ARTIST TIME OWNER 1. Hey Jude The Beatles 4:35 Disco Stew 2. Barbie Girl Aqua 3:54 Disco Stew 3. Only You Can Rock Me UFO 4:59 Disco Stew 4. Paper Soup Cats Jaw 4:18 Disco Stew 5. Rock is Cool Yeah 4:17 Ronnie Rocker 6. My Girl is Mean to Me Can’t Stand Up 3:29 Ronnie Rocker 7. Only You Can Rock Me UFO 4:52 Ronnie Rocker 8. We’re Not Gonna Take It Twisted Sister 3:09 Ronnie Rocker 9. Meadows Sleepfest 7:15 Sleeping Sam 10. Calm is Good Waterfall 6:22 Sleeping Sam 11. If I Had a Hammer Long Road 4:15 Country Candy 12. My Man is a 4×4 Driver Ms. Lonely 3:07 Country Candy 13. This Song is for Johnny Lone Wolf 4:22 Country Candy 14. Bite My Arms Off Jaw 4:12 Peter Punk 15. Where’s My Sweater The Knitters 3:41 Peter Punk 16. Is that My Toenail ? Clip 4:47 Peter Punk 17. Anvil Headache Clip 4:34 Peter Punk 18. My Hair is on Fire Jaw 3:55 Peter Punk Disco Stew before downloading: Disco Stew: 4 songs (online) Disco Stew after downloading: Disco Stew: 7 songs (online) Disco Stew after downloading Ronnie’s: Disco Stew: 8 songs (online) Song’s by Jaw: TITLE ARTIST TIME OWNER 1. Paper Soup Cats Jaw 4:18 Disco Stew 2. Bite My Arms Off Jaw 4:12 Disco Stew 3. Bite My Arms Off Jaw 4:12 Peter Punk 4. My Hair is on Fire Jaw 3:55 Peter Punk (4) Paying the Price Now, in order to make all of this legal, we must have a way to compensate the musical artists for their hard work and wonderful music. An artist should receive 25 cents each time one of their songs is downloaded. Hence, for each artist, we will keep track of how much money in royalties they have. Add the following attributes to the MusicExchangeCenter class: royalties – a HashMap with the artists’ names as the keys and the values are floats representing the total amount of royalties for that artist so far. It should only contain artists who have had songs downloaded. You will update this HashMap later. COMP 1006A/1406A – F18 – A4 Due Friday, March 20th at 11:59 PM 4 downloadedSongs – an ArrayList containing all of the songs that have been downloaded. This list will, in general, contain duplicate Song objects. Write a method in the MusicExchangeCenter class called displayRoyalties() that displays the royalties for all artists who have had at least one of their songs downloaded. It should display a two-line header and then one line per artist showing the royalty amount as well as the artist name as follows: Amount Artist ————— $0.75 Sleepfest $1.50 Clip $0.25 Jaw $0.50 Long Road $0.25 Yeah $0.25 UFO In the getSong() method in the MusicExchangeCenter, adjust the code so that if the song is found (i.e., able to be downloaded), then it is added to the downloadedSongs list. Additionally, the royalties for the artist of the song should be updated within this method. Write a method in the MusicExchangeCenter class called uniqueDownloads() that returns (i.e., not displays) a TreeSet of all downloaded Song objects such that the set is sorted alphabetically by song title. There should be no duplicates songs in this set. To add the Song objects to the TreeSet, the Song class will need to implement Comparable and you will need to write the corresponding compareTo(Song s) method in the Song class. Write a method in the MusicExchangeCenter class called songsByPopularity() that returns (i.e., not displays) an ArrayList of Pair objects where the key of the pair is an Integer representing the number of downloads and the value is the Song object. The integer key should represent the number of times that the song was downloaded. The list returned should be sorted in decreasing order according to the number of times the song was downloaded. To sort a list of Pair objects, you can use the following code: Collections.sort(yourListOfPairs, new Comparator() { public int compare(Pair p1, Pair p2) { // PUT YOUR CODE IN HERE } }); COMP 1006A/1406A – F18 – A4 Due Friday, March 20th at 11:59 PM 4 Just insert the missing code so that it returns an appropriate integer indicating whether pair p1 comes before or after pair p2 in the sort order (see notes, Chapter 8, Page 281). Run the MusicExchangeTestProgram3.java test file to make sure it works with your code. Here is the expected output: Status: Music Exchange Center (5 users on-line, 18 songs available) Here are the downloaded songs: “Bite My Arms Off” by Jaw 4:12 “Meadows” by Sleepfest 7:15 “If I Had a Hammer” by Long Road 4:15 “Is that My Toenail ?” by Clip 4:47 “Anvil Headache” by Clip 4:34 “Is that My Toenail ?” by Clip 4:47 “If I Had a Hammer” by Long Road 4:15 “Anvil Headache” by Clip 4:34 “Meadows” by Sleepfest 7:15 “Only You Can Rock Me” by UFO 4:52 “Is that My Toenail ?” by Clip 4:47 “Is that My Toenail ?” by Clip 4:47 “Rock is Cool” by Yeah 4:17 “Meadows” by Sleepfest 7:15 Here are the unique downloaded songs alphabetically: “Anvil Headache” by Clip 4:34 “Bite My Arms Off” by Jaw 4:12 “If I Had a Hammer” by Long Road 4:15 “Is that My Toenail ?” by Clip 4:47 “Meadows” by Sleepfest 7:15 “Only You Can Rock Me” by UFO 4:52 “Rock is Cool” by Yeah 4:17 Here are the downloaded songs by populariry: (4 downloads) “Is that My Toenail ?” by Clip 4:47 (3 downloads) “Meadows” by Sleepfest 7:15 (2 downloads) “Anvil Headache” by Clip 4:34 (2 downloads) “If I Had a Hammer” by Long Road 4:15 (1 downloads) “Bite My Arms Off” by Jaw 4:12 (1 downloads) “Only You Can Rock Me” by UFO 4:52 (1 downloads) “Rock is Cool” by Yeah 4:17 Here are the royalties: Amount Artist ————— $0.75 Sleepfest $1.50 Clip COMP 1006A/1406A – F18 – A4 Due Friday, March 20th at 11:59 PM 4 $0.25 Jaw $0.50 Long Road $0.25 Yeah $0.25 UFOA trie, also known as a prefix tree, is a tree-based data structure that stores key/value pairs (like a HashMap). The keys in tries are usually strings. In this assignment, you will implement a trie data structure that uses recursion to store string keys and their associated string values. The root node in the trie will be empty (no key or value). Each node in the trie, including the root, will store a hash map with character keys and trie node values. This structure will allow you to search for a string key in the trie by repeatedly looking up the node associated with the next character in the key (if it exists). As an example, consider the picture below (ignore the red for now). This trie contains the keys/values “A”, “ATE”, “ARE”, “BE”, “SIT”, and “SO” (assume the key and value are the same, null values indicate nothing has been added there). If you were to look up the key “ATE” in the trie, you would end up following the red node path. Starting at the root node, look up and go to the node associated with ‘A’. From that node, look up and go to the node associated with ‘T’, and then look up and go to the node associated with ‘E’. If the value stored in this final node is null, the key does not exist in the trie. If the value is not null, the node’s value represents the value associated with the given key (alternatively, if you are performing a put operation, you can add the value to the node). If you were to look up the key “BAT”, you would start at the root node, look up and go to the node associated with ‘B’, and then determine that the key “BAT” is not in the trie since ‘A’ is not associated COMP 1406 – W20 – A5 Due Friday, April 3 rd at 11:59 PM with the current node (i.e., is not in that node’s hashmap). If the additional keys “AT”, “BE”, and “SOD” were added, the trie would then look like: An interesting property of the trie structure is that the key for any node contained within a subtree rooted at a node X has the key that would lead to X as a prefix. As examples, “SIT”, “SO”, and “SOD” all begin with the character ‘S’ and are all contained within the sub-trie rooted at the node you would reach if you looked up the key ‘S’. If “SOME”, “SODA”, and “SOAR” were added to the above trie, they would all be contained in the subtrees of the key “S” and the key “SO”. This allows tries to easily produce a set of keys that begin with a particular prefix. To start the assignment, download the Assignment5-Base-Code.zip file from cuLearn. This zip contains an IntelliJ project containing 4 Java files: 1. TrieMapInterface: This interface defines the methods that your TrieMap class must support. These methods should work similarly to how they would for a hash map or any other map data structure. The put method should add the associated key/value pair to the trie. If the key is already in the trie, the value should be updated. The get method should return the value associated with the given key, if the key exists. If the key does not exist in the trie, the get method should return null. The containsKey method should return true if the trie contains the given key and false otherwise. The getValuesForPrefix method must return an ArrayList of String values that contains all keys within the trie that start with the specified prefix. The print method should print all of the values contained within the trie. 2. TrieMap: This class contains skeleton code outlining the methods required to implement the TrieMapInterface. I have also left method signatures from my own solution, which may provide hints regarding possible solutions. You can remove or otherwise change the class however you wish, so long as your class still implements the TrieMapInterface. All method implementations COMP 1406 – W20 – A5 Due Friday, April 3 rd at 11:59 PM must function recursively. This is the only class that you must add code to in order to complete the assignment. You are free to add code to the other classes if you wish. 3. TrieMapNode: The class representing a node in the trie. It contains a hash map with character keys and TrieMapNode values (similar to a binary tree but with more than two possible children), along with a constructor and necessary get/set methods. You don’t need to change this class but can make changes if you want. 4. TrieMapTester: This class will run several tests on your TrieMap implementation and count the number of errors. This will run a significant number of operations, so it is probably a good idea to run your own smaller tests first to verify your TrieMap implementation is likely correct. The implementation of the TrieMap class may seem difficult initially. However, after becoming familiar with recursively moving through the trie structure, you will find that most methods are quite similar. So completing the first few methods is likely to be significantly more difficult than completing the others. Personally, I would recommend implementing and testing the methods in this order: constructor, put, print, containsKey, get, getValuesForPrefix. Grade Breakdown Put Method: 10 marks Get Method: 5 marks Contains Key Method: 5 marks Get Values for Prefix Method: 20 marks Print Method: 10 marks Total: 50 marksIn this assignment, you will practice using recursion, as well as file operations. Submit a single ZIP file called assignment6.zip containing your IntelliJ project. This assignment has 50 marks – see the marking scheme posted on cuLearn for details. Assume that we have an assembly line that can take a picture of a machine part which moves along a conveyor belt. The picture (or image) is represented as a 2D grid of pixels which are either black or white. The pixels can be accessed by specifying the row and column of the pixel where rows and columns are specified by an integer value. The machine examines the images and attempts to determine whether or not the parts are broken. A broken part will appear as a set of black pixels which are not all connected together (i.e., there is a separation between one or more sets of black pixel groups. Here are some examples of four possible images. Note that (c) and (d) represent images of broken parts. The red border represents the perimeter of a part composed of black pixels. COMP 1406 – W20 – A6 Due Friday, April 24th at 11:59 PM Due Friday, March 20th at 11:59 PM (1) The PartImage class Download the provided A6-Base-Code.zip file and extract the included IntelliJ project. This project contains a PartImage class, which represents one of these images using a 2-dimensional array of booleans. You must complete the following methods in the PartImage class. Note that all the recursive methods may be implemented in a ‘destructive’ sense. That is, you can change the state of the object within your recursive implementation and do not need to recover to the original starting state. • Complete the static readFromFile(String fileName) method that will open the specified file, which will contain the data for a single part’s image. This method must read the part image data from the file and return a new PartImage object with the correct attributes to represent that part image. The data in the file will be organized like a 2D array, with each line representing a row of the part’s image data. Each row will contain some number of comma-separated 0s and 1s, indicating a white or a black space respectively. For example, the data contained in a file representing part (a) from above might look like: 0,0,0,0,0,0,0,0,0,0 0,1,1,1,1,1,1,0,0,0 0,1,1,1,1,1,1,0,0,0 0,0,0,1,1,1,1,1,1,0 0,1,1,1,1,1,1,1,1,0 0,1,1,1,1,1,1,1,1,0 0,1,1,1,1,1,1,0,0,0 0,0,0,0,1,1,1,0,0,0 0,0,0,0,0,0,0,0,0,0 Note that you cannot assume that you know how wide each row will be or how many rows are present. You will have to compute this in order to initialize the size of any 2D boolean arrays your class uses. Three possible exceptions could arise within this method: 1. FileNotFoundException – if the specified file is not found, your method’s code should handle the exception gracefully and return a null object. 2. IOException – if there is another type of input error, your method’s code should handle the exception gracefully and return a null object. 3. InvalidPartImageException – if any line in the file does not contain the same number of values as all other lines (e.g., 9 columns in one line and 10 in another), or one of the values is not 0/1, your method must throw a new InvalidPartImageException with the current filename. This exception will be handled by the provided test code. • Complete the print() method that will print out the image in the console window which mayprint something like what is shown below for the image in picture (a) above. ———- -******— -******— -********- —******- -********- -********- -******— —-***— ———- COMP 1406 – W20 – A6 Due Friday, April 24th at 11:59 PM Due Friday, March 20th at 11:59 PM • Complete the findStart() method that returns the location (row/column) of any black pixel in the image. It uses the Point2D as the return value. If no black pixel is found, the method should return null. • Complete the partSize() method so that it returns an int representing the number of black pixels in the image. This can be done using a double FOR loop. • Complete the method called expandFrom(int r, int c) that recursively examines the image by traversing its pixels, examining (i.e., “visiting”) black pixels in all directions that are connected to a starting point black pixel (specified by the parameters). The idea is that this method will determine all black pixels that are connected to the starting pixel. Additionally, the method should set the black pixels to white (hints: when a white pixel is encountered during the recursion, this is an indication that you don’t need to keep recursively checking in that direction). This method MUST be done recursively without loops, otherwise you will receive 0 marks for this part. • Complete the method called perimeterOf(int r, int c) which should return an integer representing the perimeter of the part which starts at the given (r,c) point. The method MUST be done recursively without loops, otherwise you will receive 0 marks for this part. For example, in the image (A) shown above, the perimeter is 36 (which is the red border length, not the number of black cells on the border) and in image (B) it is 106. As for the other two images, it depends where you started expanding from, since the piece is broken into multiple parts. (hints: You will need to mark pixels as being visited (perhaps use another 2D array). Make sure not to re-visit these pixels. Also, make sure to handle borders correctly. A black pixel on the top/left border corner, for example, will add 2 to the perimeter count for the top and the left.) • Complete the method called countPieces() which should return an integer representing the number of separate pieces contained in the part image. For example, part (a) above contains 1 piece, where part (d) contains 8 pieces. Once you have implemented these, you can use the PartImageTester class to test your solutions.
