Role Of The Australian Government For Unauthorised...

Introduction: The purpose of my outcome is to research comparisons between the roles of the Australian government for unauthorised arrivals found to be refugees and those who are not. According to Australian Human rights commission (2014), recently, asylum seekers who arrive without visas and by boat are detained and usually transferred to Christmas Island. On the other hand, asylum seekers who arrive in Australia by plane with appropriate documentation are granted bridging visas and released into the community pending www.humanrights.gov.au (2012). The reason of being important is issue begin from many years ago and still going, so the government has to do something and also each year the law of Australia is getting change. What is the†¦show more content†¦An asylum seeker is a person who leaves their home country for the same reasons as a refugee and has applied for protection as a refugee humanright.gov.au (2012). An asylum seeker, refugees as opposed to migrants have very different experience and reasons for leaving and moving to another country. Moreover, a refugee or an asylum seeker may not have the option to choose where to go, but migrant has. refugeecouncil.org.au (2014). What is the Australia’s humanitarian policy regarding asylum seekers and refugees? Australia Government (2015), states that, Australia has two main components in its Humanitarian program, to begin with Australia provides offshore resettlement for person who has been found to be a refugee. And processing of asylum seeker on off shore sites such as Christmas Island, Nauru and Manus Island poses a signification threat to mental and physical health amsa.org.au (2015). According to my interview (2015), with Ms Shakila Muradi ‘’we came with a fake passport from New Delhi to Kuala Lumpur, Malaysia and then we spent more money to get to Indonesia then Australia by boat. According to Australia Government (2015), Australia’s onshore Special Humanitarian Program Visa can be granted to people whose human rights are found to be exploited in their home country. The government has increased the number of resettlement place available for family members through the (SHP). And

Symbolism and Repression in The Yellow Wallpaper - 2041 Words

Symbolism and Repression in The Yellow Wallpaper Charlotte Perkins Gilman’s story, â€Å"The Yellow Wallpaper† is as a wonderful example of the gothic horror genre. It was not until the rediscovery of the story in the early 1970’s that â€Å"The Yellow Wallpaper† was recognized as a feminist indictment of a male dominated society. The story contains many typical gothic trappings, but beneath the conventional faà §ade hides a tale of repression and freedom told in intricate symbolism as seen through the eyes of a mad narrator. It is difficult to discuss the meaning in this story without first examining the author’s own personal experience. â€Å"The Yellow Wallpaper† gives an account of a woman driven to madness as a result of the†¦show more content†¦Many of the passages concerning the husband can be interpreted as containing sarcasm, a great many contain irony, and several border on parody (Johnson 528). It is true that the husband’s language is exaggerated at times, but dismissing the husband’s character as caricature seems extreme. He is instead the natural complement to the narrator’s madness and uncontrolled fancy: the character of John is control and â€Å"sanity† as defined by Victorian culture and is therefore the narrator’s opposite. Greg Johnson notes that John exhibits a near-obsession with â€Å"reason,† even as his wife grows mad. He is the narrator’s necessary counterpart, without whose stifling influence her eventual fr eedom would not be gained. And he is also transformed at the end of the tale—in a reversal of traditional gothic roles—because it is he, not a female, who faints when confronted with madness (529). Central to the story is the wallpaper itself. It is within the wallpaper that the narrator finds her hidden self and her eventual damnation/freedom. Her obsession with the paper begins subtly and then consumes both the narrator and the story. Once settled in the long-empty â€Å"ancestral estate,† a typical gothic setting, the narrator is dismayed to learn that her husband has chosen the top-floor nursery room for her. The room is papered in horrible yellow wallpaper, the design of which â€Å"commit[s] every artistic sin†(426). The design begins to fascinate the narrator and sheShow MoreRelatedCritical Analysis Of The Yellow Wallpaper1511 Words   |  7 Pagesaddress controversial social issues of the time period. One of these writers was Charlotte Perkins Gilman. Her work, â€Å"The Yellow Wallpaper†, addresses the reality of gender status and roles and the treatment of psychological disorders during the nineteenth century. When explicating her work through a psychological perspective, it is clear to see how Gilman uses setting, symbolism, and personification to portray a realistic view of a woman with a psychological disorder and her treatment. CharlotteRead MoreThe Yellow Wallpaper By Charlotte Perkins Gilman1472 Words   |  6 Pagesâ€Å"The Yellow Wallpaper,† written by Charlotte Perkins Gilman in 1892, is a great example of early works pertaining to feminism and the disease of insanity. Charlotte Gilman’s own struggles as a woman, mother, and wife shine through in this short story capturing the haunting realism of a mental breakdown.The main character, much like Gilman herself, slips into bouts of depression after the birth of her child and is prescribed a ‘rest cure’ to relieve the young woman of her suffering. Any use of theRead MoreComparison and Contrast of the Yellow Wallpaper and the Rose for Emily1078 Words   |  5 PagesParis Claypool Eng 120 Essay 1 06/12/2010 A Rose for Emily and The Yellow Wallpaper â€Å"A Rose for Emily’’ By William Faulkner and â€Å"The Yellow Wallpaper by Charlotte Perkins Gilman,† are two short stories that both incorporate qualities of similarities and difference. Both of the short stories are about how and why these women changed for lunacy. These women are forced into solitude because of the fact that they are women. Emily’s fatherRead MoreThemes, Symbols, and Feelings in The Yellow Wallpaper by Charlotte Perkins Gilman763 Words   |  4 PagesIn The Yellow Wallpaper, by Charlotte Perkins Gilman, the protagonist symbolizes the effect of the oppression of women in society in the Nineteenth Century. In The Yellow Wallpaper, the author reveals the narrator is torn between hate and love, but emotion is difficult to determine. The effects are produced by the use of complex themes used in the story, which assisted her oppression and reflected on her self-expression. The yellow wallpaper is a symbol of oppression in a woman who felt herRead MoreThe Yellow Wallpaper By Charlotte Gilman992 Words   |  4 Pagesâ€Å"The yellow wallpaper† The Yellow Wallpaper is a story about women’s repression in the 19th century. This story shows an immense difference between men and women inside society. While the men are the one making the decisions and taking responsibility, women must accept their obligations. The protagonist is repressed and appear for the effect of the oppression of women in society. This effect is develop by the use of complex symbols such as, the room, the wallpaper, the window which facilitates herRead MoreThe Yellow Wallpaper829 Words   |  4 Pages The Yellow Wallpaper Charlotte Perkins Gilmans The Yellow Wallpaper first appeared in 1892 and became a notary piece of literature for it s historical and influential context. Gilmans The Yellow Wallpaper was a first hand account of the oppression faced toward females and the mentally ill,whom were both shunned in society in the late 1890s. It is the story of an unnamed woman confined by her doctor-husband to an attic nursery with barred windows and a bolted down bed. Forbidden to writeRead MoreAnalysis Of The Poem The Yellow Wallpaper 1332 Words   |  6 Pagesmoonlight makes the woman behind the wallpaper become clearer night by night. This personification describes the way insanity is creeping onto the narrator. For a very long time, the moon associates with early fertility-centered societies and female power. In â€Å"The Yellow Wallpaper,† the contrast between daytime with its constant limitations and nighttime with its unpredictable freedoms are symbolized by the alternating effects of sun and moonlight on the wallpaper. During the daytime the freedom ofRead MoreThe Cult Of The Yellow Wallpaper By Charlotte Perkins Gilman1371 Words   |  6 PagesMichael Zhao K. Keogh AP Lit. Period 3 22 January 2015 The Cult of Domesticity â€Å"The Yellow Wallpaper,† by Charlotte Perkins Gilman, depicts a young woman’s gradual descent into insanity due to her entrapment, both mentally and physically, in the restrictive cult of domesticity. Through the narrator’s creeping spiral into madness, Gilman seeks to shed light upon the torturous and constraining societal conditions in which women are expected to live, that permeates throughout all aspects of their livesRead MoreThe Yellow Wallpaper By Charlotte Perkins Gilman1205 Words   |  5 PagesCharlotte Perkins Gilman’s â€Å"The Yellow Wallpaper†, written in 1892, is a short story told from the perspective of a woman believed to be â€Å"crazy†. The narrator believes her craziness to be a form of sickness. However, the narrator’s husband, John, believes her to be suffering from a temporary nervous depression. As the narrator’s condition worsens, she begins to see a woman moving from behind the yellow wallpaper in their bedroom. The wallpaper captures the narrator’s attention and as a result drivesRead MoreThe Yellow Wallpaper, By Katherine Perkins Gilman And Ms. Brill1206 Words   |  5 Pagesthat most affect people. Loneliness is about feeling disconnected from the rest of the world. Being isolated have a negative impact on society, but it will also have a negative impact on the person being isolated. The two short stories, â€Å"The Yellow Wallpaper† by Charlotte Perkins Gilman and â€Å"Ms. Brill† by Katherine Mansfield focuses on the way two women experience loneliness, isolation, and social expectation in their society. Social expectations may hold back women from achieving their fullest potential

Data Structures and Algorithm Analysis in C - Mark Allen Weiss free essay sample

