(learn&think)

不浮躁，不自傲，学习，思考，总结

Algorithm Design Manual Chapter 5

| Comments

Book Notes

5.1 Flavors of Graphs

  • Undirected vs. Directed
  • Weighted vs. Unweighted
  • Simple vs. Non-simple
  • Sparse vs. Dense
  • Cyclic vs. Acyclic
  • Embedded vs. Topological
  • Implicit vs. Explicit
  • Labeled vs. Unlabeled

Algorithm Design Manual Chapter 4

| Comments

Book Notes

4.3 Heapsort: Fast Sorting via Data Structures

Where in the Heap?

Problem: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. Hint: you do not have to find the kth smallest element; you need only determine its relationship to x.

Solution: There are at least two different ideas that lead to correct but inefficient algorithms for this problem:

  1. Call extract-minktimes, and test whether all of these are less thanx. This explicitly sorts the firstkelements and so gives us more information than the desired answer, but it takes O(klogn) time to do so.
  2. The kth smallest element cannot be deeper than the kth level of the heap, since the path from it to the root must go through elements of decreasing value. Thus we can look at all the elements on the first k levels of the heap, and count how many of them are less thanx, stopping when we either find k of them or run out of elements. This is correct, but takes O(min(n,2k-1)) time, since the top k elements have 2k-1 elements.

An O(k) solution can look at only k elements smaller than x, plus at most O(k) elements greater than x. Consider the following recursive procedure, called at the root with i= 1 with count=k:

Algorithm Design Manual Chapter 3

| Comments

Book Notes

Contiguous vs. Linked Data Structures

  • Contiguously-allocated structuresare composed of single slabs of memory, and include arrays, matrices, heaps, and hash tables.
  • Linked data structuresare composed of distinct chunks of memory bound together bypointers, and include lists, trees, and graph adjacency lists.

The Last Thing D Needs总结

| Comments

Effective C++ 系列的作者 Scott Meyers 在 Dconf 中 The Last Thing D Needs 聊了些 C++的特性，稍微总结一下。

Initialization

Initialization
1
2
3
4
5
6
7
8
9
10
11

int x1;         // unknown, initial(pay for it)
int x2;         // (at global scope) 0, no run time cost
static int x3;  // 0, static initialization
int *px = new int;  // heap memory, unknown, has run time cost
{
    int x4;    // unknown, has run time cost 
}
int a1[100];   // unknown
int a2[100];   // (at global scope) 0
static int a3[100];  // 0
std::vector<int> v(100);  // 0, use run time cost

Algorithm Design Manual Chapter 1

| Comments

Book Notes

Combinatorial Objects

  • Permutations - arrangements, or orderings, of items (“arrangement” “tour” “ordering” or “sequence” )
  • Subsets - selections from a set of items (“cluster” “collection” “committee” “group” “packaging” or “selection”)
  • Trees - hierarchical relationships between items (“hierarchy” “dominance relationship” “ancestor/descendant relationship” or “taxonomy”)
  • Graphs - relationships between arbitrary pairs of objects (“network” “circuit” “web” or “relationship”)
  • Points - locations in some geometric space (“sites” “positions” or “locations.)
  • Polygons - regions in some geometric spaces (“shapes” “regions” or “boundaries”)
  • Strings - sequences of characters or patterns. (“text” “characters” “patterns” or “labels”)

Programming Pearls Overview

| Comments

全书分为 3 部分：

  • 预备知识：总的概括代码涉及的知识点，比如算法和数据结构的重要性和合理性，如何写出正确的代码并证明，如何测试代码，性能评估代码，debug 等。
  • 性能：先是介绍一些估算的技巧，比如 72 法则，利特尔法则(Little’s law) 等，之后展开代码算法的性能，如何调试代码使得性能更好或更省空间。
  • 产品：讲解具体的算法，如排序，搜索等。

书本和习题大部分代码实现。