数据分析工具代写 MAT 170代写 MATLAB代写 LATEX代写

MAT 170 FINAL PROJECT

数据分析工具代写 All Final Projects need to be done individually. No teams are allowed. We will refer all suspected acts of collaboration to student judicial

• All Final Projects need to be done individually. No teams are allowed. We will refer all suspected acts of collaboration to student judicial affairs. If you want input from a fellow classmate, the TA or the Professor ask on PIAZZA. This is the only way to ‘collaborate’ in this class without violating class rules and the Code of Academic Conduct.

• NO LATE PAPERS WILL BE ACCEPTED!

If you request an incomplete grade you will 1) have to have a passing grade in this class to date, including Project 03, and 2) you will have to pass the Final Project and Project 04 for MAT 170 in Spring Quarter 2022 in order to receive a passing grade for this class. 数据分析工具代写

NOTE:

Students who are in India and are suddenly subject to a serious event or events related to the pandemic are exempt from these rules.

• Knowledge of MATLAB is presumed. Ask on Piazza if you need help. DO NOT ask a fellow student for help. Except for using MATLAB’s ‘help’ functionality by yourself this constitutes unauthorized collaboration and is a violation of course rules and hence, the Code of Academic Conduct.
• Turn in the written portion of your project as one PDF file that has been produced with LATEX and submit your PDF file to Gradescope (not CANVAS).
• Put all of your MATLAB *.m files, all of the *data files* they need in order to run properly, and your LATEX file in a folder named “youremailname Final Project”. Make a *.zip file “youremailname Final Project.zip” containing this folder and upload it to CANVAS.
• When you write your MATLAB code you should use the following “best (coding) practices”. The beginning of all of your MATLAB *.m files must include yourName, your SID and the MATLAB filename with a brief description as to what it does. Include brief comments in your code as appropriate; i.e., so that it is clear what each section of your code is designed to do.

MAKE SURE YOU UNDERSTAND THIS NEXT BULLET ITEM 数据分析工具代写

• It is VERY IMPORTANT that your submission includes one (and only one) “main” MATLAB file named “youremailname Final Project.m”, When the TA clicks on the green Run button all of the essential results for the Problems you chose to do should be printed out in the Command Window of the MATLAB Integrated Development Environment (IDE). I will refer to this MATLAB file as your “main” (MATLAB) program or your “main” *.m file.

NOTE: It is OK for you to create, use, and submit! multiple MATLAB *.m files that are called by your main program; i.e, your main *.m file. In fact, this is good programming practice. These other MATLAB *.m files should be functions that perform specific tasks. For example, you might have several functions, each in a different *.m file, one that calls another, that calls another, and so on, which together solve Problem 01(A) below. Then, you might also have one or more *.m files that call each other to solve Problem 1(B), etc. However, all of these other files should be functions that are (ultimately) called by your main MATLAB program. Here “ultimately” means that your main *.m file may call a MATLAB file named function 01.m and this function may call a MATLAB file named function.m and so on.

However, in the end, all of your results for Problem 01(A)-(C) will ultimately be displayed in the command window of the MATLAB IDE. 数据分析工具代写

The requirement stated above is that all of these *.m files should run and do whatever they are supposed to do when the TA clicks on the green Run button in the MATLAB IDE.

Finally, we will not download data files for you, retype or copy and paste text into your code. If your code does not produce all of the results for all of the MATLAB Problems with one click of the Run button, you will receive zero points for your MATLAB code submission.

• Be organized and use appropriate notation. (For example, if we used a particular notation during a lecture to denote the same quantity as you are working with, then use that same symbol in your write-up.) Show your work on every problem, especially for Part 3. Correct answers that are not supported by work will not receive full credit.

Problem 01 FINDING THE BEST PATH 数据分析工具代写

Here are some some challenges concerning optimal paths:

NOTE: You do not have to write any code for this Problem. You just have to set up the network flow models correctly.

(a)

Let G be a directed graph with distances or costs on its arcs and two special vertices s, t. We are interested on the “longest” paths using two possible definitions:

