### CMSC330 Fall 2015
### Exercises for Week 2
# Topics: Ruby strings, hashes, regular expressions


# Write a function is_palindrome?(s) that returns true if a
# string is a palindrome (in other words, if you reverse the
# string you get the same string back) and false otherwise.
def is_palindrome?(s)
end


# Write a function char_frequencies(s) that, given a string,
# returns a hash relating characters to the number of times
# they occurred.
# For example: given the string “apple”, you should return the
# hash { “a” => 1, “p” => 2, “l” => 1, “e” => 1 }.
def char_frequencies(s)
end


# Write a function is_natural_number?(s) that returns true if
# s is a natural number and false otherwise.
# Valid examples: “10”
# Invalid examples: “-5”
# Try writing two versions: one that allows whitespace at the
# beginning and end, and one that doesn’t.
def is_natural_number?(s)
end


# Write a function is_integer?(s) that returns true if s is an
# integer and false otherwise.
# Valid examples: “+15”, “-15”, “15”
# Invalid examples: “15.”
def is_integer?(s)
end


# Write a function is_decimal?(s) that returns true if s is a
# decimal number and false otherwise.
# Valid examples: “+1.0”, “+1”, “-124.124”, “1”, “-1”
# Invalid examples: “1,000.0”, “1.1.1”
def is_decimal?(s)
end


# Write a function find_all_decimals(s) that returns an array
# of all valid decimal numbers in the string.
def find_all_decimals(s)
end


# Write a function find_all_date(s) that, given a string, returns
# an array of all valid dates in the string. A valid date
# is a substring in the format MM/DD/YYYY.
def find_all_dates(s)
end


# Write a function substring_frequencies(s, regexp) that, given a
# string and a regular expression, counts the number of
# occurrences of substrings matching that regular expression.
# Return the substring frequencies in the same format as in
# char_frequencies.
# Note: this method should behave the same way as
# char_frequencies if regexp is /./
def substring_frequencies(s, regexp)
end


# Write a function common_words(s, regexp) that, given a string
# and a regular expression, returns the five most frequently
# occurring substrings matching the regular expression along with
# their frequencies in the same format as in
# substring_frequencies.
def common_words(s, regexp)
end


##### Challenge Question #####

# A sparse matrix is one that in which most of the elements consist of the same
# (default) value. If the matrix is very large, then representing it as we
# normally would require unnecessary space.

# Below is a skeleton implementation of a class SparseMat. It implements a 2-d
# square matrix whose representation assumes it will be sparse. Complete the
# implementation such that the storage of non-default elements takes O(n), n is
# the number of the elements you put into the matrix. And importantly, the
# lookup time for an element should be O(1) given the coordinates x,y
# (coordinates start at 0). Hint: you can assume that Ruby hashes have these
# properties, so you might want to use them in your implementation (but you can
# use other data structures, too, if you like).

#Methods to implement:
#  the constructor takes the size of the matrix (the dimension), and the default
#   value
#  get(x,y) returns the value at x,y or throws an exception if out of bounds
#  put(x,y,e) updates the value at x,y or throws an exception if out of bounds
#  getall(cs) returns an array of values as indicated by the coordinates in cs
#  add(M) returns a matrix that is result of adding matrix M, throws an
#   exception if the dimensions differ

# Example session:
# irb> x = SparseMax.new(2,0)
# => ...
# irb> x.get(1,2)
# IndexError: 1,2 outside of bounds of 2D-matrix size 2
#   ...
# irb> x.get(0,0)
# => 0
# irb> x.put(1,1,5)
# => 5
# irb> x.get(1,1)
# => 5
# irb> x.getall([[1,1],[0,0]])
# => [5, 0]