Clarifications (Edited 25/2/19)

• Part 1.2 i) If there are no feasible paths, the function should return an empty list.
• Part 2: There is a fourth state of “immune cells” so the initial conditions don’t need to add to 1. Additionally, the fractions are with respect to the initial number of cells at a node, so an individual “fraction” can be larger than 1 for t>0. The expression for FijFij simplifies to 0/0 if node j is isolated (qj=0qj=0). You may assume such nodes are not present in the graph (it is also fine if you set Fij=0Fij=0 for such cases).

• Note that the sums in the equations in part 2 should run from 0 to N-1 as the nodes are numbered starting from 0.

• There is a mistake in the function modelN provided in the template code, p2_template.py. The parameters g and k are in the wrong order. They should be in the same order as in model1, so please use:

  a,theta0,theta1,g,k,tau=params 

A corrected template code is here: | p2_template_v2.py

• Please do not modify input from what is specified. If you would like to add additional optional input, check with the instructor. You may add additional functions as needed as long as they do not use prohibited external modules.

• Part 1.1: You may assume that it is possible to complete all tasks in a finite number of days. Note that the dependency list for a task contains all other tasks that must be completed before it can be started. So if task A depends on B, and B depends on C, then C will be in the dependency list for A.

• Part 1.2: You may assume that the adjacency list is “symmetric” in the sense that if A[i] contains (j,Lij), then A[j] will contain (i,Lij). The signal does not “split” or “recombine” at a junction. You can assume that it is routed to move along only one individual link between junctions.

• Part 2: The template codes incorrectly assign parameter values for “theta1” and “theta2” These should be changed to “theta0” and “theta1”, respectively, to match the problem statement:

  a,theta0,theta1,g,k,tau=params 

This project consists of two parts – in the first, you will be developing/implementing algorithms on graphs, and in the second you will be simulating the propagation of an infection through an organism’s body.

Getting Started: Template files have been added to the course repo in the hw2/ directory. You can also download the files directly from here: | p1_template.py | p2_template.py

Place these files in a folder, and create copies of the template files named p1_dev.pyand p2_dev.py in this new directory. Ultimately, the final files that you submit should be titled p1.py and p2.py. Browse through the dev file; there are a few function headers, and you will have to add code for each of these functions as described below. First, however, you should add your name and 8-digit college id to the docstring at the top of each file.

Part 1. (10 pts)

For each question in this part, you should develop a correct, efficient algorithm, implement the algorithm in Python, and discuss the running time and efficiency of your implementation. Your discussion should include an estimate of the asymptotic running time and a concise description of how you constructed this estimate. You may use onlynumpy and the collections module in your final submission for part 1. No other external modules (networkx, scipy, etc…) are allowed in your codes for this part.

1) You are designing an automated assembly process for a revolutionary new smartphone. The process consists of N tasks. M of these N tasks require at least one other task to have been completed before the task itself can be started. Each task requires one day to complete (and must be started and finished within a day). You have an unlimited number of multitalented robots at your disposal which can each complete one task per day. What is the shortest number of days needed to assemble the phone?

You are provided a dependency list, L, as input. This is a list containing N sublists. The sublist, L[i]L[i] contains the indices of tasks that must be completed before task i can be started (N−MN−M of these sublists will be empty). Complete the function, scheduler in p1_dev.py so that it efficiently assigns a day to each task so that the total number of days to complete all tasks is minimized. Tasks are numbered from 0 to N-1 and the function should return an N-element list whose ith element is an integer corresponding to the day on which task i is completed. For example, if M=0, then you should return a list with N zeros. You may assume that there are no pairs of tasks where each requires the other to have been previously completed and that N>MN>M. Add a discussion of your implementation to the docstring of your function.

2) Consider the propagation of a signal with initial amplitude, a0a0, through a telecommunication network with N junctions (junctions are numbered from 0 to N-1). As a signal propagates between two connected junctions, i and j, it experiences a loss characterized by LijLij. If the amplitude at junction i is a, the amplitude at junction j is LijaLija. Note that 0≤Lij<10≤Lij<1 and a0>0a0>0. The signal at a junction can be boosted back to a0a0 provided that its amplitude when it reaches the junction exceeds a threshold: a≥amina≥amin with amin>0amin>0 a specified threshold that is the same for each junction. If the signal amplitude falls below this threshold when it reaches a junction, it is removed from the network and is not considered to have successfully reached the junction.

Network data is provided via an n-element adjacency list, A. The ith element of A is a list containing two-element tuples of the form (j,Lij)(j,Lij). if A[3] = [(4,0.5),(0,0.25)] this indicates that junction 3 has connections to two other nodes, junctions 4 and 0, and that L3,4=0.5L3,4=0.5 and L3,0=0.25L3,0=0.25. The network is undirected, so Lij=LjiLij=Lji.

i) Develop and implement an efficient algorithm to determine if a signal with initial amplitude, a0a0, can successfully propagate from junction J1J1 to junction J2J2. Here, a0,J1,J2,A,amina0,J1,J2,A,amin are all provided as input. Complete the function findPath in p1_dev.py so that it finds one feasible path (if such a path exists) and returns the path in a list containing a sequence of integers corresponding to the sequence of junctions that that the signal passes through. So, if there is a feasible path between J1=5J1=5 and J2=12J2=12 via junctions 3 and 7 (in that order), the function should return [5,3,7,12]. Add a discussion of your implementation to the docstring of your function.

ii) Now, develop an efficient algorithm to determine the minimum a0a0 needed for a signal to successfully propagate from junction J1J1 to J2J2. A,J1,J2,aminA,J1,J2,amin are all provided as input. Complete the function a0min in p1_dev.py so that it finds both a0,mina0,min and a feasible path from J1J1 to J2J2 with a0=a0,mina0=a0,min (if a path exists). The function should return both a0,mina0,min and the computed path (see the function documentation). If no feasible path exists for any a0a0, return a0,min=−1a0,min=−1 and an empty list for the path. Add a discussion of your implementation to the docstring of your function.

Notes for part 1: 1) It is generally up to you to decide if the running time for your algorithm is sufficiently small, however for question 2 ii), you are not expected to construct a linear time algorithm.

2) You are not allowed to use heapq, however, if you determine that the best approach to a problem requires a binary heap, you should choose this approach, implement it without a heap, and then discuss the benefits of the heap (and its influence on the asymptotic running time) in your analysis.