i. Suppose we define the length of a path to be the sum of the lengths on the path. Write a network flow problem to compute the longest path on a network.

ii. If we instead define the length of a path to be the largest length among all thearcs in the path, Write another network flow problem to compute the longest path on a network given this definition.

(b)

Let G be a graph with two distinguished vertices s, t. An even st-path is a path from s to t with an even number of edges. Describe a computer algorithm to find a shortest even st-path; i.e., the path with the fewest edges possible.

HINT: It is not easy to use the st-path formulation in class. Instead you can reformulate as a minimum cost perfect matching problem! Construct an auxiliary graph H from G, make a copy of the graph G, and remove vertices s, t. Call the new graph G’. Construct H starting with the union of G and G’ and joining every vertex v ∈ G different from s, t from its copy in G’ . Use H.

(c) 数据分析工具代写

Consider again, the TSP for n cities and cost of travel c_ij.

i. Write a new model for the TSP, which is different from the ones we saw in class. This time use the binary variables x_i,j,k, where it equals 1 if on the k-th leg of the trip, the salesman goes from city i to city j. Your formulation must have a cubic number of constraints. What are they?

ii. Given a graph G = (V, E) representing say the cities of California connected by highways, we wish to find out whether there is a tour of the vertices of G (a cycle visiting each vertex exactly once) which only uses the existing edges in E. Suppose you have a powerful software that solves the Traveling salesman problem. How would you use that algorithm for the TSP to answer that question? What costs should you pick on arcs?

iii. Let G be a graph with two distinguished vertices s, t. An even st-path is a path from s to t with an even number of edges. Describe a computer algorithm to find a shortest even st-path (one with as few edges as possible).

Problem 02 HOW TO INFLUENCE THE OPINION OF PEOPLE WHEN ON A BUDGET: 数据分析工具代写

Apparently it is in fashion to use social networks, like Facebook, to influence voters in elections. In this problem, you will consider a simplified model of influence in social networks. The social network is represented by an undirected graph G = (V, E) and for a set of nodes S ⊆ V , we denote by N(S) the set of their neighbors:

N(S) = {v ∈ V | ∃_u∈ S, (u, v) ∈ E}.

The influence I(S) of a set of nodes is measured by

I(S) = |N(S)|

Imagine you work now for Facebook and you are given the dataset Facebookgraph.txt, which is in the DATA directory that is in the same directory on the CANVAS FILES page that these directions are in. This dataset is in fact a subgraph of the real Facebook social graph. Each line in the file contains the id of two users, indicating that these two users are friends on Facebook.

(a)

As the designer of a marketing campaign to influence the opinion of voters, your goal is to find a subset S ⊆ V of at most K nodes whose influence is maximal. Write a mathematical model to solve this problem. Can you solve the problem for the data you were given using MATLAB?

If not, can you write a practical method to give an approximation to the optimum?

(b) 数据分析工具代写

Using any of your models/methods from part (a) write a computer program which, given the social network described in the dataset and a budget K ∈ N⁺, returns an approximately optimal set of nodes S for the influence function I(S). The function should return both the users to influence and the value (total amount of influence) obtained.

(c)

Plot the influence I(S) obtained by your function as a function of the budget K. For example, what happens when K = 1 and K = |V |?

(d)

A vertex-cover of a graph G is a set S of vertices of G such that each edge of G is incident with at least one vertex of S. The vertex cover number τ (G) is the size of a minimum vertex cover in G.

A dominating set for a graph is a subset D of vertices such that every vertex not in D is adjacent to at least one member of D. The domination number γ(G) is the smallest dominating set.

Are there any relationships among the influence function I(S), τ (G), and γ(G)? Explain.

Formulate a discrete model that given a graph finds a vertex cover with the smallest number of vertices and the smallest dominating set. Explain the reasoning on your variables and constraints.

更多代写：CS美国加拿大代上网课  代考一般多少钱  英国经济学网课代修  留学report代写  英文硕士研究论文代写 presentation代写 

合作平台：essay代写 论文代写 写手招聘 英国留学生代写