xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

扫码添加客服微信

扫描添加客服微信

Java代写 - Comp 251: Assignment

时间：2020-12-04

General instructions (Read carefully!)
• Important: All of the work you submit must be done by only you, and your work
must not be submitted by someone else. Plagiarism is academic fraud and is taken very
seriously. For Comp251, we will use software that compares programs for evidence of
similar code. This software is very effective and it is able to identify similarities in the
code even if you change the name of your variables and the position of your functions.
The time that you will spend modifying your code, would be better invested in creating
an original solution.
Please don’t copy. We want you to succeed and are here to help. Here are a couple of
general guidelines to help you avoid plagiarism:
Never look at another assignment solution, whether it is on paper or on the computer
screen. Never share your assignment solution with another student. This applies to
all drafts of a solution and to incomplete solutions. If you find code on the web, or
get code from a private tutor, that solves part or all of an assignment, do not use
or submit any part of it! A large percentage of the academic offenses in CS involve
students who have never met, and who just happened to find the same solution online,
or work with the same tutor. If you find a solution, someone else will too. The easiest
way to avoid plagiarism is to only discuss a piece of work with the Comp251 TAs, the
CS Help Centre TAs, or the COMP 251 instructors.
• Your solution must be submitted electronically on codePost, on the same course page
as for previous assignments.
• To some extent, collaborations are allowed. These collaborations should not go as far
as sharing code or giving away the answer. You must indicate on your assignments
(i.e. as a comment at the beginning of your java source file) the names of the people
with whom you collaborated or discussed your assignments (including members of the
course staff). If you did not collaborate with anyone, you write “No collaborators”. If
asked, you should be able to orally explain your solution to a member of the course
staff.
1
• This assignment is due on December 1
st at 11h55:00 pm. It is your responsibility to
guarantee that your assignment is submitted on time. We do not cover technical issues
or unexpected difficulties you may encounter. Last minute submissions are at your
own risk.
• This assignment includes a programming component, which counts for 100% of the
grade, and an optional long answer component designed to prepare you for the exams.
This component will not be graded, but a solution guide will be published.
• Multiple submissions are allowed before the deadline. We will only grade the last
submitted file. Therefore, we encourage you to submit as early as possible a preliminary
version of your solution to avoid any last minute issue.
• Late submissions can be submitted for 24 hours after the deadline, and will receive a
flat penalty of 20%. We will not accept any submission more than 24 hours after the
deadline. The submission site will be closed, and there will be no exceptions, except
medical.
• In exceptional circumstances, we can grant a small extension of the deadline (e.g. 24h)
for medical reasons only. However, such request must be submitted before the deadline,
and justified by a medical note from a doctor, which must also be submitted to the
McGill administration.
• Violation of any of the rules above may result in penalties or even absence of grading. If
anything is unclear, it is up to you to clarify it by asking either directly the course staff
during office hours, by email at (cs251@cs.mcgill.ca) or on the discussion board on
Piazza (recommended). Please, note that we reserve the right to make specific/targeted
announcements affecting/extending these rules in class and/or on the website. It is
your responsibility to monitor Piazza for announcements.
• The course staff will answer questions about the assignment during office hours or
in the online forum. We urge you to ask your questions as early as possible. We
cannot guarantee that questions asked less than 24h before the submission deadline
will be answered in time. In particular, we will not answer individual emails about the
assignment that are sent sent the day of the deadline.
Programming component
• You are provided some starter code that you should fill in as requested. Add your code
only where you are instructed to do so. You can add some helper methods. Do not
modify the code in any other way and in particular, do not change the methods or
constructors that are already given to you, do not import extra code and do not touch
the method headers. The format that you see on the provided code is the only format
accepted for programming questions. Any failure to comply with these rules will
result in an automatic 0.
COMP 251 - HW3 Page 2 of 6 Fall 2020
• Public tests cases are available on codePost. You can run them on your code at any
time. If your code fails those tests, it means that there is a mistake somewhere. Even
if your code passes those tests, it may still contain some errors. We will grade your
code with a more challenging, private set of test cases. We therefore highly encourage
you to modify that tester class, expand it and share it with other students on the
discussion board. Do not include it in your submission.
• Your code should be properly commented and indented.
• Do not change or alter the name of the files you must submit, or the method
headers in these files. Files with the wrong name will not be graded. Make sure
you are not changing file names by duplicating them. For example, main (2).java will
not be graded. Make sure to double-check your zip file.
• You can submit either a zip file or individual files on codePost. If you get
more than 0 on the public tests, it means codePost accepted your files.
• You will automatically get 0 if the files you submitted on codePost do not
compile, since you can ensure yourself that they do. Note that public test cases
do not cover every situation and your code may crash when tested on a method that
is not checked by the public tests. This is why you need to add your own test cases
and compile and run your code from command line on linux.
COMP 251 - HW3 Page 3 of 6 Fall 2020
1. (50 points) Ford-Fulkerson
We will implement the Ford-Fulkerson algorithm to calculate the Maximum Flow of a directed weighted graph. Here, you will use the files WGraph.java and FordFulkerson.java,
which are available on the course website. Your role will be to complete two methods in
the template FordFulkerson.java.
The file WGraph.java is similar to the file that you used in your previous assignment to
build graphs. The only differences are the addition of setter and getter methods for the
Edges and the addition of the parameters “source” and “destination”. There is also an
additional constructor that will allow the creation of a graph cloning a WGraph object.
Graphs are encoded using a similar format than the one used in the previous assignment.
The only difference is that now the first line corresponds to two integers, separated by
one space, that represent the “source” and the “destination” nodes. An example of such
file can be found on the course website in the file ff2.txt. These files will be used
as an input in the program FordFulkerson.java to initialize the graphs. This graph
corresponds to the same graph depicted in [CLRS2009] page 727.
Your task will be to complete the two static methods (fordfulkerson WGraph graph)
and pathDFS(Integer source, Integer destination, WGraph graph). The second
method pathDFS finds a path via Depth First Search (DFS) between the nodes “source”
and “destination” in the “graph”. You must return an ArrayList of Integers with the
list of unique nodes belonging to the path found by the DFS. The first element in the
list must correspond to the “source” node, the second element in the list must be the
second node in the path, and so on until the last element (i.e., the “destination” node) is
stored. If the path does not exist, return an empty path. The method fordfulkerson
must compute an integer corresponding to the max flow of the “graph”, as well as the
graph encoding the assignment associated with this max flow.
Once completed, compile all the java files and run the command line java FordFulkerson
ff2.txt. Your program will output a String containing the relevant information. An
example of the expected output is available in the file ff2testout.txt. This output
keeps the same format than the file used to build the graph; the only difference is that
the first line now represents the maximum flow (instead of the “source” and “destination” nodes). The other lines represent the same graph with the weights updated to the
values that allow the maximum flow. The file ff226testout.txt represents the answer
to the example showed in [CLRS2009] Page 727. You are invited to run other examples
of your own to verify that your program is correct.
2. (50 points) Bellman-Ford
We want to implement the Bellman-Ford algorithm for finding the shortest path in
a graph where edges can have negative weights. Once again, you will use the object
WGraph. Your task is to complete the method BellmanFord(WGraph g, int source)
and shortestPath(int destination) in the file BellmanFord.java.
The method BellmanFord takes an object WGraph named g as an input and an integer
that indicates the source of the paths. If the input graph g contains a negative cycle,
then the method should throw an exception (see template). Otherwise, it will return
COMP 251 - HW3 Page 4 of 6 Fall 2020
an object BellmanFord that contains the shortest path estimates (the private array of
integers distances), and for each node, its predecessor in the shortest path from the
source (the private array of integers predecessors).
The method shortestPath will return the list of nodes as an array of integers along
the shortest path from the source to the destination. If this path does not exists, the
method should throw an exception (see template).
An example input is available in bf1.txt.
3. (0 points) Knapsack Problem
We have seen in class the Knapsack problem and a dynamic programming algorithm.
One could define the Knapsack problem as following:
Definition. Let n > 0 be the number of distinct items and W > 0 be the knapsack
capacity. For each item i, wi > 0 denotes the item weight and vi > 0 denotes its value.
The goal is to maximize the total value
Xni=1
vixi
while
Xni=1
wixi ≤ W
where xi ∈ {0, 1} for i ∈ {1, . . . , n}.
Algorithm. We recall the recursive form of the dynamic programming algorithm.
Let OP T(i, w) be the maximum profit subset of items 1, . . . , i with weight limit w. If
OP T does not select the item i, then OP T selects among items {1, . . . , i 1} with weight
limit w. Otherwise, OP T selects among items {1, . . . , i 1} with weight limit w wi.
We could formalize as
OP T(i, w) =
0 if i = 0
OP T(i 1, w) if wi > w
max{OP T(i 1, w), vi + OP T(i 1, w wi)} otherwise
COMP 251 - HW3 Page 5 of 6 Fall 2020
Correctness of dynamic programming algorithm (0)
Usually, a dynamic programming algorithm can be seen as a recursion and proof by
induction is one of the easiest way to show its correctness. The structure of a proof by
strong induction for one variable, say n, contains three parts. First, we define the
Proposition P(n) that we want to prove for the variable n. Next, we show that the
proposition holds for Base case(s), such as n = 0, 1, . . . etc. Finally, in the Inductive
step, we assume that P(n) holds for any value of n strictly smaller than n0
, then we
prove that P(n0) also holds.
Use the proof by strong induction properly to show that the algorithm of the Knapsack
problem above is correct.
Bounded Knapsack Problem (0)
Let us consider a similar problem, in which each item i has ci > 0 copies (ci
is an
integer). Thus, xi
is no longer a binary value, but a non-negative integer at most equal
to ci, 0 ≤ xi ≤ ci
. Modify the dynamic programming algorithm seen at class for this
problem.
Note: One could consider a new set, in which item i has ci occurrences. Then, the
algorithm seen as class can be applied. However, this could be costly since ci might be
large. Therefore, the algorithm you propose should be different than this one.
Unbounded Knapsack Problem (0-bonus)
In this question, we consider the case where the quantity of each item is unlimited. Thus,
xi could be any non-negative integer. Provide a dynamic programming algorithm for
this problem.

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写
- archi代写