Load multiple packages to your environment using the following code (you can add more packages to the current list as per your need): knitr::opts_chunk$set(echo = TRUE) library(pacman) p_load(tidyverse, foreign, corrplot, stargazer, coefplot, effects)This week, we will begin familiarizing ourselves with the replication exercise. Download and save the paper that we will be replicating. Make sure to download and save the Online Appendix (you will find it on the ASR website).1. Read the paper closely and respond to the following questions:(a) What are the authors’ research questions? (b) What is the gap in the literature that the authors aim to fill? How does their analysis advance the literature?(c) What is the population that they are making inferences about? Be specific and make sure to identify the geographical region that they are focusing on, the time period, demographic characteristics, and so on.(d) Do they have data on all individuals in the population? If they don’t, how do they solve this? (e) Did the authors collect the data themselves? If they did, describe their sampling procedure. If they didn’t, identify and describe the data source and discuss the sampling procedure that was used to collect this data.2. As you read the text, make a list of all variables or characteristics of the population that the authors mention throughout the paper (e.g., gender, age, wages, occupation, . . . ). Submit a list with all the variables and characteristics that you have identified in the text. Note: Make sure to read footnotes and table notes; they contain important information to understand who is in the sample.3. Based on your answers to prior questions, select the samples and variables that you think you will need to replicate the paper in your IPUMS account. Submit a screenshot of the page where you can see the samples and variables that you have selected. Note: you can obtain this from your “Data Cart”.Import the dataset sat_math.dta to your R environment and examine the effect of IQ and other variables on SAT math score. Hint: use read.dta() Variable Name Variable Detail sat_math SAT Math Score female The Female Dummy (Male = 0) black/other Two Racial Dummies (White as the Reference Group) meduy Mother’s Years of Schooling feduy Father’s Years of Schooling hours Average Weekly Study Hours IQ IQ Score (0 to 100)1. Report descriptive statistics: (a) Create a table that reports descriptive statistics (you should at least report the means) of all the variables grouped by gender. Its structure should look similar to the “1970” column of Table A1a in the replication paper, except that we are using gender instead of race as the grouping variable.Note: You can either use tidyverse (group_by() and summarise) then transpose the table, or search other R packages that can generate descriptive statistics table for you. At this point, don’t worry too much about the specific formatting issues of the table. In practice, we will format the table in LaTeX instead of R Markdown.(b) Create a correlation matrix and display it. Then visualize the matrix using any one plot option that you think can effectively communicate the result from the corrplot package as demonstrated in this webpage.2. Create scatter plots: • Besides the key dependent variable (DV) sat_math, choose one numeric independent variable (IV) that seems to have a meaningful relation to the DV based on the correlation matrix you created, and then create the following plots. Note: Make sure to add appropriate titles, axis labels, and plot legend for each plot.(a) A scatter plot of the DV and IV (b) A scatter plot of the DV and IV with a fitted linear regression line (c) A scatter plot of the DV and IV, and each observation is color coded by gender (make sure to coerce your gender variable to a character or factor using as.character() or as.factor(), or recode your gender variable to a character variable with values “Male” and “Female” using mutate() and ifelse().) (d) On top of plot (c), fit a linear regression line for each gender group, the lines should also be color coded3. Additional exploratory data analysis: (a) What are your preliminary findings/reflections on the data based on the descriptive statistics, the correlation matrix, and the scatter plots? (b) What other exploratory data analysis will be useful for you to better understand the data before modeling? Please implement some additional exploratory data analysis and discuss your preliminary findings.4. Nested models: • Build five nested models that use sat_math as the DV and report regression results in a table using stargazer() from the stargazer package.Note: You can set type = “text” in stargazer() when viewing the table in R, but before knitting to PDF you should set type = “latex” (a) Model 1: Baseline (only add “IQ” as the independent variable) (b) Model 2: Model 1 + Demographic Characteristics (c) Model 3: Model 2 + Parental Education (d) Model 4: Model 3 + Weekly Study Hours (e) Model 5: Model 4 + An Interaction Between IQ and the Female Dummy5. For the result of Model 1: (a) What are the hypotheses that you are testing in this model with your t-values in the (Intercept) and IQ row of the modeling results? (b) Create a 95% confidence interval for the parameter βIQ based on Model 1 result.6. Interpret regression coefficients: (a) How does the coefficient of “IQ” change across models? What could be the possible reason(s) for such changes? (b) Interpret the coefficient of “black” in Model 4.(c) Interpret the coefficient of “meduy” in Model 4. (d) Interpret the coefficient of the interaction effect between IQ and the Female Dummy in Model 5.7. Create a coefficient plot for Model 5 with appropriate title and labels. 8. On the basis of Model 5, by holding other variables at their means, create a figure demonstrating the predicted SAT math score by gender and IQ levels (with confidence interval).Part 3 (Bonus) Data Simulation Simulation is a fun and effective way to learn about statistical inference. You will get a better understanding of how each population parameter affects the shape of the distribution.Now that we have learned about how to identify interactions from a given sample, you can try simulate a data whose true data generating process involves interaction between two variables. For example, you can try to reproduce a similar scatter plot we saw in class (the right panel) by simulating a data whose variables have such associations:Or, you can try to reproduce a scatter plot that demonstrates the Simpson’s Paradox: Note: Your output does not need to replicate the exact layout of the example graphs. You will get extra credit as long as you generate a similar graph that illustrates the relationship (either a positive or negative interaction, or the Simpson’s Paradox) clearly. Remember to use set.seed() for any random process.
Recall the formulas for population mean: µ = 1 N X N i=1 xi (1) and variance: σ 2 = 1 N X N i=1 (xi − µ) 2 (2) where N is the population size.1. Write a function in R that calculates the population mean according to Equation 1 without using any R functions that directly calculate the mean. For example, you cannot use mean() from base R, or summarise(., mean = mean()) from tidyverse. • Name your function pop mean. • The function should take a numeric vector as its input. • The function should return a numeric variable that is the population mean calculated based on the vector input.2. Write a function in R that calculates the population variance according to Equation 2 without using any R functions that directly calculate the variance. For example, you cannot use var() from base R, or summarise(., var = var()) from tidyverse. • Name your function pop var. • The function should take a numeric vector as its input. • The function should return a numeric variable that is the population variance calculated based on the vector input. • You can use the pop mean() function you just created for your pop var() function.3. Import gapminder.csv to your R environment. • Apply the two functions you just created to the lifeExp variable in gapminder. • Use R functions that directly calculate mean and variance to the same lifeExp variable vector. • Report your results of the above two steps either in text or in a table. The results for the mean should be equal, but the results for variance should be different. Find out and explain why the results in variance differ.Note: For this exercise, we will assume that there is no missing values (i.e. no NAs) in the vector, so you don’t need to consider how to deal with NA values. Hint: You can format tables using kbl() from the kableExtra package.2 Data transformation using tidyverse Import parent inc.csv to your R environment. The data frame looks like this: famid father name mother name father income mother income 1 Arthur Jess 42000 45000 2 Harry Pam 35000 24000 3 Matt Mary 78000 55000Use tidyverse functions and the piping syntax to transform the data frame to the following structure: famid type name income 1 father Arthur 42000 1 mother Jess 45000 2 father Harry 35000 2 mother Pam 24000 3 father Matt 78000 3 mother Mary 55000Make sure to document the steps you take in your code and display the tidied data frame in your PDF document.Hints: • You can review how to use the pivoting functions here. • You can use str remove() or str extract() functions for mutating a new variable that extracts part of the text from a string, for example extracting “father” from “father name”.• You can separate the original data frame into parts and then combine them if you cannot figure out how to transform it altogether. • You can format tables using kbl() from the kableExtra package.3 Population, sample, and sampling distribution To make your code reproducible, use the set.seed() function whenever you are generating random numbers or sampling randomly. Read the documentation of this function in R if you do not know how it works.1. Create a population data frame that has one variable called “value”, whose value follows a normal distribution with population mean µ = 5 and population variance σ 2 = 1 with 100,000 observations. 2. Create a histogram of the population with appropriate title and labels. Add a vertical line at the population mean.3. Draw a random sample from the population, with sample size n = 50. 4. Plot a histogram of the sample with appropriate title and labels. Add a vertical line at your point estimate of the population mean. How does this histogram compare to the one you created in question 2?5. Based on your sample, report your point estimate of the population mean ˆµ, the standard error of this estimate, and its 95% confidence interval. Show the formulas you used for calculating these statistics.6. Simulate the sampling distribution of the sample mean (n = 50) using 1,000 draws. That is, repeat the action you took for question 3 for 1,000 times and save the mean you get for each repetition to a data object. Hint: Use for loop.7. Create a histogram of the sampling distribution of the sample mean you simulated in question 6 with appropriate title and labels. Add a vertical line at your point estimate of the population mean.8. Using the sampling distribution you obtained in question 6, report your point estimate of the population mean ˆµ, the standard error of this estimate, and the 95% confidence interval of this estimate. Show the definitions or formulas you used for calculating these statistics. Hint: The standard error in this question should be worked out based on the properties of the sampling distribution.9. Repeat questions 3 to 8 increasing the size of your sample to n = 1,000. Plot and report your results. Then, using the concepts that we learned in class, summarize the differences with respect to what you obtained with a sample of 50. Hint: Which law or theorem that we learned in class is being demonstrated here?
Graphs are the most general of the common data structures; consider that a scalar object is a degenerate list, which is a degenerate tree, which is itself a degenerate graph, or in other words, every data structure we’ve discussed this semester can be represented as a graph. Due to their extreme generality, it’s rare that you’ll use a generic “graph” data structure.The limited set of things you might do with a list make two generic list implementations—an array based- and a linked-structure—good enough for most implementations, and it’s only if you are doing, e.g., low-level system programming that you might have a good reason to write a custom, one-off list. But there is so much variation in graphs that it is perhaps impossible to write a good and useful generic graph implementation.Hash tables provide a means to get constant-time look-up performance on a collection. Usually, the data comes to us at runtime, often in an on-line fashion. In this case, we take what foreknowledge we can to inform best practices in hash table construction, choosing a hash function, etc., to build a data structure with as close to optimal performance as possible; however, if the keys in the table are known beforehand, it’s always possible to construct a perfect hash table, a table in which every key maps to a unique slot.There are many algorithms to construct such a table and the associated hash function; almost all of them are implemented using graphs.For this project, you will be implementing a perfect hash table construction algorithm1 . This algorithm generates a pair of tables of random numbers. Keys are hashed with the values in each these tables, giving two integers (one for each table).These integers are then taken as node indices in a graph, with an edge between them. So long as the resultant graph—after hashing all of the keys—contains no cycles, the algorithm is ready to generate the hash table as a function of the tables (the T tables) used in the graph generation and a function g() on those tables.Algorithm Example NOTE: This algorithm looks pretty intimidating at first glance. With some careful reading and workingthrough of examples, you should find it’s actually fairly straightforward. That said, you don’t necessarily have to understand it at all! If you find yourself getting anxious about all this “scary-looking stuff”, jump down to the Requirements sections, read that, then come back here with a more relaxed mindset. It is very common for professional programmers to be required to implement solutions to problems that they don’t actually understand, so if you find yourself doing that, here or elsewhere, please know that it is normal.This is not to advocate for ignorance, however–it’s always better to understand something than not to understand it–only to recognize that sometimes the cost-benefit of understanding is too high!The example below was generated by hand, and uses an optimization that would be very difficult to implement in program control. We note that our original keys (the number names from “one” to “ten”) 1The algorithm is presented in: Zbigniew J. Czech, George Havas, and Bohdan S. Majewski, “An optimal algorithm for generating minimal perfect has functions”, Information Processing Letters, 43(5):257-264, October 1992.are unambiguously differentiable by the first two letters. Thus, we can simplify the presentation by using only the first two letters of the keys. In your Java program, you will always use the entirety of every word; however, the method that hashes the words is already implemented for you, so you don’t need to concern yourself with it unless you are endeavoring to fully understand the implementation.Our keys and the “sub-keys” that we’re using in this example follow: Key Minimum Unique Sub-key one on two tw three th four fo five fi six si seven se eight ei nine ni ten teA modulus must be chosen, giving a maximum number in our tables, and a maximum number of nodes in the resultant graph. The paper authors choose a value that is one more than twice the number of keys, so we do too. This choice has implications on the runtime of the algorithm (smaller moduli increase the probability of cycles in the resultant graph, forcing a restart of the algorithm). If the modulus is too small, the algorithm will enter an infinite loop.Next, we populate our tables, T1 and T2, with random numbers less than the modulus. Each of the two tables will have the same number of rows as the length l of the sub-key. The i th row, 0
The objective of this exercise is to decode/unzip a message archived with a binary-tree-based algorithm. The program should ask for a single filename at the start: “Please enter filename to decode: “, decode the message in the file and print it out to the console. The name of the compressed message file will end in .arch, e.g. “monalisa.arch”. The file consists of two or three lines: the first one or two lines contain the encoding scheme, and the second or third line contains the archived message.The archival algorithm uses a binary tree. The edges of the tree represent bits, and the leaf nodes contain one character each. Internal nodes are empty. An edge to a left child always represents a 0, and an edge to a right child always represents a 1. Characters are encoded by the sequence of bits along a path from the root to a particular leaf. The below tree serves as an example.The tree on the left encodes these characters: Character Encoding a 0 ! 100 d 1010 c 1011 r 110 b 111With the above encoding, the bit string: 10100101010110110111100 is parsed as 1010|0|1010|1011|0|110|111|100 which is decoded as: dadcarb!With this encoding, we can automatically infer where one character ends and another begins.That is because no character code can be the start of another character code. For example, if you have a character with the code 111, you cannot have the codes 1 and 11, as they would be internal nodes.The following steps decode one character from the bit string: Start at root Repeat until at leaf Scan one bit Go to left child if 0; else go to right child Print leaf payload3. Input Format The archive file consists of two lines: the first line contains the encoding scheme, and the second line contains the compressed string. For ease of development and to make the archive file human-readable, each bit is represented as the character ‘0’ or ‘1’, rather than as an actual bit from a binary file.The encoding scheme can be represented as a string. For example, the tree from section 2 can be represented as: ^a^^!^dc^rb where ^ indicates an internal node. The above code represents a preorder traversal of the tree.The dadcarb! message is encoded in the following file (“dadcarb.arch”): ^a^^!^dc^rb 10100101010110110111100There are four test files in project3_Test_Files.zip. Note the encoding scheme representations may include a space character and a newline character, thereby breaking the tree string into two lines! The newline character needs to be parsed correctly if the encoding file has three lines in total.4.1. Read in the first line (and possibly second line, if newline is part of the tree) of the file and construct the character tree. Convert the line input into a MsgTree structure using preorder traversal. The tree should be in a class MsgTree with the following members: public class MsgTree{ public char payloadChar; public MsgTree left; public MsgTree right;//Need static char idx to the tree string for recursive solution private static int staticCharIdx = 0; //Constructor building the tree from a string public MsgTree(String encodingString){} //Constructor for a single node with null children public MsgTree(char payloadChar){} //method to print characters and their binary codes public static void printCodes(MsgTree root, String code){} }When building the tree, try a recursive solution where staticCharIdx tracks the location within the tree string. You can pass the same tree string during recursive calls, and update the staticCharIdx to point to the next character to be read.If you decide to implement an iterative solution, you will receive a 15% bonus, as it is considerably more difficult. In that case, you cannot get the 5% bonus for printing statistics. printCodes() does a recursive preorder traversal of the MsgTree and prints all the characters and their bit codes: character code ————————- c 1011 r 110 b 111You are allowed to print the header of the table (character, code, —-) in main().4.2. Write a method public void decode(MsgTree codes, String msg) to decode the message. It would print the decoded message to the console: MESSAGE: The quick brown fox jumped over the lazy dog. You are allowed to print “MESSAGE:” in main().The overall output of the program should be the output of printCodes() followed by the output of decode(): character code ————————- c 1011 r 110 b 111 MESSAGE: The quick brown fox jumped over the lazy dog.5. Submission Put your java class code in the edu.iastate.cs228.hw4 package. Do not submit your class files. Please follow the guideline posted under Documents & Links on Canvas. Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW4.zip.No template files are provided other than Section 4.1.6. Extra credit (5% or 15%) Print the following statistics after the rest of the program output: 6.8 179 STATISTICS: Avg bits/char: Total characters: Space savings: 57.5%The space savings calculation assumes that an uncompressed character is encoded with 16 bits. It is defined as (1 – compressedBits/uncompressedBits)*100.To earn a 15% non-cumulative bonus (either 5% for statistics or 15%), you can create an non-recursive, iterative solution for building the tree, but be advised that it will require hours of more effort than the recursive solution.Name your submission Firstname_Lastname_HW4_extra.zip if you completed the work for extra credit.
1. IntroductionThe purposes of this assignment are to practice working with a linked data structure to become intimately familiar with the List and ListIterator interfaces This assignment will also provide many opportunities to practice your debugging skills.1.1. Summary of Tasks Implement a class StoutList that extends AbstractSequentialList along with inner classes for the iterators. A skeleton is provided. See the implementation and suggestions for getting started sections for details.In this assignment you will implement a somewhat peculiar-looking linked list. The list will be a doubly-linked list with dummy nodes for the head and tail. An empty list has the following form: Figure 1- an empty list So far so good. Now, let M be a fixed, positive even number. The twist is that each node can store up to M data elements, so the number of linked nodes may not correspond to the number of elements.For example, after some sequence of add and remove operations, one of these lists might have the following form: Figure 2 – a possible list of size 6, where M=4 Note that there are 6 elements, and their logical indices are shown below the nodes. The number of actual linked nodes may vary depending on the exact sequence of operations. Each node contains an array of the element type having fixed length M. Therefore, each logical index within the list is represented by two values: the node n containing the element, and the offset within that node’s array. For example, the element E shown above at logical index 4 is in node at offset2. There are special rules for adding and removing elements to ensure that all nodes, except possibly the last one, have at least elements. These rules are described in detail in a later section. Note that you can get started and make significant progress on the assignment without needing all the add and remove rules. See the section suggestions for getting started.2. Implementation of StoutList For the implementation, you must implement the class StoutList extending AbstractSequentialList . AbstractSequentialList is a partial implementation of the List interface in which the size() and listIterator() methods are abstract. All other operations have default implementations using the list iterator. The StoutList should NOT allow null elements. Your add methods (those within the iterator as well as those implemented without the iterator) should explicitly throw a NullPointerException if a client attempts to add a null element. A skeleton of the code can n1 M/2 be found in project3_template.zip. The skeleton code includes a constructor, an inner class Node, and two methods toStringInternal() . There is also some code in place to support logging.2.1. Methods to override In addition to implementing the iterators described below, you must override the following methods of AbstractList without using the iterator: int size() boolean add(E item) void add(int pos, E item) E remove(int pos) Iterator iterator() ListIterator listIterator() ListIterator listIterator(int pos) The methods above must conform to the List interface, with the added restriction that the add() methods must throw a NullPointerException if the item argument is null . The purpose of asking you to override add() and remove() is primarily to help ensure that you can get partial credit for implementing the split and merge strategies even if your iterator isn’t completely correct.2.2. The Node inner class A minimal Node class is provided for you. It has methods for adding an element at a given offset and removing an element at a given offset. Note that empty cells within the array (i.e., those with index >= count) should always be null . You can add additional features to this class if you find it helpful to do so.2.3. The toStringInternal methods These methods show the internal structure of the nodes and are useful for debugging. Normally, such a method would not be public (since it reveals implementation details), but we are making it public to simplify unit testing. For example, if the list of Figure 3 contained String objects “A”, “B”, “C”, “D” and “E”, an invocation of toStringInternal() would return the string: [(A, B, -, -), (C, D, E, -)] where the elements are displayed by invoking their own toString() methods and empty cells in the array inside each node (which should always be null ) are displayed as “-”. A second version takes a ListIterator argument and will show the cursor position as a character “|” according to the nextIndex() method of the iterator. For example, if iter is a ListIterator for the list above and has nextIndex() = 3, the invocation toStringInternal(iter) would return the string: [(A, B, -, -), (C, | D, E, -)] Do not modify these methods.2.4. Finding indices Your index-based methods remove(int pos) , add(int pos, E item) and listIterator(int pos) method must not traverse every element in order to find the node and offset for a given index; you should be able to skip over nodes just by looking at the number of elements in the node. For example, for the list of Figure 9, to find the node and offset for logical index 7, you can see 3 elements in the first node, plus 2 in the second node, which makes 5, plus 4 in the third node, which is 9. Since 7 is greater than 5 and less than or equal to 9, index 7 must be in the third node. You may find it helpful to represent a node and offset using a simple inner class similar to the following: private class NodeInfo { public Node node; public int offset; public NodeInfo(Node node, int offset) { this.node = node; this.offset = offset; } } Then you can create a helper method something like the following: // returns the node and offset for the given logical index NodeInfo find(int pos){…}You must provide a complete implementation of an inner class StoutIterator implementing Iterator and a class StoutListIterator implementing ListIterator . The StoutIterator does NOT need to implement remove() (can throw UnsupportedOperationException ). Optionally, if you are confident that your StoutListIterator is correct, you can return an instance of StoutListIterator from your iterator() method and forget about StoutIterator . However, you are encouraged to keep them separate when you first start development, since the basic onedirectional Iterator, without a remove operation, is relatively simple, while the add and remove operations for the full ListIterator are tricky.4. Suggestions for Getting Started 1. Implement add(E item) . Adding an element at the end of the list is relatively straightforward and does not require any split operations. (e.g. see Figures 3 – 5). You can use toStringInternal() to check. 2. Implement the hasNext() and next() methods of StoutIterator and implement the iterator() method. At this point the List methods contains(Object) and toString() should work.3. Start StoutListIterator. Implement ListIterator methods nextIndex() , previousIndex() , hasPrevious() , and previous() . These methods are straightforward. Implement the listIterator() method. You should then be able to iterate forward and backward, and you can check your iterator position using toStringInternal(iter) . The indexOf(Object obj) method of List should work now.4. Implement the set() method of StoutListIterator . You will need to keep track of whether to act on the element before or after the cursor (and possibly throw an IllegalStateException ), but the method is not complicated since it doesn’t have to change the structure of the list or reposition the cursor.5. Implement a helper method such as the “find” method described above under finding indices. Then you can easily implement the listIterator(int pos) method. After that, the get(int pos) of List should work.6. Implement the add(int pos, E item) method. Now you will need to carefully review the rules for adding elements. Here is a suggestion for keeping things organized. Write a helper method whose arguments include the node and offset containing the index pos at which you want to add, e.g., private NodeInfo add(Node n, int offset, E item){…} (If pos = size, the arguments should be the tail node and offset 0.) The return value should be the actual node and offset at which the new element was placed. (In some cases this will be the given node and offset, in some cases it will be the previous node, and in case of a split there might be a completely new node.) You don’t need the return value for the add method, but you will need it in the iterator.7. Implement the remove(int pos) method. Again, you will need to carefully review the rules for removing elements and merging. 8. Implement the add() method of listIterator. This is not too bad if you have the helper method from (6). The catch is that after adding an element, you have to update the logical cursor position to the element after the one that was added. 9. Implement the remove() method of listIterator. The tricky part is that you have to update the cursor position differently depending on whether you are removing ahead of the cursor or behind the cursor, and depending on whether there was a merge operation. 5. The add and remove Rules5.1. Adding an element (see Figures 3 – 8) The rules for adding an element X at index are as follows. Remember that adding an element without specifying an index is the same as adding at index i = size. For the sake of discussion, assume that the logical index = size corresponds to node = tail and offset = 0. Suppose that index occurs in node n and offset off. (Assume that index = size means n = tail and off = 0) if the list is empty, create a new node and put X at offset 0 otherwise if off = 0 and one of the following two cases occurs, if n has a predecessor which has fewer than M elements (and is not the head), put X in n’s predecessor if n is the tail node and n’s predecessor has M elements, create a new node and put X at offset 0 otherwise if there is space in node n, put X in node n at offset off, shifting array elements as necessary otherwise, perform a split operation: move the last M/2 elements of node n into a new successor node n’, and then if , put X in node n at offset off if , put X in node n’ at offset5.2. Removing an element (see Figures 9 – 14) The rules for removing an element are: if the node n containing X is the last node and has only one element, delete it; otherwise, if n is the last node (thus with two or more elements) , or if n has more than elements, remove X from n, shifting elements as necessary; otherwise (the node n must have at most elements), look at its successor n’ (note that we don’t look at the predecessor of n) and perform a merge operation as follows: if the successor node n’ has more than elements, move the first element from n’ to n. (mini-merge) if the successor node n’ has or fewer elements, then move all elements from n’ to n and delete n’ (full merge)5.3 Examples: adding some elements to a list off ≤ M/2 off > M/2 (off − M/2) M/2 M/2 M/2 M/2 Figure 3- an example list Figure 4 – after add(V) Figure 5 – after add(W) Figure 6 – after add(2, X) Figure 7 – after add(2, Y) Figure 8 – after add(2, Z) 5.4. Examples: removing some elements from a list Figure 9 – example list Figure 10 – after removing W Figure 11 – after removing Y (mini-merge) Figure 12 – after removing X (mini-merge) Figure 13 – after removing E (no merge with predecessor node) Figure 14 – after removing C (full merge with successor node)6. Sorting Implement the following two sorting methods within the StoutList class: public void sort(); public void sortReverse(); The sort() method implements insertion sort by calling a private generic method: private void insertionSort(E[] arr, Comparator
Sorting is of enormous importance in the practice of computing. Rare is the application that does not include sorting in its implementation. Everything from word processing (spell checking, indexing) and image processing (color histograms), to operating systems (page tables) and computer graphics (depth culling);indeed, the greater challenge is coming up with real-world computing problem that do not require sorting in an efficient solution. Even non-computing applications rely on sorted data; imagine a business with unsorted filing cabinets. If you can’t, that’s because that business probably wouldn’t operate for very long.Owing to its ubiquity, sorting is among the most studied and well-understood problems in all of computing. Despite this extensive analysis, we cannot definitively claim to have found a “best sort”! QUICKSORT is usually the go-to algorithm, but it is unstable—and sometimes we want stability—and it has highly undesirable O(n 2 ) worst case behavior, which, while easy to avoid in the degenerate case (through randomization), is impossible to avoid in all cases.MERGESORT is the defacto second choice. It avoids QUICKSORT’s problems, being Θ(n lg n) (best- and worst-case asymptotic running times are proportional to n lg n), and it is stable, but it is not in-place (a big problem when either resources are highly limited or data is very large), and it has larger constants, such that it will lose to QUICKSORT in the average case. Adding to this confusion is that both of these sorts tend to lose to well written O(n 2 ) sorts like INSERTION SORT and SELECTION SORT on small data sets!This is because with small n the constants that big-O brushes aside tend to dominate.The problem of writing a general sorting algorithm is further complicated by the fact that precisely how to compare two items cannot be known by the library developer. Java gets around the latter problem with the Comparable and Comparator interfaces. All other popular (and reasonable) languages have ways of dealing with this, too. And Java uses a hybrid approach in its choice of algorithm. With certain datatypes it uses a modified QUICKSORT, and with others a variation of MERGESORT1 .You are an API developer at Oracle in charge of choosing the sorting algorithm(s) for Java 10. Your analysis has already eliminated many sorts from the competition. You’re left with QUICKSORT, MERGESORT, and INSERTIONSORT. You decide to build a front-end to these algorithms which compares their performance head-to-head.The current testing is concerned only with sorting text, but even text can be sorted in many different ways: Is is case sensitive or insensitive? Do we want lexicographical order? Alphabetical? Something else entirely? Does it include characters from different alphabets? You decide to pass a configuration file listing character order to your program. You build a lookup table from the configuration alphabet.Your sorts will use a Comparator to sort according to the order in the configuration. Finding the relative positions of alphabet characters within your comparator will require BINARYSEARCH, which you must also implement.1Rather unsatisfying explanations for these choices are available in the Java 7 API documentation for public static void sort(byte[] a) and public static void sort(Object[] a).You will be implementing three sorts—QUICKSORT, MERGESORT, and INSERTIONSORT—and BINARYSEARCH, as well as a framework for testing and timing them, using the classes described below. You will time their performance using the supplied timer class and compare their actual performance over a range of input sizes compared with their expected performance as predicted by big-O analysis.Required classes, interfaces, and methods All classes, interfaces, and methods appearing in the template are required and described therein. Input main() takes two file names as arguments.The first file, the configuration file, contains an alphabet—a list of characters, one character per line— defining sorted order. There are no invalid characters, except that newlines are used as the seperator and thus cannot be a character in the sorted order.The second file, the wordlist, is a list of words to be sorted according to the order defined in the configuration file. The words are newline seperated and may contain only characters that appear in the configuration file. In particular, note that whitespace characters, like space and tab, are valid letters in our alphabets and do not delimit words! main() will read both files, process the configuration file as needed, then proceed to sort the word list with each of the three sorts. Each list may be sorted multiple times, until such time as each sort algorithm has sorted at least 1 million words.It is difficult to accurately time very short activities on a computer, because the operating system often does other things to the detriment of your performance analysis. Over long periods of time, these other activities get averaged out, but short programs that happen to run when OS activity spikes do not get the benefit of that implicit filter. Sorting inputs multiple times will reduce the noise in this processes by allowing you to measure an average over many runs.Output After all three sorts have finished, report the following statistics to the terminal for each sort: • Length of the word list • Total number of words sorted • Total time spent sorting • Total number of comparisons • Average time required to sort the word list • Words sorted per second Times should be reported to at least millisecond resolution.We will supply word lists of lengths n = 10, 100, 1000, 10000, 100000, and 10000002 . You will run your sorts on all lengths and analyze their performance over these varied ns. Write a discussion analyzing the 2An O(n 2 ) sort with n = 1000000 may not finish in a reasonable time for your analysis. If you have the time to let it finish, that’s great, and if you don’t, that’s fine too. In the latter case, simply leave that datapoint out of you analysis.measured performance compared with expected performance as per big-O. Your discussion should be no longer than 500 words and in plain text format.Classes Complete documentation of the classes and methods appear in the code templates. All classes and methods described in the templates are required; however, you may write additional classes and methods as you deem necessary. Alphabet The Alphabet class encodes the character order.AlphabetComparator The AlphabetComparator class provides an “alphabetical order” string comparator based on an Alphabet object. InsertionSorter This is a subclass of Sorter that implements INSERTIONSORT in the sort() method. MergeSorter This is a subclass of Sorter that implements MERGESORT. QuickSorter This is a subclass of Sorter that implements QUICKSORT.Sorter The Sorter class implements all the common elements of the sorts, provides an interface for an abstract Sort() method, and orchestrates statistic gathering of the various sorts. SorterFramework SorterFramework contains the main() method. It’s responsible for initializing all of the classes and running the sorts.WordList The WordList class holds the words to be sorted. It implements the Cloneable interface so that we have a straightforward method to run sorts multiple times.Submission You are required to include, in your submission, the source code for each of the classes in the code template, as well as any additional classes or methods you may have written to complete the assignment (you shouldn’t need any).You need to write proper documentation with JavaDoc for each method in each class. Write your class so that its package name is edu.iastate.cs228.hw2. Your source files (.java files) will be placed in the directory edu/iastate/cs228/hw2 (Linux) or eduiastatecs228hw2 (Windows), as defined in the template code. Be sure to put down your name after the @author tag in each class source file.Your zip file should be named Firstname_Lastname_HW2.zip. Your discussion should be in a file named analysis.txt and stored in the edu directory.
You were hired by a fictional internet provider called Blaze to compute yearly profits. Customers pay fixed monthly fees. Blaze makes a profit when customers do not use all the bandwidth they are allowed. Such users are called “Casual’ users. The region to which Blaze supplies internet is in the form of an n x m grid. Blaze can provide internet to each cell in the grid if desired.Each cell in the grid has either customers (one of three types as given below) or is in “Empty” or “Outage” states. Therefore, a cell can have one of five states: C: Casual customer: checks their email 13 times a day S: Streamer customer: an aspiring e-celebrity with an appetite for bandwidthR: Reseller customer: provides lower-cost, lower-bandwidth internet to users off the grid E: Empty grid cell O: Outage grid cell For example, below is a 4 x 4 grid: O R O R E E C O E S O S E O R RRow and column indices start from 0. The top left cell is at coordinates (0,0). Coordinates are in the form (RowIndex,ColumnIndex). In the example above, the cell at coordinates (1,1) is E (Empty). It has a 3 x 3 neighborhood centered at the square: O R O E E C E S OPlease note that the cell itself is not counted as its own neighbor, so it can have a maximum of 8 neighbors.Cells which are on the edge of the grid will have smaller neighborhoods. In the above example, the cell at the upper left corner, (0, 0), has 3 neighbors in a 2 x 2 neighborhood: O R E E Similarly, the cell at (3, 2), Reseller, has a 2 x 3 neighborhood which is: S O S O R R In the example neighborhood, a cell with a 3 x 2 neighborhood is (1,0): O R E E E S2. Cell Update Rules: Each month, the state of the cell can change depending on its current state and the state of its neighbors. The rules for those are: 1. C: Casual: If the current cell is occupied by a casual user and a. If there is any reseller in its neighborhood, then the reseller causes outage in the casual user cell. Thus, the state of the cell changes from C (Casual) to O (Outage). b. Otherwise, if there is any neighbor who is a streamer, then the casual user also becomes a streamer, in the hopes of making it big on the internet.2. S: Streamer: a. If there is any reseller in the neighborhood, the reseller causes outage for the streamer as well. b. Otherwise, if there is any Outage in the neighborhood, then the streamer leaves and the cell becomes Empty.3. R: Reseller a. If there are 3 or fewer casual users in the neighborhood, then Reseller finds it unprofitable to maintain the business and leaves, making the cell Empty. b. Also, if there are 3 or more empty cells in the neighborhood, then the Reseller leaves, making the cell Empty. Resellers do not like unpopulated regions.4. O: Outage: An Outage cell becomes an Empty cell, meaning internet access is restored on the billing cycle after an outage.5. E: Empty: If the cell is empty, then a Casual user takes it and it becomes a C.6. Additional rules: a. Any cell that (1) is not a Reseller or Outage and (2) has at most one empty neighbor OR one outage neighbor converts to Reseller. b. If none of the above rules apply, any cell with 5 or more casual neighbors becomes a Streamer. 7. If none of the rules apply, then the cell state remains unchanged for the next iteration. All cells update concurrently: each new state of a cell is based on the previous state of its neighbors.3. Determining Profit: Blaze makes a profit of $1 from casual customers. Blaze does not make a profit from streamers or resellers.Profit utilization is calculated as a percentage of potential profit for each billing cycle. For example If the region grid is 12×10, then potential profit is $120 per month, as each cell is occupied by a casual user. Thus, in a single month, profit utilization is 100*C/120, where C is the number of Casual cells. The software for this project needs to compute the profit utilization over 12 billing cycles (equivalent to one year), as a percentage of maximum profit, e.g. 23.4. Implementation Details: 1. Implement the abstract class TownCell to represent a generic cell. It has five subclasses, one for each cell type, specifically: Casual, Streamer, Reseller, Empty and Outage. These 5 subclasses need to be implemented as well.2. The Town class has a public member variable named grid, which is a 2D array of TownCell. It stores the state of each cell and holds the objects of subclasses of TownCell.3. State is an enum for the cell’s state. You may not modify this file.4. Implement an ISPBusiness class, which simulates the changes in the grid for an entire year (12 monthly cycles). Note that all its functions are static. This class should: 4.1. Create the Town object and populate the grid inside it. 4.2. The main method needs to ask the user about grid generation: “How to populate grid (type 1 or 2): 1: from a file. 2: randomly with seed” 4.2.1. If the user chooses Option 1, take a file path as input. “Please enter file path:”The format of the file is given in ISP4x4.txt. The first line contains the number of rows and columns, separated by space. After the first line, the file contains lines equal to the number of rows, and each line contains as many characters as there are columns. Each character can be: C, S, R, E, or O (upper case only). The file will not deviate from this format.4.2.2. To generate the grid randomly, ask the user for three integer values for number of rows, number of columns and seed for random number generator (in order). “Provide rows, cols and seed integer separated by spaces: “Populate the grid with an array of size: rows x cols. Then assign each cell in it using random number generator with the given seed. Java provides a random number generator. To use it, you need to import the package java.util.Random. Next, declare and initiate a Random object like below: Random generator = new Random(); Then, random numbers can be obtained by: int newRandomValue = generator.nextInt(5);The above instruction will generate a random number between 0 and 4 that corresponds to one of the cell type as given by static variables in the TownCell class. ● Templates are provided for all classes, except subclasses. You should create 5 subclasses extending TownCell. Names of those 5 classes should be exactly: Casual, Streamer, Reseller, Empty and Outage, including case. Also use the package name exactly as: edu.iastate.cs228.hw1.● Below is state of the grid as it changes for 12 billing cycles. This is just for illustration – you should not output the grid state but just the profit percentage. That is only output 38 for this case.How to populate grid (type 1 or 2): 1: from a file. 2: randomly with seedProvide rows, cols and seed integer separated by space: 4 4 10 Start: O R O R E E C O E S O S E O R R Profit:1After itr: 1 E E E E C C O E C O E O C E E E Profit: 4 After itr: 2 R C C C C C E C C E C E C C C C Profit: 12 After itr: 3 E R R R R O C C R R S R R R C R Profit: 3 After itr: 4 R E E E E E R R E E R E E E R E Profit: 0 After itr: 5 E C C R C C E E C C E R C C E R Profit: 8 After itr: 6 R C O E R S C C R S C E R C R E Profit: 5 After itr: 7 E R E R E R S C E R O R E R E R Profit: 1 After itr: 8R E R E C E O O C E E E R E R E Profit: 2 After itr: 9 E C E C O C E E O C C C E C E C Profit: 8 After itr: 10 R C C C E C C C E C S C R C R R Profit: 9 After itr: 11 E R R R R O R R R O R R E R E E Profit: 0 27.604166666666668 //only output a double as the profit %!!● The only value returned by your software is profit utilization in %, as a double. ● While you may add more classes, variables and helper functions, please do not modify access specifiers or function signature for any of the given functions. Failure to abide by this rule is considered breach of contract in the real world and carries a 50% penalty. Any helper functions introduced need to be properly commented. ● You need not worry about validating the values of rows and columns input by the user. We are assuming that user is only providing positive integers for these.5. Junit Classes: JUnit classes include CasualTest, StreamerTest, ResellerTest, EmptyTest, OutageTest, ISPBusinessTest, TownTestand TownCellTest. You also need to create all these classes. There should be at least one test method for each function for the respective classes. You should use jUnit5.6. Submission Write your classes and JUnit test classes in the edu.iastate.cs228.hw1 package. Also submit the text files with your JUnit tests. Your text files should be directly inside the project folder (i.e., along with src folder). Turn in the zip file, not your class files. Please follow the guideline posted under Documents & Links on Canvas. Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW1.zip.
The objective of this exercise is to reconstruct/unzip a message archived with a binary-treebased algorithm. The program should ask for a single filename at the start: “Please enter filename to decode: “, decode the message in the file and print it out to the console.The name of the compressed message file will end in .arch, e.g. “monalisa.arch”. The file consists of two or three lines: the first one or two lines contain the encoding scheme, and the second or third line contains the archived message.The archival algorithm uses a binary tree. The edges of the tree represent bits, and the leaf nodes contain one character each. Internal nodes are empty. An edge to a left child always represents a 0, and an edge to a right child always represents a 1. Characters are encoded by the sequence of bits along a path from the root to a particular leaf. The below tree serves as an example.The tree on the left encodes these characters: Character Encoding a 0 ! 100 d 1010 c 1011 r 110 b 111 With the above encoding, the bit string: 10110101011101101010100 is parsed as 1011|0|1010|111|0|110|1010|100 which is decoded as: cadbard!With this encoding, we can automatically infer where one character ends and another begins. That is because no character code can be the start of another character code. For example, if you have a character with the code 111, you cannot have the codes 1 and 11, as they would be internal nodes.The following steps decode one character from the bit string: Start at root Repeat until at leaf Scan one bit Go to left child if 0; else go to right child Print leaf payload3. Input Format The archive file consists of two lines: the first line contains the encoding scheme, and the second line contains the compressed string. For ease of development and to make the archive file human-readable, each bit is represented as the character ‘0’ or ‘1’, rather than as an actual bit from a binary file.The encoding scheme can be represented as a string. For example, the tree from section 2 can be represented as: ^a^^!^dc^rb where ^ indicates an internal node. The above code represents a preorder traversal of the tree.The cadbard! message is encoded in the following file (“cadbard.arch”): ^a^^!^dc^rb 10110101011101101010100There are four test files in HW4S2021_Test_Files.zip. Note: the encoding scheme representations may include a space character and a newline character, thereby breaking the tree string into two lines! The newline character needs to be parsed correctly if the encoding file has three lines in total.4.1. Read in the first line (and possibly second line, if newline is part of the tree) of the file and construct the character tree. Convert the line input into a MsgTree structure using preorder traversal. The tree should be in a class MsgTree with the following members: public class MsgTree{ public char payloadChar; public MsgTree left; public MsgTree right; /*Can use a static char idx to the tree string for recursive solution, but it is not strictly necessary*/ private static int staticCharIdx = 0; //Constructor building the tree from a string public MsgTree(String encodingString){} //Constructor for a single node with null children public MsgTree(char payloadChar){} //method to print characters and their binary codes public static void printCodes(MsgTree root, String code){} }When building the tree, try a recursive solution where staticCharIdx tracks the location within the tree string. You can pass the same tree string during recursive calls, and update the staticCharIdx to point to the next character to be read. Note: if you decide to implement an iterative solution, you will receive a 15% bonus, as it is considerably more difficult. In that case, you cannot get the 5% bonus for printing statistics. printCodes() performs recursive preorder traversal of the MsgTree and prints all the characters and their bit codes: character code ————————- c 1011 r 110 b 111You are allowed to print the header of the table (character, code, —-) in main().4.2. Write a method public void decode(MsgTree codes, String msg) to decode the message. It would print the decoded message to the console: MESSAGE: The quick brown fox jumped over the lazy dog. You are allowed to print “MESSAGE:” in main().The overall output of the program should be the output of printCodes() followed by the output of decode(): character code ————————- c 1011 r 110 b 111 MESSAGE: The quick brown fox jumped over the lazy dog. 5. Submission Put your classes in the edu.iastate.cs228.hw4 package. Turn in the zip file and not your class files. Please follow the guideline in submission_guide.pdf. Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW4.zip. No template files will be provided other than the skeleton in Section 4.1.6. Extra credit (5% or 15%) Print the following statistics after the rest of the program output: 8.0 1180 STATISTICS: Avg bits/char: Total characters: Space savings: 50.0%The space savings calculation assumes that an uncompressed character is encoded with 16 bits. It is defined as (1 – compressedBits/uncompressedBits)*100.To earn a 15% non-cumulative bonus (either 5% for statistics or 15%), you can create an non-recursive, iterative solution for building the tree, but be advised that it will require hours of extra effort compared to the recursive solution. The bonus for early submission will stack with the 5/15% bonus.Name your submission Firstname_Lastname_HW4_extra.zip if you completed the iterative solution.
1. IntroductionThe purposes of this assignment are to practice working with a linked data structure to become intimately familiar with the List and ListIterator interfaces This assignment will also provide many opportunities to practice your debugging skills.1.1. Summary of Tasks Implement a class StoutList that extends AbstractSequentialList along with inner classes for the iterators. A skeleton is provided. See the implementation and suggestions for getting started sections for details.In this assignment you will implement a somewhat peculiar-looking linked list. The list will be a doublylinked list with dummy nodes for the head and tail. An empty list has the following form: Figure 1- an empty list So far so good. Now, let M be a fixed, positive even number. The twist is that each node can store up to M data elements, so the number of linked nodes may not correspond to the number of elements.For example, after some sequence of add and remove operations, one of these lists might have the following form: Figure 2 – a possible list of size 6, where M=4 Note that there are 6 elements, and their logical indices are shown below the nodes. The number of actual linked nodes may vary depending on the exact sequence of operations. Each node contains an array of the element type having fixed length M. Therefore, each logical index within the list is represented by two values: the node n containing the element, and the offset within that node’s array. For example, the element E shown above at logical index 4 is in node at offset2. There are special rules for adding and removing elements to ensure that all nodes, except possibly the last one, have at least elements. These rules are described in detail in a later section. Note that you can get started and make significant progress on the assignment without needing all the add and remove rules. See the section suggestions for getting started.For the implementation, you must implement the class StoutList extending AbstractSequentialList. AbstractSequentialList is a partial implementation of the List interface in which the size() and listIterator() methods are abstract. All other operations have default implementations using the list iterator. The StoutList should NOT allow null elements. Your add methods (those within the iterator as well as those implemented without the iterator) should explicitly throw a NullPointerException if a client attempts to add a null element. A skeleton of the code can be found in project3_template.zip. The skeleton code includes a constructor, an inner class Node, and two methods toStringInternal(). There is also some code in place to support logging.2.1. Methods to override In addition to implementing the iterators described below, you must override the following methods of AbstractList without using the iterator: int size() boolean add(E item) void add(int pos, E item) E remove(int pos) Iterator iterator() ListIterator listIterator() ListIterator listIterator(int pos) The methods above must conform to the List interface, with the added restriction that the add() methods must throw a NullPointerException if the item argument is null. The purpose of asking you to override add() and remove() is primarily to help ensure that you can get partial credit for implementing the split and merge strategies even if your iterator isn’t completely correct. n1 M/22.2. The Node inner class A minimal Node class is provided for you. It has methods for adding an element at a given offset and removing an element at a given offset. Note that empty cells within the array (i.e., those with index >= count) should always be null. You can add additional features to this class if you find it helpful to do so.2.3. The toStringInternal methods These methods show the internal structure of the nodes and are useful for debugging. Normally, such a method would not be public (since it reveals implementation details), but we are making it public to simplify unit testing. For example, if the list of Figure 3 contained String objects “A”, “B”, “C”, “D” and “E”, an invocation of toStringInternal() would return the string: [(A, B, -, -), (C, D, E, -)] where the elements are displayed by invoking their own toString() methods and empty cells in the array inside each node (which should always be null) are displayed as “-”. A second version takes a ListIterator argument and will show the cursor position as a character “|” according to the nextIndex() method of the iterator. For example, if iter is a ListIterator for the list above and has nextIndex() = 3, the invocation toStringInternal(iter) would return the string: [(A, B, -, -), (C, | D, E, -)] Do not modify these methods.2.4. Finding indices Your index-based methods remove(int pos), add(int pos, E item) and listIterator(int pos) method must not traverse every element in order to find the node and offset for a given index; you should be able to skip over nodes just by looking at the number of elements in the node. For example, for the list of Figure 9, to find the node and offset for logical index 7, you can see 3 elements in the first node, plus 2 in the second node, which makes 5, plus 4 in the third node, which is 9. Since 7 is greater than 5 and less than or equal to 9, index 7 must be in the third node. You may find it helpful to represent a node and offset using a simple inner class similar to the following: private class NodeInfo { public Node node; public int offset; public NodeInfo(Node node, int offset) { this.node = node; this.offset = offset; } } Then you can create a helper method something like the following: // returns the node and offset for the given logical index NodeInfo find(int pos){…}3. Implementation of StoutIterator and StoutListIterator You must provide a complete implementation of an inner class StoutIterator implementing Iterator and a class StoutListIterator implementing ListIterator. The StoutIterator does NOT need to implement remove() (can throw UnsupportedOperationException). Optionally, if you are confident that your StoutListIterator is correct, you can return an instance of StoutListIterator from your iterator() method and forget about StoutIterator. However, you are encouraged to keep them separate when you first start development, since the basic one-directional Iterator, without a remove operation, is relatively simple, while the add and remove operations for the full ListIterator are tricky.4. Suggestions for Getting Started 1. Implement add(E item). Adding an element at the end of the list is relatively straightforward and does not require any split operations. (e.g. see Figures 3 – 5). You can use toStringInternal() to check. 2. Implement the hasNext() and next() methods of StoutIterator and implement the iterator() method. At this point the List methods contains(Object) and toString() should work. 3. Start StoutListIterator. Implement ListIterator methods nextIndex(), previousIndex(), hasPrevious(), and previous(). These methods are straightforward. Implement the listIterator() method. You should then be able to iterate forward and backward, and you can check your iterator position using toStringInternal(iter). The indexOf(Object obj) method of List should work now.4. Implement the set() method of StoutListIterator. You will need to keep track of whether to act on the element before or after the cursor (and possibly throw an IllegalStateException), but the method is not complicated since it doesn’t have to change the structure of the list or reposition the cursor.5. Implement a helper method such as the “find” method described above under finding indices. Then you can easily implement the listIterator(int pos) method. After that, the get(int pos) of List should work. 6. Implement the add(int pos, E item) method. Now you will need to carefully review the rules for adding elements. Here is a suggestion for keeping things organized. Write a helper method whose arguments include the node and offset containing the index pos at which you want to add, e.g., private NodeInfo add(Node n, int offset, E item){…} (If pos = size, the arguments should be the tail node and offset 0.) The return value should be the actual node and offset at which the new element was placed. (In some cases this will be the given node and offset, in some cases it will be the previous node, and in case of a split there might be a completely new node.) You don’t need the return value for the add method, but you will need it in the iterator.7. Implement the remove(int pos) method. Again, you will need to carefully review the rules for removing elements and merging. 8. Implement the add() method of listIterator. This is not too bad if you have the helper method from (6). The catch is that after adding an element, you have to update the logical cursor position to the element after the one that was added. 9. Implement the remove() method of listIterator. The tricky part is that you have to update the cursor position differently depending on whether you are removing ahead of the cursor or behind the cursor, and depending on whether there was a merge operation.5. The add and remove Rules 5.1. Adding an element (see Figures 3 – 8) The rules for adding an element X at index are as follows. Remember that adding an element without specifying an index is the same as adding at index i = size. For the sake of discussion, assume that the logical index = size corresponds to node = tail and offset = 0. Suppose that index occurs in node n and offset off. (Assume that index = size means n = tail and off = 0) if the list is empty, create a new node and put X at offset 0 otherwise if off = 0 and one of the following two cases occurs, if n has a predecessor which has fewer than M elements (and is not the head), put X in n’s predecessor if n is the tail node and n’s predecessor has M elements, create a new node and put X at offset 0 otherwise if there is space in node n, put X in node n at offset off, shifting array elements as necessary otherwise, perform a split operation: move the last M/2 elements of node n into a new successor node n’, and then if , put X in node n at offset off if , put X in node n’ at offset5.2. Removing an element (see Figures 9 – 14) The rules for removing an element are: if the node n containing X is the last node and has only one element, delete it; otherwise, if n is the last node (thus with two or more elements) , or if n has more than elements, remove X from n, shifting elements as necessary; otherwise (the node n must have at most elements), look at its successor n’ (note that we don’t look at the predecessor of n) and perform a merge operation as follows: if the successor node n’ has more than elements, move the first element from n’ to n. (mini-merge) if the successor node n’ has or fewer elements, then move all elements from n’ to n and delete n’ (full merge) 5.3 Examples: adding some elements to a list off ≤ M/2 off > M/2 (off− M/2) M/2 M/2 M/2 M/2 Figure 3- an example list Figure 4 – after add(V) Figure 5 – after add(W) Figure 6 – after add(2, X) Figure 7 – after add(2, Y) Figure 8 – after add(2, Z)5.4. Examples: removing some elements from a list Figure 9 – example list Figure 10 – after removing W Figure 11 – after removing Y (mini-merge) Figure 12 – after removing X (mini-merge) Figure 13 – after removing E (no merge with predecessor node) Figure 14 – after removing C (full merge with successor node)6. Sorting Implement the following two sorting methods within the StoutList class: public void sort(); public void sortReverse(); The sort() method implements insertion sort by calling a private generic method: private void insertionSort(E[] arr, Comparator
Question I A linear circuit has poles at S=-5, -3, -2, -7, and -8. i. If the circuit is simulated using the Forward Euler method with step size h, for what values of h is the simulation stable? ii. If the circuit is simulated using the Backward Euler method with step size h, for what values of h is the simulation stable? iii. If the circuit is simulated using the Trapezoidal Rule with step size h, for what values of h is the simulation stable?Question II Consider the following Adams-Moulton integration method: �” = �”$% + ‘( %) �”̇ + +( %) �̇ “$% + ( %) �̇ “$) Derive the difference equation corresponding the to the above method.Question III Your circuit simulator needs to perform an AC analysis at 1000 frequency points, as well as compute the sensitivity of 5 output nodes with respect to three different parameters. What is the total number of Sparse orderings, L/U factorizations and forward backward substitutions required for the full computation (including both the frequency response and its sensitivity) if: 1. We use the perturbation method. 2. We use the differentiation method. 3. We use the Adjoint method. Preliminaries 1. You can reuse and build upon your previous code for this assignment. 2. We provide you with the following additional functions that help handle time domain sources. a. volsine.m and cursine.m are two functions that add time domain sinusoidal voltage and current sources respectively. They are used in the netlist. The netlists used in the questions below should provide examples. Also read the comments in the functions for the required syntax. b. BTime.m is a function that evaluates and returns the time domain value of the right hand side vector b(t) as a function of time.3. In your submission please provide all code in a zip file in a way that allows us to run the testbenches ourselves (include all code, not just the recent one).4. Also submit a pdf file containing the answers to the questions, the output plots and the code for functions you have written for this assignment.Question I: Backward Euler Write a function called transient_beuler.m with the following header: function [tpoints,r] = transient_beuler(t1,t2,h,out) % [tpoints,r] = beuler(t1,t2,h,out) % Perform transient analysis for LINEAR Circuits using Backward Euler % assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient responseYour function should use Backward Euler with a constant step size to compute the transient response of a linear circuit. 1. Test your function by running the provided Testbench_Question1.m file. This file simulates the netlists Circuit_chebychev_filter_TD.m (provided in the assignment) in the time domain (transient) and Circuit_chebychev_filter (also provided – this is the same circuit you used before to test your fsolve) in the frequency domain using your fsolve.m function which you developed in past assignments. In your submission, include the code for the new function transient_beuler.m as well as the output plot of the testbench function.2. Explain the relation between the two plots in the output figure.Question II Trapezoidal Rule Write a function transient_trapez.m with the following header: function [tpoints,r] = transient_trapez(t1,t2,h,out) % [tpoints,r] = Transient_trapez(t1,t2,h,out) % Perform Transient Analysis using the Trapezoidal Rule for LINEAR % circuits. % assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient responseYour function should use Trapezoidal Rule with a constant step size to compute the transient response of a linear circuit. 1. Test your function by running the provided Testbench_Question2.m file. This scripts also runs your code from Question 1 and compares BE to TR. In your submission, provide the code for the function you wrote as well as the plot from the testbench. 2. By examining the plot, what can you deduce about the BE and TR methods?Question III Forward Euler Write a function transient_feuler.m with the following header: function [tpoints,r] = transient_feuler(t1,t2,h,out) % [tpoints,r] = Transient_feuler(t1,t2,h,out) % Perform Transient analysis for LINEAR circuit using Forward Euler % This function assumes the C matrix is invertible and will not work % for circuits where C is not invertible. % assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient responseYour function should use the Forward Euler method with a constant step size to compute the transient response of a linear circuit. You may assume that the C matrix of your MNA is invetible for the purposes of this assignment (this means that your function will not work for most circuits).1. In order to test your code, run the provided test bench script Testbench_Question3.m which simulates the circuit in the provided netlist Q3BEcircuit.m.2. Examine and comment on what you learn from the output files.3. It can be shown that, when the C matrix is invertible, the poles of the circuit are the eigenvalues of the matrix −�#$� (note the negative sign). Determine the stability condition of the forward euler method for this circuit and experimentally verify your results by running simulations (note the eig function in matlab computes the eigenvalues of a matrix).Question IV Nonlinear Circuits Write a function nl_transient_beuler.m with the following header: function [tpoints,r] = nl_transient_beuler(t1,t2,h,out) % [tpoints,r] = beuler(t1,t2,h,out) % Perform transient analysis for NONLINEAR Circuits using Backward Euler % Assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient responseYour function should use Backward Euler with a constant step size to compute the transient response of a nonlinear circuit. For now, you only need to support diodes and you can reuse the code you wrote before and that we have supplied to you.Test your circuit by running the provided script Testbench_Question4 which simulates the rectifier circuit in netlist Circuit_Rectifier.m also provided.
Question I Write a matlab function dcsolvealpha.m that finds the dc solution of the augmented system: �� + �(�) = ��*+ The functions is defined as follows: function Xdc = dcsolvealpha(Xguess,alpha,maxerr) % Compute dc solution using newtwon iteration for the augmented system % G*X + f(X) = alpha*b% Inputs: % Xguess is the initial guess for Newton Iteration % alpha is a paramter (see definition in augmented system above) % maxerr defined the stopping criterion from newton iteration: Stop the % iteration when norm(deltaX)
Questions: 1. Write the following matlab functions: ind.m à adds an inductor to the MNA equations vcvs.m à adds a voltage controlled voltage source to the MNA equations vccs.m à adds a voltage controlled current source to the MNA equations fsolve.m à performs a frequency domain analysis to obtain the frequency response. See the attached matlab files with the same names for more precise definitions of these functions.2. Run all Benchmark functions provided in order to test your simulator.Deliverables: 1. A pdf file containing the results of all benchmark functions (all plots), as well as the matlab code for the functions your have written. 2. The matlab m files for ind.m, vcvs.m, vccs.m, fsolve.m
In order to simplify parsing, we will use our own netlist format in ECSE597/ECSE472. For example consider the following netlist. % CIR1.M % Description of Circuit 1 % Author: R. K. % Date: Sept 17, 2019 % Comment lines start with % just like in matlab (this is in fact a matlab % script).global G C %define global variables global b; G = zeros(4,4); % Define G, 4 node circuit (do not include additional variables) C = zeros(4,4); % Define C, 4 node circuit (do not include additional variables)b = zeros(4,1); % Define b, 4 node circuit (do not include additional variables) % Try changing zeros(4,4) with sparse(4,4) for sparse routines. % See matlab help for info about sparse matrix support. vol(1,0,1); % add voltage source between nodes 0 and 1 (value =1) res(1,2,50); % add 50 ohm resistor between nodes 1 and 2 res(4,0,50); cap(2,0,0.319e-6); cap(3,4,64.72e-12); cap(4,0,0.319e-6); ind(2,0,0.317e-6); ind(2,3,1.59e-6); ind(4,0,0.317e-6);The above netlist corresponds to the following circuit which has 4 nodes. You will find on myCourses the following functions: cap.m, res.m, cur.m, vol.m, and diode.m which allow you to generate the MNA equations for circuits containing capacitors, resistors, current sources, voltage sources and diodes.You will also find the function f_vector.m which computes the nonlinear vector of the MNA, f(x), as a function of x. The file Circuit_diodeckt1.m is the netlist of a simple diode circuit. nlJacobian.m and dcsolve.m are the definitions of functions that you will need to write. Finally, Test_bench_diode1.m is the test bench that you should be able to run once you complete the assignment.1. Draw the circuit in the netlist Circuit_diodeckt1.m. 2. Write a matlab function nlJacobian.m (see function definition provided). This function should compute and return the Jacobian of the nonlinear vector f(x) 3. Write a matlab function dcsolve.m (see function definition provided). This function should use the Newton-Raphson method to compute the dc solution. It should also return the interim values of detlaX for each iteration (see function definition for details). 4. Run the script Test_bench_diode1.m to test your code.Deliverables: 1. A pdf file containing a) the schematic of the circuit in Circuit_diodeckt1.m, b) dc values computed after running test bench, c) the figure that was plotted when you ran the test bench, and d) the matlab code for nlJacobian.m and dcsolve.m. 2. The matlab m files for nlJacobian.m and dcsolve.m
1. Let X1, X2, . . . , Xn be a sample from the standard uniform U(0, 1) distribution. Find the distribution of (Pn i=1 Xi)mod1. [10 points]2. Let F be a cumulative distribution function (c.d.f.). Define F [−1](u) = min{x | F(x) ≥ u}. Show that if U ∼ U(0, 1), then F [−1](U) ∼ F. [5 points]3. There are many methods of Sampling from the Standard Normal distribution. (a) Prove that the Box-Muller algorithm provides two independent standard normal random deviates. [5 points] (b) Prove that the Polar algorithm for simulating from the standard normal distribution provides two independent standard normal random deviates. [5 points]4. Sampling from the tail of a standard normal. Perform a simulation experiment in R (or any other software) to map the rejection rate with increasing d. Compare the result with the theoretical naive rejection rate. (For this experiment, no code is required to be turned in, but you are required to describe the experiment that you set up, and also detail the results, using appropriate figures (and tables) if needed.) [10 points]5. Compressed Column Storage. Consider the n × p sparse matrix W = ((wij ) with m non-zero entries and stored in the following Compressed Column Storage (CCS) format: • Consider the triple given by A = (a, r, c). where a = (a1, a2, . . . , am) is a mdimensional vector containing the non-zero values in W (stored column-wise), r = (r1, r2, . . . , rm) is the m-dimensional vector with ri storing the row index of the corresponding ai , and c = (c1, c2, . . . , cp) is a (p + 1)-dimensional vector with ci indicating the element of a that starts the column of A. By convention, cp+1 = m + 1. Thus, ai ≡ wri,k, where ck ≤ i < ck+1. Matrices may alternatively be stored in the Compressed Row Storage format (CRS) defined correspondingly.(a) Consider the product of A with a p-variate vector x. Let y = W x. Provide an algorithm for calculating the j element of y. That is, write an algorithm which will calculate yj given W in CCS format A = (a, r, c) and without expanding it back to W. No programming is required, but only the algorithm in pseudo-code should be provided. [10 points](b) Suppose that we now have a sparse symmetric p × p matrix V . Answer the following questions: i. Develop a similar CCS-type strategy for storing the matrix V in a packed CCS format. [5 points] ii. Provide, in pseudo-code, an algorithm for finding the jth element yj of y = V x. [5 points]6. Let U1, U2, . . . , UnU be a sample from Population 1 and V 1,V 2, . . . ,V nV be a sample from Population 2. Consider the following samples hypothesized (but not known for sure) to be from different populations a follows: W1,W2, . . . ,WnW from Population 1, X1, X2, . . . , XnX to be from Population 2, Y1, Y2, . . . , YnY from Population 3, Z1, Z2, . . . , ZnZ from Population 4. The total within sum of squares (WSS) in this scenario is given by XnU i=1 kUi − µˆ 1k 2 + XnV i=1 kV i − µˆ 2k 2 + XnW i=1 kWi − µˆ 1k 2 + XnX i=1 kXi − µˆ 2k 2 + XnY i=1 kY i − µˆ 3k 2 + XnZ i=1 kZi − µˆ 4k 2 , (1) where µˆ 1 = (nUU¯ + nWW)/(nU + nW ), µˆ 2 = (nV V¯ + nXX¯ )/(nV + nX), µˆ 3 = Y¯ and µˆ 4 = Z¯ . The above total WSS can be rewritten to be a sum of WSS from the samples U1, U2, . . . , UnU and V 1,V 2, . . . ,V nV plus some terms. (This is important in the context of the following questions.) We are interested in finding how the total WSS changes when we reassign an (unsure) observation from one population to the other. To do so, we will investigate the three possibilities (there is actually a fourth, but that is the converse of Case (b) below).(a) Suppose we reassign WnW from Population 1 to Population 2. How does the total WSS in (1) change? (Note that such a reassignment affects both µˆ 1 and µˆ 2 ). [10 points](b) Suppose that from the original setup leading to (1). we reassign WnW from Population 1 to Population 3. How does the total WSS in (1) change? (Note that such a reassignment affects both µˆ 1 and µˆ 3 ). [10 points](c) Suppose that from the original setup behind (1). we reassign Y nY from Population 3 to Population 4. How does the total WSS in (1) change? (Note that such a reassignment affects both µˆ 3 and µˆ 4 .Note that an extension of this is the basis for the Hartigan-Wong (1979) implementation of the k-means algorithm.) [10 points] The reductions in all three parts above provides a stripped-down context of the basis for an efficient implementation of the k-means semi-supervised clustering algorithm.7. For each program, please write out how you compiled, executed the program and result. You may include this code in as a comment. (a) Write an annotated C program which converts temperature, from Fahrenheit to the Celsius scale and vice-versa. [7 points](b) Write an annotated C program which takes in two integers i = 320 and j = 256 and reports their product. Store the product as a short and as an int and print the result. What differences do you see? Please put in your observations and reasoning as a comment in the C program. [8 points]1. Let X ∼ Np(0, I). Let Y be a random variable having the χ 2 p -density that is independent of X. Let Z = √ Y X kXk . Show that that the density of Z is also standard multivariate normal. [10 points]2. Write an example in C to illustrate that a function passes its arguments by value. To do this, write a function which takes in two arguments: an integer and a pointer to an integer and then increments each by 1. Follow the location of the arguments inside and outside the function to illustrate the point. [10 points]3. Write a function in C which illustrates the use of the matrix multiplication algorithm using CCS representation that you wrote in the previous assignment. [20 points]4. Let X1, X2, . . . , Xn be a random multivariate sample such that Xi has only the first 1 ≤ pi ≤ p coordinates that are observed. Assume that each Xi is a realization from the pi-dimensional marginal distribution of Np(µ, Σ).Further, there are at least two is for which pi = p. Answer the following questions: (a) Find the maximum likelihood estimator of µ and Σ using direct maximization of the loglikelihood. [15 points](b) Use the expectation-maximization algorithm to formulate the maximum likelihood estimator of µ and Σ. [20 points](c) Compare the number of computations (floating point operations) needed in one EM step to the number of computations in the direct calculations. You may make simplifying assumptions as needed for calculating the number of operations. [20 points](d) How do the results in (c) change if the pi observed coordinates are not the first ones? [5 points]1. Write a C function to provide the largest eigenvalue and eigenvector of a nonnegative definite matrix using the power method. The function should take in a function pointer which defines the multiplication of a matrix in appropriate storage format and a vector. [15 points](a) Use calls to the above function in another C function which provides the first m eigenvalues of a positive definite matrix. [5 points](b) Demonstrate the above in an example program. [5 points]2. Let X1, X2, . . . , Xn be a sample. Let sij = s(Xi , Xj ) be a similarity measure between Xi and Xj . For example, sij = Corr(Xi , Xj ). Let n k i be the set of Xj s which are the k-nearest neighbors to Xi .That is, for each i, let sij1 ≥ sij2 ≥ . . . ≥ sijn−1 be the ordered similarities (in decreasing order) among {sij : j ∈ (1, 2, . . . , i − 1, i + 1, i + 2, . . . , n)}. Then Xj1 , Xj2 , . . . , Xjk are the k-nearest neighbors of Xi .(a) Write a function n k(i, j,…) in C (of appropriate arguments) which takes in a dataset and for any two observation pairs (i, j) and a user-supplied similarity measure, returns 0 if i and j are not among the k-nearest neighbors of each other and 1 if they both are among the k-nearest neighbors of the other. Let Nk be the set of (i, j) for which the above function returns 1. [15 points](b) Use the above to write a function in C which takes in a dataset and a user-supplied similarity measure and filters out those observations that are not a K-nearest neighbor to another observation. In order to make this function easy to use in big data problems, make sure that you do not unnecessarily store the distance matrix. Test the function. [5 points]3. For any X1, X2, . . . , Xn (assumed to be filtered as with a call to the previous function), calculate the similarity matrix W with non-zero elements Wij = sij when (i, j) ∈ Nk and sij = Corr(Xi , Xj ) when Corr(Xi , Xj ) > ρ.Clearly, W is a sparse symmetric matrix that can be stored in the sparse packed format. (Actually, it can be stored even more efficiently, since the diagonals are all unity but we will ignore this for now.)Let G be the diagonal matrix with W1 in the diagonals. Here 1 = (1, 1, . . . , 1)0 . It is common to think of the points X1, X2, . . . , Xn as nodes on a graph, with edges between nodes weighted by similarities Wij and gi ’s as the so-called node degrees, that is, the sum of the weights of the edges connected to node ii.Consider the standardized (with respect to the node degrees) graph Laplacian matrix as L = I − G−1W. Then L is sparse and further the smallest eigenvalues of L are the same (in reverse order) as the largest eigenvalues of G−1W, and they share the same respective eigenvectors.Obtain the first m eigenvectors. How does one determine m? One may do so on the basis of the eigenvalues of L that are close to zero (equivalently, on the basis of those eigenvalues of G−1W that are close to unity). The above framework provides the background for spectral clustering (which additionally involves clustering these eigenvectors).Write a function in C which does the above in a general framework. Test the function (if it is too cumbersome, you may test the function using a subset of the observations below for testing purposes.) [25 points]4. Microarray gene expression data. The file, diurnaldata.csv contains gene expression data on 22,810 genes from Arabidopsis plants exposed to equal periods of light and darkness in the diurnal cycle. Leaves were harvested at eleven time-points, at the start of the experiment (end of the light period) and subsequently after 1, 2, 4, 8 and 12 hours of darkness and light each.Note that there are 23 columns, with the first column representing the gene probeset. Columns 2–12 represent measurements on gene abundance taken at 1, 2, 4, 8 and 12 hours of darkness and light each, while columns 13-23 represent the same for a second replication. Note that the file has a header and also that the first column, in character, is not particularly of value.Use the functions written in the problems above to obtain the eigenvectors, using only the first replication, and provide plots of the eigenvectors for different values of k, ρ and m. Comment. [15 points]5. In this problem, you will generate and print out all possible strings c1c2 · · · c8 where ci ∈ {A, C, G, T}. Write a program that uses eight nested loops to output the strings.Can you rewrite the program to take advantage of the bitwise operators? Can you adapt the second program to output, with one minor change, all possible strings c1c2 · · · c16 of length 16? [15 points]1. Use LAPACK to write a function in C which calculates the eigenvalues of a positive definite matrix A. Test the function with a simple example. Provide instructions on how to use and test the function and test your result with the output of R. [15 points]2. Write a function in C which uses the R mathematical library to provide the loglikelihood of the gamma density. Illustrate with an example. [15 points]3. Modify the multivariate skewness function discussed in class to use the .Call() function while calling C from R. [20 points]
Consider the matrix A � = ⎣ ⎢ ⎢ ⎢ ⎡ 2 4 6 2 1 4 9 14 8 8 2 6 12 12 21 4 10 20 17 32 8 17 30 18 34⎦ ⎥ ⎥ ⎥ ⎤ 1. Use the Doolittle algorithm to decompose the matrix into L and U such that � = ��. Show intermediate results after each row and each column.2. Use the Gaussian version of the Doolittle algorithm to decompose the matrix into L and U such that � = ��. Show the intermediate steps after each sub-matrix. 3. Comment on the similarities and difference between the above two methods. Note: You can type the assignment but you do not need to. You can scan your written work and submit a pdf.Write a matlab function doolittleLU such that [L,U]=doolittleLU(A) returns the LU decomposition of A using the Doolittle algorithm. The algorithm need not do any pivoting. Submit the matlab .m file as your answer.Write a matlab function gaussianLU such that [L,U]=gaussianLU(A) returns the LU decomposition of A using the Gaussian version of the Doolittle algorithm. The algorithm need not do any pivoting. Submit the matlab .m file as your answer.
1. Use LAPACK to write a function in C which calculates the eigenvalues of a positive definite matrix A. Test the function with a simple example. Provide instructions on how to use and test the function and test your result with the output of R. [15 points]2. Write a function in C which uses the R mathematical library to provide the loglikelihood of the gamma density. Illustrate with an example. [15 points]3. Modify the multivariate skewness function discussed in class to use the .Call() function while calling C from R. [20 points]
1. Write a C function to provide the largest eigenvalue and eigenvector of a nonnegative definite matrix using the power method. The function should take in a function pointer which defines the multiplication of a matrix in appropriate storage format and a vector. [15 points](a) Use calls to the above function in another C function which provides the first m eigenvalues of a positive definite matrix. [5 points](b) Demonstrate the above in an example program. [5 points]2. Let X1, X2, . . . , Xn be a sample. Let sij = s(Xi , Xj ) be a similarity measure between Xi and Xj . For example, sij = Corr(Xi , Xj ). Let n k i be the set of Xj s which are the k-nearest neighbors to Xi .That is, for each i, let sij1 ≥ sij2 ≥ . . . ≥ sijn−1 be the ordered similarities (in decreasing order) among {sij : j ∈ (1, 2, . . . , i − 1, i + 1, i + 2, . . . , n)}. Then Xj1 , Xj2 , . . . , Xjk are the k-nearest neighbors of Xi .(a) Write a function n k(i, j,…) in C (of appropriate arguments) which takes in a dataset and for any two observation pairs (i, j) and a user-supplied similarity measure, returns 0 if i and j are not among the k-nearest neighbors of each other and 1 if they both are among the k-nearest neighbors of the other. Let Nk be the set of (i, j) for which the above function returns 1. [15 points](b) Use the above to write a function in C which takes in a dataset and a user-supplied similarity measure and filters out those observations that are not a K-nearest neighbor to another observation. In order to make this function easy to use in big data problems, make sure that you do not unnecessarily store the distance matrix. Test the function. [5 points]3. For any X1, X2, . . . , Xn (assumed to be filtered as with a call to the previous function), calculate the similarity matrix W with non-zero elements Wij = sij when (i, j) ∈ Nk and sij = Corr(Xi , Xj ) when Corr(Xi , Xj ) > ρ.Clearly, W is a sparse symmetric matrix that can be stored in the sparse packed format. (Actually, it can be stored even more efficiently, since the diagonals are all unity but we will ignore this for now.)Let G be the diagonal matrix with W1 in the diagonals. Here 1 = (1, 1, . . . , 1)0 . It is common to think of the points X1, X2, . . . , Xn as nodes on a graph, with edges between nodes weighted by similarities Wij and gi ’s as the so-called node degrees, that is, the sum of the weights of the edges connected to node ii.Consider the standardized (with respect to the node degrees) graph Laplacian matrix as L = I − G−1W. Then L is sparse and further the smallest eigenvalues of L are the same (in reverse order) as the largest eigenvalues of G−1W, and they share the same respective eigenvectors.Obtain the first m eigenvectors. How does one determine m? One may do so on the basis of the eigenvalues of L that are close to zero (equivalently, on the basis of those eigenvalues of G−1W that are close to unity). The above framework provides the background for spectral clustering (which additionally involves clustering these eigenvectors).Write a function in C which does the above in a general framework. Test the function (if it is too cumbersome, you may test the function using a subset of the observations below for testing purposes.) [25 points]4. Microarray gene expression data. The file, diurnaldata.csv contains gene expression data on 22,810 genes from Arabidopsis plants exposed to equal periods of light and darkness in the diurnal cycle. Leaves were harvested at eleven time-points, at the start of the experiment (end of the light period) and subsequently after 1, 2, 4, 8 and 12 hours of darkness and light each.Note that there are 23 columns, with the first column representing the gene probeset. Columns 2–12 represent measurements on gene abundance taken at 1, 2, 4, 8 and 12 hours of darkness and light each, while columns 13-23 represent the same for a second replication. Note that the file has a header and also that the first column, in character, is not particularly of value.Use the functions written in the problems above to obtain the eigenvectors, using only the first replication, and provide plots of the eigenvectors for different values of k, ρ and m. Comment. [15 points]5. In this problem, you will generate and print out all possible strings c1c2 · · · c8 where ci ∈ {A, C, G, T}. Write a program that uses eight nested loops to output the strings.Can you rewrite the program to take advantage of the bitwise operators? Can you adapt the second program to output, with one minor change, all possible strings c1c2 · · · c16 of length 16? [15 points]
1. Let X ∼ Np(0, I). Let Y be a random variable having the χ 2 p -density that is independent of X. Let Z = √ Y X kXk . Show that that the density of Z is also standard multivariate normal. [10 points]2. Write an example in C to illustrate that a function passes its arguments by value. To do this, write a function which takes in two arguments: an integer and a pointer to an integer and then increments each by 1. Follow the location of the arguments inside and outside the function to illustrate the point. [10 points]3. Write a function in C which illustrates the use of the matrix multiplication algorithm using CCS representation that you wrote in the previous assignment. [20 points]4. Let X1, X2, . . . , Xn be a random multivariate sample such that Xi has only the first 1 ≤ pi ≤ p coordinates that are observed. Assume that each Xi is a realization from the pi-dimensional marginal distribution of Np(µ, Σ).Further, there are at least two is for which pi = p. Answer the following questions: (a) Find the maximum likelihood estimator of µ and Σ using direct maximization of the loglikelihood. [15 points](b) Use the expectation-maximization algorithm to formulate the maximum likelihood estimator of µ and Σ. [20 points](c) Compare the number of computations (floating point operations) needed in one EM step to the number of computations in the direct calculations. You may make simplifying assumptions as needed for calculating the number of operations. [20 points](d) How do the results in (c) change if the pi observed coordinates are not the first ones? [5 points]
