Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Algorithms and data structures (CSC112) - Chapter 31

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Chapter 31 - Review 15-30. The main contents of the chapter consist of the following: Introduction to algorithms and data structures, static data structures, searching algorithms, sorting algorithms, list implementation through array,. | Algorithms and Data Structures (CSC112) 1 Review Introduction to Algorithms and Data Structures Static Data Structures Searching Algorithms Sorting Algorithms List implementation through Array ADT: Stack ADT: Queue Dynamic Data Structures (Linear) Linked List (Linear Data Structure) Dynamic Data Structures (Non-Linear) Trees, Heap, Hashing, Graphs 2 Algorithm Analysis 3 Problem Solving Space Complexity Time Complexity Classifying Functions by Their Asymptotic Growth Problem Solving: Main Steps Problem definition Algorithm design / Algorithm specification Algorithm analysis Implementation Testing Maintenance 4 1. Problem Definition What is the task to be accomplished? Calculate the average of the grades for a given student Find the largest number in a list What are the time /space performance requirements ? 5 2. Algorithm Design/Specifications Algorithm: Finite set of instructions that, if followed, accomplishes a particular task. Describe: in natural language / pseudo-code / diagrams / etc. Criteria to follow: Input: Zero or more quantities (externally produced) Output: One or more quantities Definiteness: Clarity, precision of each instruction Effectiveness: Each instruction has to be basic enough and feasible Finiteness: The algorithm has to stop after a finite (may be very large) number of steps 6 4,5,6: Implementation, Testing and Maintenance Implementation Decide on the programming language to use C, C++, Python, Java, Perl, etc. Write clean, well documented code Test, test, test Integrate feedback from users, fix bugs, ensure compatibility across different versions Maintenance 7 3. Algorithm Analysis Space complexity How much space is required Time complexity How much time does it take to run the algorithm 8 Space Complexity Space complexity = The amount of memory required by an algorithm to run to completion the most often encountered cause is “memory leaks” – the amount of memory required larger than the memory available on a given system Some . | Algorithms and Data Structures (CSC112) 1 Review Introduction to Algorithms and Data Structures Static Data Structures Searching Algorithms Sorting Algorithms List implementation through Array ADT: Stack ADT: Queue Dynamic Data Structures (Linear) Linked List (Linear Data Structure) Dynamic Data Structures (Non-Linear) Trees, Heap, Hashing, Graphs 2 Algorithm Analysis 3 Problem Solving Space Complexity Time Complexity Classifying Functions by Their Asymptotic Growth Problem Solving: Main Steps Problem definition Algorithm design / Algorithm specification Algorithm analysis Implementation Testing Maintenance 4 1. Problem Definition What is the task to be accomplished? Calculate the average of the grades for a given student Find the largest number in a list What are the time /space performance requirements ? 5 2. Algorithm Design/Specifications Algorithm: Finite set of instructions that, if followed, accomplishes a particular task. Describe: in natural language / pseudo-code / .