[Udacity CS 215] Algorithms (Final Exam)

  
previously:
第六个unit  http://www.1point3acres.com/bbs/thread-37918-1-1.html
第五个unit  http://www.1point3acres.com/bbs/thread-37701-1-1.html
第四个unit  http://www.1point3acres.com/bbs/thread-37651-1-1.html
第三个unit  http://www.1point3acres.com/bbs/thread-37565-1-1.html
第二个unit  http://www.1point3acres.com/bbs/thread-37403-1-1.html
第一个unit  http://www.1point3acres.com/bbs/thread-37390-1-1.html

期末考试

第一题
# Write a function, `bipartite` that
# takes as input a graph, `G` and tries
# to divide G into two sets where
# there are no edges between elements of the
# the same set - only between elements in
# different sets.

官方提示（下同）：用图遍历算法生成两个列表A和B; 如果把一个节点标记为A那它的邻居就标记为B，任何相邻的节点都不能同号。


第二题
# Take a weighted graph representing a social network where the weight
# between two nodes is the "love" between them.  In this "feel the
# love of a path" problem, we want to find the best path from node `i`
# and node `j` where the score for a path is the maximum love of an
# edge on this path. The returned path doesn't need to be simple, ie it can
# contain cycles or repeated vertices.

用BFS先算出从出发点到每个点的最大距离和路径。


第三题
# In lecture, we took the bipartite "Marvel" graph,
# where edges went between characters and the comics
# books they appeared in, and created a weighted graph
# with edges between characters where the weight was the
# number of comic books in which they both appeared.
#
# In this assignment, determine the weights between
# comic book characters by giving the probability
# that a randomly chosen comic book containing one of
# the characters will also contain the other


根据公式W(a, b) = W(b, a) = P(contains A and contains B | contains A or contains B) 依次计算所有character顶点对


第四题
# We want you to take the list of flights, and create a
# graph.  Then, write a modified Dijkstra's algorithm to find the best
# combination of flights to get between two cities, where flights `x`
# is better than flights `y` if `x` has lower cost *or* if they are
# tied in cost, `x` has shorter total flight time.

把做Dijkstra时用的heap加一维"总飞行时间"。


第五题
# Design and implement an algorithm that can preprocess a
# graph and then answer the question "is x connected to y in the
# graph" for any x and y in constant time Theta(1).

BFS一次，标号。不同的连通分量的顶点属于不同号。


第六题
# In the shortest-path oracle described in Andrew Goldberg's
# interview, each node has a label, which is a list of some other
# nodes in the network and their distance to these nodes.  These lists
# have the property that
#
#  (1) for any pair of nodes (x,y) in the network, their lists will
#  have at least one node z in common
#
#  (2) the shortest path from x to y will go through z.
#
# Given a graph G that is a balanced binary tree, preprocess the graph to
# create such labels for each node.  Note that the size of the list in
# each label should not be larger than log n for a graph of size n.

从根节点开始，每次为孩子节点建label时，利用父节点label和父子节点间的边距离。


第七题
# This is the same problem as "Distance Oracle I" except that instead of
# only having to deal with binary trees, the assignment asks you to
# create labels for all tree graphs.

找出当前图的"中心节点"，更新所有相连的节点的label，删除该"中心节点"，重复该过程。找中心节点的做法是在树中找出一条最长路径（对于图来说是NPC问题，但是对于树是P问题），然后在把路径的中间作为中心节点。
参考 http://stackoverflow.com/questions/3124566/binary-tree-longest-path-between-2-nodes


第八题
# Each edge (u,v) in a social network has a weight p(u,v) that
# represents the probability that u would do a favor for v if asked.
# Note that p(v,u) != p(u,v), in general. 呵呵 男女不平等呀～
#
# Write a function that finds the right sequence of friends to maximize
# the probability that v1 will do a favor for v2.
#
# We provide two standard versions of dijkstra's algorithm that were
# discussed in class. One uses a list and another uses a heap.

根据边数M和顶点数N的关系决定用heap还是用list的方式做dijkstra。 heap需要O(M*logN)。list需要O(N^2)。 另外，由于图中边的权重都为0到1的小数，可以用log把他们放大再做dijkstra。
  
  
   

Finally finish all the final exam questions with HIGHEST DISTINCTION. Cheers!!

Is there any way to get credits from 1p3 forum?

Only finish the first 3 questions...Feel so frustrated when I try to solve the problem 4-8