Software engineering algorithm design and analysis Volume 2

Software Engineering Algorithm Design And Analysis Volume 2-Free PDF

  • Date:06 Dec 2019
  • Views:61
  • Downloads:0
  • Pages:29
  • Size:329.75 KB

Share Pdf : Software Engineering Algorithm Design And Analysis Volume 2

Download and Preview : Software Engineering Algorithm Design And Analysis Volume 2


Report CopyRight/DMCA Form For : Software Engineering Algorithm Design And Analysis Volume 2


Transcription:

This guide was prepared for the University of London International Programmes by. This is one of a series of subject guides published by the University We regret that due to pressure of work the author is. unable to enter into any correspondence relating to or arising from the guide If you have any comments on this subject. guide favourable or unfavourable please use the form at the back of this guide. University of London International Programmes,Publications Office. 32 Russell Square,London WC1B 5DN,United Kingdom,www londoninternational ac uk. Published by University of London,University of London 2006. The University of London asserts copyright over all material in this subject guide except where otherwise indicated All rights. reserved No part of this work may be reproduced in any form or by any means without permission in writing from the. publisher We make every effort to respect copyright If you think we have inadvertently used your copyright material please. let us know,1 Algorithm analysis 1,1 1 Essential reading 1. 1 2 Learning outcomes 1,1 3 Problems and algorithms 1.
1 3 1 Implementation 2,1 4 Pseudo code for algorithm description 2. 1 5 Efficiency 3,1 6 Measures of performance 3,1 7 Algorithm analysis 4. 1 8 Model of computation 5,1 8 1 Counting steps 6,1 8 2 Implementation 6. 1 8 3 Characteristic operations 7,1 9 Asymptotic behaviour 8. 1 9 1 Big O notations 8,1 9 2 Comparing orders of two functions 9.
1 10 The worst and average cases 9,1 10 1 Implementation 10. 1 10 2 Typical growth rates 12,1 11 Verification of an analysis 12. 2 Abstract data types I lists and hashing tables 15. 2 1 Essential reading 15,2 2 Learning outcomes 15,2 3 From Abstraction to Implementation 16. 2 3 1 The string abstract data type 17,2 3 2 The matrix abstract data type 18. 2 3 3 The keyed list abstract data type 18,2 3 4 Common operations 19.
2 4 Data structures and software performance 19,2 5 Motivation of abstract data types 19. 2 6 Arrays 20,2 6 1 Applications 21,2 6 2 Array of objects 23. 2 6 3 Two and multi dimensional arrays 24,2 7 Lists 24. 2 7 1 References links or pointers 25,2 7 2 Implementation of the links 26. 2 7 3 Linked lists 27,2 7 4 Operations on lists 28.
2 7 5 Add one node to a linked list 29,2 7 6 Delete one node from a linked list 30. 2 7 7 Implementation 31,2 7 8 Construct a list 31,2 7 9 Implementation 32. 2 7 10 Other operations 34,2 7 11 Comparison with arrays 34. 2 8 Stacks 36,2 8 1 Operations on stacks 37, E8455 Software engineering algorithm design V2 pdf 3 29 06 2010 11 37 13. CIS226 Software engineering algorithm design and analysis vol 2. 2 8 2 Implementation 37,2 8 3 Applications 39,2 9 Queues 40.
2 9 1 Operations on queues 40,2 9 2 Implementation of queues 41. 2 9 3 Variation of queues 43,2 10 Hashing 44,2 10 1 Collision 46. 2 10 2 Collision resolving 46,2 10 3 Extra work for retrieval process 50. 2 10 4 Observation 50,3 Algorithm design techniques 53. 3 1 Essential reading 53,3 2 Learning outcomes 53,3 3 Recursion 53.
3 3 1 Implementation 56,3 3 2 What happens 57,3 3 3 Why recursion 58. 3 3 4 Tail recursion 63,3 3 5 Principles of recursive problem solving 63. 3 3 6 Common errors 63,3 4 Divide and conquer 65,3 4 1 Steps in the divide and conquer approach 66. 3 4 2 When Divide and Conquer inefficient 69,3 5 Dynamic programming 70. 3 5 1 Overlapped subproblems 70,3 5 2 Dynamic programming approach 71.
3 5 3 Efficiency of dynamic programming 72, 3 5 4 Similarity to the Divide and Conquer approach 72. 3 5 5 Observation 73, 4 Abstract data types II trees graphs and heaps 75. 4 1 Essential reading 75,4 2 Learning outcomes 75,4 3 Trees 75. 4 3 1 Terms and concepts 76,4 3 2 Implementation of a binary tree 77. 4 3 3 Recursive definition of Trees 79,4 3 4 Basic operations on binary trees 80.
4 3 5 Traversal of a binary tree 80,4 3 6 Construction of an expression tree 81. 4 4 Priority queues and heaps 84,4 4 1 Binary heaps 84. 4 4 2 Basic heap operations 86,4 5 Graphs 92,5 Traversal and searching 101. 5 1 Essential reading 101,5 2 Learning outcomes 101. 5 3 Traversal 101,5 3 1 Traversal on a linear data structure 102.
5 3 2 Binary tree traversal 102,5 3 3 Graph traversal 102. 5 3 4 Depth first traversal 102,5 3 5 Breadth first traversal 102. 5 4 Searching 104,5 5 Sequential search 105,5 6 Binary search 106. E8455 Software engineering algorithm design V2 pdf 4 29 06 2010 11 37 13. 5 7 Binary search trees 109,6 Sorting 113,6 1 Essential reading 113. 6 2 Learning outcomes 113,6 3 Introduction 113,6 4 Motivation 113.
6 5 Insertion Sort 114,6 5 1 Algorithm analysis 115. 6 6 Selection sort 115,6 7 Shellsort 117,6 8 Mergesort 118. 6 9 Quicksort 121,6 10 General lower bounds for sorting 124. 6 11 Bucket sort 126,6 12 Sorting large records 127. 6 13 Heapsort 128,7 Optimisation problems 137,7 1 Essential reading 137.
7 2 Learning outcomes 137,7 3 Optimisation problems 137. 7 3 1 Multiplication of matrices 138,7 3 2 Knapsack problem 139. 7 3 3 Coin changes 141,7 4 Greedy approach 145,7 4 1 Huffman coding 145. 7 4 2 Huffman decompression algorithm 148,8 Limits of computing 151. 8 1 Essential reading 151,8 2 Learning outcomes 151.
8 3 Computability and computational complexity theory 151. 8 4 Computational model 152,8 5 Decision problems 153. 8 6 Measure of problem complexity 154,8 7 Problem classes 155. 8 8 Class P 156,8 9 Class N P 156,8 10 P and N P 157. 8 11 NP complete problems 158,8 11 1 What do we mean by hard 158. 8 11 2 How to prove a new problem is NP complete 159. 8 11 3 The first NP complete problem 159,8 11 4 More NP complete problems 160.
9 Text string matching 161,9 1 Essential reading 161. 9 2 Learning outcomes 161,9 3 String matching 161,9 4 The string ADT 162. 9 5 String matching 164,9 5 1 Naive string matching 164. 9 5 2 Observation 166,9 5 3 Boyer Moore Algorithm 166. 9 5 4 Observation 168,9 6 KMP Algorithm 169,9 7 Tries 174.
9 7 1 Standard tries 174, E8455 Software engineering algorithm design V2 pdf 5 29 06 2010 11 37 13. CIS226 Software engineering algorithm design and analysis vol 2. 9 7 2 Compressed tries 175,10 Graphics and geometry 177. 10 1 Essential reading 177,10 2 Learning outcomes 177. 10 3 Quadtrees 177,10 4 Octtrees 178,10 5 Grid files 178. 10 6 Operations 178,10 7 Simple geometric objects 179.
10 8 Parameter spaces 179,11 Revision for CIS226b examination 181. 11 1 Examination 181,11 2 Revision materials 181,11 3 Questions in the examination 181. 11 4 Read questions carefully 182,11 5 Recommendation 182. 11 6 Revision topics I 183,11 7 Revision topics II 183. 11 8 Good luck 183,A Sample examination paper 185,B Sample solutions 189.
C Pseudocode notation 195,C 1 Values 195,C 2 Types 195. C 3 Operations 195,C 4 Priority 195,C 5 Data structures 196. C 6 Other reserved words 196,C 7 Control keywords 196. C 8 Examples of sequential structures 196, E8455 Software engineering algorithm design V2 pdf 6 29 06 2010 11 37 13. Introduction, Abstract data types or data structures provide powerful methods of.
organising large amounts of data Algorithm analysis enables you to. make a decision about the most suitable algorithm before. programming Techniques using abstract data types and design. patterns are essential in conventional software development. Once a good solution method is determined a program must still be. written and implementation has to be completed In this module we. therefore conduct a one hour laboratory session for every three. hours of lectures at Goldsmiths College University of London This. approach is to give you the opportunity to enhance your. programming skills in Java 1 In addition you will do two 1. Or in other similar programming, assignments to gain problem solving experience languages. Although there are many books on algorithms and data structures. available on the market it has been difficult to find a single text that. suits all the needs of this module On the other hand you may. already have some books on algorithms and data structures from. previous programming modules such as CIS212 or CIS109 that you. may not have finished studying, Instead of any single text for essential and desirable reading we. therefore recommend chapters from a number of text books All. topics covered in these chapters and in this subjectguide are. examinable 2 There is also a list of books for further reading and 2. See Chapter 11 for a list of, for supporting and historical background reading in the subject important examinable topics. guide Details on availability of the books can be found at. www amazon co uk or in your institution libraries, The materials covered in the books may overlap and not every. chapter of a book is required for the examination Hence you are. not expected to read all the books nor all the chapters of a single. book on the list You do however need to get hold of at least ONE. book on algorithms and data structures for frequent reference and. for studying individual topics in depth Your book does not have to. be in Java but it should cover at least 80 percent of the examinable. topics below3 3,Of course you still need to have an.
access to the other 20 percent, 1 Algorithms and efficiency analysis materials in various sources such as. in the library,2 Abstract data types and data structures. 3 Lists stacks queues and sets,4 Recursions divide and conquer. 5 Trees graphs and maps, E8455 Software engineering algorithm design V2 pdf 17 29 06 2010 11 37 14. CIS226 Software engineering algorithm design and analysis vol 2. 6 Sorting searching and hashing,7 Dynamic programming.
8 Graph algorithms greedy heuristics and approximation. 9 Complexity theory,10 Text processing, Note it would be inconvenient if not impossible for you to have to. share a library s textbook with other students to study more than 20. percent of the examinable materials because the book may be. unavailable just when you need it urgently for a coursework or. examination, To best study module CIS226b you need to follow closely the. reading instruction for each chapter in the subject guide paying a. particular attention to whether the word and is used between. reading items For example if A and B is found on the reading list. you are strongly recommended to consult the materials in both A. Below is a collection of textbooks that are recommended at various. points in the subject guide which are undated periodically Note the. books are updated frequently these days so search on the internet. for the newest edition before any purchase,Essential reading. The chapters of various books are specified as essential reading. These can be found at the beginning of each chapter of the subject. guide You should read carefully the specified chapter s in at least. one of the books on the list for each chapter of this subject guide If. there is any doubt you should consult other books on the list A full. list of these books can be found in the next section. Desirable reading, The following texts are recommended because they provide the. detailed background for understanding and appreciation of some. topics in this module, However you are not required to study all the topics in these texts.
for no single text can entirely meet the requirements of this course. unit The essential reading chapters are listed at the beginning of. each chapter of the subject guide, Michael T Goodrich and Roberto Tamassia Data Structures and Algorithms. in Java John Wiley Sons Inc 2005 fifth edition,ISBN10 0 471 73884 0 ISBN13 978 471 73884 8. Duane A Bailey Java Structures Data Structures in Java for the principled. programmer McGraw Hill Companies Inc 1999 McGraw Hill. International editions ISBN 0 13 489428 6, Jurg Nievergelt and Klaus H Hinrichs Algorithms Data Structures. Prentice Hall Inc 1993 ISBN 0 13 489428 6, E8455 Software engineering algorithm design V2 pdf 18 29 06 2010 11 37 14. Anany Levintin Introduction to the design and analysis of algorithm. Addison Wesley Professional 2003 ISBN 0 201 743957. Supporting and historical reading, These books are of interest and are recommended but you will be.
fully prepared for the examination should you have studied only. those essential texts above These are provided for completeness. and to allow the interested reader to pursue some topics in more. depth You will not be examined on the content of those books listed. in the references other than where the material appears in the texts. listed above,Additional reading, Russell L Shachelford Introduction to Computing and Algorithms. Addison Wesley Longman Inc 1998 ISBN 0 201 31451 7. Jeffrey Kingston Algorithms Data Structures Design Correctness. Analysis Addison Wesley 1997 or 1998 second edition. ISBN 0 201 40374 9, Richard Johnsonbaugh and Marcus Schaefer Algorithms Pearson. Education International 2004 ISBN 0 13 122853 6, Michael Main Data Structures and Other Projects Using Java. Addison Wesley Longman Inc 1999 ISBN 0 201 35744 5. Sara Baase and Allen Van Gelder Computer Algorithms Introduct. Software engineering algorithm design and analysis Volume 2 I Pu CO2226 2006 Undergraduate study in Computing and related programmes This is an extract from a subject guide for an undergraduate course offered as part of the

Related Books