Algorithms lecture notes

clock.rb

# find angle between clock hands
def angle(hour, minutes)

    hour += (minutes / 60.0)

    angle_hour = hour * 30
    angle_mins = minutes * 6

    (angle_hour - angle_mins).abs
end

# 1:35  -->  angle(1, 35)
puts angle(11, 55)

compress.js

// compressing a large array into smaller one
// values in between the samples kept can be ignored

        // audioSamples = <large array with lotsa values>
        var numSamples = 20;
        var cursor = 0;
        var samples = [];

        for(var i = 0; i < numSamples; i++) {
            
            while(cursor/audioSamples.length < i/numSamples && cursor < audioSamples.length) {
                cursor++;
            }

            var sample = audioSamples[cursor];
            samples.push(Math.max(sample, 0.05));
        }

division.rb

# implement division with only plus, minus, comparison operators

def divide(numerator, denominator)
    result = 0
    while numerator >= denominator
        numerator -= denominator
        result += 1
    end
    remainder = numerator
    return result, remainder
end

puts divide(12, 4).inspect
puts divide(14, 4).inspect

find_index.rb

# find a number at index
# complexity O(n) linear
def find_index(num, numbers)
    numbers.each_with_index do |n, i|
        if n == num
            return i
        end
    end
    return nil
end

puts find_index(5, [34, 57, 5, 33])

find_index_sorted.rb

# assume sorted input array
# complexity O(log N)

def find_number(numbers, find_number)

    middle = numbers.size / 2
    first = 0
    last = numbers.size - 1

    loop do
        puts "#{first}, #{middle}, #{last}"
        if find_number == numbers[middle]
            return middle
        elsif find_number < numbers[middle]
            last = middle
            middle = (last + first) / 2
        elsif find_number > numbers[middle]
            first = middle
            middle = (last + first) / 2
        elsif numbers[last] == numbers[first]
            return nil
        end

    end

    return nil
end