---
# System prepended metadata

title: Coursera - Algorithmic Thinking - Module 2
tags: [' tossug', hackpad-import]

---

---
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
