# § Algorithm Design & Analysis

{% hint style="warning" %}
此 open course [](https://republic-of-cs.gitbook.io/e/rcs.102 "mention") 還在 backlog 當中，尚未被規劃

以下是此 open course 主題、教材的 candidate：

* Trie
* Divide and Conquer
* Strongly Connected Component
* Shortest Path
* Red Black/AVL Tree
* 0 / 1 Knapsack
* Unbounded Knapsack
* 1-D DP
* 2-D DP
* Two Pointers
* Prefix Sum
* Sliding Window
* Monotonic Stack
* Greedy
* [Introduction to Algorithms](https://www.google.com/search?sca_esv=3a628dd368b03a2a\&cs=0\&sxsrf=ACQVn08DXFCXn0pN9tigNdym4E_-YJN78g:1707901606216\&q=Introduction+to+Algorithms\&stick=H4sIAAAAAAAAAONgVeLUz9U3sEwvMzMwEkrMSc8vyizJyFUoSa0oScrPzz7FiJA_xcirn65vaFiSXJViWVVsCOOn5WaVJFVUpMD4xeZ5ZeY56TkwfpJ5cZFBrilQngtklqlBVWWxBZSTZ5qSZWiEpLLAsCKlCsYvqio0jjc0yIEqNqnKsTSxPMXIA5I0SiowMTEqzoabGm9QaQ6TM8kyyS1ON4eZk2VSkGWaUpbziPEeI7fAyx_3hKWuME5ac_Ia41lGLgGf_Pzi1JzKoNScxJLUlJB8IVEuNte8ksySSiFuKU4udpDxWQVlQq5c3MGpJSH5vvkpmWmVQmZCJlycvqm5SalFxf5pQupcXM75OTmpySWZ-XlCklLiXKL6yXABfViAFitFGrntujTtHJuDIAMQKHkGO0hpaAlysbnk5yZm5gkey550P0D2ib2WMBdHSGJFfl5-bqVg4fGsA0883tsrcXIC9Si0i72112KYwMTYtG_FITYODkYBBiMmDoYqBp5FrFKeeSVF-SmlYGsVSvIVHGGRWjyBjREAhs4Xq_EBAAA\&sa=X\&ved=2ahUKEwjajLGkvaqEAxXRzjgGHdjjBdwQ7fAIegQIABBK)
* KMP algorithm
  {% endhint %}

{% hint style="success" %}

#### Peak Finding

> There exist many algorithms to find the peak element in case adjacent elements are not allowed to be equal, in 𝑂(𝑚+𝑛) and 𝑂(𝑚∗𝑙𝑜𝑔(𝑛)) time. You can find them at this page and in this MIT Lecture. None of these algorithms are applicable in case when adjacent elements are allowed to be equal.

* [**Find Peak Element**](https://aaronice.gitbook.io/lintcode/binary-search/find-peak-element)
* [**Peak Index in a Mountain Array**](https://aaronice.gitbook.io/lintcode/binary-search/peak-index-in-a-mountain-array)
* [**1901. Find a Peak Element II**](https://leetcode.com/problems/find-a-peak-element-ii/)
* [**MIT OpenCourseWare - Lecture 1: Algorithmic Thinking, Peak Finding**](https://www.youtube.com/watch?v=HtSuA80QTyo)
* [**6.006 - Introduction to Algorithms - Lecture 2: Peak Finding**](https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf)

> Variants
>
> * With or without adjacent equal elements (plateau)
> * Find any peak
> * Find every peak
> * Find absolute peak
> * Had only one (or potentially more) peak
> * 1D, 2D array
>   {% endhint %}

{% hint style="success" %}

#### Mathematical Induction/Divide and Conquer

> * [**Comp Sci in 5: Mathematical Induction**](https://www.youtube.com/watch?v=38xjqkwIDiA)
> * [**Why is Binary Search a divide and conquer algorithm?**](https://stackoverflow.com/questions/8850447/why-is-binary-search-a-divide-and-conquer-algorithm)
>   {% endhint %}

{% hint style="success" %}

#### Doubly Linked Lists

> * [**Doubly Linked Lists**](https://www.youtube.com/watch?v=vqa-MP6bgaY\&list=PLrB7VCHji9zjvFydh25HBXy3ybey3lTlA\&index=5)
>   {% endhint %}

{% hint style="success" %}

#### Skip List

> * [**1206. Design Skiplist**](https://leetcode.com/problems/design-skiplist/)
>   {% endhint %}