01 Problems ans

电 子 科 技 大 学实 验 报 告学生姓名： 学 号： 指导教师： 实验时间: 报告评分： 一、实验室名称：应用数学学院数学实验室 二、实验项目名称：抛射曲线实验 三、实验原理：炮弹飞行的简单数学模型为抛射曲线，其参数方程为⎪⎩⎪⎨⎧-⨯=⨯=20021sin cos gt t v y t v x αα 其中v 0为初始速度，α 为发射角，g 是重力加速度（约为 9.8米/秒2）。

四、实验目的：熟悉MATLAB 的集成环境，掌握MATLAB 的基本运算和数学表达式计算方法。

五、实验内容：对已知射程数据，为使炮弹击中目标需计算发射角；反之对已知的发射角数据，也需要计算射程。

设v 0 = 515米/秒，对不同目标计算射程、发射角和炮弹飞行时间。

六、实验器材（设备、元器件）：台式计算机 七、实验步骤及操作：弹道数据包括射程、发射角及炮弹飞行时间。

令参数方程中y 的表达式为零可确定炮弹飞行时间 t (α )，代入 x 的表达式可导出射程计算公式。

（1） 炮弹飞行时间计算公式：gv t ααsin 2)(0=（2） 射程计算公式：ααα2sin sin 2cos 2001gv g v v x =⨯=（3） 发射角计算公式：)/arcsin(21201v gx =α八、实验数据及结果分析：(2分)注意：红色字是填写的数据，黑色字是实验报告原有的数据。

教师参考程序如下%----抛射曲线仿真程序%----2007/01/24g=9.8;v0=515;distance=inline('515*515*sin(2*dalpha)/9.8');alpha=inline('0.5*asin(9.8*s/(515^2))');times=inline('2*515*sin(alpha)/9.8');results1(1,:)=[10,20,27];a=alpha(10000); results1(2,1)=a*180/pi;results1(3,1)=times(a);a=alpha(20000); results1(2,2)=a*180/pi;results1(3,2)=times(a);a=alpha(27000); results1(2,3)=a*180/pi;results1(3,3)=times(a);results1results2(2,:)=[45,60];results2(1,1)=distance(45*pi/180)/1000;results2(1,2)=distance(60*pi/180)/1000;results2(3,1)=times(45*pi/180);results2(3,2)=times(60*pi/180);results2九、实验结论：（1分）十、总结及心得体会：（1分）十一、对本实验过程及方法、手段的改进建议：（1分）。

【关键字】0/1分数规划、最优比率生成树、最优比率环【背景】根据楼教主的回忆录，他曾经在某一场比赛中秒掉了一道最优比率生成树问题，导致很多人跟风失败，最终悲剧。

自己总结了一些这种问题的解法，因为水平有限，如果有错误或是麻烦的地方，尽管喷。

联系我的话perseawe@，欢迎讨论，请在标题前注明[acm]或是[oi]，以免被垃圾邮件。

【知识储备】只会用到简单的公式的整理与变形，还有求和sigma。

【定义】01分数规划问题：所谓的01分数规划问题就是指这样的一类问题，给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。

如果选取i，定义x[i]=1否则x[i]=0。

每一个物品只有选或者不选两种方案，求一个选择方案使得R=sigma(a[i]*x[i])/sigma(b[i]*x[i])取得最值，即所有选择物品的总收益/总代价的值最大或是最小。

01分数规划问题主要包含一般的01分数规划、最优比率生成树问题、最优比率环问题、最大密度子图等。

我们将会对这四个问题进行讨论。

永远要记得，我们的目标是使R取到最值。

这句话我会在文中反复的强调。

【一些分析】数学分析中一个很重要的方法就是分析目标式，这样我们来看目标式。

R=sigma(a[i]*x[i])/sigma(b[i]*x[i])我们来分析一下他有什么性质可以给我们使用。

我们先定义一个函数F(L):=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])，显然这只是对目标式的一个简单的变形。

分离参数，得到F(L):=sigma((a[i]-L*b[i])*x[i])。

这时我们就会发现，如果L已知的话，a[i]-L*b[i]就是已知的，当然x[i]是未知的。

记d[i]=a[i]-L*b[i]，那么F(L): =sigma(d[i]*x[i])，多么简洁的式子。

我们就对这些东西下手了。

再次提醒一下，我们的目标是使R取到最大值。

我们来分析一下这个函数，它与目标式的关系非常的密切，L就是目标式中的R，最大化R也就是最大化L。

ASN.1(Abstract Syntax Notation One, 抽象语法符号1)是ITU-T的一个标准集，它用来编码及表示通用数据类型，这些数据类型有可打印串值，八位位组串值，位串值，整数值以及用可移值方式组合而成的其他类型序列值．简单的说，ASN.1指定了以何种方式对非平凡的数据类型进行编码，以便其他任何平台及第三方工具都能够解释其内容．比如，字母a在一些平台以ASCII编码为十进制数值97,而在其他非ASCII平台上，可能会是另外的编码．而ASN.1指定了一种编码方式，在任何平台上，字母a的编码都是统一的．ASN.1语法．ASN.1语法遵循传统的巴科斯范式BNF风格．最基本的表达式如：Name ::= type . 表示为定义某个名称为Name的元素，它的类型为type．例如：MyName ::= IA5String . 表示为定义了一个名为MyName的元素或变量，其类型为ASN.1类型IA5String (类似于ASCII字符串).类型BER简单定长方法结构化定长方法和非定长方法DERDER是BER的子集，它定义了使用一个octet string来表示任何ASN.1值的编码方法。

