算法导论 第三版 第六章 答案 英

算法导论课程作业答案Introduction to AlgorithmsMassachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leiserson Handout10Diagnostic Test SolutionsProblem1Consider the following pseudocode:R OUTINE(n)1if n=12then return13else return n+R OUTINE(n?1)(a)Give a one-sentence description of what R OUTINE(n)does.(Remember,don’t guess.) Solution:The routine gives the sum from1to n.(b)Give a precondition for the routine to work correctly.Solution:The value n must be greater than0;otherwise,the routine loops forever.(c)Give a one-sentence description of a faster implementation of the same routine. Solution:Return the value n(n+1)/2.Problem2Give a short(1–2-sentence)description of each of the following data structures:(a)FIFO queueSolution:A dynamic set where the element removed is always the one that has been in the set for the longest time.(b)Priority queueSolution:A dynamic set where each element has anassociated priority value.The element removed is the element with the highest(or lowest)priority.(c)Hash tableSolution:A dynamic set where the location of an element is computed using a function of the ele ment’s key.Problem3UsingΘ-notation,describe the worst-case running time of the best algorithm that you know for each of the following:(a)Finding an element in a sorted array.Solution:Θ(log n)(b)Finding an element in a sorted linked-list.Solution:Θ(n)(c)Inserting an element in a sorted array,once the position is found.Solution:Θ(n)(d)Inserting an element in a sorted linked-list,once the position is found.Solution:Θ(1)Problem4Describe an algorithm that locates the?rst occurrence of the largest element in a?nite list of integers,where the integers are not necessarily distinct.What is the worst-case running time of your algorithm?Solution:Idea is as follows:go through list,keeping track of the largest element found so far and its index.Update whenever necessary.Running time isΘ(n).Problem5How does the height h of a balanced binary search tree relate to the number of nodes n in the tree? Solution:h=O(lg n) Problem 6Does an undirected graph with 5vertices,each of degree 3,exist?If so,draw such a graph.If not,explain why no such graph exists.Solution:No such graph exists by the Handshaking Lemma.Every edge adds 2to the sum of the degrees.Consequently,the sum of the degrees must be even.Problem 7It is known that if a solution to Problem A exists,then a solution to Problem B exists also.(a)Professor Goldbach has just produced a 1,000-page proof that Problem A is unsolvable.If his proof turns out to be valid,can we conclude that Problem B is also unsolvable?Answer yes or no (or don’t know).Solution:No(b)Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable.If the proof turns out to be valid,can we conclude that problem A is unsolvable as well?Answer yes or no (or don’t know).Solution:YesProblem 8Consider the following statement:If 5points are placed anywhere on or inside a unit square,then there must exist two that are no more than √2/2units apart.Here are two attempts to prove this statement.Proof (a):Place 4of the points on the vertices of the square;that way they are maximally sepa-rated from one another.The 5th point must then lie within √2/2units of one of the other points,since the furthest from the corners it can be is the center,which is exactly √2/2units fromeach of the four corners.Proof (b):Partition the square into 4squares,each with a side of 1/2unit.If any two points areon or inside one of these smaller squares,the distance between these two points will be at most √2/2units.Since there are 5points and only 4squares,at least two points must fall on or inside one of the smaller squares,giving a set of points that are no more than √2/2apart.Which of the proofs are correct:(a),(b),both,or neither (or don’t know)?Solution:(b)onlyProblem9Give an inductive proof of the following statement:For every natural number n>3,we have n!>2n.Solution:Base case:True for n=4.Inductive step:Assume n!>2n.Then,multiplying both sides by(n+1),we get(n+1)n!> (n+1)2n>2?2n=2n+1.Problem10We want to line up6out of10children.Which of the following expresses the number of possible line-ups?(Circle the right answer.)(a)10!/6!(b)10!/4!(c) 106(d) 104 ·6!(e)None of the above(f)Don’t knowSolution:(b),(d)are both correctProblem11A deck of52cards is shuf?ed thoroughly.What is the probability that the4aces are all next to each other?(Circle theright answer.)(a)4!49!/52!(b)1/52!(c)4!/52!(d)4!48!/52!(e)None of the above(f)Don’t knowSolution:(a)Problem12The weather forecaster says that the probability of rain on Saturday is25%and that the probability of rain on Sunday is25%.Consider the following statement:The probability of rain during the weekend is50%.Which of the following best describes the validity of this statement?(a)If the two events(rain on Sat/rain on Sun)are independent,then we can add up the twoprobabilities,and the statement is true.Without independence,we can’t tell.(b)True,whether the two events are independent or not.(c)If the events are independent,the statement is false,because the the probability of no rainduring the weekend is9/16.If they are not independent,we can’t tell.(d)False,no matter what.(e)None of the above.(f)Don’t know.Solution:(c)Problem13A player throws darts at a target.On each trial,independentlyof the other trials,he hits the bull’s-eye with probability1/4.How many times should he throw so that his probability is75%of hitting the bull’s-eye at least once?(a)3(b)4(c)5(d)75%can’t be achieved.(e)Don’t know.Solution:(c),assuming that we want the probability to be≥0.75,not necessarily exactly0.75.Problem14Let X be an indicator random variable.Which of the following statements are true?(Circle all that apply.)(a)Pr{X=0}=Pr{X=1}=1/2(b)Pr{X=1}=E[X](c)E[X]=E[X2](d)E[X]=(E[X])2Solution:(b)and(c)only。

do quite a few in-depth research projects.• She resisted the temptation to laugh.noun + verb• An opportunity arose for me to work in China, so I went and spent a year there.•People feel educational standards slipped when the government cut finances.noun + noun•James has been a team leader / member / player, and he is now able to enjoy the fruits of his hard work.•Their demanding work schedule means they have less time to devote to school assignments. adjective + noun•And they reported lower levels of commitment to school and more modest educational aspirations.•This is not an empty threat; I will call the police if this happens again!verb + adverb• She smiled proudly as she looked at the photos of her new grandson.•I don’t like to travel with my brother because he drives carelessly.adverb + verb• I fully understand that there will be serious problems when doing this project.•You may respectfully listen to their advice, but don’t take it too seriously.In this unit about working part-time while studying, we have come across quite a few useful grammatical collocations, mainly in the patterns of “adjective + noun” and “noun + noun”.Please take a look at the following list of collocations in this unit:Text Astudent achievement, school performance, school engagement, heavy commitment, academicyear, school achievement, school commitment, educational aspirations, school careers, working students, school assignments, non-working students Text Bhigher education, undergraduate student, wealthy students, educational performance, formal education, educational funding, educational benefits PART IIKEY TO EXERCISESSECTION A111) A teaching assistant in kindergarten or a tutor2) A cashier in a store3) A waiter in a restaurant4) A car cleaner2 • I would like to work as a teaching assistantin kindergarten. I really enjoy spending timewith small children and I am thinking ofworking as a teacher in kindergarten in thefuture. So working as a teaching assistantwould definitely be a great experience for me.• I would like to work in a company, whetherbig or small, because in the future I plan toestablish my own business. Working part-time in a company would give me some ideaof what it is like to work in a company, howa company is run, and what job a boss shoulddo.210 Third Edition2In my opinion, the most important advantages of doing part-time jobs are: gaining work experience, acquiring communicative skills, and building connections for future career. In doing part-time jobs, especially those jobs which are related to my field of study, I can build up my work experience and enrich my resume. Besides, in working, I may have to communicate with different kinds of people, soit can help develop my communicative skills, which are essential to success. And in getting to know some important people in the workplace, I can build some contacts for my future career.Understanding the text11To measure the impact of employment on student achievement.2According to the research, a heavy commitment to part-time work undermines and significantly interferes with school achievement andcommitment.3About 10 hours per week or less.4Students become interested in study again.5Students may take easier classes, copyothers’ assignments, cut class, or refuse todo assignments, and over time, students’commitment to school is eroded bit by bit.6Students may find school less rewarding and interesting, and it is highly possible that thosewho have been working long hours will dropout of school before graduation.7Because teenagers working long hours frequently have more money to spend than their peers,and they often become used to spending theirearnings on drugs and alcohol.8Doing part-time jobs while studying isacceptable, but students should work nomore than 10 hours a week if they want to besuccessful in school. Critical thinking21 • Yes, I think early employment can definitelybuild character because besides study,you have to fit yourself into the workingenvironment. You can learn interpersonalskills, social responsibility and professionalethics in a working setting. Moreover, youhave to try hard to strike a balance betweenwork, study, and play. In this way, you willdevelop a strong sense of responsibility andboost your self-confidence.• No, not necessarily. Though early employmentmay help students to gain some workexperience, it is not necessarily helpful inbuilding their character. Because they have tospend quite a lot of time working and maybecome less responsible or less committedto their study. Too much work may also leadto alcohol and drug abuse. So, in some cases,early employment undermines character-building rather than help it.2 • Yes, I agree. Students have so many academictasks to complete in college that they hardlyhave any extra time for work. If they work,they will certainly have to spend less time andenergy on study, which is likely to depresstheir school performance. I see many workingstudents around me sleep in class, skip class,or copy others’ assignments. If they cannotbe responsible students when they should be,how could they become responsible peopleafter graduation? So, I think students shouldtake study as their main task instead of doingpart-time jobs.• No, I don’t agree. College students shouldprepare themselves for future careers, so theyneed not only to perform well academicallybut also develop other skills becausesurviving in society requires more than bookknowledge. Working part-time can exposestudents to the real world and help themacquire basic interpersonal skills. Besides, byearning money to pay for their study, collegestudents can learn how to manage their211UNIT 6 Earn as you learn?money and become less dependent on theirparents.3 • Yes, I agree with the author that workingwhile studying has many negative impactson students, such as not getting enough rest,decreased school performance, abuse of drugsand alcohol. As one’s time and energy arelimited, working, even part-time, will affectone’s study. Therefore, students should takestudy seriously and it is critical not to worklong hours while studying at college.• No, I don’t think there are so many negativeimpacts of working while studying asmentioned by the author. I have manyclassmates who are working part-timeto cover their tuition. Most of them areresponsible students as they want to sharethe financial burden with their parents. Theyalso study very hard for scholarships. At thesame time, they try to make full use of theirworking time. Some of them work with theirprofessors in the lab, so their work does notinterfere with their study. In fact, workingmay benefit their study because they canapply what is learned in class in practice.4 • Yes, I think part-time jobs may help builda sense of responsibility, which in turn mayenhance students’ school performance.Because if you take part-time jobs whilestudying, you have to follow the work ethics,observe the working schedule, work up toexpectations, contribute to teamwork, andbalance work and study. All these will helpyou to multitask, to be more efficient, tocultivate a sense of responsibility, and toenhance your school performance.• No, I don’t think part-time jobs help to builda sense of responsibility, not to mentionenhancing students’ school performancebecause students who take part-time work,especially those who work long hours, haveto strike a balance between work and study.To meet the demanding working schedule,more often than not, they have to cut corners,for example, by devoting less time to studyor ignoring homework. Moreover, they mayspend more on entertainment and luxurygoods as they have more spending money.Students who work long hours usually fail tomeet the academic requirements and have noclear plan for career development.5Part-time employment provides a good opportunity for students to learn many otherthings other than book knowledge. It has many positive influences:• building a sense of responsibility as you haveto accomplish your tasks;• building self-discipline as you have to manageyour time well and rely on yourself;• gaining social skills and work experienceas you interact with people outside theclassroom;• broadening your vision as you learn about theworkplace and society;• having more employment opportunities asyou gain work experience in preparation foryour future career.Words in use31indicate 2conventional3assess 4decrease5alter 6has undermined7 compromise 8controversial9resolved 10 abandonWord building4form formationoccupation occupysolve solution(To be continued)212 Third Editionpersuade persuasion transmit transmission original originality flexibility flexible secure security simple simplicity prosperousprosperity51 solution2 transmission3 prosperity4 formation5 flexible6 occupied7 originality8 productivity9 simplicity10 persuasion 11 representation 12 securityBanked cloze61 J2 C3 H4 D5 M6 G7 I8 A9 E 10 NExpressions in use71 cutting back on2 interfere with3 take a toll on4 at risk of5 dropped out6 in turn7 contribute to 8 are accustomed to 9 held on to 10in other wordsStructure analysis8(Continued )213UNIT 6 Earn as you learn?Structured writing9There are several reasons why people get fired from their jobs. First, people may lose their jobs if they have some dishonest behaviors, such as cheating in their job applications or telling lies in work. Second, employees may be fired due to poor attendance. No boss likes an employee who is often late for or absent from work. Third, people having difficulty getting along with their co-workers are also likely to be fired because they may cause conflicts in the workplace. Therefore, to be a good employee, it isimportant to be honest, punctual, and cooperative.10间隔年指的是学生休假不去上学而去旅游或工作等的一段时间，但不一定是一年。

算法导论（第三版）－复习－第六部分图论22-26［转］22习题22.1-5 有向图G(V, E)的平⽅图。

链表表⽰时，对每结点u的Adj[u]中所有v加⼊队列，后边出队边将Adj[v]加⼊Adj[u]中。

矩阵表⽰时，若w[i, j]、w[j, k]同时为1则将w[i, k]置1.习题22.1-6 O(V)的时间寻找通⽤汇点。

汇点的特征是邻接矩阵的第j列除[j, j]外所有元素为1. 可将每⾏调整[j ,j]后作为⼀个整数，所有整数与运算，为1的位是汇点。

