tailieunhanh - Lecture Algorithms and data structures: Chapter 1 - Introduction to Data Structure and Algorithms
The course focuses on strategies and techniques to efficiently store data (Data Structures) and to perform processing on such data in efficient ways (Algorithms), as well as on the analysis and design of such techniques. In this lecture, the following topics will be covered: Mathematical review; asymptotic and algorithm analysis; relationships and data structures; requential storage: Lists, queues, stacks, deques; hash tables; trees; priority queues and heaps; sort algorithms; graphs and graph algorithms; algorithm design techniques; complexity classes and NP completeness. | Algorithms and Data Structures (CSC112) 1 Introduction 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, Graphs, Hashing 2 What is a Computer Program? To exactly know, what is data structure? We must know: What is a computer program? Input Some mysterious processing Output 3 Definition An organization of information, usually in memory, for better algorithm efficiency such as queue, stack, linked list and tree. 4 3 steps in the study of data structures Logical or mathematical description of the structure Implementation of the structure on the computer Quantitative analysis of the structure, which includes determining the amount of memory needed to store the structure and the time required to process the structure 5 Lists (Array /Linked List) Items have a position in this Collection Random access or not? Array Lists internal storage container is native array Linked Lists public class Node { private Object data; private Node next; } first last 6 6 Stacks Collection with access only to the last element inserted Last in first out insert/push remove/pop top make empty Top Data4 Data3 Data2 Data1 7 7 Queues Collection with access only to the item that has been present the longest Last in last out or first in first out enqueue, dequeue, front, rear priority queues and deques Data4 Data3 Data2 Data1 Front Rear Deletion Insertion 8 8 Trees Similar to a linked list public class TreeNode { private Object data; private TreeNode left; private TreeNode right; } Root 9 9 Hash Tables Take a key, apply function f(key) = hash value store data or object based on hash value Sorting O(N), access O(1) if a perfect hash function and enough memory for table how deal with collisions? 10 10 Other ADTs Graphs Nodes with unlimited connections between other nodes 11 11 cont . | Algorithms and Data Structures (CSC112) 1 Introduction 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, Graphs, Hashing 2 What is a Computer Program? To exactly know, what is data structure? We must know: What is a computer program? Input Some mysterious processing Output 3 Definition An organization of information, usually in memory, for better algorithm efficiency such as queue, stack, linked list and tree. 4 3 steps in the study of data structures Logical or mathematical description of the structure Implementation of the structure on the computer Quantitative analysis of the structure, which includes determining the amount of memory needed to store the structure and the time required to process the structure 5 Lists (Array /Linked List) Items have a position in .
đang nạp các trang xem trước
