xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

扫码添加客服微信

扫描添加客服微信

C/C++代写|算法代写 - COMP3600/6466 Algorithms Assignment 1

时间：2020-10-13

COMP3600/6466 Algorithms Assignment 1
COMP3600/6466 — Algorithms
Convenor & lecturer: Hanna Kurniawati
E-mail: comp 3600 6466@anu.edu.au
Assignment 3
Due: Monday, 26 October 2020 23:59 Canberra Time
Grace Period Ends: Tuesday, 27 October 2020 13:00 Canberra Time
Late Penalty: 100%
Notes:
• In this assignment, you need to submit: .
– A written/typed answer to the questions as a single .pdf file, named A3-studentID.pdf.
– Source codes as a single file, named A3-studentID.cpp file (or suitable extension for the programming
language you use). In this assignment, you can use C/C++/Java. However, support will be provided only
for C/C++. Moreover, please pay attention to the following:
∗ To ensure we can run your program with no problem, you need to use the template provided during
tutorials and test your program on the provided test cases (the template and test cases are available in
the class website).
∗ We will compile and run your program from command prompt in Linux using the command:
> g++ -std=c++11 A3-studentID.cpp -o A3-studentID
> ./A3-studentID input1.txt > output1.txt
– You need to compress all files (the .pdf and .cpp) into a single .zip file named A3-studentID.zip and save
this .zip file as draft in Wattle before the due date .
• We provide 13 hours grace period. This means, there will be no penalty if you submit OR save as draft before
the grace period ends. However, we will NOT accept assignment after the grace period ends.
• Assignment marking:
– The total mark you can get in this assignment is 100 points.
– Whenever explanation/argument/reasoning/derivation is requested, the explanation/derivation is worth
80% of the points you can get for the question.
– This assignment will contribute 25% to your overall mark.
• Discussion with your colleagues are allowed and encouraged. However, you still need to work on the assignment on your own AND write the names you discussed this assignment with.
• You are allowed to use materials from textbooks, other books, websites, etc., but you do need to provide the
references to these materials.
[25 pts] Part A
1. [5 pts] In a max-heap where all elements are distinct, where is the smallest element located? Please explain.
2. [5pts] Ms RB would like to transform a red-black tree into a black-only tree by setting the children of the red
nodes to become the children of the parent of the red nodes, and then removing the red nodes. What can you
say about the leaves’ depth of the resulting tree? Please explain.
3. [10pts] Suppose you need to represent a set of data whose keys are: 1, 2, 3, 4, 5, 6, 7, 8, 9 as an AVL tree.
(a) [5pts] Draw an instantiation of the shallowest AVL tree that you can construct for the above data set and
explain why it is indeed the shallowest AVL tree possible for the data set.
(b) [5pts] Draw an instantiation of the deepest AVL tree that you can construct for the above data set and
explain why it is indeed the deepest AVL tree possible for the data set.
4. [5 pts] Mr H argues that for a hash table with chaining and simple universal hashing, the expected time complexity to search for an item can be made to be O( 1n ). He suggested that this time complexity is achievable simply
by setting the number of slots in the hash table to be n2 (n is the number of elements in the table) because this
setting will lead to a load factor α = 1n
. Is Mr H correct? Please explain why or why not.
1
COMP3600/6466 Algorithms Assignment 1
[35 pts] Part B
5. [5 pts] Mr B said that he found a comparison-based method to construct a Binary Search Tree in O(n), where
n is the number of elements in the data set. Could this be true? Please provide a proof or counter-example to
support your argument.
6. [10 pts] Consider a hash table T with m slots. Suppose T contains a single element, and this element has key
k. Ms Search has been searching for r keys that are different from k in hash table T. Assuming T uses simple
uniform hashing and chaining, what is the probability that at least one of the r searches collide with the m slot
containing key k? Please provide the derivation.
7. [10 pts] Recall the matrix chain multiplication problem we discussed in class (week-8 Tuesday, based on
[CLRS] 15.2). Mr SP says that we can compute the optimal solution to this problem faster, simply by recursively splitting the (sub-)chain of matrices As · As+1 · · · Ae at Ak, where 1 ≤ s ≤ e, the size of Ai for i ∈ [s, e]
is pii1× pi
, and k is selected to minimise the value pii1× pk × pj (i.e., k = arg mini∈[s,ee1] pi). To make it clearer,
below is the pseudo-code of the algorithm Mr SP proposed. The output of the pseudo-code is a string of the
chain of matrices together with their parenthesis.
Algorithm 1 SP-MatrixChainMult(A chain of matrices As, As+1, · · · , Ae)
1: if s == e then
2: Return “As”
3: Let k = arg mini∈[s,ee1] pi
4: Return “(SP-MatrixChainMult(As, · · · Ak)) · (SP-MatrixChainMult(Ak+1, · · · Ae))”
Is Mr SP’s algorithm correct? Please explain your answer by either providing a proof or a counter-example.
8. [10 pts] As a program manager at a large company, Mr PM is overseeing multiple projects. As a good program
manager, he needs to foresee whether there will be delays in each of his projects. To this end, he asked your
help to develop a Dynamic-Programming approach to compute an estimated longest duration to finish a project.
To compute the above estimate, you can assume a project is divided into multiple tasks, starting from an initial
task and ending at a final task. The dependencies between tasks can be represented as a weighted directed
graph, called the task graph. The vertices of a task graph represent the tasks, an edge from a vertex v to another
vertex v0
in a task graph means the task represented by v must be completed first before the task represented
by v0
can start, and the weight associated with with vertex vv0
indicates the time duration to complete the task
represented by v. One can then compute the estimated longest duration to finish a project by finding the longest
path from the vertex representing the initial task to the vertex representing the final task in the task graph.
In this question, you need to provide the sub-problems and recursive definition of the optimal value function
(i.e., step-1 and step-2 of Dynamic Programming development steps, as discussed in class in week8 Tuesday
lecture based on [CLRS] 15.Intro and 15.3) to find the longest path in the task graph.
[40 pts] Part C
9. Ms C has been preparing to start her own restaurant —a TCA Burger franchise— in her city, Arrebnac. She has
finalised all the necessary franchising agreement and licensing for the restaurant, as well as signed the lease and
finished refurbishing her TCA Burger shop in a strategic location at the Arrebnac City Centre. Now, she needs
to start hiring her staff.
Ms C plans to fill n positions, and hires exactly one person for each position. She budgeted a total of at most
B × $10, 000 per year to pay the salaries of the people she will hire. In this problem, we use the term salary
to include everything an employee will receive (ie, including superannuation and other benefits). For each
position-i (i ∈ [1, n]), Ms C receives ki applicants. Each applicant stated the salary they requested. Let’s denote
si j × $1, 000 as the yearly salary that applicant-j for position-i requested. You can assume Ms C pays the requested salary without negotiation, and that higher salary equals better performance. Ms C would like to hire
her staff, such that the total yearly salary she will need to pay is the highest possible not exceeding her budget.
2
COMP3600/6466 Algorithms Assignment 1
To simplify the problem, you can assume B and si j for all i ∈ [1, n], j ∈ [1, ki] are all positive integers, with
10 ≤ B ≤ 300 and 10 ≤ si j ≤ 100. Furthermore, the number of positions and applicants are limited too, with
1 ≤ n ≤ 25 and 1 ≤ ki ≤ 150 for i ∈ [1, n].
Your task is to help Ms C makes the hiring decision by developing a dynamic-programming algorithm to find
the applicants to hire, so that each position is filled by exactly one person, and the total salary is the highest
possible not exceeding B × $10, 000. To this end, please answer the following questions.
(a) [10 pts] Please provide step-1 and step-2 of the dynamic programming development steps (the steps are
as discussed in class in week8 Tuesday lecture based on [CLRS] 15.Intro and 15.3).
(b) [4 pts] Please show that for the sub-problems you have defined in Q9, the sub-problem graph is a directed
acyclic graph.
(c) [6 pts] Please provide the pseudo-code for top-down and bottom-up dynamic programming to help Ms C.
(d) [5] Please derive the asymptotic time complexity of your bottom-up dynamic programming solution.
(e) [10 pts] Please implement the bottom-up dynamic programming algorithm you have developed above.
Input to the Program. The program will accept a single argument, which is the name of the input file.
The input is a text file containing n + 1 lines, where n is the number of positions to be filled. The first
line consists of two numbers, separated by a white space. The first number is B and the second number
is n. Each line-(i + 1) in the next n lines consists of ki + 1 numbers, separated by a white space. The first
number represents the number applicants for position-i, while the next ki numbers represent the requested
salaries si j of each applicant, indexed from 1 to ki.
Example:
17 2
3 100 50 70
2 95 75
The above input means that Ms C’s budget is $170, 000 and two positions are to be filled. For the first
position, 3 applicants apply, with the requested yearly salary for the first, second, and third applicants
being $100, 000, $50, 000, and $70, 000 respectively (i.e., s1,1 = 100, s1,2 = 50, s1,3 = 70). For the second
position, there’s only two applicants, with their yearly requested salary being $95, 000 and $75, 000.
Output to the Program. The program should output to standard output. If the problem has one or more
solution, the program should output a single line containing of n + 1 numbers separated by a white space.
The first number is the total salary cost of the people selected to be hired. The next n numbers are the
indices of the selected applicant, starting from the selected applicant for the first position, then the second,
etc.. If the same total salary cost can be achieved by selecting more than one set of selected applicants, any
set of them will be acceptable. If the problem has no solution, the program should output “no solution”.
Output example for the example input scenario:
165000 3 1
Program Marking. If your program compiles and runs, you will get 2 points. We will then run your
program on 4 test cases. For each test case, your dynamic programming algorithm (including data structure
construction) will be given a total of (0.0001 × M × T otalNumberO f Applicants) ms CPU time to find a
solution. You can assume your program will have access to at most 12GB RAM. It will be run as a single
thread process on a computer with Intel i7 3.4GHz processor. For each test case that your program solves
correctly within the given time and memory limit, you will get 2 points.
Note: The test cases for marking will be different from the example test cases.
(f) [5 pts] Please compare the empirical running time of your program and the asymptotic time complexity you have derived in Q9.d. For this purpose, you need to create at least 5 scenarios with increasing
parameter size, and provide a comparison between the theoretical and empirical time-complexity.
3

- 留学生代写
- 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代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写