---
hackpadID: 7jW9K4YejFp
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# Coursera - Algorithmic Thinking - Module 2

[課程綱要](/j0ApzQ1mQGK)

## Terminology

worst-case running time

best-case running time

tightest upper bound

BFS = Breadth-first Search

* The running time is O(n^2) or O(m+n) or O(m). m is the number of edge. n is the number of node.
* O(n^2) when the graph is closed to complete graph.
* O(m+n) when the graph is sparse.
* O(m) when the graph is sparse and m > n.
* For the tree search algorithm, you also need to consider how tree is stored. Adjacency matrix and adjacency list might have different complexity. 

* 有沒有按讚的地方？CZChen++

* The worse case is O(n^2).

## Homework

**Question 8**

n0=1 的意思是從 n 等於 1 開始都要成立

## Project

## Application

Question 1

Question 2

[兩千次 computer network graph 的結果](https://class.coursera.org/algorithmicthink-001/forum/thread?thread_id=699)，大家可以參考一下

**Question 3**

**Question 4**

**Question 5**

**Bonus Question 6**

**Challenge - Disjoint set algorithm**

What is this?

[Project](https://class.coursera.org/algorithmicthink-001/wiki/Programming_assignment_3) 中有說過：

**Challenge problem:** In the Application, you will compute the resilience of graphs with several thousand nodes and edges. In desktop Python, this computation will take on the order of a few seconds. In CodeSkulptor, this computation will take 3-5 minutes per graph. As a challenge, investigate other asymptotically faster approaches to implementing compute_resilence. We have implemented one approach based on a simple [disjoint set algorithm](http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_linked_lists) that has a running time of _O_(_n_log(_n_)+_m_). This method can perform all of the analysis in the Application part of this Module in CodeSkulptor in a few seconds.

## Progress

* czchen

* Homework
* Project
* Application

* [FourDollars](https://tossug.hackpad.com/ep/profile/tgNQRpN8EgG)

* Homework
* Project

* Application

* [Kommodore Kezza](/ep/profile/CvxduB5FRRT)

* Homework
* Project
* Application
* Peer Assessment

* Q6 要等 [rubric 改動](https://class.coursera.org/algorithmicthink-001/forum/thread?thread_id=839#comment-2764)過後再看看

* allenwangs

* Homework
* Project
* Application
* Peer Assessment