习题22.1-7 有向⽆环图的关联矩阵B，BB’每个元素C[i, j]=∑B[i, k]*B’[k, j]=∑B[i, k]*B[j, k]，即同时进i, j两结点与同时出i, j的结点总数-⼀进⼀出i, j两结点的结点总数。

习题22.2-7 类似BFS，d mod2为0则标为B（娃娃脸），d mod2为1则标为H（⾼跟鞋）。

但若有边连接相同类的结点，则⽆法划分。

wrestler(G){for each u in G{(u,v)=Adj[u];if(v.mark==u.mark){throw error;}if(v.d==NIL) {v.d=u.d+1; v.mark=v.d mod 2;}}}习题22.2-8 任意点之间的最短路径。

重复的Dijktra算法或Floyd-Warshall算法习题22.2-9 ⽆向图扩展为有向图。

问题变成要遍历所有边⼀次。

访问结点u时，将u的⼦结点v的其他边都可视为⼦集v，问题等价于u到v，访问v的集合，v到u。

u标为visiting⼊列，然后访问v，v标为visiting⼊列，然后访问v的后继结点，访问过的边标为visited，返回到visiting的点时，如果该点所有连接的边都标为visited只剩⼀条返回上级的边，则返回上级结点并将点标为visited，v出列，访问u的其他⼦结点，最终u出列。

全部结点出列后达到遍历所有边⼀次。

do quite a few in-depth research projects.• She resisted the temptation to laugh.noun + verb• An opportunity arose for me to work in China, so I went and spent a year there.•People feel educational standards slipped when the government cut finances.noun + noun•James has been a team leader / member / player, and he is now able to enjoy the fruits of his hard work.•Their demanding work schedule means they have less time to devote to school assignments. adjective + noun•And they reported lower levels of commitment to school and more modest educational aspirations.•This is not an empty threat; I will call the police if this happens again!verb + adverb• She smiled proudly as she looked at the photos of her new grandson.•I don’t like to travel with my brother because he drives carelessly.adverb + verb• I fully understand that there will be serious problems when doing this project.•You may respectfully listen to their advice, but don’t take it too seriously.In this unit about working part-time while studying, we have come across quite a few useful grammatical collocations, mainly in the patterns of “adjective + noun” and “noun + noun”.Please take a look at the following list of collocations in this unit:Text Astudent achievement, school performance, school engagement, heavy commitment, academicyear, school achievement, school commitment, educational aspirations, school careers, working students, school assignments, non-working students Text Bhigher education, undergraduate student, wealthy students, educational performance, formal education, educational funding, educational benefits PART IIKEY TO EXERCISESSECTION A111) A teaching assistant in kindergarten or a tutor2) A cashier in a store3) A waiter in a restaurant4) A car cleaner2 • I would like to work as a teaching assistantin kindergarten. I really enjoy spending timewith small children and I am thinking ofworking as a teacher in kindergarten in thefuture. So working as a teaching assistantwould definitely be a great experience for me.• I would like to work in a company, whetherbig or small, because in the future I plan toestablish my own business. Working part-time in a company would give me some ideaof what it is like to work in a company, howa company is run, and what job a boss shoulddo.210 Third Edition2In my opinion, the most important advantages of doing part-time jobs are: gaining work experience, acquiring communicative skills, and building connections for future career. In doing part-time jobs, especially those jobs which are related to my field of study, I can build up my work experience and enrich my resume. Besides, in working, I may have to communicate with different kinds of people, soit can help develop my communicative skills, which are essential to success. And in getting to know some important people in the workplace, I can build some contacts for my future career.Understanding the text11To measure the impact of employment on student achievement.2According to the research, a heavy commitment to part-time work undermines and significantly interferes with school achievement andcommitment.3About 10 hours per week or less.4Students become interested in study again.5Students may take easier classes, copyothers’ assignments, cut class, or refuse todo assignments, and over time, students’commitment to school is eroded bit by bit.6Students may find school less rewarding and interesting, and it is highly possible that thosewho have been working long hours will dropout of school before graduation.7Because teenagers working long hours frequently have more money to spend than their peers,and they often become used to spending theirearnings on drugs and alcohol.8Doing part-time jobs while studying isacceptable, but students should work nomore than 10 hours a week if they want to besuccessful in school. Critical thinking21 • Yes, I think early employment can definitelybuild character because besides study,you have to fit yourself into the workingenvironment. You can learn interpersonalskills, social responsibility and professionalethics in a working setting. Moreover, youhave to try hard to strike a balance betweenwork, study, and play. In this way, you willdevelop a strong sense of responsibility andboost your self-confidence.• No, not necessarily. Though early employmentmay help students to gain some workexperience, it is not necessarily helpful inbuilding their character. Because they have tospend quite a lot of time working and maybecome less responsible or less committedto their study. Too much work may also leadto alcohol and drug abuse. So, in some cases,early employment undermines character-building rather than help it.2 • Yes, I agree. Students have so many academictasks to complete in college that they hardlyhave any extra time for work. If they work,they will certainly have to spend less time andenergy on study, which is likely to depresstheir school performance. I see many workingstudents around me sleep in class, skip class,or copy others’ assignments. If they cannotbe responsible students when they should be,how could they become responsible peopleafter graduation? So, I think students shouldtake study as their main task instead of doingpart-time jobs.• No, I don’t agree. College students shouldprepare themselves for future careers, so theyneed not only to perform well academicallybut also develop other skills becausesurviving in society requires more than bookknowledge. Working part-time can exposestudents to the real world and help themacquire basic interpersonal skills. Besides, byearning money to pay for their study, collegestudents can learn how to manage their211UNIT 6 Earn as you learn?money and become less dependent on theirparents.3 • Yes, I agree with the author that workingwhile studying has many negative impactson students, such as not getting enough rest,decreased school performance, abuse of drugsand alcohol. As one’s time and energy arelimited, working, even part-time, will affectone’s study. Therefore, students should takestudy seriously and it is critical not to worklong hours while studying at college.• No, I don’t think there are so many negativeimpacts of working while studying asmentioned by the author. I have manyclassmates who are working part-timeto cover their tuition. Most of them areresponsible students as they want to sharethe financial burden with their parents. Theyalso study very hard for scholarships. At thesame time, they try to make full use of theirworking time. Some of them work with theirprofessors in the lab, so their work does notinterfere with their study. In fact, workingmay benefit their study because they canapply what is learned in class in practice.4 • Yes, I think part-time jobs may help builda sense of responsibility, which in turn mayenhance students’ school performance.Because if you take part-time jobs whilestudying, you have to follow the work ethics,observe the working schedule, work up toexpectations, contribute to teamwork, andbalance work and study. All these will helpyou to multitask, to be more efficient, tocultivate a sense of responsibility, and toenhance your school performance.• No, I don’t think part-time jobs help to builda sense of responsibility, not to mentionenhancing students’ school performancebecause students who take part-time work,especially those who work long hours, haveto strike a balance between work and study.To meet the demanding working schedule,more often than not, they have to cut corners,for example, by devoting less time to studyor ignoring homework. Moreover, they mayspend more on entertainment and luxurygoods as they have more spending money.Students who work long hours usually fail tomeet the academic requirements and have noclear plan for career development.5Part-time employment provides a good opportunity for students to learn many otherthings other than book knowledge. It has many positive influences:• building a sense of responsibility as you haveto accomplish your tasks;• building self-discipline as you have to manageyour time well and rely on yourself;• gaining social skills and work experienceas you interact with people outside theclassroom;• broadening your vision as you learn about theworkplace and society;• having more employment opportunities asyou gain work experience in preparation foryour future career.Words in use31indicate 2conventional3assess 4decrease5alter 6has undermined7 compromise 8controversial9resolved 10 abandonWord building4form formationoccupation occupysolve solution(To be continued)212 Third Editionpersuade persuasion transmit transmission original originality flexibility flexible secure security simple simplicity prosperousprosperity51 solution2 transmission3 prosperity4 formation5 flexible6 occupied7 originality8 productivity9 simplicity10 persuasion 11 representation 12 securityBanked cloze61 J2 C3 H4 D5 M6 G7 I8 A9 E 10 NExpressions in use71 cutting back on2 interfere with3 take a toll on4 at risk of5 dropped out6 in turn7 contribute to 8 are accustomed to 9 held on to 10in other wordsStructure analysis8(Continued )213UNIT 6 Earn as you learn?Structured writing9There are several reasons why people get fired from their jobs. First, people may lose their jobs if they have some dishonest behaviors, such as cheating in their job applications or telling lies in work. Second, employees may be fired due to poor attendance. No boss likes an employee who is often late for or absent from work. Third, people having difficulty getting along with their co-workers are also likely to be fired because they may cause conflicts in the workplace. Therefore, to be a good employee, it isimportant to be honest, punctual, and cooperative.10间隔年指的是学生休假不去上学而去旅游或工作等的一段时间，但不一定是一年。

Unit 6–Section ALanguage Focus–Words in Use1.When employees participated in the problem-solving process, they were much more willingto (implement) solutions to the problems.2. A strong police force has been placed between the two (rival) groups in the village toprevent fighting and killing.3.Although personally we believe this to be of only secondary importance, its potential rolein (motivating) innovative acts cannot be ignored.4.Though many things have been changed culturally, there is a commitment and sense of responsibility that have not yet been (discarded) in today's society.5.Western nations have older and shrinking populations since they entered the 21st century and their (fluctuating) birth rates have also posed problems.6.She didn't want to marry him and was (prejudiced) against him because he had only a bachelor's degree and didn't meet her expectations for marriage.7.The president is in trouble and will have to work hard to (restore) his credibility afterpeople discovered that he was not telling the truth.8.To study a number of subjects in the humanities has been both enjoyable and (enlightening) , providing me with a new and different perspective on the world in which we live.9.People are concerned about the environment issue because air and water pollution not only affects everyone's health but also makes it difficult for businesses to (profit) .10.Instead of ignoring or envying successful students, I made it my mission to (investigate)the mysterious causes of their success and greatness.Word Building1.strategy2.sympathy3.confirm4.locate5.reflect6.provide7.install8.register9.quotation10.sympathy11.critic12.industrial1.strategic2.sympathetic3.confirmation4.location5.reflection6.provision7.installation8.registration9.quote10.sympathize11.criticize12.industrialize1.He's usually indifferent to the feelings of other people; he can neither understand nor (sympathize) with my eagerness and anxiety.2.There has been no official (confirmation) that the documents are original, although different sources from the media and the public suggest that they are.3.There's a consensus that the (strategic) defense of a country depends on a powerful airforce and marine force, in addition to advanced arms.4.Total construction time of the shop was about 30 days including the (installation) of the newly-imported machines and the assembly of the various parts.5.To illustrate my point of view, I would like to (quote) from a source that many of us findmore authoritative than the words of a businessman.6.People need to be kind. Therefore, I am not ashamed to be regarded as (sympathetic) to the anxieties of those who are treated harshly in life.7.In business, we often do things inappropriately. For example, we may (criticize) someone's work in front of their co-workers.8.The restaurant has recently moved here because its owners want to provide a convenient (location) for their customers in this area.9.Cultural awareness will help you when you learn the language. After all, language is a(n) (reflection) of the culture from which it developed.10.Students are no longer learning how to (industrialize) agricultural economy; instead, they are learning the digital economy.11.People living in this remote area for generations have harsh living conditions and poor (provision) of housing, food and medicines.12.If you do not get the detailed information required for the school's (registration) , you maylose the opportunity to take the classes you want.Banked ClozeSimplifying is not necessarily about less. It can be about more: more time, more enjoyment, more accomplishment, and more of what (1) (profits) you. If you do a lot of things that don't bring you joy or support your long-term plan, then doing less of that kind of things makes sense because you can't (2) (preserve) everything. The purpose of simplifying is to remove what's not important.To understand what should be (3) (discarded), try to think of activities and things as either assets or obligations. An asset is something that is valuable. Some (4) (corresponding) examples are stocks, bonds, buildings, land, gold, etc., but a little more broadly, an asset is anything that can strengthen and (5) (motivate) you, moving you closer to your goals. However, obligations are debts. An obligation is anything that (6) (weakens) you, moves you farther from your goals, provides negative stress, creates anxiety, and decreases your health. Then how can you (7) (implement) the idea of simplifying? Think about your daily activities and start with just one area. For example,you may begin with (8) (obligations) by making a long list of your daily activities. Your list may (9) (revolve) around such routines as paying bills and planning a birthday party for a friend, etc.Do the activities get you closer to your goals? If not, (10) (modify) the list. Remove what is unnecessary in order to concentrate more on something important in your life.Language Focus–Expressions in Use1.Though he was 80 years old, blind and hardly able to walk, his family (was attached to)him so much that they could hardly bear the thought of his death.2.The support our volunteers provide to the community as well as society cannot (be measured in) purely practical terms, and their continuing contribution is vital.3.Please don't forget the Tourist Guide, which should (come in handy) when you travel to different places in Asia and Europe for the next few weeks.4.These people living in this area are still (clinging to) their traditions which give their life meaning and help them in answering many questions.5.You will (pay a big price) for not learning English; you never know how much you willmiss without being able to speak English.6.If you (are exhausted from) travel and trying to adjust to a new time zone, you may not beready to face the new challenging environment yet.7.The general manager of the company intends to introduce new management courses, and tighter controls will be (imposed on) internal management to raise efficiency.8.Class discussions next week will (revolve around) the importance of love, communication anda close relationship between parents and their children.Translation英译汉Minimalism (极简主义) is about getting rid of excess stuff and keeping only what you need. Minimalist living, in simplest terms, is to live with as less as possible, mentally and physically until you achieve peace of mind. Results that ensue are less stress, more time, and increased happiness. Minimalists like to say that they're living more meaningfully, more deliberately, and that the minimalist lifestyle allows them to focus on what's more important in life: friends, hobbies, travel, experiences. Of course, minimalism doesn't meanthere's anything inherently wrong with owning material possessions. Today's problem seems to be that we tend to givetoo much meaning to our things, often forsaking ( 扔掉 ) our health, our relationships, our passions, our personal growth, and our desire to contribute beyond ourselves. In addition to its application in people's daily life, minimalism also finds application in many creative disciplines, including art, architecture, design, dance, film making, theater, music, fashion, photography and literature.极简主义是指去掉剩余的，仅保存需要的部分。

