notes on learning algorithm

learn-algorithms.md

https://cses.fi/book/book.pdf

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/assignments/

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-videos/

Lec 1 | Mathematic for computer science

A proof is a method of ascertaining a proof

• experimenting/observing
• sampling, counter example
• judge, jury
• word of God
• authority, god

A mathematical proof is a verification of a proposition by a chain of logical deduction from a set of axioms

• a proposition is a statement that is either true or false
• an axiom is a proposition that is "assumed" to be true

Lec 1 | Introduction to algorithm

• 1D array find a peak solution

func findPeakElement(nums []int) int {
    return findPeakUtil(nums, 0, len(nums)-1, len(nums))
}

func findPeakUtil(nums []int, low, high int, length int) int {
    mid := low + (high - low) / 2
    
    if (mid == length - 1 || nums[mid] >= nums[mid + 1]) && (mid == 0 || nums[mid] >= nums[mid - 1]) {
        return mid
    } else if nums[mid] < nums[mid + 1] {
        return findPeakUtil(nums, mid+1, high, length)
    } else {
        return findPeakUtil(nums, low, mid-1, length)
    }
    
    return -1
}