Algorithms Day 31 L18.2 Negative-weight cycles Recall: If a graph G = (V, E) contains a negative￾weight cycle, then some shortest paths may not exist. Example:

Definition. A directed graph (digraph) G = (V, E) is an ordered pair consisting of • a set V of vertices (singular: vertex)

How large should a hash table be? Problem: What if we don’t know the proper size in advance? Goal: Make the table as small as possible, but large enough so that it won’t overflow (or otherwise become inefficient)

Computational geometry Algorithms for solving “geometric problems” in 2D and higher. Fundamental objects: point line segment line Basic structures: point set polygon

Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items

Algorithms Day 12 L8.2 A weakness of hashing Problem: For any hash function h, a set of keys exists that can cause the average access time of a hash table to skyrocket. IDEA: Choose the hash function at random, independently of the keys

Order statistics Select the ith smallest of n elements (the element with rank i)

Proposed by C.A.R. Hoare in 1962. Divide-and-conquer algorithm. Sorts “in place” (like insertion sort, but notlike merge sort). Very practical (with tuning)

The analysis of merge sort fromLecture 1 required us to solve arecurrence. Recurrences are like solving integrals,differential equations, etc.o Learn a few tricks

前面介绍了 Keil 软件的使用，从中我们可以看到 Keil 的强大功能，不过，对于初学者 来说，还有些不直观，调试过程中看到的是一些数值，并没有看到这些数值所引起的外围电 路的变化，例如数码管点亮、发光管发光等。为了让初学者更好地入门，笔者利用 Keil 提 供的 AGSI 接口开发了两块仿真 实验板