DER 用于需要使用唯一的octet string编码的应用程序，例如根据一个ASN.1编码来计算数字签名。

DER在X.509的第8.7节定义。

DER在第3节给出的规则基础上增加了如下限制：1. 如果长度在0－127之间，必须使用短型长度表示法。

2. 如果长度大于等于128，必须使用长型长度表示法。

并且长度必须使用尽可能少的字节表示。

3. 对于简单string类型和在其基础上使用隐式标签生成的类型，必须使用简单定长编码方法。

4. 对于结构化类型和在其基础上使用隐式标签生成的类型、及在任何类型基础上使用显式标签生成的类型，必须使用结构化定长编码方法。

对于特殊类型（如BIT STRING、SEQUENCE、SET和SET OF）的其他限制见第5节。

01编码矩阵乘法01编码矩阵乘法是一种基于二进制编码的矩阵乘法算法。

在普通矩阵乘法的基础上，将矩阵中的元素用二进制表示，并按照二进制位进行相乘和相加的操作。

具体来说，对于两个大小为n×m和m×p的矩阵A和B，它们的01编码矩阵乘法可以按照以下步骤进行：1. 初始化一个n×p的零矩阵ans，用于存储结果。

2. 对于A矩阵中的每个元素a(i,j)，将其转换为二进制编码，并存储为一个长度为m的二进制串a_str。

3. 对于B矩阵中的每个元素b(i,j)，将其转换为二进制编码，并存储为一个长度为n的二进制串b_str。

4. 对于ans矩阵中的每个位置(i,j)，计算a_str和b_str的按位与运算，并将结果转换为十进制数，然后加到ans(i,j)中。

5. 重复步骤2-4，直到遍历完所有元素。

下面是一个示例代码，演示如何使用01编码矩阵乘法计算两个矩阵的乘积：```pythonimport numpy as npdef matrix_multiplication(A, B):n = len(A)m = len(A[0])p = len(B[0])ans = np.zeros((n, p))for i in range(n):for j in range(p):a_str = ''.join(str(int(x)) for x in A[i]) b_str = ''.join(str(int(x)) for x in B[j]) ans[i][j] += int(a_str & b_str)return ans```需要注意的是，01编码矩阵乘法的计算复杂度较高，因此在处理大规模矩阵时可能会比较耗时。

此外，由于采用了二进制编码，需要使用按位与运算符(&)来进行相乘操作，这可能会增加代码的复杂性。

