51作业君
首页
低价平台
服务介绍
代写程序
代写论文
编程辅导
程序案例
论文案例
联系方式
诚邀英才
代写选择指南
程序辅导案例
>
Program
>
程序代写案例-CSE30 UCSC
欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
Python Abstractions CSE30 UCSC 2021 Instructor: Dr. Larissa Munishkina Grade Calculation Programming Assignments 30 Lab Assignments 30 r>Quizzes 20 Final 15 Class Participation 5 Agenda Quiz 4 Sorting Algorithms Searching Algorithms ADT: Graph, Tree, Binary Search Tree, Hash Table Hamiltonian Path and Cycle Eulerian Path Labs, Lectures, and Textbook All material in quiz 4 is based on: lectures 7, 8, 9 online textbook Ch. 6.1-6.16, 7.1-7.15, 8.1-8.19 labs 7 and 8 Sorting Algorithms Sorting O(n2) Bubble Sort Selection Sort Insertion Sort Shell Sort Quick Sort Sorting O(nlogn) Merge Sort Heap Sort Sorting O(n) Counting Sort Radix Sort Bucket Sort Sorting Algorithm Analysis Time Complexity Best Average Worst Bubble Sort O(n) O(n2) O(n2) Selection Sort O(n) O(n2) O(n2) Insertion Sort O(n) O(n2) O(n2) Shell Sort O(n) O(n2) O(n2) Quick Sort O(nlogn) O(nlogn) O(n2) Merge Sort O(nlogn) O(nlogn) O(nlogn) Counting Sort O(n) O(n) O(n) Sorting Algorithm Analysis Space (Memory) Complexity Best Average Worst Bubble Sort O(1) O(1) O(1) Selection Sort O(1) O(1) O(1) Insertion Sort O(1) O(1) O(1) Shell Sort O(1) O(1) O(1) Quick Sort O(1) O(1) O(1) Merge Sort O(n) O(n) O(n) Counting Sort O(n) O(n) O(n) Searching Algorithms List Search Linear Search Binary Search Hashing Binary Search Tree Graph Search Breadth First Search (BFS) Depth First Search (DFS) Path Eulerian Path Hamiltonian Path and Cycle List Search Linear Search Binary Search Hashing Binary Search Tree Algorithm Analysis Search Data Best case Average Case Worst Case Sequential Search unsorted O(1) O(n) O(n) Sequential Search sorted O(1) O(n) O(n) Binary Search unsorted O(1) O(n) O(n) Binary Search sorted O(1) O(logn) O(logn) Hashing both O(1) O(1) O(n) Binary Tree both O(1) O(logn) O(n) Tree A tree consist of nodes and edges A node is a fundamental part of a tree. It can have a name and additional information An edge is a connection between two nodes that correspond to a relation between nodes An edge is incoming if it comes to a node and outgoing if it goes from a node. Every node (except the root) is connected by exactly one incoming edge from a node called parent. Each node may have several outgoing edges to other nodes called children. Tree Properties A tree path is an ordered list of nodes that are connected by edges. The level of a node n is the number of edges on the path from the root node to n The height of a tree is equal to the maximum level of a node in the tree. Examples: binary (max child nodes = 2) and ternary trees (max child nodes = 3) Binary Tree A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child A full binary tree is a tree in which every node has either 0 or 2 children A complete binary tree has completely filled levels with exception of the last, and all nodes in the last level are as far left as possible A perfect binary tree is a binary tree in which all interior nodes have two children, and all leaves have the same level A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1 A full binary tree A complete (but not full) binary tree Binary Heap Heap is represented as a binary tree: each node on the tree has at maximum two children. Heap is a complete binary tree: a node on the left should have two children before a node on the right has any. The root of the tree has the lowest key. Each parental node has the key that is lower than keys of its children Binary Search Tree A binary search tree is a sorted tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree A binary tree is a data structure used for storing and fast retrieval of information, as well as efficient maintenance of data using addition and removal of data items Used for: Binary Search Lookup Tables Priority Queue Maps and Sets Types: AVL Red-Black Self-balancing Graph A graph is a data structure that consists of a finite set of vertices (also called nodes) and a finite set of edges represented as unordered pairs of vertices (for an undirected graph) or a set of ordered pairs (for a directed graph) A tree is a particular kind of a graph Graph Types: Undirected Graph Directed Graph Directed Acyclic Graph(DAG) Bipartite Graph Undirected Graph DAG Bipartite Graph Directed Graph Breadth First Search Starts at one node (root) and explores all nodes at the same depth prior to moving on to the nodes at the next depth level A depth level is distance (number of edges) between a node and the root (the start node) Extra memory such as a queue is needed for traversal in order to keep track of the encountered but not yet explored nodes Used for: Finding shortest path (Dijkstra) Ford-Fulkerson algorithm, flow network, matching Depth First Search The algorithm starts at one node (root) and explores as far as possible along each branch before backtracking by traversing recursively from a parent to its child until it reaches a leaf The depth-first search is used in many applications and algorithms: Finding strongly connected components Topological sorting Maze solving and generating Eulerian Path Definitions: Eulerian path is a walk in a finite graph that visits every edge exactly once Eulerian circuit or Eulerian cycle is a Eulerian path that starts and ends on the same vertex Leonhard Euler was the first who described these paths in the famous Seven Bridges of Konigsberg problem in 1736: Is it possible to construct a path (or a cycle) that visits each edge in a graph exactly once? Euler's Theorem: A connected graph has a Euler cycle if and only if every vertex has even degree Hamiltonian Cycle A Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once A Hamiltonian cycle is a cycle that has all properties of a Hamiltonian path and has the start node equal to the end node Determining whether Hamiltonian paths and cycles exist in graphs is NP- complete and known as the Hamiltonian cycle (path) problem
欢迎咨询51作业君
官方微信
TOP
Email:51zuoyejun
@gmail.com
添加客服微信:
abby12468