RePublic of CS
  • INFO
    • ❔What is RePublic of CS?
    • πŸ—ΊοΈRCS Open Course
    • πŸ›οΈRCS Classroom
    • πŸ‘©β€πŸŒΎRCS Forum (soon)
    • 🌟RCS Mentors
    • πŸ™‹ε¦‚δ½•εƒθˆ‡ε­ΈηΏ’οΌŸ
      • ⏳RCS.101 x Miters (24 Q2)
  • βš’οΈRCS.101
    • Β§ DSA In Action
    • RCS.101.a
    • RCS.101.b
    • RCS.101.c
    • RCS.101.d
    • ΒΆ Graduation
      • Apx: BFS/Shortest Path
      • Apx: Classic Applications
      • Apx: Techniques & Tricks
      • Apx: Morris Traversal
      • Apx: RCS.101 x Miters W6
      • Apx: In-place Merge Sort
  • πŸ“šRCS.102
    • Β§ Algorithm Design & Analysis
    • βŒ› Divide & Conquer
    • βŒ› Recursion
  • 🧡RCS.103
    • Β§ SYS/PARL Programming
  • πŸ¦€RCS.201
    • Β§ Rust
  • 🧱RCS.301
    • Β§ Software Architecture
  • 🏰RCS.302
    • Β§ Web System Design
  • πŸ“£MEDIA
    • YouTube
    • Twitch
    • Threads
    • Discord Forum
    • Become an Editor
    • Resources
  • πŸ“œArticles
    • System Design, Actually
Powered by GitBook
On this page
  1. RCS.102

Β§ Algorithm Design & Analysis

Last updated 1 year ago

ζ­€ 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

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

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

Doubly Linked Lists

Skip List

Introduction to Algorithms
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
Comp Sci in 5: Mathematical Induction
Why is Binary Search a divide and conquer algorithm?
Doubly Linked Lists
1206. Design Skiplist
πŸ“š
Page cover image