Symbol-table problem Symbol table T holding n records: key key[x] [x]

The depth of a node = the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have

Dynamic order statistics OS-SELECT(i, S): returns the ith smallest element in the dynamic set S. OS-RANK(x, S): returns the rank of x ∈ S in the sorted order of S’s elements. IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes

Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u – 1} of size u subject to these operations:

Dynamic programming Design technique, like divide-and-conquer. Example: Longest Common Subsequence (LCS)

Consider a digraph G = (V, E) with edge-weight function w : E → R. The weight of path p = v1 → v2 → L → vk is defined to be

Shortest paths Single-source shortest paths Nonnegative edge weights

Take-home quiz No notes (except this one)

树是一类结构较为简单的图，是用途极 为广泛的离散数学模型，特别是二叉树， 它在计算机科学中用得最多.因此在学习 时应很好地掌握好诸如树的充要条件、 生成树、最优生成树、根树、树的各种 算法、及二叉树的访问次序等内容.平面 图是实际背景很强的一类图，能用本章 介绍的方法判断一个图是否为平面图

一、 使用HDL设计的先进性 二、Verilog的主要用途 三、 Verilog的历史 四、如何从抽象级(levels of abstraction)理解 五、电路设计 六、Verilog描述 – 逻辑仿真算法 – 如何启动Verilog-XL和NC Verilog仿真器 – 如何显示波形 1. 进一步学习Verilog的结构描述和行为描述 2. Verilog混合（抽象）级仿真 1. 理解Verilog中使用的词汇约定 2. 认识语言专用标记(tokens) 3. 学习timescale