CSCI 3110语言编程辅导、写作

” CSCI 3110语言编程辅导、写作Lecture Notes for CSCI 3110:Design and Analysis of AlgorithmsTravis GagieFaculty of Computer ScienceDalhousie UniversitySummer 2021 /brContents1 Clink versus BOOM 3I Divide and Conquer 82 Colouring Graphs 9Assignment 1 19Solution 213 Euclid, Karatsuba, Strassen 244 Fast Fourier Transform 32Assignment 2 37Solutions 395 Asymptotic Bounds 446 Sorting 51Assignment 3 59Solutions 611II Greedy Algorithms 627 Huffman Coding 638 Minimum Spanning Trees 749 More Greedy Algorithms 82Assignment 4 91Midterm 1 93Solutions 95III Dynamic Programming 9810 Edit Distance 9911 Subset Sum and Knapsack 10712 Optimal Binary Search Trees and Longest Increasing Subsequences 113Assignment 5 1202Chapter 1Clink versus BOOMImagine Im standing in front of you holding up two little pieces of silver-grey metal and betweenus is a bucket of water. You Can see the pieces of metal look pretty much the same; I tap themon the desk so you can tell they sound about the same; I pass them around so you can check theyfeel about the same, weigh about the same, smell the same (not really at all), although I warn younot to taste them. I take them back and throw first one into the bucket, where it goes clink, andthen the other, where it goes BOOM.Even if we had in-person classes I probably wouldnt be allowed to explode things in front ofmy students thats what tenure is for! but I want you to think about how two things thatseem the same can behave so Differently. Explaining that for those two little pieces of metal gets usinto discussions that get pretty deep pretty quickly, of chemical reactions and molecules and atoms.The famous physicist Richard Feynman said that if some disaster were going to wipe out nearly allscientific knowledge and he could choose once sentence to pass on to future generations, it would beall things are made of atoms. Other scientists might choose deep statements from their own fieldsthat have changed humanitys view of the universe and our place in it: for an astronomer, theearth goes around the sun; for a biologist, species arise through a process of natural selection;for a psychologist, the mind is a function of the brain. Statements about mathematics usuallyarent quite so controversial, at least among non-mathematicians, but the story goes that the firstmathematician to prove that the square root of 2 is irrational was thrown overboard by his fellowPythagoreans.So, what have we got? Youve been studying computer science in university for a few yearsnow, and Id like to know what youve learned about our field that can reasonably be consideredone of the great scientific truths. The speed of processors doubles every 18 months? Addingworkers to a late software project makes it later? All your bases are belong to us? The cakeis a lie? This is when Id really like to be able to stop and let you think, and then hear whatyou have to say. Under the circumstances, however, Im just going to have to assume most of youchose to study computer science because its fun, you can do cool things with it (including savingpeoples lives and making the world a better place), it pays pretty well and its indoor work withno heavy lifting even though it may not tell us deep things about the universe.3Thats rather a shame. If you check Scientific Americans list of 100 or so Books that Shaped aCentury of Science, under Physical Sciences and mixed in with Stephen Hawkings A Brief His-tory of Time, Primo Levis The Periodic Table, Carl Sagans The Pale Blue Dot, Paul Diracs Quan-tum Mechanics, The Collected Papers of Albert Einstein, Linus Paulings Nature of the ChemicalBond and Feynmans QED, youll find books about computer science (or things close to it): BenoitMandelbrots Fractals, Norbert Weiners Cybernetics and, last but definitely not least, Knuths Artof Computer Programming. So apparently we are doing deep things, were just not teaching youabout them.Actually, I think that in a very important sense, we are the deepest of the sciences. To under-stand where the basic rules of psychology come from, for example, you must know something aboutbiology; to understand where the basic rules of biology come from, you must know something aboutchemistry; to understand where the Basic rules of chemistry come from, you must know somethingabout physics; to understand where the basic rules of physics come from, you must know some-thing about mathematics; but who tells the mathematicians what they can and cannot do? We do.Philosophers, theologians and politicians might claim to, but I think the mathematicians largelyignore them. One field has really stood up to mathematics and laid down the law, and that fieldwas computer science.At the International Congress of Mathematicians in 1900, a famous mathematician namedDavid Hilbert proposed ten problems that he thought mathematicians should work on in the 20thcentury. He later expanded the list to 23 problems, which were published in 1902 in the Bulletin ofthe American Mathematical Society. Lets talk about Hilberts Tenth Problem (for the integers): todevise a process according to which it can be determined in a finite number of operations whether[a given Diophantine equation with integer coefficients] is solvable in [the integers]. Notice Hilbertdidnt ask whether such a process existed; back then, people assumed that if a mathematicalstatement were true, with enough effort they should be able to prove it.Ill assume you all know what a quadratic equation in one variable is, and that you can tell ifone has a solution in the reals using the quadratic formula. There are similar but more complicatedformulas for solving cubic and quartic equations in one variable, which fortunately I never learned.If youre given a quintic equation in one variable with integer coefficients, then you may be ableto use the rational-root theorem (which I actually did learn once upon a time!) to get it down toa quartic, which you can then solve with the quartic formulas. (For anything more complicated,maybe you can try Galois Theory, but I cant help you there.) Anyway, the Diophantine equationsHilbert was talking about are sort of like these equations but with a finite number of variables. Hewanted a way to solve any given Diophantine equation that has integer coefficients or, at least, away to tell if it even has an integer solution.So, solving Diophantine equations over the integers was considered an important mathematicsproblem by important mathematicians. Unfortunately for them, in 1970 Yuri Matiyasevich showedin his doctoral thesis that we Can take a certain general model of a computer, called a TuringMachine, and encode it as a Diophantine equation with integer coefficients, in such a way that theTuring Machine halts if and only if the Diophantine equation has an integer solution. It was alreadyknown that determining whether a Turing Machine halts is generally incomputable, meaning thereis no algorithm for it (and that had already thrown a spanner in Hilberts plan for 20th-centurymathematics), so Matiyasevichs Theorem (also known as a Matiyasevich-Robinson-Davis-Putnam4Figure 1.1: The seven bridges of Konigsberg in Eulers time ( httpss://commons.wikimedia.org/wiki/File:Konigsberg_bridges.png).Theorem, for some other mathematicians who laid the groundwork) says Hilberts Tenth Problemis impossible (for the integers). So, computer science told mathematics that it couldnt havesomething it really wanted.I guess 1970 seems like a long time ago and we dont want to relive old victories so althoughwell talk a bit about Turing Machines and the Halting Problem and computability and HilbertsEntscheidungsproblem in this course mostly were not going to focus on the gap between possibleand impossible problems (and I wont mention Diophantine equations again). Instead, were goingto focus on the nature of the gap between easy problems (we have a polynomial-time solution thatruns on a standard computer) and hard problems (we dont) which is the deepest open questionin computer science and has been for a long time, since 1971. Echoing Hilbert, in 2000 the ClayMathematics Institute proposed a list of seven problems they thought mathematicians should workon in the 21st century, including this one of easy versus hard, and backed each with a million-dollar prize. To quickly illustrate the gap between easy and hard, Id like to talk about two classicproblems, determining whether a graph has an Eulerian cycle and whether it has a Hamiltoniancycle. At first these problems seem almost the same, but it turns out that one goes clink andthe other goes BOOM (we think).In the 1730s, the citizens of Konigsberg (then in Prussia, now the Russian city of Kaliningrad)wrote to the famous mathematician Leonhard Euler asking whether it was possible to start some-where in their city (shown as it existed then in Figure 1.1), walk around it in such a way as tocross each of their seven bridges once and only once, and arrive back at the starting point. Euleranswered that it was not possible since, if we draw a graph with each shore and island as a vertexand each bridge as an edge, all of the vertices have odd degree, where a vertexs degree is thenumber of edges incident to it. He observed that in such a walk now called an Eulerian cycle ofa graph every time we visit a vertex we reduce the number of uncrossed edges incident to it by2 (we arrive across one and leave across one); therefore, in order for a graph to have an Euleriancycle, it is a necessary condition that it be connected (that is, it must be possible to get from anyvertex to any other vertex) and every vertex must have even degree.Euler also showed that this is also a sufficient condition, which is less obvious. Suppose westart at some vertex v in a graph G that satisfies the condition, and walk around until we get stuck5(that is, we arrive at a vertex All of whose incident edges weve already crossed). Where can we getstuck? Well, when were at a vertex w 6= v then well have crossed off an odd number of edgesincident to w (one for each time weve arrived there and one for each time weve left, and wevearrived once more often than weve left); therefore, since an even number minus an odd numberis an odd number and 0 isnt odd, theres always at least one edge left for us to leave across. Itfollows that we can only get stuck back at v, after tracing out a cycle C in G.Let G be the graph resulting from deleting from G the edges in C. If v has positive degree inG then we can start there again and find and delete another cycle; otherwise, if some other vertexhas positive degree in G, we can start there and find and delete another cycle. If we keep doingthis until there are no edges left, we get a decomposition of G into edge-disjoint cycles (meaningthe cycles can share vertices but not edges). Take any of the cycles C1, choose a vertex v it shareswith any of the other cycles, and choose another cycle C2 containing v. (If C1 doesnt share anyvertices with any other cycles, then its vertices arent connected to the rest of the graph, contraryto our assumption.) Replace C1 and C2 by a single (non-simple) cycle C3 that makes a figure 8 insome sense: if we start at v then we first cross all the edges in C1 and return to v, then cross allthe edges in C2 and return to v. Repeating this cycle-merging, we eventually obtain an Euleriancycle of the graph.Its not totally trivial to implement this algorithm cleanly but its not all that hard either (soI gave it as a homework exercise last year) and it obviously takes only polynomial time in the sizeof the graph. In other words, the problem of determining whether a graph is Eulerian (contains anEulerian cycle) goes clink. Its actually an important problem that comes up in de novo genomeassembly: one of the most common ways to assemble DNA reads is by building whats called ade Bruijn graph of the k-mers they contain, for some appropriate value of k, and then trying tofind an Eulerian tour of that graph (tour instead of cycle because it need not end where itstarted). Its likely, for example, that this played a role in sequencing the Covid genome, whichwas important for developing a test for whether people were infected. Now lets consider a problemwhich seems deceptively similar at first.In 1857 William Rowan Hamilton Showed how to walk along the edges of a dodecahedron,visiting each vertex once and only once, until arriving back at the starting point. Such a walk ina graph is now called a Hamiltonian cycle, and its an obvious counterpart to an Eulerian cyclebut focusing on visiting vertices instead crossing edges. Hamilton didnt give a general result likeEulers, however, and in fact no one has ever found an efficient algorithm for determining whether agiven graph is Hamiltonian (that is, it has a Hamiltonian cycle). By efficient, in computer sciencewe mean that the algorithm takes time polynomial in the size of the graph (in this case, the sum ofthe number of vertices and the number of edges). Obviously there are necessary conditions we cancheck quickly (for example, the graph has to be connected), and there are sufficient conditions wecan check quickly (for example, if a graph is a clique then its Hamiltonian, meaning it contains aHamiltonian cycle), and there are some kinds of graphs that are easy (for example, cycles or trees),and some graphs are small enough that we can deal with them by brute force. . . but nobodys everfound an algorithm that can handle all graphs in polynomial time. In other words, it seems thisproblem goes BOOM.To see why people would really like to be able to determine whether a graph is Hamiltonian,suppose youre in charge of logistics for a delivery company and youre looking at a map trying to6plan the route of a delivery truck that has to visit n cities, in any order and then return home. Youcan tell the distance between each pair of cities and you want to know if its possible for the truckto make its deliveries while travelling at most a certain total distance. (This problem is called theTravelling Salesperson Problem or TSP or, assuming the truck travels only in the plane,Euclidian TSP; computer scientists often use Small Caps for tricky problems.) If every roadbetween two cities has distance 1, then the truck can travel distance n if and only if the graph withcities as vertices and roads as edges, is Hamiltonian. It follows that if HamCycle (the problem ofdetermining whether a graph is Hamiltonian) goes BOOM, then TSP goes BOOM too. Thatis, if HamCycle is hard, then so is TSP, because in some sense HamCycle can be turned intoTSP. Dont worry, well see a lot more about this later in the course.How can two problems determining if a graph is Eulerian and if its Hamiltonian thatseem so similar be so different? Well, we hope investigating that will lead us to a deep truth, likeinvestigating the reactions of those pieces of metal to water could lead us to studying atoms. Wemay not even really care as much about the problems themselves as we do about what studyingthem can tell us: my chemistry teacher might forgive me if I forgot that sodium metal explodes inwater, but hed be really annoyed if I forgot the atomic theory; similarly, you may pass this courseeven if you forget Eulers algorithm, but I really do want you to remember something about thedifference between easy and hard problems.Another way of saying this is that you shouldnt miss the forest for the trees. Think of EulersAlgorithm as a tree and HamCycle as a tree and yourself as a student of geography: youre notreally interested in individual Trees as much as youre interested in the general layout of the forestand, metaphorically, whether theres a big river splitting it into two pieces. In the next class,well talk about another classic problem, colouring graphs, some versions of which (1-colourability,2-colourability, planar k-colourability for k 4) are easy and some versions of which (planar 3-colourability, general k-colourability for k 3) are thought to be hard. Does anyone really careabout 47-colourability in particular, say? Probably not, but by the end of this course you shouldunderstand that its on the same side of the river as HamCycle and TSP and planar 3-colourabilityand general k-colourability for any other k 3 (that is, the BOOM side, to mix metaphors), andon the opposite side from finding Eulerian cycles and 1- or 2-colourability (the clink side).Investigating the difference between the complexity of finding Eulerian and Hamiltonian cyclesand between 2-colouring and 3-colouring graphs also leads us to a shallow but important truthabout this course: its dangerous to answer questions just by pattern matching! That is, justbecause a problem sounds similar to something youve seen before, dont think you can just writethe answer to the old problem and get part marks.Summing up, here are some things to remember while taking this course:Computer science is the deepest of the sciences!Some problems are possible, some arent and thats deep.Some problems are easy, some probably arent and thats deep, too.Dont miss the forest for the trees.Its dangerous to answer questions just by pattern matching.7Part IDivide and Conquer8Chapter 2Colouring GraphsWhen I was in primary school geography was mainly about colouring maps, which I was prettygood at except that I kept loosing my pencil crayons, so my maps werent as colourful as the otherchildrens. I was therefore really impressed when I learned that in 1852 Francis Guthrie found away to colour a map of the counties of England (there were 39 back then) using only four colours,such that no two counties with the same colour share a border (although meeting at a point isok). This made him wonder if it was possible to 4-colour any (planar) map like this. He wrote tohis brother, who was studying With the mathematician De Morgan (who formulated De MorgansLaws of propositional logic, which you may have heard about last year), and the conjecture waspublished in The Athen?um magazine in 1854 and 1860. In 1890 Heawood proved any planar mapcan be 5-coloured, and in 1976 Appel and Haken finally proved the original conjecture by checking1834 cases with a computer.(An important (and very long) Part of the proof was checked manually by Hakens daughterDorothea, who taught me third-year algorithms at Queens 22 years later; shes also a coauthor ofthe Master Theorem that well discuss next week.)Appel and Hakens Four-Colour Theorem is considered part of graph theory, instead of geogra-phy, because if someone gives us a planar map and we draw a vertex in each region and put an edgebetween two vertices if and only if their regions share a border, then we get a planar graph thatcan be coloured with k colours such that no two vertices with the same colour share an edge, if andonly if the original map can be coloured with k colours. For example, Figure 2.1 shows the graphwe get for the map of the counties of Nova Scotia. (Actually, if we put an edge for every sharedborder so one edge between France and Spain for their border west of Andorra and another fortheir border east of it, for example then the graph and the map are duals, meaning that fromthe graph we can reconstruct Something thats topologically equivalent to the map, and from thatwe can reconstruct the graph, and so on.) Its easy to find planar graphs that require 4 colours,such as a 4-clique (a graph on four vertices with edges between every pair), but its not so easyto tell whether a given planar graph can be 3-coloured. In fact, as mentioned in the last lecture,thats a BOOM problem.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“