Open Problems ListArising from MathsCSP Workshop,Oxford,March2006Version0.3,April25,20061Complexity and Tractability of CSPQuestion1.0(The Dichotomy Conjecture)Let B be a relational structure.The problem of deciding whether a given relational structure has a homomorphism to B is denoted CSP(B).For which(finite)structures is CSP(B)decidable in polynomial time?Is it true that for anyfinite structure B the problem CSP(B)is either decidable in polynomial time or NP-complete?Communicated by:Tomas Feder&Moshe Vardi(1993) Question1.1A relational structure B is called hereditarily tractable if CSP(B )is tractable for all substructures B of B.Which structures B are hereditarily tractable?Communicated by:Pavol Hell Question1.2A weak near-unanimity term is defined to be one that satisfies the following identities:f(x,...,x)=x and f(x,y,....y)=f(y,x,y,....y)=...=f(y,...,y,x).Is CSP(B)tractable for any(finite)structure B which is preserved by a weak near-unanimity term?Communicated by:Benoit Larose,Matt Valeriote Question1.3A constraint language1S is called globally tractable for a problem P,if P(S)is tractable,and it is called(locally)tractable if for everyfinite L⊆S,P(L)is tractable.These two notions of tractability do not coincide in the Abduction problem(see talk by Nadia Creignou).•For which computational problems related to the CSP do these two notions of tractability coincide?•In particular,do they coincide for the standard CSP decision problem?Communicated by:Nadia Creignou 1That is,a(possibly infinite)set of relations over somefixed set.1Question1.4(see also Question3.5)It has been shown that when a structure B has bounded pathwidth duality the corresponding problem CSP(B)is in the complexity class NL (see talk by Victor Dalmau).Is the converse also true(modulo some natural complexity-theoretic assumptions)?Communicated by:Victor Dalmau Question1.5Is there a good(numerical)parameterization for constraint satisfaction problems that makes themfixed-parameter tractable?Question1.6Further develop techniques based on delta-matroids to complete the com-plexity classification of the Boolean CSP(with constants)with at most two occurrences per variable(see talk by Tomas Feder).Communicated by:Tomas Feder Question1.7Classify the complexity of uniform Boolean CSPs(where both structure and constraint relations are specified in the input).Communicated by:Heribert Vollmer Question1.8The microstructure graph of a binary CSP has vertices for each variable/value pair,and edges that join all pairs of vertices that are compatible with the constraints.What properties of this graph are sufficient to ensure tractability?Are there properties that do not rely on the constraint language or the constraint graph individually?2Approximability and Soft ConstraintsQuestion2.1Is it true that Max CSP(L)is APX-complete whenever Max CSP(L)is NP-hard?Communicated by:Peter Jonsson Question2.2Prove or disprove that Max CSP(L)is in PO if the core of L is super-modular on some lattice,and otherwise this problem is APX-complete.The above has been proved for languages with domain size3,and for languages contain-ing all constants by a computer-assisted case analysis(see talk by Peter Jonsson).Develop techniques that allow one to prove such results without computer-assisted analysis.Communicated by:Peter Jonsson Question2.3For some constraint languages L,the problem Max CSP(L)is hard to approximate better than the random mindless algorithm on satisfiable or almost satisfiable instances.Such problems are called approximation resistant(see talk by Johan Hastad).Is a single random predicate over Boolean variables with large arity approximation resistant?What properties of predicates make a CSP approximation resistant?What transformations of predicates preserve approximation resistance?Communicated by:Johan Hastad2Question2.4Many optimisation problems involving constraints(such as Max-Sat,Max CSP,Min-Ones SAT)can be represented using soft constraints where each constraint is specified by a cost function assigning some measure of cost to each tuple of values in its scope.Are all tractable classes of soft constraints characterized by their multimorphisms?(see talk by Peter Jeavons)Communicated by:Peter Jeavons 3AlgebraQuestion3.1The Galois connection between sets of relations and sets of operations that preserve them has been used to analyse several different computational problems such as the satisfiability of the CSP,and counting the number of solutions.How can we characterise the computational goals for which we can use this Galois connection?Communicated by:Nadia Creignou Question3.2For any relational structure B=(B,R1,...,R k),let co-CSP(B)denote the class of structures which do not have a homomorphism to B.It has been shown that the question of whether co-CSP(B)is definable in Datalog is determined by P ol(B),the polymorphisms of the relations of B(see talk by Andrei Bulatov).Let B be a core,F the set of all idempotent polymorphisms of B and V the variety generated by the algebra(B,F).Is it true that co-CSP(B)is definable in Datalog if and only if V omits types1and2(that is,the local structure of anyfinite algebra in V does not contain a G-set or an affine algebra)?Communicated by:Andrei Bulatov Question3.3Does every tractable clone of polynomials over a group contain a Mal’tsev operation?Communicated by:Pascal Tesson Question3.4Classify(w.r.t.tractability of corresponding CSPs)clones of polynomials of semigroups.Communicated by:Pascal Tesson Question3.5Is it true that for any structure B which is invariant under a near-unanimity operation the problem CSP(B)is in the complexity class NL?Does every such structure have bounded pathwidth duality?(see also Question1.4)Both results are known to hold for a2-element domain(Dalmau)and for majority operations(Dalmau,Krokhin).Communicated by:Victor Dalmau,Benoit Larose3Question3.6Is it decidable whether a given structure is invariant under a near-unanimity function(of some arity)?Communicated by:Benoit Larose Question3.7Let L be afixedfinite lattice.Given an integer-valued supermodular func-tion f on L n,is there an algorithm that maximizes f in polynomial time in n if the function f is given by an oracle?The answer is yes if L is a distributive lattice(see“Supermodular Functions and the Complexity of Max-CSP”,Cohen,Cooper,Jeavons,Krokhin,Discrete Applied Mathemat-ics,2005).More generally,the answer is yes if L is obtained fromfinite distributive lattices via Mal’tsev products(Krokhin,Larose–see talk by Peter Jonsson).The smallest lattice for which the answer is not known is the3-diamond.Communicated by:Andrei Krokhin Question3.8Find the exact relationship between width and relational width.(It is known that one is bounded if and and only if the other is bounded.)Also,what types of width are preserved under natural algebraic constructions?Communicated by:Victor Dalmau 4LogicQuestion4.1The(basic)Propositional Circumscription problem is defined as fol-lows:Input:a propositional formulaφwith atomic relations from a set S,and a clause c.Question:is c satisfied in every minimal model ofφ?It is conjectured(Kirousis,Kolaitis)that there is a trichotomy for this problem,that it iseither in P,coNP-complete or inΠP2,depending on the choice of S.Does this conjecturehold?Communicated by:Nadia Creignou Question4.2The Inverse Satisfiability problem is defined as follows: Input:afinite set of relations S and a relation R.Question:is R expressible by a CNF(S)-formula without existential variables?A dichotomy theorem was obtained by Kavvadias and Sideri for the complexity of this problem with constants.Does a dichotomy hold without the constants?Are the Schaefer cases still tractable?Communicated by:Nadia Creignou4Question4.3Let LFP denote classes of structures definable infirst-order logic with a least-fixed-point operator,let HOM denote classes of structures which are closed under homomorphisms,and let co-CSP denote classes of structures defined by not having a homomorphism to somefixed target structure.•Is LFP∩HOM⊆Datalog?•Is LFP∩co-CSP⊆Datalog?(forfinite target structures)•Is LFP∩co-CSP⊆Datalog?(forω-categorical target structures)Communicated by:Albert Atserias,Manuel BodirskyQuestion4.4(see also Question3.2)Definability of co-CSP(B)in k-Datalog is a sufficient condition for tractability of CSP(B),which is sometimes referred to as having width k. There is a game-theoretic characterisation of definability in k-Datalog in terms of(∃,k)-pebble games(see talk by Phokion Kolaitis).•Is there an algorithm to decide for a given structure B whether co-CSP(B)is definable in k-Datalog(for afixed k)?•Is the width hierarchy strict?The same question when B isω-categorical,but not necessarilyfinite?Communicated by:Phokion Kolaitis,Manuel BodirskyQuestion4.5Find a good logic to capture CSP with“nice”(e.g.,ω-categorical)infinite templates.Communicated by:Iain Stewart 5Graph TheoryQuestion5.1The list homomorphism problem for a(directed)graph H is equivalent to the problem CSP(H∗)where H∗equals H together with all unary relations.•It is conjectured that the list homomorphism problem for a reflexive digraph is tractable if H has the X-underbar property(which is the same as having the bi-nary polymorphism min w.r.t.some total ordering on the set of vertices),and NP-complete otherwise.•It is conjectured that the list homomorphism problem for an irreflexive digraph is tractable if H is preserved by a majority operation,and NP-complete otherwise. Do these conjectures hold?Communicated by:Tomas Feder&Pavol Hell5Question5.2“An island of tractability?”Let A m be the class of all relational structures of the form(A,E1,...,E m)where each E i is an irreflexive symmetric binary relation and the relations E i together satisfy the following‘fullness’condition:any two distinct elements x,y are related in exactly one of the relations E i.Let B m be the single relational structure({1,...,m},E1,...,E m)where each E i is the symmetric binary relation containing all pairs xy except the pair ii.(Note that the relations E i are not irreflexive.)The problem CSP(A m,B m)is defined as:Given A∈A m,is there a homomorphism from A to B m?When m=2,this problem is solvable in polynomial time-it is the recognition problem for split graphs(see“Algorithmic Graph Theory and Perfect Graphs”,M.C.Golumbic, Academic Press,New York,1980)When m>3,this problem is NP-complete(see“Full constraint satisfaction problems”,T.Feder and P.Hell,to appear in SIAM Journal on Computing).What happens when m=3?Is this an“island of tractability”?Quasi-polynomial algorithms are known for this problem(see“Full constraint satisfaction problems”,T. Feder and P.Hell,,to appear in SIAM Journal on Computing,and“Two algorithms for list matrix partitions”,T.Feder,P.Hell,D.Kral,and J.Sgall,SODA2005).Note that a similar problem for m=3was investigated in“The list partition problem for graphs”, K.Cameron,E.E.Eschen,C.T.Hoang and R.Sritharan,SODA2004.Communicated by:Tomas Feder&Pavol Hell Question5.3Finding the generalized hypertree-width,w(H)of a hypergraph H is known to be NP-complete.However it is possible to compute a hypertree-decomposition of H in polynomial time,and the hypertree-width of H is at most3w(H)+1(see talk by Georg Gottlob).Are there other decompositions giving better approximations of the generalized hypertree-width that can be found in polynomial time?Communicated by:Georg Gottlob Question5.4It is known that a CSP whose constraint hypergraph has bounded fractional hypertree width is tractable(see talk by Daniel Marx).Is there a hypergraph property more general than bounded fractional hypertree width that makes the associated CSP polynomial-time solvable?Are there classes of CSP that are tractable due to structural restrictions and have unbounded fractional hypertree width?Communicated by:Georg Gottlob,Daniel Marx Question5.5Prove that there exist two functions f1(w),f2(w)such that,for every w, there is an algorithm that constructs in time n f1(w)a fractional hypertree decomposition of width at most f2(w)for any hypergraph of fractional hypertree width at most w(See talk by Daniel Marx).Communicated by:Daniel Marx6Question5.6Turn the connection between the Robber and Army game and fractional hypertree width into an algorithm for approximating fractional hypertree width.Communicated by:Daniel Marx Question5.7Close the complexity gap between(H,C,K)-colouring and (H,C,K)-colouring (see talk by Dimitrios Thilikos)Find a tight characterization for thefixed-parameter tractable(H,C,K)-colouring problems.•For the(H,C,K)-colouring problems,find nice properties for the non-parameterisedpart(H−C)that guaranteefixed-parameter tractability.•Clarify the role of loops in the parameterised part C forfixed-parameter hardnessresults.Communicated by:Dimitrios Thilikos6Constraint Programming and ModellingQuestion6.1In a constraint programming system there is usually a search procedure that assigns values to particular variables in some order,interspersed with a constraint propagation process which modifies the constraints in the light of these assignments.Is it possible to choose an ordering for the variables and values assigned which changes each problem instance as soon as possible into a new instance which is in a tractable class? Can this be done efficiently?Are there useful heuristics?Question6.2The time taken by a constraint programming system tofind a solution toa given instance can be dramatically altered by modelling the problem differently.Can the efficiency of different constraint models be objectively compared,or does it depend entirely on the solution algorithm?Question6.3For practical constraint solving it is important to eliminate symmetry,in order to avoid wasted search effort.Under what conditions is it tractable to detect the symmetry in a given problem in-stance?7Notes•Representations of constraints-implicit representation-effect on complexity•Unique games conjecture-structural restrictions that make it false-connectionsbetween definability and approximation•MMSNP-characterise tractable problems apart from CSP7•Migrate theoretical results to tools•What restrictions do practical problems actually satisfy?•Practical parallel algorithms-does this align with tractable classes?•Practically relevant constraint languages(”global constraints”)•For what kinds of problems do constraint algorithms/heuristics give good results?8。