算法导论第三版第六章答案英Chapter6Michelle Bodnar,Andrew LohrDecember31,2016Exercise6.1-1At least2h and at most2h+1?1.Can be seen because a complete binarytree of depth h?1hasΣh?1i=02i=2h?1elements,and the number of elementsin a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive.Exercise6.1-2Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these kleaves,which must have length m.It is clear from the way we de?ned m that m= lg n .Exercise6.1-3If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtreeExercise6.1-4The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1Exercise6.1-6No,the array is not a max-heap.7is contained in position9of the array,so its parent must be in position4,which contains6.This violates the max-heap property.Exercise6.1-7It su?ces to show that the elements with no children are exactly indexed by{ n/2 +1,...,n}.Suppose that we had an i in this range.It’s childeren would be located at2i and2i+1but both of these are≥2 n/2 +2>n and so are not in the array.Now,suppose we had an element with no kids,this means that2i and2i+1are both>n,however,this means that i>n/2.This means that i∈{ n/2 +1,...,n}.Exercise6.2-1271731613101571248902717101613315712489027171016138157124830Exercise6.2-2Algorithm1MIN-HEAPIFY(A,i)1:l=LEF T(i)2:r=RIGHT(i)3:if l≤A.heap?size and A[l]4:smallest=l5:else smallest=i6:end if7:if r≤A.heap?size and A[r]8:smallest=r9:end if10:if smallest=i then11:exchange A[i]with A[smallest]12:MIN-HEAPIFY(A,smallest)13:end ifThe running time of MIN-HEAPIFY is the same as that of MAX-HEAPIFY. Exercise6.2-3The array remains unchanged since the if statement on line line8will be false.2Exercise6.2-4If i>A.heap?size/2then l and r will both exceed A.heap?size so the if statement conditions on lines3and6of the algorithm will never be satis?ed. Therefore largest=i so the recursive call will never be made and nothing will happen.This makes sense because i necessarily corresponds to a leaf node,so MAX–HEAPIFY shouldn’t alter the heap.Exercise6.2-5Iterative Max Heapify(A,i)while il=LEFT(i)r=LEFT(i)largest=iif l≤A.heap-size and A[l]>A[i]thenlargest=lend ifif l≤A.heap-size and A[r]>A[i]thenlargest=rend ifif largest=i thenexchange A[i]and A[largest]elsereturn Aend ifend whilereturn AExercise6.2-6Consider the heap resulting from A where A[1]=1and A[i]=2for 2≤i≤n.Since1is the smallest element of the heap,it must be swapped through each level of the heap until it is a leaf node.Since the heap has height lg n ,MAX-HEAPIFY has worst-case time?(lg n).Exercise6.3-1531710841962295317228419610953192284176109584192231761098451922317610984221953176109842219103176593Exercise6.3-2If we had started at1,we wouldn’t be able to guarantee that the max-heap property is maintained.For example,if the array A is given by[2,1,1,3]then MAX-HEAPIFY won’t exchange2with either of it’s children,both1’s.How-ever,when MAX-HEAPIFY is called on the left child,1,it will swap1with3. This violates the max-heap property because now2is the parent of3.Exercise6.3-3All the nodes of height h partition the set of leaves into sets of size between 2h?1+1and2h,where all but one is size2h.Just by putting all the children of each in their own part of trhe partition.Recall from6.1-2that the heap has height lg(n) ,so,by looking at the one element of this height(the root),we get that there are at most2 lg(n) leaves.Since each of the vertices of height h partitions this into parts of size at least2h?1+1,and all but one corresponds to a part of size2h,we can let k denote the quantity we wish to bound,so,(k?1)2h+k(2h?1+1)≤2 lg(n) ≤n/2sok≤n+2h2h+1+2h+1≤n2h+1≤n2h+1Exercise6.4-14513225717208451320257172845252013717284255201371728425132057172842513208717254413208717252520134871725252013178742525513178742202517135874220252135874172025132587417202513852741720254852713172025845271317202587524131720254752813172025745281317202524578131720255427813172025245781317202542578131720252457813172025Exercise6.4-2We’ll prove the loop invariant of HEAPSORT by induction:Base case:At the start of the?rst iteration of the for loop of lines2-5we have i=A.length.The subarray A[1..n]is a max-heap since BUILD-MAX-HEAP(A)was just called.It contains the n smallest elements,and the empty subarray A[n+1..n]trivially contains the0largest elements of A in sorted order.Suppose that at the start of the i th iteration of of the for loop of lines2-5, the subarray A[1..i]is a max-heap containing the i smallest elements of A[1..n] and the subarray A[i+1..n]contains the n?i largest elements of A[1..n]in sorted order.SinceA[1..i]is a max-heap,A[1]is the largest element in A[1..i]. Thus it is the(n?(i?1))th largest element from the original array since the n?i largest elements are assumed to be at the end of the array.Line3swaps A[1]with A[i],so A[i..n]contain the n?i+1largest elements of the array, and A[1..i?i]contains the i?1smallest elements.Finally,MAX-HEAPIFY is called on A,1.Since A[1..i]was a max-heap prior to the iteration and only the elements in positions1and i were swapped,the left and right subtrees ofnode1,up to node i?1,will be max-heaps.The call to MAX-HEAPIFY will place the element now located at node1into the correct position and restore the5max-heap property so that A[1..i?1]is a max-heap.This concludes the next iteration,and we have veri?ed each part of the loop invariant.By induction, the loop invariant holds for all iterations.After the?nal iteration,the loop invariant says that the subarray A[2..n] contains the n?1largest elements ofA[1..n],sorted.Since A[1]must be the n th largest element,the whole array must be sorted as desired.Exercise6.4-3If it’s already sorted in increasing order,doing the build max heap-max-heap call on line1will takeΘ(n lg(n))time.There will be n iterations of the for loop, each takingΘ(lg(n))time because the element that was at position i was the smallest and so will have lg(n) steps when doing max-heapify on line5.So, it will beΘ(n lg(n))time.If it’s already sorted in decreasing order,then the call on line one will only takeΘ(n)time,since it was already a heap to begin with,but it will still take n lg(n)peel o?the elements from the heap and re-heapify.Exercise6.4-4Consider calling HEAPSORT on an array which is sorted in decreasing order. Every time A[1]is swapped with A[i],MAX-HEAPIFY will be recursively called a number of times equal to the height h of the max-heap containing the elements of positions1through i?1,and has runtime O(h).Since there are2k nodes at height k,the runtime is bounded below bylg ni=12i log(2i)=lg ni=1i2i=2+( lg n ?1)2 lg n =?(n lg n).Exercise6.4-5Since the call on line one could possibly take only linear time(if the input was already a max-heap for example),we will focus on showing that the for loop takes n log n time.This is the case because each time that the last element is placed at the beginning to replace the max element being removed,it has to go through every layer,because it was already very small since it was at the bottom level of the heap before.Exercise6.5-1The following sequence of pictures shows how the max is extracted from the heap.1.Original heap:615 13540126298172.we move the last element to the top of theheap 3.13>9>1so,we swap1and13.4.Since12>5>1,we swap1and12.75.Since6>2>1,we swap1and6.Exercise6.5-2The following sequence of pictures shows how10is inserted into the heap, then swapped with parent nodes until the max-heap property is restored.The node containing the new key is heavily shaded.1.Original heap:815 13540126298172.MAX-HEAP-INSERT(A,10)is called,so we?rst append a node assignedvalue?∞:3.The key value of the new node is updated:4.Since the parent key is smaller than10,the nodes are swapped:95.Since the parent node is smaller than10,the nodes are swapped:Exercise6.5-3Heap-Minimum(A)1:return A[1]Heap-Extract-Min(A)1:if A.heap-size<1then2:Error“heap under?ow”3:end if4:min=A[1]5:A[1]=A[A.heap?size]6:A.heap?size??7:Min-heapify(A,1)8:return minHeap-decrease-key(A,i,key)101:if key?A[i]then2:Error“new key larger than old key”3:end if4:A[i]=key5:while i>1and A[P arent(i)]6:exchange A[i]with A[P arent(i)]7:i=P arent(i)8:end whileMin-Heap-Insert(A,key)1:A.heap?size++2:A[A.heap?size]=∞3:Heap-Decrease-Key(A,A.heap-size,key)Exercise6.5-4If we don’t make an assignment to A[A.heap?size]then it could contain any value.In particular,when we call HEAP-INCREASE-KEY,it might be the case that A[A.heap?size]initially contains a value larger than key,causing an error.By assigning?∞to A[A.heap?size]we guarantee that no error will occur.However,we could have assigned any value less than or equal to key to A[A.heap?size]and the algorithm would still work.Exercise6.5-5Initially,we have a heap and then only change the value at i to make it larger.This can’t invalidate the ordering between i and it’s children,the only other thing that needs to be related to i is that i is less than it’s parent,which may be false.Thus we have the invariant is true at initialization.Then,when we swap i with its parent if it is larger,since it is larger than it’s parent,it must also be larger than it’s sibling,also,since it’s parent was initially above its kids in the heap,we know that it’s parent is larger than it’s kids.The only relation in question is then the new i and it’s parent.At termination,i is the root,so it has no parent,so the heap property must be satis?ed everywhere.Exercise6.5-6Replace A[i]by key in the while condition,and replace line5by“A[i]= A[P ARENT(i)].”After the end of the while loop,add the line A[i]=key. Since the key value doesn’t change,there’s no sense in assigning it until we know where it belongs in the heap.Instead,we only make the assignment of the parent to the child node.At the end of the while loop,i is equal to the position where key belongs since it is either the root,or the parent is at least11key,so we make the assignment.Exercise6.5-7Have a?eld in the structure that is just a count of the total number of elements ever added.When adding an element,use thecurrent value of that counter as the key.Exercise6.5-8The algorithm works as follows:Replace the node to be deleted by the last node of the heap.Update the size of the heap,then call MAX-HEAPIFY to move that node into its proper position and maintain the max-heap property. This has running timeO(lg n)since the number of times MAX-HEAPIFY is recursively called is as most the height of the heap,which is lg n . Algorithm2HEAP-DELETE(A,i)1:A[i]=A[A.heap?size]2:A.heap?size=A.heap?size+13:MAX-HEAPIFY(A,i)Exercise6.5-9Construct a min heap from the heads of each of the k lists.Then,to?nd the next element in the sorted array,extract the minimum element(in O lg(k) time).Then,add to the heap the next element from the shorter list from which the extracted element originally came(also O(lg(k))time).Since?nding the next element in the sorted list takes only at most O(lg(k))time,to? nd the whole list,you need O(n lg(k))total steps.Problem6-1a.They do not.Consider the array A= 3,2,1,4,5 .If we run Build-Max-Heap,we get 5,4,1,3,2 .However,if we run Build-Max-Heap’,we will get 5,4,1,2,3 instead.b.Each insert step takes at most O(lg(n)),since we are doing it n times,weget a bound on the runtime of O(n lg(n)).Problem6-2a.It will su?ce to show how to access parent and child nodes.In a d-ary array,PARENT(i)= i/d ,and CHILD(k,i)=di?d+1+k,where CHILD(k,i) gives the k th child of the node indexed by i.12b.The height of a d-ary heap of n elements is with1of log d n.c.The following is an implementation of HEAP-EXTRACT-MAX for a d-aryheap.An implementation of DMAX-HEAPIFY is also given,which is the analog of MAX-HEAPIFY for d-ary heap.HEAP-EXTRACT-MAX con-sists of constant time operations,followed by a call to DMAX-HEAPIFY.The number of times this recursively calls itself is bounded by the height of the d-ary heap,so the running time is O(d log d n).Note that the CHILD function is meant to be the one described in part(a).Algorithm3HEAP-EXTRACT-MAX(A)for a d-ary heap1:if A.heap?size<1then2:error“heap under?ow”3:end if4:max=A[1]5:A[1]=A[A.heap?size]6:A.heap?size=A.heap?size?17:DMAX-HEAPIFY(A,1)Algorithm4DMAX-HEAPIFY(A,i)1:largest=i2:for k=1to d do3:if CHILD(k,i)≤A.heap?size and A[CHILD(k,i)]>A[i]then4:if A[CHILD(k,i)]>largest then5:largest=A[CHILD(k,i)]6:end if7:end if8:end for9:if largest=i then10:exchange A[i]with A[largest]11:DMAX-HEAPIFY(A,largest)12:end ifd.The runtime of this implementation of INSERT is O(log d n)since the whileloop runs at most as many times as the height of the d-ary array.Note that when we call PARENT,we mean it as de?ned in part(a).e.This is identical to the implementation of HEAP-INCREASE-KEY for2-aryheaps,but with the PARENT function interpreted as in part(a).The run-time is O(log d n)since the while loop runs at most as many times as the height of the d-ary array.13Algorithm5INSERT(A,key)1:A.heap?size=A.heap?size+12:A[A.heap?size]=key3:i=A.heap?size4:while i>1and A[P ARENT(i)5:exchange A[i]with A[P ARENT(i)]6:i=P ARENT(i)7:end whileAlgorithm6INCREASE-KEY(A,i,key)1:if key2:error“new key is smaller than current key”3:end if4:A[i]=key5:while i>1and A[P ARENT(i)6:exchange A[i]with A[P ARENT(i)]7:i=P ARENT(i)8:end whileProblem6-3a.2345 891214 16∞∞∞∞∞∞∞b.For every i,j,Y[1,1]≤Y[i,1]≤Y[i,j].So,if Y[1,1]=∞,we know thatY[i,j]=∞for every i,j.This means that no elements exist.If Y is full,it has no elements labeled∞,in particular,the element Y[m,n]is not labeled ∞.c.Extract-Min(Y,i,j),extracts the minimum value from the young tableau Yobtained by Y [i ,j ]=Y[i +i?1,j +j?1].Note that in running this algorithm,several accesses may be made out of bounds for Y,de? ne these to return∞.No store operations will be made on out of bounds locations.Since the largest value of i+j that this can be called with is n+m,and this quantity must increase by one for each call,we have that the runtime is bounded by n+m.d.Insert(Y,key)Since i+j is decreasing at each step,starts as n+m and isbounded by2below,we know that this program has runtime O(n+m). e.Place the n2elements into a Young Tableau by calling the algorithm frompart d on each.Then,call the algorithm from part c n2to obtain the numbers in increasing order.Both of these operations take time at most2n∈O(n), and are done n2times,so,the total runtime is O(n3)141:min=Y[i,j]2:if Y[i,j+1]=Y[i+1,j]=∞then3:Y[i,j]=∞4:return min5:end if6:if Y[i,j+1]7:Y[i,j]=Y[i,j+1]8:Y[i,j+1]=min9:return Extract-min(y,i,j+1)10:else11:Y[i,j]=Y[i+1,j]12:Y[i+1,j]=min13:return Extract-min(y,i+1,j)14:end if1:i=m,j=n2:Y[i,j]=key3:while Y[i?1,j]>Y[i,j]or Y[i,j?1]>Y[i,j]do 4:if Y[i?1,j]5:Swap Y[i,j]and Y[i,j?1]6:j??7:else8:Swap Y[i,j]and Y[i?1,j]9:i??10:end if11:end while15f.Find(Y,key).Let Check(y,key,i,j)mean to return true if Y[i,j]=key,oth-erwise do nothingi=j=1while Y[i,j]Check(Y,key,i,j)i++end whilewhile i>1and jCheck(i,j)if Y[i,j]j++elsei–end ifend whilereturn false16。

新编英语教程第三版练习册6答案【篇一：新编英语教程3 unit1-10练习册1-10课答案及书本第一部分连词题】fumesmoke or vapour ; offensive or suffocating gas2. sandyof the colour of sand ; pale reddish-yellow3. somehowfor some reason or other4. stale dry and unappetizing5. dingy dirty-looking ; not fresh or cheerful6. proceed go ahead7. bloodshotfull of blood ; red because the small blood vessels are swollen or broken8. dismayedmade afraid or discouraged at the prospect of troubleunit 21. rage be very angry2. a vegetable plot a small piece of land for growing vegetables3. croaking rough and harsh4. murmur speak in a low but not clear voice5. wind down lower ( the car window ) by turning the handle6. gesture of despairmovement of the head or hand to show helplessness7. brutalcruel8. quarantinethe period of separation from others so that the disease cannot spreadunit 31. globeworld2. circlemove around3. indirectlynot straight to the point ; in a roundabout way4. idle talk talking about unimportant things5. coincidence a combination of events happening in such a way that it seems planned or arranged6. hastily in a hurry7. demand ask forcefully8. roar speak in a loud, deep voiceunit 41. willthe legal statement concerning the disposal of one’s property after death2. signature person’s name written by himself3. literaryof literature4. suppositiona guess5. playwrightdramatist, a person who writes plays6. vague not clearly known7. confirmprove the truth of something8. verse poetryunit 61. outlaya spending of money2. refill a new filling3. theoretically in theory4. uranium heavy white metal which is radioactive, a source of atomic energy5. bonnet metal lid on the front of a car6. submarine a ship that can stay under water7. radiationthe process in which energy in the form of rays is sent out from atoms8. syntheticnot naturally produced ; artificialunit 71. pose as pretend to be2. pest an annoying thing3. suspense and anxietystate of being anxious and uncertain about something unknown4. fidgeting moving about restlessly5. assuremake somebody believe, feel sure6. apace quickly7. inquisitive chatterboxa person who is curious about other people and talkative8. obstinacy and willfulnessstubbornness and pig-headedness9. escapism that which makes one stay away from unpleasant reality10. justifygive a good reason foruint 8shelter------------------------- f. protection;a building offering protectionbecome engrossed in----------d. have one’s attention completely taken up bycontent--------------------------e. satisfactionbrowse--------------------------a. read here and there in books especially for enjiymentvariety --------------------------b. collection of different kinds of thingsapart from ----------------------g. besadestempt----------------------------c. attractunit 9fledgling------------------------j. young and inexperiencedspectacular---------------------e. very impressiveadroit --------------------------g. quick and skilfulcoma----------------------------i. unconsciousness due to injuryflurry---------------------------a. sudden excitementrecuperate---------------------b. get back one’s strengthmassive hemorrhage----------c.l osing a lot of bloodfragile--------------------------f. easily injured or brokenconcussion--------------------d. (an)injury to the brainpermanent---------------------h. lasting for a long time or forever unit10cudgel-------------------------c. short,thick stickbuck---------------------------g. lower one’s head or body so as to avoid being hitplacatory----------------------f. submissive,undisturbednegligently-------------------h. carelesslywry----------------------------b. twistedbawling-----------------------a. loud,rough shoutingpandemouium----------------d. (scene of)wila and noisy disorder gramophone------------------e. record-playerunit1 p121. it is an excellent photograph of mrs. johnson.george, her son, has decided tomake several 2. there was a temporary 3. this muslin is beautiful! but it’s so flimsy. is it ?4. the helicopter came to rescue the the plane crash as soon as thelocal authorities received the radio message.5. have you seen the school in the suburbs of london?6. a proverb says that a little7. he was tall and muscular. obviously he has a perfect .8. at the end of the interview the young man overcame his about his salary.9. the headmaster opened the door and looked at the with an air ofdisapproval.10. his efforts for an early proved to be a failure because he had to make suchan awkward journey.unit 2p281. 2. while (cross) the street, you must keep your eyes open.3. (damage) during the war, the airport has never been usedagain.4. ’t possibly pay him a visit.5. 6. (walk) through the fields, one can take a look at the wild flowers.7. we didn’t t hink he was very old, 8. she was wheeled to the hospital,(follow) by her children.9. the children went to the park, a mile away from the school, (sing and talk10. i am sorry to have kept you (wait) for two hours.11. can you hear the children (shout) in the next room?12. he whispered “watch out” at the same time (try) to make as little noise as possible.13. the little girl sat in a corner in deep silence, (let) her doll dangle at her side.14. (find) the room unlocked, we immediately went in.unit 8p122a1. we haven’t seen him for more than ten years and i find hima (change) person, he has become a 2. in the (qualify) teachers will be sent here.3. there lived an unusually (determine) farmer in the nearby village.4. in order to improve our (lead) comrades in our department have made a5. taking a camel ride was a6. teaching is a more (demand) job than working as a tourist guide.7. the child, very (please), cleaned her (soil) hands and went to bed with her lovely toy.8. your unwillingness to cooperate with the doctor has made the case even more9. the (interest) spectators sat watching the (excite) football match for an hour in spite of their (soak) clothes.10. after a (tire) day ta work, the (tire) woman sat in the park enjoying the beautiful sunset with a pleasant smile on her face.b1. the doctor insisted on (give) the patient an immediate operation2. (fascinate), we watched the sun3. if you practice (sing) often, you will know how (do) it without (make) such an exhibition of yourself.4. peter hated (keep) to his bed. he missed (play) with his friends and never failed(be) at the window (see) them (climb) the apple-tree.5. would you mind (open) the window?6. i persuaded him (take) care of the child while i went i really could not depend on his7. i oughtto tell (tell) my secretary to post the letter for me this morning but i was busy (prepare) a speech and i forgot8. “would you like ”“i would preferas a rule, i prefer (read) to watch(watch) tv.”9. “yesterday i found one of the pages in the book i bought you change it for me?”“i’m sorry”10. reference books are not allowed (take) out of the teachers’ readingroom.11. “the (clean).”“you needn’t tell me, i haven’t time”12. “it is no use our (wait) for him any longer. he doesn’t know the way sohe won’t come.”“but the film is worth ”“he’ll regret ”“i’m sure he’ll show up at any minute. he knows howused (be) a tourist guide in this city when he was young.”unit 9 p138a1. boxing has been a controversial topic of conversation for a long time, itssupporters say that it is man’s instinct to wish to show that histhan that of his opponent.(strong)2. they maintain that this instinct makes boxing a sport that is fine and3. they also say that it is very good for young boys to learn how to defendthemselves in case of 4. those who wish to see the of boxing say just the opposite.(abolish)5. they declare that it is6. professional fighters are particularly criticized, but even more so the promoters ofboxing matches who, it is said, make untold out of the sufferings of the boxer.(wealthy)7. but it must be realized that boxers too can make a lot of money, and a good fightercan look forward to a comfortable if he is sensible.(retire)8. and it is that a famous boxer can attract far morespectators that eventhe most famous pop singer or film star.(deny)9. even the most can’t fail to be affected by the exciting atmosphere ofan important boxing match.(emotion)10. although we may not always approve of the motives that lead a man to take upprofessional boxing as a career, we can’t help admiring his in the ring.(brave)as a rule in a gesture of despairat such short noticein hostile silence claimkeep to ones bedcling to no exception to help outspoil if only1.as a rule southerners prefer rice, whereas northerners prefer steamed bread.2.everyone must get up at six to do morning exercises and those who stay up late are no exception to the rule.3. keep to your bed for three days,drink a lot of water and take two pills after each meal,the【篇二：新编英语教程第六册练习册paraphrase答案】nothing in life is more exciting and rewarding than the sudden flash of light that leaves you a changed person--not only changed, but changed for the better.the most inspiring and gratifying fact of life is the unexpected spark of enlightenment that makes you different and a better person than before.2. he came across the street, finally, muffled in his ancient overcoat, shapeless felt hat pulled down over his bald head, looking more like an energetic gnome than an eminent psychiatrist.at last he walked over from the other side of the street, wrapped in his old-fashioned overcoat, his bald head covered by a shapeless felt hat. he looked like a dwarfish old man fullof energy rather than a well-known psychiatrist.3. the woman who spoke next had never married because of a sense of obligation to her widowed mother; she recalled bitterly all the marital chances she had let go by.the next speaker on the tape was a woman who had remained single because she thought she was obliged to take care of her mother who was a widow. she still remembered and told others miserably about all the chances of marriage she had missed.4. in the end, if you let it become a habit, it can become a real roadblock, an excuse for not trying any more.eventually, if you form a ha bit of saying “if only”, the phrase can really turn to an obstruction, providing you with an excuse for giving up trying anything at all.5. ... you never got out of the past tense. not once did you mention the future.…you are always thinking of the pa st, regretting and lamenting. you did not look forward to what you can do in the future at all.6. my, my, said the old man slyly. if only we had come down ten seconds sooner, wed have caught that cab, wouldnt we? the old man said to me trickily, using the phrase “if only” on purpose, “if only we’d got here ten seconds earlier, we’d have caught the cab.” i laughed and understood what he meant. so i followed his advice and said, “next time i’ll run faster”.unit 21. moses pleaded a speech defect to rationalize his reluctance to deliver jehovahs edict to pharaoh. moses justified his unwillingness to pass jehovah’s order to pharaoh, saying that he was “slow of speech”.2. yet for all the trouble procrastination may incur, delay can often inspire and revive a creative soul.delay leads to problems. however, in many cases, it can often stimulate the creativity in an artist.3. he notes that speedy action can be embarrassing or extremely costly.he points out that hastiness may give rise to decision which turn out to be humiliating or expensive.4. bureaucratization, which flourished amid the growing burdens of government and the greater complexity of society, was designed to smother policymakers in blankets of legalism, compromise and reappraisal---and thereby prevent hasty decisions from being made.excessive red-tape(官样文章；繁文缛节) developed because public administration was expanding in scope and because society was growing more and more complicated. in this sense, red-tape helped those in charge of policy to be fully engaged in enormous amount of paperwork and judgment, thus making it impossible for an immature decision to result.5. ...many of my friends go through agonies when they face a blank page.…many of my friends have a hard time the moment they attempt to put pen to paper.unit 31. of course, my father is a gentleman of the old school, a member of the generation to whom a good deal of modern architecture is unnerving; but i suspect---i more than suspect, i am convinced---that his negative response was not so much to the architecture as to a violation of his concept of the nature of money.brought up in the old tradition, my father is naturally not prepared to accept the idea of modern architecture; his objection to it, i would assume, indeed i should say i am pretty sure, is not a result of his strong dislike of the physicalbuilding itself, but rather that of his refusal to change his attitude towards money.2. if a buildings design made it appear impregnable, the institution was necessarily sound, and the meaning of the heavy wall as an architectural symbol dwelt in the prevailing attitude toward money, rather than in any aesthetic theory.if a building was made to look sturdy/invulnerable, it would be accordingly regarded as reliable, and the significance of the thick walls would be measured not by their artistic value, butby their seeming ability to provide a safe location for money.3. in a primitive society, for example, men pictured the world as large, fearsome, hostile, and beyond human control.people in a primitive society, for example, saw the world as an enormous planet full of fear, hatred and disorder.4.the principal function of todays wall is to separate possible undesirable outside air from the controlled conditions of temperature and humidity which we have created inside.today a wall serves mainly as a physical means to protect the desired atmosphere inside from being disturbed by anything unwelcome outside.5. to repeat, it is not our advanced technology, but our changing conceptions of ourselves in relation to the world that determine how we shall build our walls.again, the decisive factor that can influence the design of a wall is not the advancement of science and technology, but our ever-changing attitude towards our place in this world.unit 41. he was a man of exuberant fancy, and, withal, of an authority so irresistible that, at his will, he turned his varied fancies into facts.he was a man rich in whimsies, and intolerant of any act bold enough as to challenge his authority. when his mind caught upon something, absurd as it might be, he would do everything to make sure that it was done in the way he wished.2. when every member of his domestic and political systems moved smoothly in its appointed course, his nature was bland and genial; but whenever there was a little hitch, and some of his orbs got out of their orbits, he was blander and more genial still, for nothing pleased him so much as to make the crooked straight, and crush down uneven places.when all his subjects behaved in such a manner as they were told to, he could be gentle and kind. and he could even be more so, if anything not conforming to what he expected should occur, because that offered a great chance for him to see the undesirable removed, a thing he was most delighted in doing.3. he could open either door he pleased: he was subject to no guidance or influence but that of the aforementioned impartial and incorruptible chance.he enjoyed total freedom to choose what to do: he was not directed or influenced by anyone as to which door to open. the only thing that was decisive in terms of his fate was the above-mentioned chance, granted to all the accused alike.4. this element of uncertainty lent an interest to the occasion which it could not otherwise have attained.the fact that no one could tell for sure what might happen (to the accused) made this from of trial more attractive than any other form of justice.5. thus the masses were entertained and pleased, and the thinking part of the community could bring no charge of unfairness against this plan; for did not the accused person have the whole matter in his own hands?thus people enjoyed coming here to watch, and those guided by reason in the society could not possibly question the fairness of this form of trial; for was it not the fact that all the accused were given equal chances to make decisions upon their won destiny?unit51. this semi-barbaric king had a daughter as blooming as his most florid fancies, and with a soul as fervent and imperious as his own.this semi-barbaric king had a daughter as exuberant as the wildest of his notions, a daughter who possessed a nature as fierce and tyrannical as his own.2. of course, everybody knew that the deed with which the accused was charged had been done.it was, of course, known to all that he was guilty of the offense of conducting an affair with the princess.3. ...; but the king would not think of allowing any fact of this kind to interfere with the workings of the tribunal, in which he took such great delight and satisfaction.…,even though the king was well aware that the love affair had taken place, he would still refuse to let the normal method of deciding guilt or innocence be disturbed, because he was extremely enthusiastic about his way of setting matters of this kind.4. ...; but gold, and the power of a womans will, had brought the secret to the princess..…; but because she had the money, and above all, because her determination was so irresistible, the princess was able to get access to the secret.5. he understood her nature, and his soul was assured thatshe would never rest until she had made plain to herself this thing, hidden to all other lookers-on, even to the king.he knew her so well that he was perfectly positive that she would never cease to search for the secret, which remained unknown to all other spectators, even to the king himself.unit 61. there seems to be a general assumption that brilliant people cannot stand routine; that they need a varied, exciting life in order to do their best.it is generally believed that a colorless life can freeze acreative mind, and that only a colorful life can inspire a man to creative work.2. the outstanding characteristic of mans creativeness is the ability to transmute trivial impulses into momentous consequences.one of the wonders human creativity works is that man can make full use of even insignificant feelings to produce far-reaching results.3. an eventful life exhausts rather than stimulates.a life full of diversions stops man’s creativity instead of activating it.4. it is usually the mediocre poets, writers, etc.,who go in search of stimulating events to release their creative flow.only literary artists of an average type rely on excitements inlife as a source for their creative work./ great poets, writers, etc., create works of art out of trivial and common subject.5. people who find dull job unendurable are often dull people who do not know what to do with themselves when at leisure.people who are unable to see how to be patient withrepetitious work are usually those who are unable to see where to find fun in life when it comes to relaxation.【篇三：新编英语教程6 第三版译文】txt>在生活中，没有什么比顿悟更令人激动和兴奋的，它可以改变一个人——不仅仅是改变，而且变得更好。

Chapter16Michelle Bodnar,Andrew LohrApril12,2016Exercise16.1-1The given algorithm would just stupidly compute the minimum of the O(n) numbers or return zero depending on the size of S ij.There are a possible number of subproblems that is O(n2)since we are selecting i and j so that1≤i≤j≤n.So,the runtime would be O(n3).Exercise16.1-2This becomes exactly the same as the original problem if we imagine time running in reverse,so it produces an optimal solution for essentially the same reasons.It is greedy because we make the best looking choice at each step.Exercise16.1-3As a counterexample to the optimality of greedily selecting the shortest, suppose our activity times are{(1,9),(8,11),(10,20)}then,picking the shortestfirst,we have to eliminate the other two,where if we picked the other two instead,we would have two tasks not one.As a counterexample to the optimality of greedily selecting the task that conflicts with the fewest remaining activities,suppose the activity times are {(−1,1),(2,5),(0,3),(0,3),(0,3),(4,7),(6,9),(8,11),(8,11),(8,11),(10,12)}.Then, by this greedy strategy,we wouldfirst pick(4,7)since it only has a two con-flicts.However,doing so would mean that we would not be able to pick the only optimal solution of(−1,1),(2,5),(6,9),(10,12).As a counterexample to the optimality of greedily selecting the earliest start times,suppose our activity times are{(1,10),(2,3),(4,5)}.If we pick the ear-liest start time,we will only have a single activity,(1,10),whereas the optimal solution would be to pick the two other activities.Exercise16.1-4Maintain a set of free(but already used)lecture halls F and currently busy lecture halls B.Sort the classes by start time.For each new start time which you encounter,remove a lecture hall from F,schedule the class in that room,1and add the lecture hall to B.If F is empty,add a new,unused lecture hall to F.When a classfinishes,remove its lecture hall from B and add it to F. Why this is optimal:Suppose we have just started using the m th lecture hall for thefirst time.This only happens when ever classroom ever used before is in B.But this means that there are m classes occurring simultaneously,so it is necessary to have m distinct lecture halls in use.Exercise16.1-5Run a dynamic programming solution based offof the equation(16.2)where the second case has“1”replaced with“v k”.Since the subproblems are still indexed by a pair of activities,and each calculation requires taking the minimum over some set of size≤|S ij|∈O(n).The total runtime is bounded by O(n3). Exercise16.2-1A optimal solution to the fractional knapsack is one that has the highest total value density.Since we are always adding as much of the highest value density we can,we are going to end up with the highest total value density. Suppose that we had some other solution that used some amount of the lower value density object,we could substitute in some of the higher value density object meaning our original solution coud not of been optimal.Exercise16.2-2Suppose we know that a particular item of weight w is in the solution.Then we must solve the subproblem on n−1items with maximum weight W−w. Thus,to take a bottom-up approach we must solve the0-1knapsack problem for all items and possible weights smaller than W.We’ll build an n+1by W+1table of values where the rows are indexed by item and the columns are indexed by total weight.(Thefirst row and column of the table will be a dummy row).For row i column j,we decide whether or not it would be advantageous to include item i in the knapsack by comparing the total value of of a knapsack including items1through i−1with max weight j,and the total value of including items1through i−1with max weight j−i.weight and also item i.To solve the problem,we simply examine the n,W entry of the table to determine the maximum value we can achieve.To read offthe items we include, start with entry n,W.In general,proceed as follows:if entry i,j equals entry i−1,j,don’t include item i,and examine entry i−1,j next.If entry i,j doesn’t equal entry i−1,j,include item i and examine entry i−1,j−i.weight next. See algorithm below for construction of table:Exercise16.2-3At each step just pick the lightest(and most valuable)item that you can pick.To see this solution is optimal,suppose that there were some item j that we included but some smaller,more valuable item i that we didn’t.Then,we could replace the item j in our knapsack with the item i.it will definitelyfit2Algorithm10-1Knapsack(n,W)1:Initialize an n+1by W+1table K2:for j=1to W do3:K[0,j]=04:end for5:for i=1to n do6:K[i,0]=07:end for8:for i=1to n do9:for j=1to W do10:if j<i.weight then11:K[i,j]=K[i−1,j]12:end if13:K[i,j]=max(K[i−1,j],K[i−1,j−i.weight]+i.value)14:end for15:end forbecause i is lighter,and it will also increase the total value because i is more valuable.Exercise16.2-4The greedy solution solves this problem optimally,where we maximize dis-tance we can cover from a particular point such that there still exists a place to get water before we run out.Thefirst stop is at the furthest point from the starting position which is less than or equal to m miles away.The problem exhibits optimal substructure,since once we have chosen afirst stopping point p,we solve the subproblem assuming we are starting at bining these two plans yields an optimal solution for the usual cut-and-paste reasons.Now we must show that this greedy approach in fact yields afirst stopping point which is contained in some optimal solution.Let O be any optimal solution which has the professor stop at positions o1,o2,...,o k.Let g1denote the furthest stopping point we can reach from the starting point.Then we may replace o1by g2to create a modified solution G,since o2−o1<o2−g1.In other words,we can actually make it to the positions in G without running out of water.Since G has the same number of stops,we conclude that g1is contained in some optimal solution.Therefore the greedy strategy works.Exercise16.2-5Consider the leftmost interval.It will do no good if it extends any further left than the leftmost point,however,we know that it must contain the leftmost point.So,we know that it’s left hand side is exactly the leftmost point.So,we just remove any point that is within a unit distance of the left most point since3they are contained in this single interval.Then,we just repeat until all points are covered.Since at each step there is a clearly optimal choice for where to put the leftmost interval,thisfinal solution is optimal.Exercise16.2-6First compute the value of each item,defined to be it’s worth divided by its weight.We use a recursive approach as follows:Find the item of median value, which can be done in linear time as shown in chapter9.Then sum the weights of all items whose value exceeds the median and call it M.If M exceeds W then we know that the solution to the fractional knapsack problem lies in taking items from among this collection.In other words,we’re now solving the frac-tional knapsack problem on input of size n/2.On the other hand,if the weight doesn’t exceed W,then we must solve the fractional knapsack problem on the input of n/2low-value items,with maximum weight W−M.Let T(n)denote the runtime of the algorithm.Since we can solve the problem when there is only one item in constant time,the recursion for the runtime is T(n)=T(n/2)+cn and T(1)=d,which gives runtime of O(n).Exercise16.2-7Since an identical permutation of both sets doesn’t affect this product,sup-pose that A is sorted in ascending order.Then,we will prove that the product is maximized when B is also sorted in ascending order.To see this,suppose not,that is,there is some i<j so that a i<a j and b i>b j.Then,consideronly the contribution to the product from the indices i and j.That is,a b ii a b j j,then,if we were to swap the order of b1and b j,we would have that contributionbe a b ji a b ij.we can see that this is larger than the previous expression becauseit differs by a factor of(a ja i )b i−b j which is bigger than one.So,we couldn’t ofmaximized the product with this ordering on B.Exercise16.3-1If we have that x.freq=b.freq,then we know that b is tied for lowest frequency.In particular,it means that there are at least two things with lowest frequency,so y.freq=x.freq.Also,since x.freq≤a.freq≤b.freq=x.freq, we must have a.freq=x.freq.Exercise16.3-2Let T be a binary tree corresponding to an optimal prefix code and suppose that T is not full.Let node n have a single child x.Let T be the tree obtained by removing n and replacing it by x.Let m be a leaf node which is a descendant of x.Then we have4cost(T )≤c∈C\{m}c.freq·d T(c)+m.freq(d T(m)−1)<c∈Cc.freq·d T(c)=cost(T)which contradicts the fact that T was optimal.Therefore every binary tree corresponding to an optimal prefix code is full.Exercise16.3-3An optimal huffman code would be00000001→a0000001→b000001→c00001→d0001→e001→f01→g1→hThis generalizes to having thefirst n Fibonacci numbers as the frequencies in that the n th most frequent letter has codeword0n−11.To see this holds,we will prove the recurrencen−1i=0F(i)=F(n+1)−1This will show that we should join together the letter with frequency F(n)with the result of joining together the letters with smaller frequencies.We will prove it by induction.For n=1is is trivial to check.Now,suppose that we have n−1≥1,then,F(n+1)−1=F(n)+F(n−1)−1=F(n−1)+n−2i=0F(i)=n−1i=0F(i)See also Lemma19.2.Exercise16.3-4Let x be a leaf node.Then x.freq is added to the cost of each internal node which is an ancestor of x exactly once,so its total contribution to the new way of computing cost is x.freq·d T(x),which is the same as its old contribution. Therefore the two ways of computing cost are equivalent.5Exercise16.3-5We construct this codeword with monotonically increasing lengths by always resolving ties in terms of which two nodes to join together by joining together those with the two latest occurring earliest elements.We will show that the ending codeword has that the least frequent words are all having longer code-words.Suppose to a contradiction that there were two words,w1and w2so that w1appears more frequently,but has a longer codeword.This means that it was involved in more merge operation than w2was.However,since we are always merging together the two sets of words with the lowest combined frequency,this would contradict the fact that w1has a higher frequency than w2.Exercise16.3-6First observe that any full binary tree has exactly2n−1nodes.We can encode the structure of our full binary tree by performing a preorder traversal of T.For each node that we record in the traversal,write a0if it is an internal node and a1if it is a leaf node.Since we know the tree to be full,this uniquely determines its structure.Next,note that we can encode any character of C in lg n bits.Since there are n characters,we can encode them in order of appearance in our preorder traversal using n lg n bits.Exercise16.3-7Instead of grouping together the two with lowest frequency into pairs that have the smallest total frequency,we will group together the three with lowest frequency in order to have afinal result that is a ternary tree.The analysis of optimality is almost identical to the binary case.We are placing the symbols of lowest frequency lower down in thefinal tree and so they will have longer codewords than the more frequently occurring symbolsExercise16.3-8For any2characters,the sum of their frequencies exceeds the frequency of any other character,so initially Huffman coding makes128small trees with2 leaves each.At the next stage,no internal node has a label which is more than twice that of any other,so we are in the same setup as before.Continuing in this fashion,Huffman coding builds a complete binary tree of height lg(256)=8, which is no more efficient than ordinary8-bit length codes.Exercise16.3-9If every possible character is equally likely,then,when constructing the Huff-man code,we will end up with a complete binary tree of depth7.This means that every character,regardless of what it is will be represented using7bits. This is exactly as many bits as was originally used to represent those characters, so the total length of thefile will not decrease at all.6Exercise16.4-1Thefirst condition that S is afinite set is a given.To prove the second condition we assume that k≥0,this gets us that I k is nonempty.Also,to prove the hereditary property,suppose A∈I k this means that|A|≤k.Then, if B⊆A,this means that|B|≤|A|≤k,so B∈I stly,we prove the exchange property by letting A,B∈I k be such that|A|<|B|.Then,we can pick any element x∈B\A,then,|A∪{x}|=|A|+1≤|B|≤k,so,we can extend A to A∪{x}∈I k.Exercise16.4-2Let c1,...,c m be the columns of T.Suppose C={c i1,...,c ik}is depen-dent.Then there exist scalars d1,...,d k not all zero such that kj=1d j c ij=0.By adding columns to C and assigning them to have coefficient0in the sum, we see that any superset of C is also dependent.By contrapositive,any subset of an independent set must be independent.Now suppose that A and B are two independent sets of columns with|A|>|B|.If we couldn’t add any col-umn of A to be whilst preserving independence then it must be the case that every element of A is a linear combination of elements of B.But this implies that B spans a|A|-dimensional space,which is impossible.Therefore our in-dependence system must satisfy the exchange property,so it is in fact a matroid.Exercise16.4-3Condition one of being a matroid is still satisfied because the base set hasn’t changed.Next we show that I is nonempty.Let A be any maximal element of I then,we have that S−A∈I because S−(S−A)=A⊆A which is maximal in I.Next we show the hereditary property,suppose that B⊆A∈I ,then, there exists some A ∈I so that S−A⊆A ,however,S−B⊇S−A⊆A so B∈I .Lastly we prove the exchange property.That is,if we have B,A∈I and |B|<|A|we canfind an element x in A−B to add to B so that it stays independent.We will split into two cases.Ourfirst case is that|A|=|B|+1.We clearly need to select x to be the single element in A−B.Since S−B contains a maximal independent set Our second case is if thefirst case does not hold.Let C be a maximal inde-pendent set of I contained in S−A.Pick an aribitrary set of size|C|−1from some maximal independent set contained in S−B,call it D.Since D is a subset of a maximal independent set,it is also independent,and so,by the exchange property,there is some y∈C−D so that D∪{y}is a maximal independent set in I.Then,we select x to be any element other than y in A−B.Then, S−(B∪{x})will still contain D∪{y}.This means that B∪{x}is independent in(I)7Exercise16.4-4Suppose X⊂Y and Y∈I.Then(X∩S i)⊂(Y∩S i)for all i,so |X∩S i|≤|Y∩S i|≤1for all1≤i≤k.Therefore M is closed under inclusion.Now Let A,B∈I with|A|=|B|+1.Then there must exist some j such that|A∩S j|=1but B∩S j|=0.Let a=A∩S j.Then a/∈B and |(B∪{a})∩S j|=1.Since|(B∪{a})∩S i|=|B∩S i|for all i=j,we must have B∪{a}∈I.Therefore M is a matroid.Exercise16.4-5Suppose that W is the largest weight that any one element takes.Then, define the new weight function w2(x)=1+W−w(x).This then assigns a strictly positive weight,and we will show that any independent set that that has maximum weight with respect to w2will have minimum weight with respect to w.Recall Theorem16.6since we will be using it,suppose that for our matriod,all maximal independent sets have size S.Then,suppose M1and M2 are maximal independent sets so that M1is maximal with respect to w2and M2is minimal with respect to w.Then,we need to show that w(M1)=w(M2). Suppose not to achieve a contradiction,then,by minimality of M2,w(M1)> w(M2).Rewriting both sides in terms of w2,we have w2(M2)−(1+W)S> w2(M1)−(1+W)S,so,w2(M2)>w2(M1).This however contradicts maximality of M1with respect to w2.So,we must have that w(M1)=w(M2).So,a maximal independent set that has the largest weight with respect to w2also has the smallest weight with respect to w.Exercise16.5-1With the requested substitution,the instance of the problem becomesa i1234567d i4243146w i10203040506070We begin by just greedily constructing the matroid,adding the most costly to leave incomplete tasksfirst.So,we add tasks7,6,5,4,3.Then,in order to schedule tasks1or2we need to leave incomplete more important tasks.So, ourfinal schedule is 5,3,4,6,7,1,2 to have a total penalty of only w1+w2=30.Exercise16.5-2Create an array B of length n containing zeros in each entry.For each ele-ment a∈A,add1to B[a.deadline].If B[a.deadline]>a.deadline,return that the set is not independent.Otherwise,continue.If successfully examine every element of A,return that the set is independent.8Problem16-1a.Always give the highest denomination coin that you can without going over.Then,repeat this process until the amount of remaining change drops to0.b.Given an optimal solution(x0,x1,...,x k)where x i indicates the number ofcoins of denomination c i.We willfirst show that we must have x i<c for every i<k.Suppose that we had some x i≥c,then,we could decrease x i by c and increase x i+1by1.This collection of coins has the same value and has c−1fewer coins,so the original solution must of been non-optimal.This configuration of coins is exactly the same as you would get if you kept greedily picking the largest coin possible.This is because to get a total value of V,you would pick x k= V c−k and for i<k,x i (V modc i+1)c−i .This is the only solution that satisfies the property that there aren’t more than c of any but the largest denomination because the coin amounts are a base c representation of V modc k.c.Let the coin denominations be{1,3,4},and the value to make change for be6.The greedy solution would result in the collection of coins{1,1,4}butthe optimal solution would be{3,3}.d.See algorithm MAKE-CHANGE(S,v)which does a dynamic programmingsolution.Since thefirst forloop runs n times,and the inner for loop runs k times,and the later while loop runs at most n times,the total running time is O(nk).Problem16-2a.Order the tasks by processing time from smallest to largest and run them inthat order.To see that this greedy solution is optimal,first observe that the problem exhibits optimal substructure:if we run thefirst task in an optimal solution,then we obtain an optimal solution by running the remaining tasks in a way which minimizes the average completion time.Let O be an optimal solution.Let a be the task which has the smallest processing time and let b be thefirst task run in O.Let G be the solution obtained by switching the order in which we run a and b in O.This amounts reducing the completion times of a and the completion times of all tasks in G between a and b by the difference in processing times of a and b.Since all other completion times remain the same,the average completion time of G is less than or equal to the average completion time of O,proving that the greedy solution gives an optimal solution.This has runtime O(n lg n)because we mustfirst sort the elements.b.Without loss of generality we my assume that every task is a unit time task.Apply the same strategy as in part(a),except this time if a task which we9Algorithm2MAKE-CHANGE(S,v)Let numcoins and coin be empty arrays of length v,and any any attempt to access them at indices in the range−max(S),−1should return∞for i from1to v dobestcoin=nilbestnum=∞for c in S doif numcoins[i−c]+1<bestnum thenbestnum=numcoins[i-c]bestcoin=cend ifend fornumcoins[i]=bestnumcoin[i]=bestcoinend forlet change be an empty setiter=vwhile iter>0doadd coin[iter]to changeiter=iter−coin[iter]end whilereturn changewould like to add next to the schedule isn’t allowed to run yet,we must skip over it.Since there could be many tasks of short processing time which have late release time,the runtime becomes O(n2)since we might have to spend O(n)time deciding which task to add next at each step.Problem16-3a.First,suppose that a set of columns is not linearly independent over F2then,there is some subset of those columns,say S so that a linear combination of S is0.However,over F2,since the only two elements are1and0,a linear combination is a sum over some subset.Suppose that this subset is S ,note that it has to be nonempty because of linear dependence.Now,consider the set of edges that these columns correspond to.Since the columns had their total incidence with each vertex0in F2,it is even.So,if we consider the subgraph on these edges,then every vertex has a even degree.Also,since our S was nonempty,some component has an edge.Restrict our attention to any such component.Since this component is connected and has all even vertex degrees,it contains an Euler Circuit,which is a cycle.Now,suppose that our graph had some subset of edges which was a cycle.Then,the degree of any vertex with respect to this set of edges is even,so,10when we add the corresponding columns,we will get a zero column in F2.Since sets of linear independent columns form a matroid,by problem16.4-2, the acyclic sets of edges form a matroid as well.b.One simple approach is to take the highest weight edge that doesn’t completea cycle.Another way to phrase this is by running Kruskal’s algorithm(seeChapter23)on the graph with negated edge weights.c.Consider the digraph on[3]with the edges(1,2),(2,1),(2,3),(3,2),(3,1)where(u,v)indicates there is an edge from u to v.Then,consider the two acyclic subsets of edges B=(3,1),(3,2),(2,1)and A=(1,2),(2,3).Then, adding any edge in B−A to A will create a cycle.So,the exchange property is violated.d.Suppose that the graph contained a directed cycle consisting of edges corre-sponding to columns S.Then,since each vertex that is involved in this cycle has exactly as many edges going out of it as going into it,the rows corre-sponding to each vertex will add up to zero,since the outgoing edges count negative and the incoming vertices count positive.This means that the sum of the columns in S is zero,so,the columns were not linearly independent.e.There is not a perfect correspondence because we didn’t show that not con-taining a directed cycle means that the columns are linearly independent, so there is not perfect correspondence between these sets of independent columns(which we know to be a matriod)and the acyclic sets of edges (which we know not to be a matroid).Problem16-4a.Let O be an optimal solution.If a j is scheduled before its deadline,we canalways swap it with whichever activity is scheduled at its deadline without changing the penalty.If it is scheduled after its deadline but a j.deadline≤j then there must exist a task from among thefirst j with penalty less than that of a j.We can then swap a j with this task to reduce the overall penalty incurred.Since O is optimal,this can’t happen.Finally,if a j is scheduled after its deadline and a j.deadline>j we can swap a j with any other late task without increasing the penalty incurred.Since the problem exhibits the greedy choice property as well,this greedy strategy always yields on optimal solution.b.Assume that MAKE-SET(x)returns a pointer to the element x which isnow it its own set.Our disjoint sets will be collections of elements which have been scheduled at contiguous times.We’ll use this structure to quickly find the next available time to schedule a task.Store attributes x.low and x.high at the representative x of each disjoint set.This will give the earliest and latest time of a scheduled task in the block.Assume that UNION(x,y)11maintains this attribute.This can be done in constant time,so it won’t af-fect the asymptotics.Note that the attribute is well-defined under the union operation because we only union two blocks if they are contiguous.Without loss of generality we may assume that task a1has the greatest penalty,task a2has the second greatest penalty,and so on,and they are given to us in the form of an array A where A[i]=a i.We will maintain an array D such that D[i]contains a pointer to the task with deadline i.We may assume that the size of D is at most n,since a task with deadline later than n can’t possibly be scheduled on time.There are at most3n total MAKE-SET,UNION,and FIND-SET operations,each of which occur at most n times,so by Theorem21.14the runtime is O(nα(n)).Algorithm3SCHEDULING-VARIATIONS(A)1:Initialize an array D of size n.2:for i=1to n do3:a i.time=a i.deadline4:if D[a i.deadline]=NIL then5:y=FIND-SET(D[a i.deadline])6:a i.time=y.low−17:end if8:x=MAKE-SET(a i)9:D[a i.time]=x10:x.low=x.high=a i.time11:if D[a i.time−1]=NIL then12:UNION(D[a i.time−1],D[a i.time])13:end if14:if D[a i.time+1]=NIL then15:UNION(D[a i.time],D[a i.time+1])16:end if17:end forProblem16-5a.Suppose there are m distinct elements that could be requested.There may besome room for improvement in terms of keeping track of the furthest in future element at each position.If you maintain a(double circular)linked list witha node for each possible cache element and an array so that in index i thereis a pointer corresponding to the node in the linked list corresponding to the possible cache request i.Then,starting with the elements in an arbitrary order,process the sequence r1,...,r n from right to left.Upon processing a request move the node corresponding to that request to the beginning of the linked list and make a note in some other array of length n of the element at the end of the linked list.This element is tied for furthest-in-future.Then, just scan left to right through the sequence,each time just checking some12set for which elements are currently in the cache.It can be done in constant time to check if an element is in the cache or not by a direct address table. If an element need be evicted,evict the furthest-in-future one noted earlier. This algorithm will take time O(n+m)and use additional space O(m+n). If we were in the stupid case that m>n,we could restrict our attention to the possible cache requests that actually happen,so we have a solution that is O(n)both in time and in additional space required.b.Index the subproblems c[i,S]by a number i∈[n]and a subset S∈ [m]k.Which indicates the lowest number of misses that can be achieved with an initial cache of S starting after index i.Then,c[i,S]=minx∈{S}(c[i+1,{r i}∪(S−{x})]+(1−χ{ri}(x)))which means that x is the element that is removed from the cache unless it is the current element being accessed,in which case there is no cost of eviction.c.At each time we need to add something new,we can pick which entry toevict from the cache.We need to show the there is an exchange property.That is,if we are at round i and need to evict someone,suppose we evict x.Then,if we were to instead evict the furthest in future element y,we would have no more evictions than before.To see this,since we evicted x,we will have to evict someone else once we get to x,whereas,if we had used the other strategy,we wouldn’t of had to evict anyone until we got to y.This is a point later in time than when we had to evict someone to put x back into the cache,so we could,at reloading y,just evict the person we would of evicted when we evicted someone to reload x.This causes the same number of misses unless there was an access to that element that wold of been evicted at reloading x some point in between when x any y were needed,in which case furthest in future would be better.13。

Ch10算法导论第三版第十章答案英Chapter10Michelle Bodnar,Andrew LohrApril12,2016Exercise10.1-14414134141841Exercise10.1-2We will call the stacks T and R.Initially,set T.top=0and R.top=n+1. Essentially,stack T uses the?rst part of the array and stack R uses the last part of the array.In stack T,the top is the rightmost element of T.In stack R, the top is the leftmost element of R.Algorithm1PUSH(S,x)1:if S==T then2:if T.top+1==R.top then3:error“over?ow”4:else5:T.top=T.top+16:T[T.top]=x7:end if8:end if9:if S==R then10:if R.top?1==T.top then11:error“over?ow”12:else13:R.top=R.top?1 14:T[T.top]=x 15:end if16:end if1Algorithm2POP(S) if S==T thenif T.top==0then error“under?ow”elseT.top=T.top?1. return T[T.top+1] end ifend ifif S==R thenif R.top==n+1then error“under?ow”elseR.top=R.top+1. return R[R.top?1] end ifend ifExercise10.1-34414131313838Exercise10.1-4Algorithm3ENQUEUEif Q.head==Q.tail+1,or Q.head==1and Q.tail==Q.length then error“over?ow”end ifQ[Q.tail]=xif Q.tail==Q.length thenQ.tail=1elseQ.tail=Q.head+1end ifExercise10.1-5As in the example code given in the section,we will neglect to check for over?ow and under?ow errors.2Algorithm4DEQUEUEerror“under?ow”end ifx=Q[Q.head]if Q.head==Q.length thenQ.head=1elseQ.head=Q.head+1end ifreturn xAlgorithm5HEAD-ENQUEUE(Q,x) Q[Q.head]=xif Q.head==1thenQ.head=Q.lengthelseQ.head=Q.head?1end ifAlgorithm6TAIL-ENQUEUE(Q,x) Q[Q.tail]=xif Q.tail==Q.length thenQ.tail=1elseQ.tail=Q.tail+1end ifAlgorithm7HEAD-DEQUEUE(Q,x) x=Q[Q.head]if Q.head==Q.length thenQ.head=1elseQ.head=Q.head+1end ifAlgorithm8TAIL-DEQUEUE(Q,x) x=Q[Q.tail]if Q.tail==1thenQ.tail=Q.lengthelseQ.tail=Q.tail?1end if3Exercise10.1-6The operation enqueue will be the same as pushing an element on to stack 1.This operation is O(1).To dequeue,we pop an element from stack2.If stack 2is empty,for each element in stack1we pop it o?,then push it on to stack2. Finally,pop the top item from stack2.This operation is O(n)in the worst case.Exercise10.1-7The following is a way of implementing a stack using two queues,where pop takes linear time,and push takes constant time.The?rst of these ways,consists of just enqueueing eachelement as you push it.Then,to do a pop,you dequque each element from one of the queues and place it in the other,but stopping just before the last element.Then,return the single element left in the original queue.Exercise10.2-1To insert an element in constant time,just add it to the head by making it point to the old head and have it be the head.To delete an element,it needs linear time because there is no way to get a pointer to the previous element in the list without starting at the head and scanning along.Exercise10.2-2The PUSH(L,x)operation is exactly the same as LIST-INSERT(L,x).The POP operation sets x equal to L.head,calls LIST-DELETE(L,L.head),then returns x.Exercise10.2-3In addition to the head,also keep a pointer to the last element in the linked list.To enqueue,insert the element after the last element of the list,and set it to be the new last element.T o dequeue,delete the?rst element of the list and return it.Exercise10.2-4First let L.nil.key=k.Then run LIST-SEARCH’as usual,but remove the check that x=L.nil.Exercise10.2-5To insert,just do list insert before the current head,in constant time.To search,start at the head,check if the element is the current node being in-spected,check the next element,and so on until at the end of the list or you4found the element.This can take linear time in the worst case.To delete,again linear time is used because there is no wayto get to the element immediately before the current element without starting at the head and going along the list.Exercise10.2-6Let L1be a doubly linked list containing the elements of S1and L2be a doubly linked list containing the elements of S2.We implement UNION as fol-lows:Set L1.nil.prev.next=L2.nil.next and L2.nil.next.prev=L1.nil.prev so that the last element of L1is followed by the?rst element of L2.Then set L1.nil.prev=L2.nil.prev and L2.nil.prev.next=L1.nil,so that L1.nil is the sentinel for the doubly linked list containing all the elements of L1and L2. Exercise10.2-7Algorithm9REVERSE(L)a=L.head.nextb=L.headwhile a=NIL dotmp=a.nexta.next=bb=aa=tmpend whileL.head=bExercise10.2-8We will store the pointer value for L.head separately,for convenience.In general,A XOR(A XOR C)=C,so once we know one pointer’s true value we can recover all the others(namely L.head)by applying this rule.Assuming there are at least two elements in the list,the?rst element will contain exactly the address of the second.Algorithm10LISTnp-SEARCH(L,k)p=NILx=L.headwhile x=NIL and x.key=k dotemp=xx=pXORx.npp=tempend whileTo reverse the list,we simply need to make the head be the“last”ele-5Algorithm11LISTnp-INSERT(L,x)x.np=L.headL.nil.np=xXOR(L.nil.npXORL.head)L.head=xAlgorithm12LISTnp-Delete(L,x)L.nil.np=L.nil.npXORL.headXORL.head.npL.head.np.np=L.head.np.npXORL.headment before L.nil instead of the?rst one after this.This is done by settingL.head=L.nil.npXORL.head.Exercise10.3-1A multiple array version could be L=2,/34567/124819511/23456A single array version could be L=4,127/410481371916105191311/16 Exercise10.3-2Algorithm13Allocate-Object()if free==NIL thenerror“out of space”elsex=freefree=A[x+1]end ifExercise10.3-3Allocate object just returns the index of some cells that it’s guaranteed tonot give out again until they’ve been freed.The prev attribute is not modi?ed because only the next attribute is used by the memory manager,it’s up to the code that calls allocate to use the prev and key attributes as it sees?t.Exercise10.3-4For ALLOCATE-OBJECT,we will keep track of the next available spot inthe array,and it will always be one greater than the number of elements being stored.For FREE-OBJECT(x),when a space is freed,we will decrement the6Algorithm14Free-Object(x)A[x+1]=freefree=xposition of each element in a position greater than that of x by1and update pointers accordingly.This takes linear time.Exercise10.3-5See the algorithm COMP ACT IF Y?LIST(L,F)Exercise10.4-1181274510221Note that indices8and2in the array do not appear,and,in fact do not represent a valid tree.Exercise10.4-2See the algorithm PRINT-TREE.Exercise10.4-3Exercise10.4-4See the algorithm PRINT-TREE.Exercise10.4-5See the algorithm INORDER-PRINT’(T)Exercise10.4-6Our two pointers will be left and right.For a node x,x.left will point to the leftmost child of x and x.right will point to the sibling of x immediately to its right,if it has one,and the parent of x otherwise.Our boolean value b,stored at x,will be such that b=depth(x)mod2.T o reach the parent of a node, simply keep following the“right”pointers until the parity of the boolean value changes.To?nd all the children of a node,start by?nding x.left,then follow7Algorithm15COMPACTIFY-LIST(L,F)if n=m thenreturnend ife=max{max i∈[m]{|key[i]|},max i∈L{|key[i]|}}increase every element of key[1..m]by2efor every element of L,if its key is greater than e,reduce it by2e f=1while key[f]<="" p="">f++end whilea=L.headif a>m thennext[prev[f]]=next[f]prev[next[f]]=prev[f]next[f]=next[a]key[f]=key[a]prev[f]=prev[a]F REE?OBJECT(a)f++while key[f]<="" p="">f++end whileend ifwhile a=L.head doif a>m thennext[prev[f]]=next[f]prev[next[f]]=prev[f]next[f]=next[a]key[f]=key[a]prev[f]=prev[a]F REE?OBJECT(a)f++while key[f]<="" p="">f++end whileend ifend while8Algorithm16PRINT-TREE(T.root) if T.root==NIL thenreturnelsePrint T.root.keyPRINT-TREE(T.root.left)PRINT-TREE(T.root.right)end ifAlgorithm17INORDER-PRINT(T) let S be an empty stack push(S,T)while S is not empty doU=pop(S)if U=NIL thenprint U.keypush(S,U.left)push(S,U.right)end ifend whileAlgorithm18PRINT-TREE(T.root) if T.root==NIL then returnelsePrint T.root.keyx=T.root.left?childwhile x=NIL doPRINT-TREE(x)x=x.right?siblingend whileend if9Algorithm19INORDER-PRINT’(T) a=T.leftprev=Twhile a=T doif prev=a.left thenprint a.keyprev=aa=a.rightelse if prev=a.right thenprev=aa=a.pelse if prev=a.p thenprev=aa=a.leftend ifend whileprint T.keya=T.rightwhile a=T doif prev=a.left thenprint a.keyprev=aa=a.rightelse if prev=a.right thenprev=aa=a.pelse if prev=a.p thenprev=aa=a.leftend ifend while10the“right”pointers until the parity of the boolean value changes,ignoring thislast node since it will be x.Problem10-1For each,we assume sorted means sorted in ascending order unsorted,single sorted,single unsorted,double sorted,double SEARCH(L,k)n n n nINSERT(L,x)1111DELET E(L,x)n n11SUCCESSOR(L,x)n1n1P REDECESSOR(L,x)n n n1 MINIMUM(L,x)n1n1MAXIMUM(L,x)n n n1 Problem10-2In all three cases,MAKE-HEAP simply creates a new list L,sets L.head=NIL,and returns L in constant time.Assume lists are doubly linked.T o realizea linked list as a heap,we imagine the usual array implementation of a binaryheap,where the children of the i th element are2i and2i+1.a.To insert,we perform a linear scan to see where to insert an element suchthat the list remains sorted.This takes linear time.The?rst element in thelist is the minimum element,and we can?nd it in constant time.Extract-minreturns the?rst element of the list,then deletes it.Union performs a mergeoperation between the two sorted lists,interleaving their entries such thatthe resulting list is sorted.This takes time linear in the sum of the lengthsof the two lists.b.To insert an element x into the heap,begin linearly scanning the list untilthe?rst instance of an element y which is strictly larger than x.If no suchlarger element exists,simply insert x at the end of the list.If y does exist,replace y t by x.This maintains the min-heap property because x≤y andy was smaller than each of its children,so x must be as well.Moreover,xis larger than its parent because y was the?rst element in the list to exceedx.Now insert y,starting the scan at the node following x.Since we checkeach node at most once,the time is linear in the size of the list.To get theminimum element,return the key of the head of the list in constant time.To extract the minimum element,we?rst call MINIM UM.Next,we’ll replacethe key of the head of the list by the key of the second smallest element yin the list.We’ll take the key stored at the end of the list and use it toreplace the key of y.Finally,we’ll delete the last element of the list,and callMIN-HEAPIFY on the list.T o implement this with linked lists,we need tostep through the list to get from element i to element2i.We omit this detailfrom the code,but we’ll consider it for runtime analysis.Since the value ofi on which MIN-HEAPIFY is called is always increasing and we never need11to step through elements multiple times,the runtime is linear in the length of the list.Algorithm20EXTRACT-MIN(L)min=MINIMUM(L)Linearly scan for the second smallest element,located in position i.L.head.key=L[i]L[i].key=L[L.length].keyDELETE(L,L[L.length])MIN-HEAPIFY(L[i],i)return minAlgorithm21MIN-HEAPIFY(L[i],i)1:l=L[2i].key2:r=L[2i+1].key3:p=L[i].key4:smallest=i5:if L[2i]=NIL and l6:smallest=2i7:end if8:if L[2i+1]=NIL and r<l[smallest]then< bdsfid="416" p=""></l[smallest]then<>9:smallest=2i+110:end if11:if smallest=i then12:exchange L[i]with L[smallest]13:MIN-HEAPIFY(L[smallest],smallest)14:end ifUnion is implemented below,where we assume A and B are the two list representations of heaps to be merged.The runtime is again linear in the lengths of the lists to be merged.c.Since the algorithms in part b didn’t depend on the elements being distinct,we can use the same ones.Problem10-3a.If the original version of the algorithm takes only t iterations,then,we havethat it was only at most t random skips though the list to get to the desired value,since each iteration of the original while loop is a possible random jump followed by a normal step through the linked list.b.The for loop on lines2-7will get run exactly t times,each of which is constantruntime.After that,the while loop on lines8-9will be run exactly X t times.So,the total runtime is O(t+E[X t]).12Algorithm22UNION(A,B)1:if A.head=NIL then2:return B3:end if4:i=15:x=A.head6:while B.head=NIL do7:if B.head.key≤x.key then8:Insert a node at the end of list B with key x.key9:x.key=B.head.key10:Delete(B,B.head)11:end if x=x.next12:end while13:return A/doc/8010751696.html,ing equation C.25,we have that E[X t]= ∞i=1P r(X t≥i).So,we needto show that P r(X t≥i)≤(1?i/n)t.This can be seen because having X t being greater than i means that each random choice will result in an element that is either at least i steps before the desired element,or is after the desired element.There are n?i such elements,out of the total n elements that we were pricking from.So,for a single one of the choices to be from such a range, we have a probability of(n?i)/n=(1?i/n).Since each of the selections was independent,the total probability that all of them were is(1?i/n)t, as /doc/8010751696.html,stly,we can note that since the linked list has length n,the probability that X t is greater than n is equal to zero.d.Since we have that t>0,we know that the function f(x)=x t is increasing,so,that means that x t≤f(x).So,n?1r=0r t=nr t dr≤nf(r)dr=e.E[X t]≤nr=1 (1?r/n)t= nr=1ti=0ti(?r/n)i= ti=0nr=1ti(?r/n)i =ti=0ti(?1)in i?1+ n?1r=0 (r)tti=0ti(?1)in i?1+n i+1/n ≤ti=0ti(?1)in ii+1=1t+1ti=0t+1i+1(?n)i≤(1?n)t+1t+1f.We just put together parts b and e to get that it runs in time O(t+n/(t+1)).But,this is the same as O(t+n/t).13g.Since we have that for any number of iterations t that the ?rst algorithm takes to ?nd its answer,the second algorithm will return it in time O (t +n/t ).In particular,if we just have that t =√n .The second algorithm takestime only O (√n ).This means that tihe ?rst list search algorithm is O (√n )as well.h.If we don’t have distinct key values,then,we may randomly select an element that is further along than we had been before,but not jump to it because it has the same key as what we were currently at.The analysis will break when we try to bound the probability that X t ≥i .14。

单词：1. die down变得越来越弱直到消失eg. When the flames die down, we will be able to see the extent(程度) of the damage.2. lick vt.舔；<口>打败 vt.& vi.轻轻拍打；战胜 n.舔；一舐的量，少量eg. The boy quickly devoured(狼吞虎咽的吃光) the delicious, home-cooked meal, and his plate could not have been cleaner had he not licked it .3. shrewd adj.精明的，敏锐的；奸诈的，狡猾的；有眼光的；精于盘算的eg. He was too shrewd to follow them upon a road which could only lead to an impasse(死胡同)。

4. penalty n.惩罚；刑罚；害处；足球点球eg. In 1969, Britain abolished(废除) the death penalty（死刑）for murder.5. in brief简而言之，简单地说eg. It’s a long letter. In brief, he says he is opposed to the project we are going to undertake.6. for one不管别人，至少……，作为其中一个，举例来说eg. Having toured the countryside for two months, I , for one, have come to believe (渐渐相信) that the situation there has never been better than now.7. guarantee n. 保证，担保；保证人，保证书；抵押品vt. 保证，担保eg. Shanghai Airlines guarantees its customers top-quality service.8. facility n. 设备；容易；能力；灵巧eg. The city’s public indoor recreation facilities(室内娱乐设施) are extensive（大量的，广泛的）, which is important for a city like Minneapolis where the winters are long.9. initial adj. 最初的；开始的；首字母的eg. Having heard about the wedding my initial reaction was one of complete disbelief.10. earn/make a living谋生eg. Now that(既然) her parents were both gone and she was left alone in the world, she needed to find a way to earn a living.11. enterprise n. 企（事）业单位；事业，计划；事业心，进取心eg. Once the bank notified them of its approval (同意；批准；赞成) of the loan (贷款；借款；借用), they began to implement (实施，执行；使生效，实现；落实；把…填满) their plans for a small business enterprise.12. agent n. 代理人；代理商；药剂；特工eg. As this place is a high-risk flood area(洪水高发区), you had better see an insurance agent（保险公司，保险代理人）soon.13. tragic adj. 悲剧的；悲惨的eg. According to the local newspaper, the tragic accident resulted in (引起，导致，以…为结局；落得；致使) the loss of three people.14. permanent adj. 永久（性）的，永恒的，不变的，耐久的，持久的，经久的；稳定的；常务的，常设的eg. Among its permanent collection(永久的收藏) is a masterpiece (杰作，名作)of the great 18th century French painter donated to (捐献给)the museum by Mr, Dawson.15. expand vt. 使…变大；扩张；详述vi. 扩展；发展；张开；展开eg. In 2001 our business was going so rapidly that we began to expand abroad.16. rumor n.谣言，<美>传闻;咕哝；vt. 谣传；传说eg. The rumors about my colleague(同事)’s love affair（婚外情）all turned out to be false, but her reputation （n. 名气，名声；信誉，声望）was hurt just the same.词组：1. play about/around鬼混eg. It’s time he stopped playing around and began to take life seriously(.认真地；严肃地；严重地).2. play at三心二意，假装……的有戏eg. This is a job that needs to be tackled whole-heartedly(全心全意), not played at.3. play back往后倒，把…打回给对方；后退一步接球；播放；重播eg. When we’ve finished the recording（记录，唱片，磁带）we’ll play it back.4. play down轻描淡写；故意缩小…的重要性；和善地对待；放低身价eg. He gave all the credit to his colleagues, and play down his own part in the discovery.5. play off (against)重新比赛，加赛；取笑; 挑拨离间eg. Always a clever diplomat（外交官）, he played off one potential （潜在的，有可能的）enemy of his country against another, so he kept them divided（分离）.6. play on/upon对……加以利用eg. The Empire played on/upon its neighbours’ fears of military expansion (军事扩张) to obtain trade concessions （贸易让步）from them.7. play up强调，着重，是突出；努力；积极地比赛；夸大；为…做广告eg. The coach (教练) played up the possibilities（可能性）, and kept our minds off our weaknesses.8. play with同…一起玩；玩弄…；（不太认真地）考虑；逗eg. He has often played with the idea of emigrating (移民) to Canada, but that’s as far as it’s gone.1. die away(尤指声音、光、风）逐渐消失，停止；昏厥；自行消失eg. Ronny’s steps died away, and there was a moment of absolute silence.2. die down变得越来越弱直到消失eg. The applause (掌声) died down and the actors were able to continue.3. die for渴望，为…而献身；<口>急需（某物）eg. In those days, she was died for a break, away from her family and household commitments（家庭承诺）.4. die from/of死于（某种原因，不包括疾病、过度悲伤等）eg. The disease from which he died was at that time incurable.5. die off相继死去，先后死去；（温度）降下来；相继死亡eg. A water shortage had struck the area(缺水区) and wild life was dying off alarmingly（令人担忧的）in the intense heat.6. die out（指物种、家族、习惯、观念等）绝迹，消失；绝种；绝灭；淘汰eg. Only those species (物种) adaptable enough to cope with changing conditions survived. The others died out.填空：There was only one exception (只有一个例外) to the rule of advance payment.A certain（某一）young man had a very wealthy uncle, living in Milwaukee, whose heir（继承人）he was, but the uncle was not getting along（进展）in years fast enough. The young man, then 18 years old, did not wish to waste the “best years of his life” as a poor boy. He wanted the money while he was young, but his uncle was as healthy as he was wealthy. The Zeritskys were the obvious answer to his problem.They undertook to deep-freeze the youth without advance payment. They further undertook to watch the Milwaukee papers until the death of the uncle should be reported, whereupon（因此）they would defrost the boy. In exchange for （作为……的交换）this, the youth, thinking of course that money would be no problem （钱不是问题）when he came out, agreed to pay double.The uncle lived 17 years longer, during which time he seems to have forgotten his nephew（侄子）and to have become deeply interested in a mystic society, to which he left his entire fortune. The Zeritskys duly（按时）defrosted the boy, and whether they or he were the more disappointed is impossible to imagine.He , poor fellow, spent the rest of his life, including the best years, paying off（还账）his debt which amounted to（数目达到）$9,400. The books record his slow but regular （定期的）payments over the next 43 years, and indicate（指出）that he had only $250 left to pay when he died.改错：Soon after Monahan’s great exposure（暴露，接触）rocked the nation, many clients leaped into（跳入，突然进入）print to tell their experiences.One story was told by the husband who had planned to be got away from（逃离……）his malicious（恶毒的）wife with the help of the Zeritskys, and (加whose) intentions（目的，意图）were unfortunately（不幸的）discovered by her. With shrewd（狡猾的）reasoning, she figured approximately （近似的，大约）the number of years he had chosen to be absent（缺席）, and put himself (改为herself) away for a like period（时期）. In a TV dramatization（剧本）rather pessimistically（悲观地）entitling (改为entitled)You Can’t Get Away , the husband described his sensations（感觉）upon being（一被……）defrosted after 15 years, only (加to) find his wife waiting for him right there in the reception room（接待室）of the Zeritsky plant（植物，草木；设备；工厂；庄稼）.“She was as perfectly preserved（保存）as I was ,” he said. “Any (改为Every) irritating（令人恼火的）habit that had made my life unbearable（无法忍受的）with her was absolutely intact（原封不动的）.”Another story came down(去掉) from the daughter of a Zeritsky client. Her father was still, at the age of one hundred and two, passionately（热情的）interested inpolitics, but the chances of his lasting until the next election was (改为were) not good. The daughter herself suggested the deep freeze and he welcomed the idea. He decided on a twenty-year stay because, in his own words, “As (改为If) the Republicans（共和主义者）can’t get into the White House in twenty years, I give up.” Of (改为Upon) his return, he found that his condition had not been fulfilled. His daughter described him as utterly（完全的）baffling (改为baffled)（受挫）by the new world. He lived in it just a week before he left it, this time for good. His last words were, “How do you people stand it?”翻译：1. 总之，这些实验室设备太贵，而且也许过时了。

第6章 堆排序本章要介绍另一种排序算法，即堆排序（heapsort）。

像合并排序而不像插入顺序，堆排O n n。

像插入排序而不像合序的运行时间为(lg)并排序，它是一种原地（inplace）排序算法：在任何时候，数组中只有常数个元素存储在输入数组以外。

这样，堆排序就把我们讨论过的两种排序算法的优点结合起来。

堆排序还引入另一种算法设计技术：利用某种数据结构（在此算法中为“堆”）来管理算法执行中的信息。

堆数据结构不只是在堆排序中有用，还可以构成一个有效的优先队列。

堆数据结构在后续章节的算法中还将重复出现。

“堆”这个词最初是在堆排序中提出的，但后来就逐渐指“废料收集存储区”，就像程序设计语言Lisp 和Java中所提供的设施那样。

我们这里的堆数据结构不是废料收集存储区；本书中以后任何地方提到堆结构，都是指本章定义的结构。

6.1 堆（二叉）堆数据结构是一种数组对象，如图6-1所示，它可以被视为一棵完全二叉树（见B.5.3节）。

树中每个结点与数组中存放该结点值的那个元素对应。

树的每一层都是填满的，最后一层可能除外（最后一层从一个结点的左子树开始填）。

表示堆的数组A是—个具有两个属性的对象；A.length是数组中的元素个数，A.heap-size 是存放在A 中的堆的元素个数。

就是说，虽然从A[1..A.length]中都可以包含有效值，但A[A.heap-size]之后的元素都不属于相应的堆，此处.A heap size −≤.A length 。

树的根为A[1]，给定了某个结点的下标i，其父结点PARENT（i）、左儿子LEFT（i）和右儿子RIGHT（i）的下标可以简单地计算出来： PARENT(i)1 return /2i ⎢⎥⎣⎦LEFT(i)1 return 2iRIGHT(i)1 return 2i+1图6-1一个最大堆（大根堆）可被看作a）一棵二叉树和b）—个数组。

圆圈中的数字表示树中每个结点存储的值，结点上方的数宇表示对应的数组下标。