Structures, Algorithm Analysis: Table of Contents ,1/1 Data Structures and Algorithm Analysis in C by Mark Allen Weiss PREFACE CHAPTER 1: INTRODUCTION CHAPTER 2: ALGORITHM ANALYSIS CHAPTER 3: LISTS, STACKS, AND QUEUES CHAPTER 4: TREES CHAPTER 5: HASHING CHAPTER 6: PRIORITY QUEUES (HEAPS) CHAPTER 7: SORTING CHAPTER 8: THE DISJOINT SET ADT CHAPTER 9: GRAPH ALGORITHMS CHAPTER 10: ALGORITHM DESIGN TECHNIQUES CHAPTER 11: AMORTIZED ANALYSIS mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: PREFACE ,1/4 PREFACE Purpose/Goals Return to Table of Contents Next Chapter This book describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 16 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored. Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they solve have become larger and more complex, thus requiring development of more intricate programs to solve the problems. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. This book is suitable for either an advanced data structures (CS7) course or a first-year graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers and recursion, and some background in discrete math. Approach I believe it is important for students to learn how to program for themselves, not how to copy programs from a book. On the other hand, it is virtually impossible to discuss realistic programming issues without including sample code. For this reason, the book usually provides about half to three-quarters of an implementation, and the student is encouraged to supply the rest. The algorithms in this book are presented in ANSI C, which, despite some flaws, is arguably the most popular systems programming language. The use of C instead of Pascal allows the use of dynamically allocated arrays (see for instance rehashing in Ch. 5). It also produces simplified code in several places, usually because the and () operation is short-circuited. Most criticisms of C center on the fact that it is easy to write code that is barely readable. Some of the more standard tricks, such as the simultaneous assignment and testing against 0 via if (x=y) are generally not used in the text, since the loss of clarity is compensated by mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: PREFACE ,2/4 only a few keystrokes and no increased speed. I believe that this book demonstrates that unreadable code can be avoided by exercising reasonable care. Overview Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5. Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an indepth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail. Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using ADTS, fast implementation of these data structures, and an exposition of some of their uses. There are almost no programs (just routines), but the exercises contain plenty of ideas for programming assignments. Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced but not analyzed. Seventyfive percent of the code is written, leaving similar cases to be completed by the student. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters. Chapter 5 is a relatively short chapter concerning hash tables. Some analysis is performed and extendible hashing is covered at the end of the chapter. Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important general-purpose sorting algorithms are covered and compared. Three algorithms are analyzed in detail: insertion sort, Shellsort, and quicksort. External sorting is covered at the end of the chapter. Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskals algorithm is not discussed. Chapter 9 covers graph algorithms. Algorithms on graphs are interesting not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: PREFACE ,3/4 context, a short discussion on complexity theory (including NP-completeness and undecidability) is provided. Chapter 10 covers algorithm design by examining common problem-solving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the students appreciation of an example algorithm is not obscured by implementation details. Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed. Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnsons book on NP-completeness can be used to augment this text. Exercises Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section. Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks. A solutions manual containing solutions to almost all the exercises is available separately from The Benjamin/Cummings Publishing Company. References References are placed at the end of each chapter. Generally the references either are historical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises. Acknowledgments I would like to thank the many people who helped me in the preparation of this and previous versions of the book. The professionals at Benjamin/Cummings made my book a considerably less harrowing experience than I had been led to expect. Id like to thank my previous editors, Alan Apt and John Thompson, as well as Carter Shanklin, who has edited this version, and Carters assistant, Vivian McDougal, for answering all my questions and putting up with my delays. Gail Carrigan at Benjamin/Cummings and Melissa G. Madsen and Laura Snyder at Publication Services did a wonderful job with production. The C version was handled by Joe Heathward and his outstanding staff, who were able to meet the production schedule despite the delays caused by Hurricane Andrew. I would like to thank the reviewers, who provided valuable comments, many of mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: PREFACE ,4/4 which have been incorporated into the text. Alphabetically, they are Vicki Allan (Utah State University), Henry Bauer (University of Wyoming), Alex Biliris (Boston University), Jan Carroll (University of North Texas), Dan Hirschberg (University of California, Irvine), Julia Hodges (Mississippi State University), Bill Kraynek (Florida International University), Rayno D. Niemi (Rochester Institute of Technology), Robert O. Pettus (University of South Carolina), Robert Probasco (University of Idaho), Charles Williams (Georgia State University), and Chris Wilson (University of Oregon). I would particularly like to thank Vicki Allan, who carefully read every draft and provided very detailed suggestions for improvement. At FIU, many people helped with this project. Xinwei Cui and John Tso provided me with their class notes. Id like to thank Bill Kraynek, Wes Mackey, Jai Navlakha, and Wei Sun for using drafts in their courses, and the many students who suffered through the sketchy early drafts. Maria Fiorenza, Eduardo Gonzalez, Ancin Peter, Tim Riley, Jefre Riser, and Magaly Sotolongo reported several errors, and Mike Hall checked through an early draft for programming errors. A special thanks goes to Yuzheng Ding, who compiled and tested every program in the original book, including the conversion of pseudocode to Pascal. Id be remiss to forget Carlos Ibarra and Steve Luis, who kept the printers and the computer system working and sent out tapes on a minutes notice. This book is a product of a love for data structures and algorithms that can be obtained only from top educators. Id like to take the time to thank Bob Hopkins, E. C. Horvath, and Rich Mendez, who taught me at Cooper Union, and Bob Sedgewick, Ken Steiglitz, and Bob Tarjan from Princeton. Finally, Id like to thank all my friends who provided encouragement during the project. In particular, Id like to thank Michele Dorchak, Arvin Park, and Tim Snyder for listening to my stories; Bill Kraynek, Alex Pelin, and Norman Pestaina for being civil next-door (office) neighbors, even when I wasnt; Lynn and Toby Berk for shelter during Andrew, and the HTMC for work relief. Any mistakes in this book are, of course, my own. I would appreciate reports of any errors you find; my e-mail address is [emailprotected] du. M. A. W. Miami, Florida September 1992 Go to Chapter 1 Return to Table of Contents mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,1/14 CHAPTER 1: INTRODUCTION Previous Chapter Return to Table of Contents Next Chapter In this chapter, we discuss the aims a nd goals of this text and briefly review programming concepts and discrete mathematics. We will See that how a program performs for reasonably large input is just as important as its performance on moderate amounts of input. Review good programming style. Summarize the basic mathematical background needed for the rest of the book. Briefly review recursion. 1. 1. Whats the Book About? Suppose you have a group of n numbers and would like to determine the kth largest. This is known as the selection problem. Most students who have had a programming course or two would have no difficulty writing a program to solve this problem. There are quite a few obvious solutions. One way to solve this problem would be to read the n numbers into an array, sort the array in decreasing order by some simple algorithm such as bubblesort, and then return the element in position k. A somewhat better algorithm might be to read the first k elements into an array and sort them (in decreasing order). Next, each remaining element is read one by one. As a new element arrives, it is ignored if it is smaller than the kth element in the array. Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. When the algorithm ends, the element in the kth position is returned as the answer. Both algorithms are simple to code, and you are encouraged to do so. The natural questions, then, are which algorithm is better and, more importantly, is either algorithm good enough? A simulation using a random file of 1 million elements and k = 500,000 will show that neither algorithm finishes in a reasonable amount of timeeach requires several days of computer processing to terminate (albeit eventually with a correct answer). An alternative method, discussed in Chapter 7, gives a solution in about a second. Thus, although our proposed algorithms work, they cannot be considered good algorithms, because they are entirely impractical for input sizes that a third algorithm can handle in a reasonable amount of time. A second problem is to solve a popular word puzzle. The input consists of a twodimensional array of letters and a list of words. The object is to find the words in the puzzle. These words may be horizontal, vertical, or diagonal in any mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,2/14 direction. As an example, the puzzle shown in Figure 1. 1 contains the words this, two, fat, and that. The word this begins at row 1, column 1 (1,1) and extends to (1, 4); two goes from (1, 1) to (3, 1); fat goes from (4, 1) to (2, 3); and that goes from (4, 4) to (1, 1). Again, there are at least two straightforward algorithms that solve the problem. For each word in the word list, we check each ordered triple (row, column, orientation) for the presence of the word. This amounts to lots of nested for loops but is basically straightforward. Alternatively, for each ordered quadruple (row, column, orientation, number of characters) that doesnt run off an end of the puzzle, we can test whether the word indicated is in the word list. Again, this amounts to lots of nested for loops. It is possible to save some time if the maximum number of characters in any word is known. It is relatively easy to code up either solution and solve many of the real-life puzzles commonly published in magazines. These typically have 16 rows, 16 columns, and 40 or so words. Suppose, however, we consider the variation where only the puzzle board is given and the word list is essentially an English dictionary. Both of the solutions proposed require considerable time to solve this problem and therefore are not acceptable. However, it is possible, even with a large word list, to solve the problem in a matter of seconds. An important concept is that, in many problems, writing a working program is not good enough. If the program is to be run on a large data set, then the running time becomes an issue. Throughout this book we will see how to estimate the running time of a program for large inputs and, more importantly, how to compare the running times of two programs without actually coding them. We will see techniques for drastically improving the speed of a program and for determining program bottlenecks. These techniques will enable us to find the section of the code on which to concentrate our optimization efforts. 1 2 3 4 1 2 3 4 t w o f h a a g i t h d s s g t Figure 1. 1 Sample word puzzle . 2. Mathematics Review This section lists some of the basic formulas you need to memorize or be able to derive and reviews basic proof techniques. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,3/14 1. 2. 1. Exponents xa xb = xa+b xa -xb (xa)b = xab = xa-b xn + xn = 2xn 2n + 2n = 2n+1 x2n 1. 2. 2. Logarithms In computer science, all logarithms are to base 2 unless specified otherwise. DEFINITION: xa = b if and only if logx b = a Several convenient equalities follow from this definition. THEOREM 1. . PROOF: Let x = logc b, y = logc a, and z = loga b. Then, by the definition of logarithms, cx = b, cy = a, and az = b. Combining these three equalities yields (cy)z = cx = b. Therefore, x = yz, which implies z = x/y, proving the theorem. THEOREM 1. 2. log ab = log a + log b PROOF: Let x = log a, y = log b, z = log ab. Then, assuming the default base of 2, 2x= a, 2y = b, 2z = ab. Combining the last three equalities yields 2x2y = 2z = ab. Therefore, x + y = z, which proves the theorem. Some other useful formulas, which can all be derived in a similar manner, follow. log a/b = log a log b k:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,4/14 log(ab) = b log a log x x for all x 0 log 1 = 0, log 2 = 1, log 1,024 = 10, log 1,048,576 = 20 1. 2. 3. Series The easiest formulas to remember are and the companion, In the latter formula, if 0 a 1, then and as n tends to , the sum approaches 1/(1 -a). These are the geometric series formulas. in the following manner. Let S be the sum. We can derive the last formula for Then S = 1 + a + a2 + a3 + a4 + a5 + . . . Then S = a + a2 + a3 + a4 + a5 + . . . If we subtract these two equations (which is permissible only for a convergent series), virtually all the terms on the right side cancel, leaving S aS = 1 which implies that We can use this same technique to compute , a sum that occurs frequently. We write mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,5/14 and multiply by 2, obtaining Subtracting these two equations yields Thus, S = 2. Another type of common series in analysis is the arithmetic series. Any such series can be evaluated from the basic formula. For instance, to find the sum 2 + 5 + 8 +. . . + (3k 1), rewrite it as 3(1 + 2+ 3 +. . . + k) (1 + 1 + 1 +. . . + 1), which is clearly 3k(k + 1)/2 k. Another way to remember this is to add the first and last terms (total 3k + 1), the second and next to last terms (total 3k + 1), and so on. Since there are k/2 of these pairs, the total sum is k(3k + 1)/2, which is the same answer as before. The next two formulas pop up now and then but are fairly infrequent. When k = -1, the latter formula is not valid. We then need the following formula, which is used far more in computer science than in other mathematical disciplines. The numbers, HN, are known as the harmonic numbers, and the sum is known as a harmonic sum. The error in the following approximation tends to y 0. 57721566, which is known as Eulers constant. These two formulas are just general algebraic manipulations. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,6/14 1. 2. 4. Modular Arithmetic We say that a is congruent to b modulo n, written a b(mod n), if n divides a b. Intuitively, this means that the remainder is the same when either a or b is divided by n. Thus, 81 and a d 61 1(mod 10). As with equality, if a b (mod n), then a + c b + c(mod n) b d (mod n). There are a lot of theorems that apply to modular arithmetic, some of which require extraordinary proofs in number theory. We will use modular arithmetic sparingly, and the preceding theorems will suffice. 1. 2. 5. The P Word The two most common ways of proving statements in data structure analysis are proof by induction and proof by contradiction (and occasionally a proof by intimidation, by professors only). The best way of proving that a theorem is false is by exhibiting a counterexample. Proof by Induction A proof by induction has two standard parts. The first step is proving a base case, that is, establishing that a theorem is true for some small (usually degenerate) value(s); this step is almost always trivial. Next, an inductive hypothesis is assumed. Generally this means that the theorem is assumed to be true for all cases up to some limit k. Using this assumption, the theorem is then shown to be true for the next value, which is typically k + 1. This proves the theorem (as long as k is finite). As an example, we prove that the Fibonacci numbers, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, . . . 1. (Some definitions have F0 = 0, which , Fi = Fi-1 + Fi-2, satisfy Fi ; (5/3)i, for i shifts the series. ) To do this, we first verify that the theorem is true for the trivial cases. It is easy to verify that F1 = 1 ; 5/3 and F2 = 2 112. Proof by Contradiction Proof by contradiction proceeds by assuming that the theorem is false and showing that this assumption implies that some known property is false, and hence the original assumption was erroneous. A classic example is the proof that there is an infinite number of primes. To prove this, we assume that the theorem is false, so that there is some largest prime pk. Let p1, p2, . . . , pk be all the primes in order and consider N = p1p2p3. . . pk + 1 Clearly, N is larger than pk, so by assumption N is not prime. However, none of p1, p2, . . . , pk divide N exactly, because there will always be a remainder of 1. This is a contradiction, because every number is either prime or a product of primes. Hence, the original assumption, that pk is the largest prime, is false, which implies that the theorem is true. nt f( int x ) { /*1*/ /*2*/ else /*3*/ } return( 2*f(x-1) + x*x ); if ( x = 0 ) return 0; Figure 1. 2 A recursive function 1. 3. A Brief Introduction to Recursion Most mathematical functions that we are familiar with are described by a simple formula. For instance, we can convert temperatures from Fahrenheit to Celsius by applying the formula C = 5(F 32)/9 Given this formula, it is trivial to write a C function; with declarations and braces removed, the one-line formula translates to one line of C. Mathematical functions are sometimes defined in a less standard form. As an example, we can define a function f, valid on nonnegative integers, that satisfies f(0) = 0 and f(x) = 2f(x 1) + x2. From this definition we see that f(1) = 1, f(2) = 6, f(3) = 21, and f(4) = 58. A function that is defined in terms of itself is called recursive. C allows functions to be recursive. * It is important to remember that what C provides is merely an attempt to follow the recursive spirit. Not all mathematically recursive functions are efficiently (or correctly) implemented by Cs simulation of recursion. The idea is that the recursive function f ought to be expressible in mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,9/14 only a few lines, just like a non-recursive function. Figure 1. 2 shows the recursive implementation of f. *Using recursion for numerical calculations is usually a bad idea. We have done so to illustrate the basic points. Lines 1 and 2 handle what is known as the base case, that is, the value for which the function is directly known without resorting to recursion. Just as declaring f(x) = 2 f(x 1) + x2 is meaningless, mathematically, without including the fact that f (0) = 0, the recursive C function doesnt make sense without a base case. Line 3 makes the recursive call. There are several important and possibly confusing points about recursion. A common question is: Isnt this just circular logic? The answer is that although we are defining a function in terms of itself, we are not defining a particular instance of the function in terms of itself. In other words, evaluating f(5) by computing f(5) would be circular. Evaluating f(5) by computing f(4) is not circularunless, of course f(4) is evaluated by eventually computing f(5). The two most important issues are probably the how and why questions. In Chapter 3, the how and why issues are formally resolved. We will give an incomplete description here. It turns out that recursive calls are handled no differently from any others. If f is called with the value of 4, then line 3 requires the computation of 2 * f(3) + 4 * 4. Thus, a call is made to compute f(3). This requires the computation of 2 * f(2) + 3 * 3. Therefore, another call is made to compute f(2). This means that 2 * f(1) + 2 * 2 must be evaluated. To do so, f(1) is computed as 2 * f(0) + 1 * 1. Now, f(0) must be evaluated. Since this is a base case, we know a priori that f(0) = 0. This enables the completion of the calculation for f(1), which is now seen to be 1. Then f(2), f(3), and finally f(4) can be determined. All the bookkeeping needed to keep track of pending function calls (those started but waiting for a recursive call to complete), along with their variables, is done by the computer automatically. An important point, however, is that recursive calls will keep on being made until a base case is reached. For instance, an attempt to evaluate f(-1) will result in calls to f(-2), f(-3), and so on. Since this will never get to a base case, the program wont be able to compute the answer (which is undefined anyway). Occasionally, a much more subtle error is made, which is exhibited in Figure 1. 3. The error in the program in Figure 1. 3 is that bad(1) is defined, by line 3, to be bad(1). Obviously, this doesnt give any clue as to what bad(1) actually is. The computer will thus repeatedly make calls to bad(1) in an attempt to resolve its values. Eventually, its bookkeeping system will run out of space, and the program will crash. Generally, we would say that this function doesnt work for one special case but is correct otherwise. This isnt true here, since bad(2) calls bad(1). Thus, bad(2) cannot be evaluated either. Furthermore, bad(3), bad(4), and bad(5) all make calls to bad (2). Since bad(2) is unevaluable, none of these values are either. In fact, this program doesnt work for any value of n, except 0. With recursive programs, there is no such thing as a special case. These considerations lead to the first two fundamental rules of recursion: 1. Base cases. You must always have some base cases, which can be solved without recursion. . Making progress. For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case. Throughout this book, we will use recursion to solve problems. As an example of a nonmathematical use, consider a large dictionary. Words in dictionaries are defined in terms of other words. When we look up a word, we might not always understand the definition, so we might have to look up words in the definition. Likewise, we might not understand some of those, so we might have to continue this search for a while. As the dictionary is finite, eventually either we will come to a point where we understand all of the words in some definition (and thus understand that definition and retrace our path through the other definitions), or we will find that the definitions are circular and we are stuck, or that some word we need to understand a definition is not in the dictionary. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,10/14 int bad( unsigned int n ) { /*2*/ else /*3*/ } return 0; return( bad (n/3 + 1) + n 1 ); Figure 1. 3 A nonterminating recursive program Our recursive strategy to understand words is as follows: If we know the meaning of a word, then we are done; otherwise, we look the word up in the dictionary. If we understand all the words in the definition, we are done; otherwise, we figure out what the definition means by recursively looking up the words we dont know. This procedure will terminate if the dictionary is well defined but can loop indefinitely if a word is either not defined or circularly defined. Printing Out Numbers Suppose we have a positive integer, n, that we wish to print out. Our routine will have the heading print_out(n). Assume that the only I/O routines available will take a single-digit number and output it to the terminal. We will call this routine print_digit; for example, print_digit(4) will output a 4 to the terminal. Recursion provides a very clean solution to this problem. To print out 76234, we need to first print out 7623 and then print out 4. The second step is easily accomplished with the statement print_digit(n%10), but the first doesnt seem any simpler than the original problem. Indeed it is virtually the same problem, so we can solve it recursively with the statement print_out(n/10). This tells us how to solve the general problem, but we still need to make sure that the program doesnt loop indefinitely. Since we havent defined a base case yet, it is clear that we still n ; 10. Now print_out(n) is have something to do. Our base case will be print_digit(n) if 0 defined for every positive number from 0 to 9, and larger numbers are defined in terms of a smaller positive number. Thus, there is no cycle. The entire procedure* is shown Figure 1. 4. *The term procedure refers to a function that returns void. We have made no effort to do this efficiently. We could have avoided using the mod routine (which is very expensive) because n%10 = n n/10 * 10. Recursion and Induction Let us prove (somewhat) rigorously that the recursive number-printing program works. To do so, well use a proof by induction. THEOREM 1. 4 mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,11/14 The recursive number-printing algorithm is correct for n PROOF: 0. First, if n has one digit, then the program is trivially correct, since it merely makes a call to print_digit. Assume then that print_out works for all numbers of k or fewer digits. A number of k + 1 digits is expressed by its first k digits followed by its least significant digit. But the n/10 , which, by the indicated hypothesis number formed by the first k digits is exactly is correctly printed, and the last digit is n mod10, so the program prints out any (k + 1)-digit number correctly. Thus, by induction, all numbers are correctly printed. void print_out( unsigned int n ) /* print nonnegative n */ { if( n 0 b. log(ab) = b log a 1. 6 Evaluate the following sums: mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. n. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ,13/14 1. 7 Estimate *1. 8 What is 2100 (mod 5)? 1. 9 Let Fi be the Fibonacci numbers as defined in Section 1. 2. Prove the following: **c. Give a precise closed-form expression for Fn. 1. 10 Prove the following formulas: References There are many good textbooks covering the mathematics reviewe d in this chapter. A small subset is [1], [2], [3], [11], [13], and [14]. Reference [11] is specifically geared toward the analysis of algorithms. It is the first volume of a three-volume series that will be cited throughout this text. More advanced material is covered in [6]. Throughout this book we will assume a knowledge of C [10]. Occasionally, we add a feature where necessary for clarity. We also assume familiarity with pointers and recursion (the recursion summary in this chapter is meant to be a quick review). We will attempt to provide hints on their use where appropriate throughout the textbook. Readers not familiar with these should consult [4], [8], [12], or any good intermediate programming textbook. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTION ? ,14/14 General programming style is discussed in several books. Some of the classics are [5], [7], and [9]. 1. M. O. Albertson and J. P. Hutchinson, Discrete Mathematics with Algorithms, John Wiley Sons, New York, 1988. 2. Z. Bavel, Math Companion for Computer Science, Reston Publishing Company, Reston, Va. , 1982. 3. R. A. Brualdi, Introductory Combinatorics, North- Holland, New York, 1977. 4. W. H. Burge, Recursive Programming Techniques, Addison-Wesley, Reading, Mass. , 1975. 5. E. W. Dijkstra, A Discipline of Programming, Prentice Hall, Englewood Cliffs, N. J. , 1976. 6. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Mass. , 1989. 7. D. Gries, The Science of Programming, Springer-Verlag, New York, 1981. 8. P. Helman and R. Veroff, Walls and Mirrors: Intermediate Problem Solving and Data Structures, 2d ed. , Benjamin Cummings Publishing, Menlo Park, Calif. , 1988. 9. B. W. Kernighan and P. J. Plauger, The Elements of Programming Style, 2d ed. , McGraw- Hill, New York, 1978. 10. B. W. Kernighan and D. M. Ritchie, The C Programming Language, 2d ed. , Prentice Hall, Englewood Cliffs, N. J. , 1988. 11. D. E. Knuth, The Art of Computer Programming, Vol. : Fundamental Algorithms, 2d ed. , Addison-Wesley, Reading, Mass. , 1973. 12. E. Roberts, Thinking Recursively, John Wiley Sons, New York, 1986. 13. F. S. Roberts, Applied Combinatorics, Prentice Hall, Englewood Cliffs, N. J. , 1984. 14. A. Tucker, Applied Combinatorics, 2d ed. , John Wiley Sons, New York, 1984. Go to Chapter 2 Return to Table of Contents mk:@MSITStore:K:Data. Str uctures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 2: ALGORITHM ANALYSIS ,1/30 CHAPTER 2: ALGORITHM ANALYSIS Previous Chapter Return to Table of Contents Next Chapter An algorithm is a clearly specified set of simple instructions to be followed to solve a problem. Once an algorithm is given for a problem and decided (somehow) to be correct, an important step is to determine how much in the way of resources, such as time or space, the algorithm will require. An algorithm that solves a problem but requires a year is hardly of any use. Likewise, an algorithm that requires a gigabyte of main memory is not (currently) useful. In this chapter, we shall discuss How to estimate the time required for a program. How to reduce the running time of a program from days or years to fractions of a second. The results of careless use of recursion. Very efficient algorithms to raise a number to a power and to compute the greatest common divisor of two numbers. 2. 1. Mathematical Background The analysis required to estimate the resource use of an algorithm is generally a theoretical issue, and therefore a formal framework is required. We begin with some mathematical definitions. Throughout the book we will use the following four definitions: DEFINITION: T(n) = O(f(n)) if there are constants c and n0 such that T(n) (n) when n cf n0. (g(n)) if there are constants c and n0 such that T(n) DEFINITION: T(n) = cg(n) when n n0. (h(n)) if and only if T(n) = O(h(n)) and T(n) = (p(n)). (h(n)). DEFINITION: T(n) = DEFINITION: T(n) = o(p(n)) if T(n) = O(p(n)) and T(n) mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 2: ALGORITHM ANALYSIS ,2/30 The idea of these definitions is to establish Given two functions, there are usually points the other function, so it does not make sense (n). Thus, we compare their relative rates of analysis of algorithms, we shall see why this a relative order among functions. here one function is smaller than to claim, for instance, f(n) g growth. When we apply this to the is the important measure. Although 1,000n is larger than n2 for small values of n, n2 grows at a faster rate, and thus n2 will eventually be the larger function. The turning point is n = 1,000 in this case. The first definition says that eventually there is some point n0 past which c f (n) is always at leas t as large as T(n), so that if constant factors are ignored, f(n) is at least as big as T(n). In our case, we have T(n) = 1,000n, f(n) = n2, n0 = 1,000, and c = 1. We could also use n0 = 10 and c = 100. Thus, we can say that 1,000n = O(n2) (order n-squared). This notation is known as Big-Oh notation. Frequently, instead of saying order . . . , one says Big-Oh . . . . If we use the traditional inequality operators to compare growth rates, then the first definition says that the growth rate of T(n) is less than or equal to ( ) that of f(n). The second definition, T(n) = (g(n)) (pronounced omega), ) that of g says that the growth rate of T(n) is greater than or equal to ( (n). The third definition, T(n) = (h(n)) (pronounced theta), says that the growth rate of T(n) equals ( = ) the growth rate of h(n). The last definition, T (n) = o(p(n)) (pronounced little-oh), says that the growth rate of T(n) is less than ( n, then mmod n m/2. PROOF: There are two cases. If n m/2, then obviously, since the remainder is smaller than n, the theorem is true for this case. The other case is n m/2. But then n goes into m once with a remainder m n m/2, proving the theorem. One might wonder if this is the best bound possible, since 2 log n is about 20 for our example, and only seven operations were performed. It turns out that the constant can be improved slightly, to roughly 1. 4 log n, in the worst case (which is achievable if m and n are consecutive Fibonacci numbers). The averagecase performance of Euclids algorithm requires pages and pages of highly sophisticated mathematical analysis, and it turns out that the average number of iterations is about . Exponentiation Our last example in this section deals with raising an integer to a power (which is also an integer). Numbers that result from exp onentiation are generally quite mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 2: ALGORITHM ANALYSIS ,22/30 arge, so an analysis only works if we can assume that we have a machine that can store such large integers (or a compiler that can simulate this). We will count the number of multiplications as the measurement of running time. int pow( int x, unsigned int n) { /*1*/ /*2*/ /*1*/ /*4*/ /*5*/ /*6*/ else /*7*/ } return( pow( x*x, n/2 ) * x ); if( n == 0 ) return 1; if( n == 1 ) return x; if( even( n ) ) return( pow( x*x, n/2 ) ); Figure 2. 11 Efficient exponentiation The obvious algorithm to compute xn uses n 1 multiples. The recursive algorithm in Figure 2. 11 does better. Lines 1 to 4 handle the base case of the recursion. Otherwise, if n is even, we have xn = xn/2 . xn/2, and if n is odd, x = x(n-1)/2 x(n-1)/2 x. For instance, to compute x62, the algorithm does the following calculations, which involves only nine multiplications: x3 = (x2)x, x7 = (x3)2x, x15 = (x7)2x, x31 = (x15)2x, x62 = (x31)2 The number of multiplications required is clearly at most 2 log n, because at most two multiplications (if n is odd) are required to halve the problem. Again, a recurrence formula can be written and solved. Simple intuition obviates the need for a brute-force approach. It is sometimes interesting to see how much the code can be tweaked without affecting correctness. In Figure 2. 11, lines 3 to 4 are actually unnecessary, because if n is 1, then line 7 does the right thing. Line 7 can also be rewritten as /*7*/ return( pow( x, n-1 ) * x ); without affecting the correctness of the program. Indeed, the program will still run in O(log n), because the sequence of multiplications is the same as before. However, all of the following alternatives for line 6 are bad, even though they look correct: mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 2: ALGORITHM ANALYSIS ,23/30 /*6a*/ /*6b*/ /*6c*/ eturn( pow( pow( x, 2 ), n/2 ) ); return( pow( pow( x, n/2 ), 2 ) ); return( pow( x, n/2 ) * pow( x, n/2 ) ); Both lines 6a and 6b are incorrect because when n is 2, one of the recursive calls to pow has 2 as the second argument. Thus, no progress is made, and an infinite loop results (in an eventual crash). Using line 6c affects the efficiency, because there are now two recursive calls of size n/2 instead of only one. An analysis will show that the running time is no longer O(log n). We leave it as an exercise to the reader to determine the new running time. 2. 4. 5 Checking Your Analysis Once an analysis has been performed, it is desirable to see if the answer is correct and as good as possible. One way to do this is to code up the program and see if the empirically observed running time matches the running time predicted by the analysis. When n doubles, the running time goes up by a factor of 2 for linear programs, 4 for quadratic programs, and 8 for cubic programs. Programs that run in logarithmic time take only an additive constant longer when n doubles, and programs that run in O(n log n) take slightly more than twice as long to run under the same circumstances. These increases can be hard to spot if the lower-order terms have relatively large coefficients and n is not large enough. An example is the jump from n = 10 to n = 100 in the running time for the various implementations of the maximum subsequence sum problem. It also can be very difficult to differentiate linear programs from O(n log n) programs purely on empirical evidence. Another commonly used trick to verify that some program is O(f(n)) is to compute the values T(n)/ f(n) for a range of n (usually spaced out by factors of 2), where T(n) is the empirically observed running time. If f(n) is a tight answer for the running time, then the computed values converge to a positive constant. If f(n) is an over-estimate, the values converge to zero. If f (n) is an under-estimate and hence wrong, the values diverge. As an example, the program fragment in Figure 2. 12 computes the probability that two distinct positive integers, less than or equal to n and chosen randomly, are relatively prime. (As n gets large, the answer approaches 6/ 2. ) You should be able to do the analysis for this program instantaneously. Figure 2. 13 shows the actual observed running time for this routine on a real computer. The table shows that the last column is most likely, and thus the analysis that you should have gotten is probably correct. Notice that there is not a great deal of difference between O(n2) and O(n2 log n), since logarithms grow so slowly. 2. 4. 6. A Grain of Salt Sometimes the analysis is shown empirically to be an over-estimate. If this is the case, then either the analysis needs to be tightened (usually by a clever observation), or it may be the case that the average running time is significantly less than the worst-case running time and no improvement in the bound is possible. There are many complicated algorithms for which the worstcase bound is achievable by some bad input but is usually an over-estimate in practice. Unfortunately, for most of these problems, an average-case analysis is extremely complex (in many cases still unsolved), and a worst-case bound, even though overly pessimistic, is the best analytical result known. rel = 0; tot = 0; for( i=1; inext; free( p ); p = tmp; p = L-;next; L-;next = NULL; while( p ! = NULL ) /* header assumed */ Figure 3. 15 Correct way to delete a list Figure 3. 16 A doubly linked list 3. 2. 5. Doubly Linked Lists Sometimes it is convenient to traverse lists backwards. The standard implementation does not help here, but the solution is simple. Merely add an extra field to the data structure, containing a pointer to the previous cell. The cost of this is an extra link, which adds to the space requirement and also doubles the cost of insertions and deletions because there are more pointers to fix. On the other hand, it simplifies deletion, because you no longer have to refer to a key by using a pointer to the previous cell; this information is now at hand. Figure 3. 16 shows a doubly linked list. 3. 2. 6. Circularly Linked Lists A popular convention is to have the last cell keep a pointer back to the first. This can be done with or without a header (if the header is present, the last cell points to it), and can also be done with doubly linked lists (the first cells previous pointer points to the last cell). This clearly affects some of the tests, but the structure is popular in some applications. Figure 3. 17 shows a double circularly linked list with no header. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ? ,12/47 3. 2. 7. Examples We provide three examples that use linked lists. The first is a simple way to represent single-variable polynomials. The second is a method to sort in linear time, for some special cases. Finally, we show a complicated example of how linked lists might be used to keep track of course registration at a university. The Polynomial ADT We can define an a bstract data type for single-variable polynomials (with nonnegative exponents) by using a list. Let . If most of the coefficients ai are nonzero, we can use a simple array to store the coefficients. We could then write routines to perform addition, subtraction, multiplication, differentiation, and other operations on these polynomials. In this case, we might use the type declarations given in Figure 3. 18. We could then write routines to perform various operations. Two possibilities are addition and multiplication. These are shown in Figures 3. 19 to 3. 21. Ignoring the time to initialize the output polynomials to zero, the running time of the multiplication routine is proportional to the product of the degree of the two input polynomials. This is adequate for dense polynomials, where most of the terms are present, but if p1(x) = 101000 + 514 + 1 and p2(x) = 31990 21492 + 11x + 5, then the running time is likely to be unacceptable. One can see that most of the time is spent multiplying zeros and stepping through what amounts to nonexistent parts of the input polynomials. This is always undesirable. Figure 3. 17 A double circularly linked list typedef struct { int coeff_array[ MAX_DEGREE+1 ]; unsigned int high_power; } *POLYNOMIAL; Figure 3. 18 Type declarations for array implementation of the polynomial ADT An alternative is to use a singly linked list. Each term in the polynomial is contained in one cell, and the cells are sorted in decreasing order of exponents. For instance, the linked lists in Figure 3. 22 represent p1(x) and p2(x). We could then use the declarations in Figure 3. 23. void mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,13/47 zero_polynomial( POLYNOMIAL poly ) { unsigned int i; for( i=0; icoeff_array[i] = 0; poly-high_power = 0; } Figure 3. 19 Procedure to initialize a polynomial to zero oid add_polynomial( POLYNOMIAL poly1, POLYNOMIAL poly2, POLYNOMIAL poly_sum ) { int i; zero_polynomial( poly_sum ); poly_sum-high_power = max( poly1-high_power, poly2-high_power); for( i=poly_sum-high_power; i=0; i ) poly_sum-coeff_array[i] = poly1-coeff_array[i] + poly2-coeff_array[i]; } Figure 3. 20 Procedure to add two polynomials void mult_polynomial( POLYNOMIAL poly1, POLYNOMIAL poly2, POLYNOMIAL poly_prod ) { unsigned int i, j; zero_polynomial( poly_prod ); poly_prod-high_power = poly1-high_power mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. hm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,14/47 + poly2-high_power; if( poly_prod-high_power MAX_DEGREE ) error(Exceeded array size); else for( i=0; ihigh_power; i++ ) for( j=0; jhigh_power; j++ ) poly_prod-coeff_array[i+j] += poly1-coeff_array[i] * poly2-coeff_array[j]; } Figure 3. 21 Procedure to multiply two polynomials Figure 3. 22 Linked list representations of two polynomials typedef struct node *node_ptr; struct node { int coefficient; int exponent; node_ptr next; } ; typedef node_ptr POLYNOMIAL; /* keep nodes sorted by exponent */ Figure 3. 23 Type declaration for linked list implementation of the Polynomial ADT The operations would then be straightforward to implement. The only potential difficulty is that when two polynomials are multiplied, the resultant polynomial will have to have like terms combined. There are several ways to do this, but we will leave this as an exercise. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,15/47 Radix Sort A second example where linked lists are used is called radix sort. Radix sort is sometimes known as card sort, because it was used, until the advent of modern computers, to sort old-style punch cards. If we have n integers in the range 1 to m (or 0 to m 1) 9, we can use this information to obtain a fast sort known as bucket sort. We keep an array called count, of size m, which is initialized to zero. Thus, count has m cells (or buckets), which are initially empty. When ai is read, increment (by one) count [ai]. After all the input is read, scan the count array, printing out a representation of the sorted list. This algorithm takes O(m + n); the proof is left as an exercise. If m = (n), then bucket sort is O(n). Radix sort is a generalization of this. The easiest way to see what happens is by example. Suppose we have 10 numbers, in the range 0 to 999, that we would like to sort. In general, this is n numbers in the range 0 to np 1 for some constant p. Obviously, we cannot use bucket sort; there would be too many buckets. The trick is to use several passes of bucket sort. The natural algorithm would be to bucket-sort by the most significant digit (digit is taken to base n), then next most significant, and so on. That algorithm does not work, but if we perform bucket sorts by least significant digit first, then the algorithm works. Of course, more than one number could fall into the same bucket, and, unlike the original bucket sort, these numbers could be different, so we keep them in a list. Notice that all the numbers could have some digit in common, so if a simple array were used for the lists, then each array would have to be of size n, for a total space requirement of (n2). The following example shows the action of radix sort on 10 numbers. The input is 64, 8, 216, 512, 27, 729, 0, 1, 343, 125 (the first ten cubes arranged andomly). The first step bucket sorts by the least significant digit. In this case the math is in base 10 (to make things simple), but do not assume this in general. The buckets are as shown in Figure 3. 24, so the list, sorted by least significant digit, is 0, 1, 512, 343, 64, 125, 216, 27, 8, 729. These are now sorted by the next least significant digit (the tens dig it here) (see Fig. 3. 25). Pass 2 gives output 0, 1, 8, 512, 216, 125, 27, 729, 343, 64. This list is now sorted with respect to the two least significant digits. The final pass, shown in Figure 3. 26, bucket-sorts by most significant digit. The final list is 0, 1, 8, 27, 64, 125, 216, 343, 512, 729. To see that the algorithm works, notice that the only possible failure would occur if two numbers came out of the same bucket in the wrong order. But the previous passes ensure that when several numbers enter a bucket, they enter in sorted order. The running time is O(p(n + b)) where p is the number of passes, n is the number of elements to sort, and b is the number of buckets. In our case, b = n. 0 1 512 343 64 125 216 27 8 729 - mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,16/47 0 1 2 3 4 5 6 7 8 9 Figure 3. 24 Buckets after first step of radix sort 8 1 0 216 512 729 27 125 343 64 -0 1 2 3 4 5 6 7 8 9 Figure 3. 25 Buckets after the second pass of radix sort 64 27 8 1 0 125 216 343 512 729 0 1 2 3 4 5 6 7 8 9 Figure 3. 26 Buckets after the last pass of radix sort As an example, we could sort all integers that are rep resentable on a computer (32 bits) by radix sort, if we did three passes over a bucket size of 211. This algorithm would always be O(n) on this computer, but probably still not as efficient as some of the algorithms we shall see in Chapter 7, because of the high constant involved (remember that a factor of log n is not all that high, and this algorithm would have the overhead of maintaining linked lists). Multilists Our last example shows a more complicated use of linked lists. A university with 40,000 students and 2,500 courses needs to be able to generate two types of reports. The first report lists the class registration for each class, and the second report lists, by student, the classes that each student is registered for. The obvious implementation might be to use a two-dimensional array. Such an array would have 100 million entries. The average student registers for about three courses, so only 120,000 of these entries, or roughly 0. 1 percent, would actually have meaningful data. What is needed is a list for each class, which contains the students in the class. We also need a list for each student, which contains the classes the student is registered for. Figure 3. 27 shows our implementation. mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ? ,17/47 As the figure shows, we have combined two lists into one. All lists use a header and are circular. To list all of the students in class C3, we start at C3 and traverse its list (by going right). The first cell belongs to student S1. Although there is no explicit information to this effect, this can be determined by following the students linked list u ntil the header is reached. Once this is done, we return to C3s list (we stored the position we were at in the course list before we traversed the students list) and find another cell, which can be determined to belong to S3. We can continue and find that S4 and S5 are also in this class. In a similar manner, we can determine, for any student, all of the classes in which the student is registered. Figure 3. 27 Multilist implementation for registration problem Using a circular list saves space but does so at the expense of time. In the worst case, if the first student was registered for every course, then every entry would need to be examined in order to determine all the course names for that student. Because in this application there are relatively few courses per student and few students per course, this is not likely to happen. If it were suspected that this could cause a problem, then each of the (nonheader) cells could have pointers directly back to the student and class header. This would double the space requirement, but simplify and speed up the implementation. 3. 2. 8. Cursor Implementation of Linked Lists Many languages, such as BASIC and FORTRAN, do not support pointers. If linked lists are required and pointers are not available, then an alternate implementation must be used. The alternate method we will describe is known as a cursor implementation. The two important items present in a pointer implementation of linked lists are k:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,18/47 1. The data is stored in a collection of structures. Each structure contains the data and a pointer to the next structure. 2. A new structure can be obtained from the systems global memory by a call to malloc and rele ased by a call to free. Our cursor implementation must be able to simulate this. The logical way to satisfy condition 1 is to have a global array of structures. For any cell in the array, its array index can be used in place of an address. Figure 3. 28 gives the type declarations for a cursor implementation of linked lists. We must now simulate condition 2 by allowing the equivalent of malloc and free for cells in the CURSOR_SPACE array. To do this, we will keep a list (the freelist) of cells that are not in any list. The list will use cell 0 as a header. The initial configuration is shown in Figure 3. 29. A value of 0 for next is the equivalent of a pointer. The initialization of CURSOR_SPACE is a straightforward loop, which we leave as an exercise. To perform an malloc, the first element (after the header) is removed from the freelist. ypedef unsigned int node_ptr; struct node { element_type element; node_ptr next; }; typedef node_ptr LIST; typedef node_ptr position; struct node CURSOR_SPACE[ SPACE_SIZE ]; Figure 3. 28 Declarations for cursor implementation of linked lists Slot Element Next 0 1 2 3 4 5 1 2 3 4 5 6 mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorith m Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,19/47 6 7 8 9 10 7 8 9 10 0 Figure 3. 29 An initialized CURSOR_SPACE To perform a free, we place the cell at the front of the freelist. Figure 3. 30 shows the cursor implementation of malloc and free. Notice that if there is no space available, our routine does the correct thing by setting p = 0. This indicates that there are no more cells left, and also makes the second line of cursor_new a nonoperation (no-op). Given this, the cursor implementation of linked lists is straightforward. For consistency, we will implement our lists with a header node. As an example, in Figure 3. 31, if the value of L is 5 and the value of M is 3, then L represents the list a, b, e, and M represents the list c, d, f. osition cursor_alloc( void ) { position p; p = CURSOR_SPACE[O]. next; CURSOR_SPACE[0]. next = CURSOR_SPACE[p]. next; return p; } void cursor_free( position p) { CURSOR_SPACE[p]. next = CURSOR_SPACE[O]. next; CURSOR_SPACE[O]. next = p; } Figure 3. 30 Routines: cursor-alloc and cursor-free Slot Element Next - mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CH APTER 3: LISTS, STACKS, AND QUEUES ,20/47 0 1 2 3 4 5 6 7 8 9 10 b f header header c d e a 6 9 0 7 0 10 4 8 2 0 1 Figure 3. 1 Example of a cursor implementation of linked lists To write the functions for a cursor implementation of linked lists, we and return the identical parameters as the pointer implementation. The are straightforward. Figure 3. 32 implements a function to test whether empty. Figure 3. 33 implements the test of whether the current position last in a linked list. The function find in Figure 3. 34 returns the position of x in list L. The code to implement deletion is shown in Figure 3. 35. Again, the interface for the cursor implementation is identical to the pointer implementation. Finally, Figure 3. 36 shows a cursor implementation of insert. The rest of the routines are similarly coded. The crucial point is that these routines follow the ADT specification. They take specific arguments and perform specific operations. The implementation is transparent to the user. The cursor implementation could be used instead of the linked list implementation, with virtually no change required in the rest of the code. int is_empty( LIST L ) { return( CURSOR_SPACE[L]. next == 0 } /* using a header node */ must pass routines a list is is the Figure 3. 32 Function to test whether a linked list is emptycursor implementation mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. hm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,21/47 int is_last( position p, LIST L) { return( CURSOR_SPACE[p]. next == 0 } /* using a header node */ Figure 3. 33 Function to test whether p is last in a linked listcursor implementation position find( element_type x, LIST L) /* using a header node */ { position p; / *1*/ /*2*/ /*3*/ /*4*/ } p = CURSOR_SPACE[L]. next; while( p CURSOR_SPACE[p]. element ! = x ) p = CURSOR_SPACE[p]. next; return p; Figure 3. 34 Find routinecursor implementation void delete( element_type x, LIST L ) { position p, tmp_cell; p = find_previous( x, L ); if( ! s_last( p, L) ) { tmp_cell = CURSOR_SPACE[p]. next; CURSOR_SPACE[p]. next = CURSOR_SPACE[tmp_cell]. next; cursor_free( tmp_cell ); } } mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,22/47 Figure 3. 35 Deletion routine for linked listscursor implementation /* Insert (after legal position p); */ /* header implementation assumed */ void insert( element_type x, LIST L, position p ) { position tmp_cell; /*1*/ /*2*/ /*3*/ else { /*4*/ /*5*/ /*6*/ } } CURSOR_SPACE[tmp_cell]. lement = x; CURSOR_SPACE[tmp_cell]. next = CURSOR_SPACE[p]. next; CURSOR_SPACE[p]. next = tmp_cell; tmp_cell = cursor_alloc( ) if( tmp_cell == 0 ) fatal_error(Out of space!!! ); Figure 3. 36 Insertion routine for linked listscursor implementation The freelist represents an interesting data structure in its own right. The cell that is removed from the freelist is the one that was most recently placed there by virtue of free. Thus, the last cell placed on the freelist is the first cell taken off. The data structure that also has this property is known as a stack, and is the topic of the next section. . 3. The Stack ADT 3. 3. 1. Stack Model A stack is a list with the restriction that inserts and deletes can be performed in only one position, namely the end of the list called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element. The most recently inserted element can be examined prior to performing a pop by use of the top routine. A pop or top on an empty stack is generally considered an error in the stack ADT. On the other hand, ru nning out of space when performing a push is an implementation k:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,23/47 error but not an ADT error. Stacks are sometimes known as LIFO (last in, first out) lists. The model depicted in Figure 3. 37 signifies only that pushes are input operations and pops and tops are output. The usual operations to make empty stacks and test for emptiness are part of the repertoire, but essentially all that you can do to a stack is push and pop. Figure 3. 38 shows an abstract stack after several operations. The general model is that there is some element that is at the top of the stack, and it is the only element that is visible. Figure 3. 37 Stack model: input to a stack is by push, output is by pop Figure 3. 38 Stack model: only the top element is accessible 3. 3. 2. Implementation of Stacks Of course, since a stack is a list, any list implementation will do. We will give two popular implementations. One uses pointers and the other uses an array, but, as we saw in the previous section, if we use good programming principles the calling routines do not need to know which method is being used. Linked List Implementation of Stacks The first implementation of a stack uses a singly linked list. We perform a push by inserting at the front of the list. We perform a pop by deleting the element at the front of the list. A top operation merely examines the element at the front of the list, returning its value. Sometimes the pop and top operations are combined into one. We could use calls to the linked list routines of the previous mk:@MSITStore:K:Data. Structures. and. Algorithm. Analysis. in. C. chm::/ 2006-1-27 Structures, Algorithm Analysis: CHAPTER 3: LISTS, STACKS, AND QUEUES ,24/47 ection, but we will rewrite the stack routines from scratch for the sake of clarity. First, we give the definitions in Figure 3. 39. We implement the stack us

Literary Analysis of the Speech free essay sample

Frederick Douglass was a fiery orator and his speeches were often published in various abolitionist newspapers. Among his well-known speeches is The Meaning of July Fourth for the Negro, presented in Rochester, New York, on July 5, 1852, a version of which he published as a booklet. It is often studied in literature classes today. Douglass moved to Rochester in 1847, when he became the publisher of The North Star, an abolitionist weekly. There were approximately 500 attendees who heard him speak, each paying twelve and a half cents. He had been invited to speak about what the Fourth of July means for Americas black population, and while the first part of his speech praises what the founding fathers did for this country, his speech soon develops into a condemnation of the attitude of American society toward slavery. Douglass begins his speech by addressing Mr. President, Friends and Fellow Citizens. Here, he is likely addressing the president of the Anti-Slavery Society — not the president of the United States. We will write a custom essay sample on Literary Analysis of the Speech or any similar topic specifically for you Do Not WasteYour Time HIRE WRITER Only 13.90 / page It is noteworthy that Douglass considers himself a citizen, an equal to the spectators in attendance.Throughout this speech, as well as his life, Douglass advocated equal justice and rights, as well as citizenship, for blacks. He begins his speech by modestly apologizing for being nervous in front of the crowd and recognizes that he has come a long way since his escape from slavery. He tells the audience that they have gathered to celebrate the Fourth of July, but he reminds them that the nation is young, and, like a young child, it is still impressionable and capable of positive change.He touches on the history of the American Revolutionaries fight for freedom against their legal bondage under British rule. He tells the audience that he supports the actions of these revolutionaries. Douglass thereby sets up an argument for the freeing of slaves. He reminds the audience that, in 1776, many people thought it was subversive and dangerous to revolt against British tyranny. In 1852, however, with hindsight, to say that America was right, and England wrong is exceedingly easy. Similarly, he reasons, in 1852, people consider abolitionism a dangerous and subversive political stance. Douglass thus implies that future generations will probably consider his anti-slavery stance patriotic, just, and reasonable. Douglass praises and respects the signers of the Declaration of Independence, people who put the interests of a country above their own. He concedes, however, that the main purpose of his speech is not to give praise and thanks to these men, for he says that the deeds of those patriots are well known.Instead, he urges his listeners to continue the work of those great revolutionaries who brought freedom and democracy to this land. Douglass then asks a rhetorical question: Are the great principles of political freedom and of natural justice, embodied in that Declaration of Independence, extended to us [blacks]? He pushes forward his thesis: This Fourth July [sic] is yours, not mine [italics his]. Indeed, he says, to ask a black person to celebrate the white mans freedom from oppression and tyranny is inhuman mockery and sacrilegious irony. By sacrilegious, he means the evil defilement of sacred American ideals — democracy, freedom, and equal rights. The real subject of his speech, he concedes, is American slavery. He condemns America for being untrue to its founding principles, its past, and its present. The audience must fulfill what the founders of the country advocated. To the slave, Douglass tells the audience, your 4th of July is a sham; your boasted liberty, an unholy license [for enslaving blacks] . . . your shouts of liberty and equality, hollow mockery. Douglass spends the next part of his speech pre-empting some of the arguments that theoretical opponents might make. As for the mildly sympathetic spectator who complains that the abolitionist fails to make a favorable impression by constantly denouncing slavery rather than making persuasive arguments, Douglass retorts by saying that there are no more arguments to be made. He says there is no person on earth who would be in favor of becoming a slave himself. How can it be, therefore, that some people are in favor of imposing a condition on others that they would not impose on themselves?As for those who maintain that slavery is part of a divine plan, Douglass argues that something which is inhuman cannot be considered divine. He considers such a pro-slavery posture to be blasphemy because it gives cruelty a place in Gods nature. Douglass condemns the profits made from the slave trade, and, once again, he compares the treatment of slaves to that of animals. He mentions that in Balti more, slave traders transported slaves in chains to ships in the dead of night because anti-slavery activism had made the public aware of the cruelty of that trade. Douglass recalls that when he was a child, the cries of chained slaves passing his house on route to the docks in the middle of the night had a chilling, unsettling effect on him. Next, Douglass condemns the American churches and ministers (excluding, of course, abolitionist religious movements such as Garrisons) for not speaking out against slavery. The contemporary American church, by remaining silent and acquiescing to the existence of slavery, he argues, is more of an infidel than Paine, Voltaire, or Bolingbroke (three eighteenth-century philosophers who spoke out against the churches of their time).Douglass argues that the church is superlatively guilty — superlative, meaning even more guilty — because it is an institution which has the power to eradicate slavery by condemning it. The Fugitive Slave Law, Douglass reasons, is tyrannical legislation because it removes all due process and civil rights for the black person: For black men, there is neither law nor justi ce, humanity nor religion. (Under this Act, even freed blacks could easily be accused of being fugitive slaves and taken to the South. The Christian church which allows this law to remain in effect, Douglass says, is not really a Christian church at all. Douglass returns to his theme of American democracy and freedom. He criticizes American ideology as inconsistent. For him, while it professes freedom, it does not give all people that right. And while it advocates democracy in Europe and elsewhere, it does not grant it to its own entire people. Similarly, he argues that while the American Declaration of Independence states that all men are created equal, American society creates an under-class of men and women.To his opponents who believe that the Constitution permits slavery, Douglass offers the writings of Spooner, Goodell, Sewall, and Smith — four abolitionists whose essays clearly vindicate the Constitution from any design to support slavery. Douglass sides with those activists who believe that the founding fathers meant to eliminate slavery and that the Constitution reflects this. Douglass concludes on an optimistic note. He believes that anti-slavery sentiments will eventually triumph over pro-slavery forces. Nations, particularly Western countries, in the mid-nineteenth century were generally against slavery.In fact, slavery was banned in the British colonies in 1834 and in the French colonies in 1848; politicians in those countries could no longer claim to support the rights of man while allowing slavery. He argues that no longer can the cruelties of American slavery be hidden from the rest of the world. Trade and commerce have opened up borders, and political ideas know no boundaries. Douglass closes his essay with a poem by Garrison entitled The Triumph of Freedom, stressing the inevitable arrival of freedom and the abolitionists promise to fight slavery whateer the peril or the cost.

Definition and Examples of a Written Summary of Text

Definition and Examples of a Written Summary of Text A summary, also known as an abstract, precis, or synopsis, is a shortened version of a text that highlights its key points. The word summary comes from the Latin, sum. Examples of Summaries A Summary of the Short Story Miss Brill by Katherine MansfieldMiss Brill is the story of an old woman told brilliantly and realistically, balancing thoughts and emotions that sustain her late solitary life amidst all the bustle of modern life. Miss Brill is a regular visitor on Sundays to the Jardins Publiques (the Public Gardens) of a small French suburb where she sits and watches all sorts of people come and go. She listens to the band playing, loves to watch people and guess what keeps them going and enjoys contemplating the world as a great stage upon which actors perform. She finds herself to be another actor among the so many she sees, or at least herself as part of the performance after all....One Sunday Miss Brill puts on her fur and goes to the Public Gardens as usual. The evening ends with her sudden realization that she is old and lonely, a realization brought to her by a conversation she overhears between a boy and a girl presumably lovers, who comment on her unwelcome pr esence in their vicinity. Miss Brill is sad and depressed as she returns home, not stopping by as usual to buy her Sunday delicacy, a slice of honey-cake. She retires to her dark room, puts the fur back into the box and imagines that she has heard something cry. -K. Narayana Chandran. A Summary of Shakespeares HamletOne way of discovering the overall pattern of a piece of writing is to summarize it in your own words. The act of summarizing is much like stating the  plot of a play. For instance, if you were asked to summarize the story of Shakespeares Hamlet, you might say: Its the story of a young prince of Denmark who discovers that his uncle and his mother have killed his father, the former king. He plots to get revenge, but in his obsession with revenge he drives his sweetheart to madness and suicide, kills her innocent father, and in the final scene poisons and is poisoned by her brother in a duel, causes his mothers death, and kills the guilty king, his uncle. This summary contains a number of dramatic elements: a cast of characters (the prince; his uncle, mother, and father; his sweetheart; her father, and so on), a scene (Elsinore Castle in Denmark), instruments (poisons, swords), and actions (discovery, dueling, killing). -Richard E. Young, Alton L. Becker, and Kenneth L. Pike. Steps in Composing a Summary The primary purpose of a summary is to give an accurate, objective representation of what the  work  says. As a general rule, you should not include your own ideas or interpretations. Paul Clee and Violeta Clee Summarizing condenses in your own words the main points in a passage: Reread the passage, jotting down a few keywords.State the main point in your own words and be objective: Dont mix your reactions with the summary.Check your summary against the original, making sure that you use  quotation marks  around any exact phrases that you borrow. -Randall VanderMey, et al. Here...is a general procedure you can use [for composing a summary]: Step 1: Read the text for its main points.Step 2: Reread carefully and make a descriptive outline.Step 3: Write out the texts thesis or main point. . . .Step 4: Identify the texts major divisions or chunks. Each division develops one of the stages needed to make the whole main point. . . .Step 5: Try summarizing each part in one or two sentences.Step 6: Now combine your summaries of the parts into a coherent whole, creating a condensed version of the texts main ideas in your own words. -(John C. Bean, Virginia Chappell, and Alice M. Gillam, Reading Rhetorically. Pearson Education, 2004) Characteristics of a Summary The purpose of a  summary is to give a reader a condensed and objective account of the main ideas and features of a text. Usually, a summary has between one and three paragraphs or one hundred to three hundred words, depending on the length and complexity of the original essay and the intended audience and purpose. Typically, a summary will do the following: Cite the author and title of the text. In some cases, the place of publication or the context for the essay may also be included.Indicate the main ideas of the text. Accurately representing the main ideas (while omitting the less important details) is the major goal of the summary.Use direct quotations of keywords, phrases, or sentences. Quote the text directly for a few key ideas; paraphrase the other important ideas (that is, express the ideas in your own words.)Include author tags. (According to Ehrenreich or as Ehrenreich explains) to remind the reader that you are summarizing the author and the text, not giving your own ideas. . . .Avoid summarizing specific examples or data unless they help illustrate the thesis or main idea of the text.Report the main ideas as objectively as possible...Do not include your reactions; save them for your response. -(Stephen Reid,  The Prentice Hall Guide for Writers, 2003) A Checklist for Evaluating Summaries Good summaries must be fair, balanced, accurate, and complete. This checklist of questions will help you evaluate drafts of a summary: Is the summary economical and precise?Is the summary neutral in its representation of the original authors ideas, omitting the writers own opinions?Does the summary reflect the proportionate coverage given various points in the original text?Are the original authors ideas expressed in the summary writers own words?Does the summary use attributive tags (such as Weston argues) to remind readers whose ideas are being presented?Does the summary quote sparingly (usually only key ideas or phrases that cannot be said precisely except in the original authors own words)?Will the summary stand alone as a unified and coherent piece of writing?Is the original source cited so that readers can locate it? -John C. Bean On the Summary App  Summly Upon hearing, in March of [2013], reports that a 17-year-old schoolboy had sold a piece of software to Yahoo! for $30 million, you might well have entertained a few preconceived notions about what sort of child this must be...The app [that then 15-year-old Nick] DAloisio designed, Summly, compresses long pieces of text into a few representative sentences. When he released an early iteration, tech observers realized that an app that could deliver brief, accurate summaries would be hugely valuable in a world where we read everything - from news stories to corporate reports - on our phones, on the go...There are two ways of doing natural language processing: statistical or semantic, DAloisio explains. A semantic system attempts to figure out the actual meaning of a text and translate it succinctly. A statistical system - the type DAloisio used for Summly - doesnt bother with that; it keeps phrases and sentences intact and figures out how to pick a few that best encapsulate the entir e work. It ranks and classifies each sentence, or phrase, as a candidate for inclusion in the summary. Its very mathematical. It looks at frequencies and distributions, but not at what the words mean. -Seth Stevenson. The Lighter Side of Summaries Here are some...famous works of literature that could easily have been summarized in a few words: Moby-Dick: Dont mess around with large whales, because they symbolize nature and will kill you.A Tale of Two Cities: French people are crazy.Every poem ever written: Poets are extremely sensitive. Think of all the valuable hours we would save if authors got right to the point this way. Wed all have more time for more important activities, such as reading newspaper columns. -Dave Barry. To summarize: it is a well-known fact that those people who must want to rule people are, ipso facto, those least suited to do it. To summarize the summary: anyone who is capable of getting themselves made President should on no account be allowed to do the job. To summarize the summary of the summary: people are a problem. -Douglas Adams. Sources K. Narayana Chandran,  Texts and Their Worlds II. Foundation Books, 2005)Richard E. Young, Alton L. Becker, and Kenneth L. Pike,  Rhetoric: Discovery and Change. Harcourt, 1970Paul Clee and Violeta Clee,  American Dreams, 1999.Randall VanderMey, et al.,  The College Writer, Houghton, 2007Stephen Reid,  The Prentice Hall Guide for Writers, 2003John C. Bean, Virginia Chappell, and Alice M. Gillam  Reading Rhetorically. Pearson Education, 2004Seth Stevenson, How Teen Nick DAloisio Has Changed the Way We Read.  Wall Street Journal Magazine, November 6, 2013Dave Barry,  Bad Habits: A 100% Fact-Free Book. Doubleday, 1985Douglas Adams,  The Restaurant at the End of the Universe. Pan Books, 1980

Round

Round Round Round By Maeve Maddox The word round is the ideal word to illustrate the fact that a word is not a part of speech until it is used in a sentence. Of the eight classic parts of speech–noun, verb, adjective, adverb, preposition, conjunction, pronoun, and interjection–round can function as five of them. 1. Round as Noun We speak of a round of golf and the rounds of a boxing match. We sing musical rounds like â€Å"Row, Row, Row Your Boat† and â€Å"Frere Jacques.† Shakespeare spoke of a king’s crown as â€Å"a golden round.† The steps of a ladder are called rounds. The creed of the United States Postal Service, translated from Herodotus, declares, â€Å"Neither snow nor rain nor heat nor gloom of night stays these couriers from the swift completion of their appointed rounds.† Here are some more common meanings of round as a noun: a large piece of beef a slice of bread, especially toast a regularly recurring sequence the constant passage and recurrence of days the act of ringing a set of bells in sequence a circular route a regular visit by a doctor or a nurse in a hospital a set of drinks bought for all the people in a group an amount of ammunition needed to fire one shot. a single volley of fire by artillery an outburst of applause a period or bout of play at a game or sport a division of a game show a session of meetings for discussion 2. Round as Adjective Anything that is spherical in shape may be described as round, for example, balls marbles, oranges, and grapes. Also round are cake pans, plates, Frisbees, wheels, CDs, and bagels. Vowels can be round, (i.e., enunciated by contracting the lips to form a circular shape.) Applied to a quantity of something, round can mean large or considerable: â€Å"A million dollars is a good round sum.† But applied to an estimate, round means rough or approximate: â€Å"The figure of three thousand years was only a round guess.† Shakespeare and his contemporaries frequently used round in the sense of outspoken: â€Å"Sir Toby, I must be round with you.† Horses can trot at â€Å"a good round pace,† and scholars often have â€Å"round shoulders.† 3. Round as Verb You can round a piece of clay into a ball, round the edges of a table, round the bases, round chickens into a corner, round out your gnome collection, round a number, and round suddenly on someone who has been annoying you. 4. Round as Adverb and Preposition These uses of round are more common in British usage than in American: â€Å"When the door slammed, everyone turned round.† (adverb) â€Å"At last, the bus came round the corner.† (preposition) See Round vs. Around for a discussion of these two uses of round. Want to improve your English in five minutes a day? Get a subscription and start receiving our writing tips and exercises daily! Keep learning! Browse the Vocabulary category, check our popular posts, or choose a related post below:Fly, Flew, (has) FlownFlied?"Replacement for" and "replacement of"English Grammar 101: Sentences, Clauses and Phrases

History of the Japanese in North America Essay Example | Topics and Well Written Essays - 1000 words

History of the Japanese in North America - Essay Example People from Japan began migrating to the U.S. in significant numbers following the political, cultural, and social changes stemming from the 1868 Meiji Restoration. Particularly after the Chinese Exclusion Act of 1882, Japanese immigrants were sought by industrialists to replace the Chinese immigrants. In 1907, the "Gentlemen's Agreement" between the governments of Japan and the U.S. ended immigration of Japanese workers (i.e., men), but permitted the immigration of spouses of Japanese immigrants already in the U.S. The Immigration Act of 1924 banned the immigration of all but a token few Japanese. The ban on immigration produced unusually well-defined generational groups within the Japanese American community. Initially, there was an immigrant generation, the Issei, and their U.S.-born children, the Nisei. The Issei were exclusively those who had immigrated before 1924. Because no new immigrants were permitted, all Japanese Americans born after 1924 were--by definition--born in the U.S. This generation, the Nisei, became a distinct cohort from the Issei generation in terms of age, citizenship, and language ability, in addition to the usual generational differences. Institutional and interpersonal racism led many of the Nisei to marry other Nisei, resulting in a third distinct generation of Japanese Americans, the Sansei. Significant Japanese immigration did not occur until the Immigration Act of 1965 ended 40 years of bans against immigration from Japan and other countries. The Naturalization Act of 1790 restricted naturalized U.S. citizenship to "free white persons," which excluded the Issei from citizenship. As a result, the

Labor Relations Reseach Paper Research Example | Topics and Well Written Essays - 1250 words

Labor Relations Reseach - Research Paper Example Predominantly, in the heavy industries of south west and the north east, another get natured in the thriving consumer industries of the east, southern coast provinces (Beik, 2005). This has steered to the rise of two new labor movements. State sector workers have complained and struck to shield their jobs, while in foreign-owned and private factories, dismal conditions and dictatorial management are matters that have provoked insurgency. The largest and the most dramatic labor protests in China get induced by laid-off workers against the regularly corrupt and illegal methods in which their enterprises get sold off, or for owing unpaid benefits, which they remained entitled to. Nevertheless, their radicalism happens at the moment of departure from the working classes when they do not anymore have the power to halt production. However, there has been a rising trend for workers to be against the corrupt conditions in which their enterprises get privatized, and to leap in before they get laid off (Pringle, 2010). Deng Xiaoping agreed as many western academics ostensibly do not, that not only is there no essential connection between political and economic liberalism, but the realization of China’s economic success has been reliant on political repression to subdue the inevitable dissatisfaction (Oxford University, 2011). When tanks rolled into Tiananmen Square in 1989, he described the frightening logic behind the resolution: â€Å"Even if we sacrifice 10 to 20 thousand persons, we must exercise control above the situation of the country and get twenty years tranquility in response†. However, workers showed to be far stronger than Deng expected, with strikes recounted even in the 2nd half of 1989. The most significant feature of the growing industrial disturbance is that for the first while since 1948, strikes have become an undying feature of Chinese society. In addition, unlike the past, this has occurred at a time of agreement among the leadership o f Communist Party (Oxford University, 2011). For instance, the Chinese Honda Motor Company faced the worst strikes in its 18-year-old manufacturing business. The company said it needed to develop communication with its employees in the nation after the strikes took the company by shock. Honda, Japanese second - largest automaker, made the report after strikes at 2 suppliers in China paused its car output in China for the first time and required the company to raise their wages. Another third strike, at Honda Lock (Guangdong) Company, Guangdong province, got suspended for the union leaders and management to negotiate over pay. There are no effective networks in China for management and workers to negotiate, said Crothall Geoffrey, a Hong Kong-based China Labor Bulletin advocacy group spokesman. Discussions between the two parties get handled by government - associated union officers who can not selected by the workers. Honda is trying to construct a system that will facilitate a flow of communication between workers via managers to Honda management team and Japanese company officials (Beik, 2005). The first measure to be taken by the company was increasing its wages as demanded by the striking workers. Before any communication developments, the company had to solve the underlying problems of the strike which primarily included wages increment. After ward, the company had