1. GREEDY METHOD sometimes works well for optimization problems
1) Huffman codes
: Initialize n one-node trees with alphabet characters and the tree weights with their frequencies.
Repeat the following step n-1 times
① Join two binary trees with smallest weights into one (as left and right subtrees)
② Make its weight equal the sum of the weights of the two trees.
③ Mark edges leading to left and right subtrees with 0’s and 1’s, respectively.
2) Minimum spanning tree
A minimum spanning tree is a least-cost subset of the edges of a graph that connects all the nodes
① Start by picking any node and adding it to the tree
② Repeatedly: Pick any least-cost edge from a node in the tree to a node not in the tree, and add the edge and new node to the tree
③ Stop when all nodes have been added to the tree
: Initialize n one-node trees with alphabet characters and the tree weights with their frequencies.
Repeat the following step n-1 times
① Join two binary trees with smallest weights into one (as left and right subtrees)
② Make its weight equal the sum of the weights of the two trees.
③ Mark edges leading to left and right subtrees with 0’s and 1’s, respectively.
2) Minimum spanning tree
A minimum spanning tree is a least-cost subset of the edges of a graph that connects all the nodes
① Start by picking any node and adding it to the tree
② Repeatedly: Pick any least-cost edge from a node in the tree to a node not in the tree, and add the edge and new node to the tree
③ Stop when all nodes have been added to the tree
3) Traveling salesman
A salesman must visit every city (starting from city A), and wants to cover the least possible distance
–He can revisit a city (and reuse a road) if necessary
He does this by using a greedy algorithm: He goes to the next nearest city from wherever he is
A salesman must visit every city (starting from city A), and wants to cover the least possible distance
–He can revisit a city (and reuse a road) if necessary
He does this by using a greedy algorithm: He goes to the next nearest city from wherever he is
4) Dijkstra's algorithm (the shortest path)
|
5) Kruskal's algorithm (minimum-cost spanning tree)
|
6) Prim's algorithm (minimum-cost spanning tree)
2. DYNAMIC PROGRAMMING
Dynamic Programming is a general algorithm design technique for solving problems defined by recurrences with overlapping subproblems
Example of Dynamic Programming : Knapsack Problem
Knapsack of capacity W=5
Knapsack of capacity W=5
3. BACKTRACKING
Backtracking is a methodical way of trying out various sequences of decisions, until you find one that "works"
1) Solve a maze
There are 3 choices - Go straight, Go left, Go right
Cf. Movie 'Maze Runner'
In the movie, you have to escape the maze.
You do not have enough information. So, you go into maze everyday until find the exit.
1) Solve a maze
There are 3 choices - Go straight, Go left, Go right
Cf. Movie 'Maze Runner'
In the movie, you have to escape the maze.
You do not have enough information. So, you go into maze everyday until find the exit.
2) Coloring a map
Adjacent countries must be in different colors.
* Most can be colored within 5 colors except Mobius strip.
Adjacent countries must be in different colors.
* Most can be colored within 5 colors except Mobius strip.
4) Branch-and-Bound
Applicable to optimization problems
Applicable to optimization problems
STEP 1. Levels 0 and 1 of the state-space tree for the instance of the assignment problem being solved with the best-first branch-and-bound algorithm. The number above a node shows the order in which the node was generated. A node's fields indicate the job number assigned to person a and the lower bound value, lb, for this node. |
4. HCI
A study of all aspects of how people interact with computer hardware and software.
At first, Understand your materials (Ex. computers, people) 1. Models of interaction 1) Terms of interaction Domain : the area of work under study Goal : what you want to achieve Task : how you go about doing it 2) Norman model : Concentrates on user's view * 7 stages –user establishes the goal –formulates intention –specifies actions at interface –executes action |
–perceives system state
–interprets system state –evaluates system state with respect to goal 3) Interaction framework 2. Ergonomics 1) Physical aspects of interfaces 2) Industrial interfaces 3. Interaction styles 1) Dialogue 2) Distinct styles of interaction 4. Elements of the wimp interface 1) Windows, Icons, Menus, Pointers, etc. 5. Interactivity 6. Experience, engagement and fun |