In addition to this project description, there are 2 files for this assignment:

• project2.py: a Python file which you will complete and submit on Blackboard (see below for details)

• report2.tex: a Latex template file for the short report which you will submit. The discussion and figure(s) described below should be placed in this report.

Part 1

1.  (3 points) Analyze the function part1q1 included in project2.py which works with a list (Hlist), a dictionary (Hdict), and the heapq package.  There are three options. Setting option=0 leads to an initialization step which returns an Hlist and Hdict which can then be used as input when option=1 or option=2.  Carefully explain the tasks carried out by the function when  option=1 or option=2, and estimate the asymptotic running time when option=2.  When analyzing the running time, assume that the length of Hlist is n = 2m  − 1 where m is a positive integer.  You do not need to discuss the option=0 case.

2.  (5 points)

(a) Now analyze the function part1q2 which takes a weighted NetworkX graph as

input along with two integers corresponding to nodes in the graph (see function documentation for more details).  Explain both the problem that the code is attempting to solve and the strategy that it is using to solve this problem. You may refer directly to particularly important parts of the code, but a line-by- line analysis is not needed. A constraint is needed for the graph edge-weights for the code to reliably produce useful results.  Provide such a constraint in your report along with a concise explanation of why it is needed.

(b) The implementation in part1q2  contains one or more tangible inefficiencies

which negatively affect the running time when the function is applied to large sparse graphs. Develop an improved version of the function which resolves the most important inefficiency (or inefficiencies) that you identify.  Place your improved code in part1q3, and add a brief explanation of the changes you have made and how they improve the asymptotic running time of the code. If you identify several inefficiencies, choose the two you consider to be the most important when deciding how to change the code. Note: You should not use any NetworkX functions, and you should not use built-in functions to improve the walltime of the code; the focus here should be on improving the running time.

Part 2

Consider the following model for opinion dynamics in a group of n individuals:

 =   f(xi − xj ), i = 1, 2, ...,n              (1)

f(xi − xj ) = −(xi − xj )exp [−(xi − xj )2] .               (2)

Here, xi  is the real-valued opinion of individual i; xi   = 0 indicates a neutral opinion, xi  > 0 indicates a positive opinion, and xi  < 0 indicates a negative opinion.

1.  (2 pts) Complete the function RHS in part2q1  so that numerical solutions to the model are efficiently computed using solve ivp; the initial condition is set within the function.

2.  (3 pts) Set n = 50, and find an equilibrium solution, x, which satisfies the following conditions:

i. The magnitudes of the elements in x should satisfy, 0  <  |xi | ≤ 1000  (i = 1, 2, ...,n)

ii. x should contain at least n/2 = 25 distinct values

Add the code used to generate x to the function part2q2.  The function includes code for saving your solution, and you should submit the file that is created.  In your report, briefly explain your approach to finding x and include a description of the Python tool(s) that you used along with an explanation of how you checked the accuracy of your solution.  Note:  a simple but acceptable approach is to attempt to generate several equilibrium solutions and select the first one that satisfies the given conditions.

3.  (3 pts) Analyze the behavior (or types of behavior) that can occur when a small perturbation is added to the equilibrium solution that you found in question 2 (for example, are oscillatory dynamics expected?).  You should focus on providing a qualitative description of how the system responds to small perturbations, and full solutions for the response to a specific perturbation do not need to be computed. Add the code you develop for your analysis to the function, part2q3, and add a clear and concise explanation of your analysis and conclusions to your report.  Note:  if you were unable to find a solution to 2.   which satisfied the given constraints, you should relax the constraints so that a non-trivial equilibrium solution can be generated for this question.

4.  (4 pts) Now consider the following stochastic opinion model:

dxi  = dt  f(xi − xj ) + µdWi (t), i = 1, 2, ...,n             (3)

f(xi − xj ) = −(xi − xj )exp [(xi − xj )2] .                       (4)