Module:Introduction(Week2out of5)Course:Algorithmic Toolbox(Course1out of6)Specialization:Data Structures and Algorithms Programming Assignment1:IntroductionRevision:September10,2016IntroductionWelcome to your first programming assignment of the Algorithmic Toolbox class!It consists of seven algorithmic problems.The first three problems require you just to implement carefully the algorithms covered in the lectures.The remaining four problems will require you to first design an algorithm and then to implement it.For all the problems,we provide starter solutions in C++,Java,and Python3.These solutions implement straightforward naive algorithms that usually work only for small inputs.To verify this, you may want to submit these solutions to the grader.This will usually give you a“time limit exceeded”message for Python starter files and either“time limit exceeded”or“wrong answer”message for C++and Java solutions(the reason for wrong answer being an integer overflow issue).Your goal is to replace a naive algorithm with an efficient one.In particular,you may want to use the naive implementation for stress testing your efficient implementation.In this programming assignment,the grader will show you the input data if your solution fails on any of the tests.This is done to help you to get used to the algorithmic problems in general and get some experience debugging your programs while knowing exactly on which tests they fail.However,for all the following programming assignments,the grader will show the input data only in case your solution fails on one of the first few tests(please review the questions9.4and9.5in the FAQ section for a more detailed explanation of this behavior of the grader).1Learning OutcomesUpon completing this programming assignment you will be able to:1.See the huge difference between a slow algorithm and a fast one.2.Play with examples where knowing something interesting about a problem helps to design an algorithmthat is much faster than a naive one.3.Implement solutions that work much more faster than straightforward solutions for the following com-putational problems:(a)compute a small Fibonacci number;(b)compute the last digit of a large Fibonacci number;(c)compute a huge Fibonacci number modulo m;(d)compute the last digit of a sum of Fibonacci numbers;(e)compute the last digit of a partial sum of Fibonacci numbers;(f)compute the greatest common divisor of two integers;(g)compute the least common multiple of two integers.4.Implement the algorithms covered in the lectures,design new algorithms.5.Practice implementing,testing,and debugging your solution.In particular,you will find out how inpractice,when you implement an algorithm,you bump into unexpected questions and problems not covered by the general description of the algorithm.You will also check your understanding of the algorithm itself and most probably see that there are some aspects you did not think of before you had to actually implement it.You will overcome all those complexities,implement the algorithms,test them,debug,and submit to the system.Remember the advice(link)we gave you in the first module about testing your programs and feel free to return to those videos or parts of them again while working on your assignment.In the end of this document you will find also general recommendations on solving algorithmic problems.Passing Criteria:3out of7Passing this programming assignment requires passing at least3out of7code problems from this assignment. In turn,passing a code problem requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.2Contents1Problem:Small Fibonacci Number4 2Problem:Last Digit of a Large Fibonacci Number6 3Problem:Greatest Common Divisor8 4Problem:Least Common Multiple10 5Advanced Problem:Huge Fibonacci Number modulo m12 6Advanced Problem:Sum of Fibonacci Numbers14 7Advanced Problem:Partial Sum of Fibonacci Numbers16 8General Instructions and Recommendations on Solving Algorithmic Problems188.1Reading the Problem Statement (18)8.2Designing an Algorithm (18)8.3Implementing Your Algorithm (18)8.4Compiling Your Program (18)8.5Testing Your Program (20)8.6Submitting Your Program to the Grading System (20)8.7Debugging and Stress Testing Your Program (20)9Frequently Asked Questions219.1I submit the program,but nothing happens.Why? (21)9.2I submit the solution only for one problem,but all the problems in the assignment are graded.Why? (21)9.3What are the possible grading outcomes,and how to read them? (21)9.4How to understand why my program fails and to fix it? (22)9.5Why do you hide the test on which my program fails? (22)9.6My solution does not pass the tests?May I post it in the forum and ask for a help? (23)9.7My implementation always fails in the grader,though I already tested and stress tested it alot.Would not it be better if you give me a solution to this problem or at least the test casesthat you use?I will then be able to fix my code and will learn how to avoid making mistakes.Otherwise,I do not feel that I learn anything from solving this problem.I am just stuck (23)31Problem:Small Fibonacci NumberProblem IntroductionRecall the definition of Fibonacci sequence:F0=0,F1=1,and F i=F i−1+F i−2fori≥2.Your goal in this problem is to implement an efficient algorithm for computingFibonacci numbers.The starter files for this problem contain an implementationof the following naive recursive algorithm for computing Fibonacci numbers in C++,Java,and Python3:Fibonacci(n):if n≤1:return nreturn Fibonacci(n−1)+Fibonacci(n−2)Try compiling and running a starter solution on your machine.You will see that computing,say,F40already takes noticeable time.Another way to appreciate the dramatic difference between an exponential time al-gorithm and a polynomial time algorithm is to use the following visualization byDavid Galles:/~galles/visualization/DPFib.html.Try computing F20by a recursive algorithm by entering“20”and pressing the“Fi-bonacci Recursive”button.You will see an endless number of recursive calls.Now,press“Skip Forward”to stop the current algorithm and call the iterative algorithmby pressing“Fibonacci Table”.This will compute F20very quickly.(Note that the visualization uses a slightly different definition of Fibonacci numbers:F0=1insteadof F0=0.This of course has almost no influence on the running time.)Problem DescriptionTask.Given an integer n,find the n th Fibonacci number F n.Input Format.The input consists of a single integer n.Constraints.0≤n≤45.Output Format.Output F n.Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scala time in seconds11 1.55 1.52553 Memory Limit.512MB.Sample1.Input:3Output:2Explanation:F3=2.4Sample2.Input:10Output:55Explanation:F10=55.Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: fibonacciNeed Help?Ask a question or see the questions asked by other learners at this forum thread.52Problem:Last Digit of a Large Fibonacci NumberProblem IntroductionYour goal in this problem is to find the last digit of n-th Fibonacci number.Recall that Fibonacci numbers grow exponentially fast.For example,F200=280571172992510140037611932413038677189525.Therefore,a solution likeF[0]←0F[1]←1for i from2to n:F[i]←F[i−1]+F[i−2]print(F[n]mod10)will turn out to be too slow,because as i grows the i th iteration of the loop computes the sum of longer and longer numbers.Also,for example,F1000does not fit into the standard C++int type.To overcome this difficulty,you may want to store in F[i]not the i th Fibonacci number itself,but just its last digit(that is,F i mod10).Computing the last digit of F i is easy:it is just the last digit of the sum of the last digits of F i−1and F i−2:F[i]←(F[i−1]+F[i−2])mod10This way,all F[i]’s are just digits,so they fit perfectly into any standard integer type,and computing a sum of F[i−1]and F[i−2]is performed very quickly.Problem DescriptionTask.Given an integer n,find the last digit of the n th Fibonacci number F n(that is,F n mod10).Input Format.The input consists of a single integer n.Constraints.0≤n≤107.Output Format.Output the last digit of F n.Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scalatime in seconds11 1.55 1.52553Memory Limit.512MB.Sample1.Input:3Output:2Explanation:F3=2.6Sample2.Input:331Output:9Explanation:F331=668996615388005031531000081241745415306766517246774551964595292186469. Sample3.Input:327305Output:5Explanation:F327305does not fit into one line of this pdf,but its last digit is equal to5.Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: fibonacci_last_digitNeed Help?Ask a question or see the questions asked by other learners at this forum thread.73Problem:Greatest Common Divisor Problem IntroductionThe greatest common divisor GCD(a,b)of two non-negative integers a and b (which are not both equal to0)is the greatest integer d that divides both a and b. Your goal in this problem is to implement the Euclidean algorithm for computing the greatest common divisor.Efficient algorithm for computing the greatest common divisor is an important basic primitive of commonly used cryptographic algorithms like RSA.GCD(1344,217) =GCD(217,42) =GCD(42,7)=GCD(7,0)=7Problem DescriptionTask.Given two integers a and b,find their greatest common divisor.Input Format.The two integers a,b are given in the same line separated by space.Constraints.1≤a,b≤2·109.Output Format.Output GCD(a,b).Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scalatime in seconds11 1.55 1.52553Memory Limit.512MB.Sample1.Input:1835Output:1Explanation:18and35do not have common non-trivial divisors.Sample2.Input:288515381183019Output:17657Explanation:28851538=17657·1634,1183019=17657·67.Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: gcdWhat To DoTo solve this problem,it is enough to implement carefully the corresponding algorithm covered in the lectures.8Need Help?Ask a question or see the questions asked by other learners at this forum thread.94Problem:Least Common MultipleProblem IntroductionThe least common multiple of two positive integers a and b is the least positiveinteger m that is divisible by both a and b.Problem DescriptionTask.Given two integers a and b,find their least common multiple.Input Format.The two integers a and b are given in the same line separated by space.Constraints.1≤a,b≤2·109.Output Format.Output the least common multiple of a and b.Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scalatime in seconds11 1.55 1.52553Memory Limit.512MB.Sample1.Input:68Output:24Explanation:Among all the positive integers that are divisible by both6and8(e.g.,48,480,24),24is the smallest one.Sample2.Input:288515381183019Output:1933053046Explanation:1933053046is the smallest positive integer divisible by both28851538and1183019.Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: lcm10What To DoPlay with small datasets to find out how the least common multiple LCM(a,b)is related to the greatest common divisor GCD(a,b).Do you see?For any two positive integers a and b,LCM(a,b)·GCD(a,b)=a·b. Prove this property and implement an algorithm for computing the least common multiple using your solution for the greatest common divisor.Need Help?Ask a question or see the questions asked by other learners at this forum thread.115Advanced Problem:Huge Fibonacci Number modulo mWe strongly recommend you start solving advanced problems only when you are done with the basic problems (for some advanced problems,algorithms are not covered in the video lectures and require additional ideas to be solved;for some other advanced problems,algorithms are covered in the lectures,but implementing them is a more challenging task than for other problems).Problem IntroductionIn this problem,your goal is to compute F n modulo m,where n may be really huge:up to1018.For such values of n,an algorithm looping for n iterations will not fit into one second for sure.Therefore we need to avoid such a loop.To get an idea how to solve this problem without going through all F i for i from0to n,let’s see what happens when m is small—say,m=2or m=3.i0123456789101112131415F i01123581321345589144233377610F i mod20110110110110110F i mod30112022101120221Take a detailed look at this table.Do you see?Both these sequences are periodic!For m=2,the period is011and has length3,while for m=3the period is01120221and has length8.Therefore,to compute, say,F2015mod3we just need to find the remainder of2015when divided by8.Since2015=251·8+7,we conclude that F2015mod3=F7mod3=1.This is true in general:for any integer m≥2,the sequence F n mod m is periodic.The period always starts with01and is known as Pisano period.Problem DescriptionTask.Given two integers n and m,output F n mod m(that is,the remainder of F n when divided by m). Input Format.The input consists of two integers n and m given on the same line(separated by a space). Constraints.1≤n≤1018,2≤m≤105.Output Format.Output F n mod m.Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scalatime in seconds11 1.55 1.52553Memory Limit.512MB.Sample1.Input:1239Output:1Explanation:F1mod239=1mod239=1.12Sample2.Input:2391000Output:161Explanation:F239mod1000=39679027332006820581608740953902289877834488152161(mod1000)=161. Sample3.Input:281621358830524Output:10249Explanation:F2816213588does not fit into one page of this file,but F2816213588mod30524=10249.Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: fibonacci_hugeNeed Help?Ask a question or see the questions asked by other learners at this forum thread.136Advanced Problem:Sum of Fibonacci NumbersWe strongly recommend you start solving advanced problems only when you are done with the basic problems (for some advanced problems,algorithms are not covered in the video lectures and require additional ideas to be solved;for some other advanced problems,algorithms are covered in the lectures,but implementing them is a more challenging task than for other problems).Problem IntroductionThe goal in this problem is to find the last digit of a sum of the first n Fibonacci numbers.Problem DescriptionTask.Given an integer n,find the last digit of the sum F0+F1+···+F n.Input Format.The input consists of a single integer n.Constraints.0≤n≤1014.Output Format.Output the last digit of F0+F1+···+F n.Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scalatime in seconds11 1.55 1.52553Memory Limit.512MB.Sample1.Input:3Output:4Explanation:F0+F1+F2+F3=0+1+1+2=4.Sample2.Input:100Output:5Explanation:The sum is equal to927372692193078999175,the last digit is5.Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: fibonacci_sum_last_digitWhat To DoInstead of computing this sum in a loop,try to come up with a formula for this sum.For this,play with small values of n.Then,use a solution for the previous problem.14Need Help?Ask a question or see the questions asked by other learners at this forum thread.157Advanced Problem:Partial Sum of Fibonacci NumbersWe strongly recommend you start solving advanced problems only when you are done with the basic problems (for some advanced problems,algorithms are not covered in the video lectures and require additional ideas to be solved;for some other advanced problems,algorithms are covered in the lectures,but implementing them is a more challenging task than for other problems).Problem IntroductionNow,we would like to find the last digit of a partial sum of Fibonacci numbers:F m+F m+1+···+F n.Problem DescriptionTask.Given two non-negative integers m and n,where m≤n,find the last digit of the sum F m+F m+1+···+F n.Input Format.The input consists of two non-negative integers m and n separated by a space. Constraints.0≤m≤n≤1018.Output Format.Output the last digit of F m+F m+1+···+F n.Time Limits.language C C++Java Python C#Haskell JavaScript Ruby Scalatime in seconds11 1.55 1.52553Memory Limit.512MB.Sample1.Input:37Output:1Explanation:F3+F4+F5+F6+F7=2+3+5+8+13=31.Sample2.Input:1010Output:5Explanation:F10=55.Sample3.Input:10200Output:2Explanation:F10+F11+···+F200=73454486715781809323490890211044929642326216Starter FilesThe starter files for this problem contain an implementation of a naive algorithm for the problem in C++, Java,and Python3.For these programming languages,your goal is to replace the naive algorithm with an efficient one.For other programming languages,you need to implement a solution from scratch.Filename: fibonacci_partial_sumWhat To DoUse a solution for the previous problem to solve this problem.Need Help?Ask a question or see the questions asked by other learners at this forum thread.178General Instructions and Recommendations on Solving Algorith-mic ProblemsYour main goal in an algorithmic problem is to implement a program that solves a given computational problem in just few seconds even on massive datasets.Your program should read a dataset from the standard input and write an answer to the standard output.Below we provide general instructions and recommendations on solving such problems.Before reading them,go through readings and screencasts in the first module that show a step by step process of solving two algorithmic problems:link.8.1Reading the Problem StatementYou start by reading the problem statement that contains the description of a particular computational task as well as time and memory limits your solution should fit in,and one or two sample tests.In some problems your goal is just to implement carefully an algorithm covered in the lectures,while in some other problems you first need to come up with an algorithm yourself.8.2Designing an AlgorithmIf your goal is to design an algorithm yourself,one of the things it is important to realize is the expected running time of your ually,you can guess it from the problem statement(specifically,from the subsection called constraints)as follows.Modern computers perform roughly108–109operations per second.So,if the maximum size of a dataset in the problem description is n=105,then most probably an algorithm with quadratic running time is not going to fit into time limit(since for n=105,n2=1010)while a solution with running time O(n log n)will fit.However,an O(n2)solution will fit if n is up to103=1000, and if n is at most100,even O(n3)solutions will fit.In some cases,the problem is so hard that we do not know a polynomial solution.But for n up to18,a solution with O(2n n2)running time will probably fit into the time limit.To design an algorithm with the expected running time,you will of course need to use the ideas covered in the lectures.Also,make sure to carefully go through sample tests in the problem description.8.3Implementing Your AlgorithmWhen you have an algorithm in mind,you start implementing it.Currently,you can use the following programming languages to implement a solution to a problem:C,C++,C#,Haskell,Java,JavaScript, Python2,Python3,Ruby,Scala.For all problems,we will be providing starter solutions for C++,Java,and Python3.If you are going to use one of these programming languages,use these starter files.For other programming languages,you need to implement a solution from scratch.8.4Compiling Your ProgramFor solving programming assignments,you can use any of the following programming languages:C,C++, C#,Haskell,Java,JavaScript,Python2,Python3,Ruby,and Scala.However,we will only be providing starter solution files for C++,Java,and Python3.The programming language of your submission is detected automatically,based on the extension of your submission.We have reference solutions in C++,Java and Python3which solve the problem correctly under the given restrictions,and in most cases spend at most1/3of the time limit and at most1/2of the memory limit. You can also use other languages,and we’ve estimated the time limit multipliers for them,however,we have no guarantee that a correct solution for a particular problem running under the given time and memory constraints exists in any of those other languages.Your solution will be compiled as follows.We recommend that when testing your solution locally,you use the same compiler flags for compiling.This will increase the chances that your program behaves in the18same way on your machine and on the testing machine(note that a buggy program may behave differently when compiled by different compilers,or even by the same compiler with different flags).∙C(gcc5.2.1).File extensions:.c.Flags:gcc-pipe-O2-std=c11<filename>-lm∙C++(g++5.2.1).File extensions:.cc,.cpp.Flags:g++-pipe-O2-std=c++14<filename>-lmIf your C/C++compiler does not recognize-std=c++14flag,try replacing it with-std=c++0x flag or compiling without this flag at all(all starter solutions can be compiled without it).On Linux and MacOS,you most probably have the required compiler.On Windows,you may use your favorite compiler or install,e.g.,cygwin.∙C#(mono3.2.8).File extensions:.cs.Flags:mcs∙Haskell(ghc7.8.4).File extensions:.hs.Flags:ghc-O∙Java(Open JDK8).File extensions:.java.Flags:javac-encoding UTF-8java-Xmx1024m∙JavaScript(Node v6.3.0).File extensions:.js.Flags:nodejs∙Python2(CPython2.7).File extensions:.py2or.py(a file ending in.py needs to have a first line which is a comment containing“python2”).No flags:python2∙Python3(CPython3.4).File extensions:.py3or.py(a file ending in.py needs to have a first line which is a comment containing“python3”).No flags:python3∙Ruby(Ruby2.1.5).File extensions:.rb.ruby∙Scala(Scala2.11.6).File extensions:.scala.scalac198.5Testing Your ProgramWhen your program is ready,you start testing it.It makes sense to start with small datasets—for example, sample tests provided in the problem description.Ensure that your program produces a correct result.You then proceed to checking how long does it take your program to process a massive dataset.For this,it makes sense to implement your algorithm as a function like solve(dataset)and then implement an additional procedure generate()that produces a large dataset.For example,if an input to a problem is a sequence of integers of length1≤n≤105,then generate a sequence of length exactly105,pass it to your solve()function,and ensure that the program outputs the result quickly.Also,check the boundary values.Ensure that your program processes correctly sequences of size n= 1,2,105.If a sequence of integers from0to,say,106is given as an input,check how your program behaves when it is given a sequence0,0,...,0or a sequence106,106,...,106.Check also on randomly generated data.For each such test check that you program produces a correct result(or at least a reasonably looking result).In the end,we encourage you to stress test your program to make sure it passes in the system at the first attempt.See the readings and screencasts from the first week to learn about testing and stress testing:link.8.6Submitting Your Program to the Grading SystemWhen you are done with testing,you submit your program to the grading system.For this,you go the submission page,create a new submission,and upload a file with your program.The grading system then compiles your program(detecting the programming language based on your file extension,see Subsection8.4) and runs it on a set of carefully constructed tests to check that your program always outputs a correct result and that it always fits into the given time and memory limits.The grading usually takes no more than a minute,but in rare cases when the servers are overloaded it might take longer.Please be patient.You can safely leave the page when your solution is uploaded.As a result,you get a feedback message from the grading system.The feedback message that you will love to see is:Good job!This means that your program has passed all the tests.On the other hand, the three messages Wrong answer,Time limit exceeded,Memory limit exceeded notify you that your program failed due to one these three reasons.Note that the grader will not show you the actual test you program have failed on(though it does show you the test if your program have failed on one of the first few tests;this is done to help you to get the input/output format right).8.7Debugging and Stress Testing Your ProgramIf your program failed,you will need to debug it.Most probably,you didn’t follow some of our suggestions from the section8.5.See the readings and screencasts from the first week to learn about debugging your program:link.You are almost guaranteed to find a bug in your program using stress testing,because the way these programming assignments and tests for them are prepared follows the same process:small manual tests, tests for edge cases,tests for large numbers and integer overflow,big tests for time limit and memory limit checking,random test generation.Also,implementation of wrong solutions which we expect to see and stress testing against them to add tests specifically against those wrong solutions.Go ahead,and we hope you pass the assignment soon!20。