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

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

This chapter shows you how to apply your query formulation skills to building applications with views. This chapter also emphasizes views as the foundation for building database applications. Before discussing the link between views and database applications, essential background is provided. | 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 / .