binary tree二叉树
recurrences递归
closed forms解析解
recursion递归
iteration迭代
closed form ( non-recursively)将递归展开
asymptotic 渐近
Algorithms: for solving problems, transforming data.
- A sequence of well-defined, computer-implementable instructions for solving a problem
- Algorithms operate on data.
Data structures: for storing data; arranging data in a way that suits an
algorithm.
1)Linear data structures: stacks and queues
2)Trees and graphs
3)Dictionaries
• Storing data
• Organizing data so that it can be used efficiently
Brute Force Algorithms
• Straightforward problem solving approach, usually based directly on the problem’s statement.
• Exhaustive search for solutions is a prime example.
Selection sort/String matching/Closest pair/Exhaustive search for combinatorial solutions/Graph traversal
• Simple, easy to program, widely applicable.
• Standard approach for small tasks.
• Reasonable algorithms for some problems.
• But: Generally inefficient—does not scale well.
• Use brute force for prototyping, or when it is known that input remains small.
in-place if it does not require additional memory except, perhaps, for a few units of memory是否使用多余的空间
stable if it preserves the relative order of elements with identical keys 对相同的元素是否保持原有的空间顺序
input-insensitive if its running time is fairly independent of input properties other than size是否其运行时间只与输入值的大小有关
Recursion
• A very natural approach when the data structure is recursive (e.g. lists, trees)
• But also examples of naturally recursive array processing algorithms
• Next week we’ll express depth first graph traversal recursively (the natural way);
• Although our recursive algorithm is short and elegant, it is not the most efficient way of solving the problem.
• Its running time grows exponentially as you grow the input amount.
• More efficient solutions can be developed using memoing or dynamic programming(around Week 10).
Decrease-and-Conquer by-a-Constant
• In this approach, the size of the problem is reduced by some constant in each iteration of the algorithm.
- Insertion Sort
- topological sorting
- Decrease-and-Conquer by-a-Factor
- Decrease-by-a-constant-factor
binary search - Decrease-by-a-variable-factor
interpolation search
Divide and Conquer
The divide-and-conquer strategy tries to make the most of this idea:
1.Divide the given problem instance into smaller instances.
2.Solve the smaller instances recursively.
3.Combine the smaller solutions to solve the original instance.
The Master Theorem/Mergesort/ Quicksort/ Tree traversal/ Closest Pair revisited
heap and priority queue-13
The heap is a very useful data structure for priority queues, used in many algorithms.
A heap is a complete binary tree which satisfies the heap condition:
– Each child has a priority (key) which is not greater than its parents.子数小于等于父max-heap
• A priority queue is a set (or pool) of elements.
• An element is injected into the priority queue together with a priority (often the key
value itself) and elements are ejected according to priority.
• We think of the heap as a partially ordered binary tree.
• Since it can be easily maintained as a complete tree, the standard implementation
uses an array to represent the tree.
- H[1]是最大的数，eject的时间复杂度是O(1)+重新存储heap的时间
- heap的高是log2(n)的向下取整，树的高是log2(n)的向下取整，空树高为-1.
- heap的parents节点为1 到n/2向下取整
As an abstract data type, the priority queue supports the following operations on a “pool”
of elements (ordered by some linear order):
– find an item with maximal priority
– insert a new item with associated priority
– test whether a priority queue is empty
– eject the largest element.
• Other operations may be relevant, for example:
– replace the maximal item with some new item
– construct a priority queue from a list of items
– join two priority queue.
Transform-and-Conquer is a group of design techniques that:
– Transform: Modify the problem to a more amenable form, and then
– Conquer: Solve it using known efficient algorithms.
1)Instance simplification
Finding the median找到中位数
Uniqueness checking唯一性检查
Finding the mode找到众数
2)Representational change
3)Problem reduction
A binary search tree, or BST, is a binary tree that stores elements in all internal
nodes, with each sin-tree satisfying the BST property:
Let the root be r; then each element in the left subtree is smaller that r and each
element in the right sub-tree is larger than r. (For simplicity, we assume that all
keys are different.)
AVL tree
• Named after Adelson-Velsky and Landis
• Recall that we defined the height of the empty tree as -1.
• For a binary (sub-) tree, let the balance factor be the difference between the height of
its left sub-tree and that of its right sub-tree.
• An AVL tree is a BST in which the balance factor is -1, 0, or 1, for every sub-tree.
Regaining balance can achieved with one or two simple, local transformtions, socalled rotations.
It is always the lowest unbalanced subtree that is re-balanced.
2-3 trees and 2-3-4 trees are search trees that allow more than one item to be stored
in a tree node.
• As with BSTs, a node that holds a single item has (at most) two children.
• A node that holds two items (a so-called 3-node) has (at most) three children.
Hashing is a standard way of implementing the abstract data type “dictionary”.
A good hash function uniformly distributes data items across the entire set of possible hash values.
A perfect hash function allows for constant time search, insertion, and deletion, into and from a hash table.
When using an open addressing method of collision resolution, all data records reside in a single bucket array.
• Implemented well, it makes data retrieval very fast.
• A key can be anything, as long as we can map it efficiently to a positive integer. In particular, the set k of keys needs not be bounded.
• Assume we have a table of size m (the hash table).
• The idea is to have a function h: k → {1, … , m} (the hash function) determine where records are
stored: A record with key k should be stored in location h(k).
• The address h(k) is the hash address.
In some cases different keys will be mapped to the same hash table address.
When this happens we have a collision.
Dynamic programming is an algorithm design technique that is sometimes applicable when we want to solve a recurrence relation and the recursion involves overlapping instances.
The bottom-up approach used the tabulated results, rather than solving overlapping
sub-problems repeatedly.使用表数据
Optimisation problems sometimes allow for clever dynamic programming solutions.
– the objective is to find the best possible combination: the one with the lowest cost, or higher profit, subject to some constraints.
• For dynamic programming to be useful, the optimality principle must hold:
– An optimal solution to a problem is composed of optimal solutions to its subproblems.一个问题的最优解是由它的子问题的最优解组成的
• While not always, this principle often holds.
动态规划：用于解决具有overlapping subproblems（memoization） 和 optimal substructure（使用局部最优解构造整体最优解）属性的问题
贪心算法：greedy choice property（是指在做每一步的选择时不需要和以前的选择一起考虑）和optimal substructure.
top-down通常以递归形式出现，从父问题开始，递归地求解子问题。top-down的求解过程通常与memoization结合，即将计算过的结果缓存在数组或者哈希表等结构中。当进入递归求解问题时，先查看缓存中是否已有结果，如果有则直接返回缓存的结果。
bottom-up通常以循环形式出现。bottom-up的求解过程通常与tabulation结合，即先解最小的子问题，解决后将结果记录在表格中（通常是一维或二维数组），解决父问题时直接查表拿到子问题的结果，然后将父问题的结果也填在表中，直到把表格填满，最后填入的就是起始问题的结果。
贪心算法
A natural strategy to problem solving is to make decision based on what is the locally best choice.当前最优状态下，找下一步
In general we cannot expect locally best choices to yield globally best outcomes.
• However, there are some well-known algorithms that rely on the greedy approach, being both correct and fast.
• In other cases, for hard problems, a greedy algorithm can sometimes serve as an acceptable approximation algorithm
Transitive closure is important in all sorts of applications where we want to see of some “goal start” is reachable from some “initial state”.
From an information-theoretic point of view, most computer files contain a lot of redundancy.
• Compression is used to store files in less space.
• For text files, savings up to 50% are common.
• For binary files, savings up to 90% are common.
• Savings in space mean savings in time for files transmission.
A trie is a binary tree for search applications.
• To search for a key we look at individual bits of a key and descend to the left whenever a bit is 0, to the right whenever it is 1.
• Using a trie to determine codes means that no code will be the prefix of another!
How many different binary search trees (BSTs) with elements {1,2,3,4} are there? And how many with elements {1,2,3,4,5}?
