§ Algorithm Design & Analysis

此 open course RCS.102 還在 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

• KMP algorithm

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

• Peak Index in a Mountain Array

• 1901. Find a Peak Element II

• MIT OpenCourseWare - Lecture 1: Algorithmic Thinking, Peak Finding

• 6.006 - Introduction to Algorithms - Lecture 2: Peak Finding

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

Mathematical Induction/Divide and Conquer

• Comp Sci in 5: Mathematical Induction

• Why is Binary Search a divide and conquer algorithm?

Doubly Linked Lists

• Doubly Linked Lists

Skip List

• 1206. Design Skiplist