程序代写案例-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作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468