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是否其運行時間只與輸入值的大小有關(guān)
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.子數(shù)小于等于父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]是最大的數(shù)宏侍，eject的時間復雜度是O(1)+重新存儲heap的時間
- heap的高是log2(n)的向下取整，樹的高是log2(n)的向下取整杨名，空樹高為-1.
- heap的parents節(jié)點為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找到中位數(shù)
Uniqueness checking唯一性檢查
Finding the mode找到眾數(shù)
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.使用表數(shù)據(jù)
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.一個問題的最優(yōu)解是由它的子問題的最優(yōu)解組成的
? While not always, this principle often holds.
動態(tài)規(guī)劃：用于解決具有overlapping subproblems（memoization） 和 optimal substructure（使用局部最優(yōu)解構(gòu)造整體最優(yōu)解）屬性的問題
貪心算法：greedy choice property（是指在做每一步的選擇時不需要和以前的選擇一起考慮）和optimal substructure.
top-down通常以遞歸形式出現(xiàn)宴猾，從父問題開始崇呵，遞歸地求解子問題陨囊。top-down的求解過程通常與memoization結(jié)合，即將計算過的結(jié)果緩存在數(shù)組或者哈希表等結(jié)構(gòu)中诱建。當進入遞歸求解問題時稀并，先查看緩存中是否已有結(jié)果仅颇，如果有則直接返回緩存的結(jié)果。
bottom-up通常以循環(huán)形式出現(xiàn)碘举。bottom-up的求解過程通常與tabulation結(jié)合忘瓦，即先解最小的子問題，解決后將結(jié)果記錄在表格中（通常是一維或二維數(shù)組）引颈，解決父問題時直接查表拿到子問題的結(jié)果政冻，然后將父問題的結(jié)果也填在表中，直到把表格填滿线欲，最后填入的就是起始問題的結(jié)果明场。
貪心算法
A natural strategy to problem solving is to make decision based on what is the locally best choice.當前最優(yōu)狀態(tài)下，找下一步
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}?
