khult/Arrays and Matrices

## Arrays and Matrices
//==================================================
//
// Homework 2, Part B
//
// Name: Kristofer Hult
//
//==================================================


//================================================
// Vec
//================================================

class Vec private (private val elems:Array[Double]) {
  val length = elems.length

  def this(x:Double) = this(Array(x))

  def apply(i:Int) = elems(i)

  def ++(other:Vec) = {
    val r_length = length + other.length
    val r_elems = new Array[Double](r_length)
    for (i <- 0 to length - 1) r_elems(i) = elems(i)
    for (i <- 0 to other.length - 1) r_elems(length + i) = other.elems(i)
    new Vec(r_elems)
  }

  def +(other:Vec) = {
    val r_elems = new Array[Double](length)
    for (i <- 0 to length - 1) r_elems(i) = elems(i) + other.elems(i)
    new Vec(r_elems)
  }

  def *(other:Vec) = {
    var p = 0.0
    for (i <- 0 to length - 1)
      p = p + (elems(i) * other.elems(i))
    p
  }

  override def toString = {
    var s = "<" + this.apply(0)
    for (j <- 1 to length - 1)
      s = s + ", " + this.apply(j)
    s + ">"
  }

  // overrides the default definition of == (an alias of equals)
  override def equals(other:Any):Boolean = other match {
    // if other is an instance of Vec then ...
    case o:Vec =>
      for (j <- 0 to length - 1)
        if (this.apply(j) != o.apply(j)) return false
      true
    // otherwise return false
    case _ => false
  }
}


//================================================
// Matrix
//================================================

// Suggestion: for testing purposes it is convenient
//             to implement toString first


// (The main constructor of) Matrix takes as input
// an array of n > 0 vectors all of the same length
class Matrix private (a:Array[Vec]) {

  // Public constructor
  def this(v:Vec) = this(Array(v))
  def this(x:Double) = this(new Vec(x))

  // the array is stored as is in the private field rows
  // the element at position (i,j) in the matrix is stored
  // as the j-th element of the i-th vector in rows
	 private val rows = a

	// integer field h stores the height of the matrix
 val h = {rows.length}

 // integer field w stores the width of the matrix
 val w = {rows(0).length }

 /* given i in [0 .. h-1] and j in [1 .. w-1],
    apply(i,j) returns the matrix element at position (i,j)
 */
 def apply(i:Int, j:Int) = {
   rows(i).apply(j)
 }
	/* given a matrix other with other.w == w,
	   /(other) returns a new matrix m such that
	   - m.h == h + other.h
	   - m.w == w
	   - for all i in [0 .. h-1] and j in [0 .. w-1],  m(i,j) == this(i,j)
	   - for all i in [h .. r.h-1] and j in [0 .. w-1],  m(i,j) == other(i,j)
	*/
	def /(other:Matrix) = {
	    val mLength = h + other.h
      val vectors = new Array[Vec](mLength)

      for (i <- 0 to h - 1) {
             vectors(i) = new Vec(apply(i, 0))
             for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j))
                }
      for (i <- 0 to other.h - 1) {
             vectors(i + h) = new Vec(other.apply(i, 0))
             for (j <- 1 to w - 1) vectors(i + h) ++= new Vec(other.apply(i, j))
                }
      new Matrix(vectors)
}

	/* given a matrix other with other.h == h,
	   ++(other) returns a new matrix m such that
	   - m.h == h
	   - m.w == w + other.w
	   - for all i in [0 .. h-1] and j in [0 .. w-1],  m(i,j) == this(i,j)
	   - for all i in [0 .. h-1] and j in [w .. r.w-1],  m(i,j) == other(i,j)
	*/
	def ++(other:Matrix) = {
	  val mLength = w + other.w
    val vectors = new Array[Vec](h)

    for (i <- 0 to h - 1) {
           vectors(i) = new Vec(apply(i, 0))
           for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j))
           for (j <- 0 to other.w - 1) vectors(i) ++= new Vec(other.apply(i, j))
           }
    new Matrix(vectors)
}
	/* given a matrix other with other.h == h and other.w == w,
	   +(other) returns a new matrix m such that
	   - m.h == h
	   - m.w == w
	   - for all i in [0 .. h-1] and j in [0 .. w-1],
	     m(i,j) == this(i,j) + other(i,j)
	*/
	def +(other:Matrix) ={
      val vectors = new Array[Vec](h)
      for (i <- 0 to h - 1) {
          vectors(i) = new Vec(apply(i, 0))
          for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j) + other.apply(i, j))
                }
      new Matrix(r_vecs)
        }

 /* given a j in [0 .. w-1],
    col(j) returns a vector v whose elements come
    from the j-th column of the matrix, i.e.,
    - v.length == h
    - for all i in [0 .. h-1] ,  v(i) == this(i,j)
 */
  private def col (j:Int) = {
   var c = new Vec(rows(0)(j))
   for (i <- 1 to h - 1)
     c = c ++ new Vec(rows(i)(j))
   c
 }

	/* transpose returns a new matrix m such that
	   - m.h == w
	   - m.w == h
	   - for all i in [0 .. m.h-1] and j in [0 .. m.w-1],  m(i,j) == this(j,i)

	   Suggestion: use method col
	*/
 def transpose =  {
     val vectors = new Array[Vec](h)
     for (i <- 0 to h - 1) r_vecs(i) = col(i)
     new Matrix(vectors)
        }


  /* given an i in [0 .. h-1], rowToString(i)
    returns a string of the form  | d1 d2 ... dw |
    where d1, ..., dw are the (the string representation of)
    the elements in row i
 */
 private def rowToString(i:Int) = {
   var s = "| "
   for (j <- 0 to w - 1)
     s = s + this.apply(i,j) + " "
   s ++ "|"
 }

/* toString returns a string of the form

   | d_00 d_01 ... d_0q |
   | d_10 d_11 ... d_1q |
   |  .    .        .   |
   |  .    .        .   |
   |  .    .        .   |
   | d_p0 d_p1 ... d_pq |

   where d_ij is the (the string representation of) this(i,j)
 */
 override def toString = {
     var out:String = "";
     for (i <- 0 to h - 1) out ++= rowToString(i) + "\n"
     out
        }

 // overrides the default definition of == (an alias of equals)
 override def equals(other:Any):Boolean = other match {
   // if o is an instance of Matrix then ...
   case o:Matrix =>
     for (i <- 0 to h - 1; j <- 0 to w - 1)
       if (this(i,j) != o(i,j)) return false
     true
		// otherwise return false
		case _ => false
  }
}


// A few test cases you could try
val m1 = new Matrix(1) ++ new Matrix(2) ++ new Matrix(3)
val m2 = new Matrix(4) ++ new Matrix(5) ++ new Matrix(6)
val m3 = m1 / m2 / m1
val m4 = m1 ++ m2


val m = new Matrix

## Classes
//==================================================
//
// Homework 3
//
// Name: Kristofer Hult
//
//==================================================

/* Generic abstract class for finite sets */
abstract class FinSet[T] protected () {
	 /* returns a list consisting of the set's elements */
  def toList:List[T]

  /* given a value x, it retuns a new set consisting of x
     and all the elemens of this (set)
  */
  def +(x:T):FinSet[T]

  /* given a set other, it returns the union of this and other,
     i.e., a new set consisting of all the elements of this and
     all the elements of other
  */
  def U(other:FinSet[T]):FinSet[T]

  /* given a set other, it returns the intersection of this and other,
     i.e., a new set consisting of all the elements that occur both
     in this and in other
  */
  def ^(other:FinSet[T]):FinSet[T]

  /* given a set other, it returns the difference of this and other,
     i.e., a new set consisting of all the elements of this that
     do not occur in other
  */
  def \(other:FinSet[T]):FinSet[T]

  /* given a value x, it retuns true if and only if x is an element of this
  */
  def contains(x: T):Boolean

  /* given a set other, it returns true if and only if this is included
     in other, i.e., iff every element of this is an element of other
  */
  def <=(other:FinSet[T]):Boolean = {
  	case o:FinSet[T] =>  (this <= o)
    case _ => false
  }

  override def toString = "{" ++ (toList mkString ", ") ++ "}"

  // overrides the default definition of == (an alias of equals)
  override def equals(other:Any):Boolean = other match {
    // if other is an instance of FinSet[T] then ...
    case o:FinSet[T] =>
      // it is equal to this iff it includes and is included in this
      (this <= o) && (o <= this)
    case _ => false
  }
  // Note: compiling the method equals above may produce this warning:
  // "there were 1 unchecked warnings; re-run with -unchecked for details"
  // You can ignore it
}


/* Generic concrete class implementing finite sets internally
   as lists with no repetitions
*/
// Precoditions: the input list l has no repeated elements
class ListSet[T] private (l: List[T]) extends FinSet[T] {
  def this() = this(Nil)

  // invariant: elems is a list with no repetitions
  //            storing all of the set's elements
  private val elems = l

  /* this method can be useful in implementing some of the methods
     from FinSet. Given a value x and a list l with no repetitions,
     it returns a list with no repetitions consisting
     of x and all the elements of l
  */
  private def add(x:T, l:List[T]):List[T] = l match {
    case Nil => x :: Nil
    case y :: t => if (x == y) l else y :: add(x, t)
  }

  val toList = elems   /* returns a list consisting of the set's elements */


  def +(x: T) = {
  	new ListSet[T](this.add(x, elems))/* given a value x, it retuns a new list consisting of x
     																	and all the elemens of this (set)
  																		*/
  }


  def U(other:FinSet[T]) = {
  	/* given a list other, it returns the union of this and other,
     i.e., a new list consisting of all the elements of this and
     all the elements of other
  	*/
  	var UList=List[T]()
  	for(i<-other.toList){
  		UList=this.add(i,UList)
  	}
  	new ListSet[T](UList)
  }

  def ^(other:FinSet[T]) = {
   /* given a list other, it returns the intersection of this and other,
     i.e., a new list consisting of all the elements that occur both
     in this and in other
   */
   var IList=List[T]()
   for(i<-other.toList){
  		if(elems.contains(i){
  			IList=i::IList
  		}
  	}
   new ListSet[T](IList)
  }

  def \(other:FinSet[T]) = {
  	/* given a list other, it returns the difference of this and other,
     i.e., a new list consisting of all the elements of this that
     do not occur in other
  	*/
  	var DiffList=List[T]()
  	for(i<-elems){
  		if(!other.contains(i)){
  			DiffList=i::DiffList
  		}
  	}

  }


  def contains(x:T) = {
  	/* given a value x, it retuns true if and only if x is an element of this
   */
    for(i<-other.toList){
    	if(x==toList[i])
    }
}


/* Generic concrete class implementing finite sets internally
   as immutable Maps from T to Unit
*/
class MapSet[T] private (m: Map[T, Unit]) extends FinSet[T] {
  def this() = this(Map())

  // invariant: the pair (x, ()) is in the map elems if and
  //            only if x is an element of the set
  private val elems = m

  /* This method can be useful in implementing toList. Given
     - a list List( (x1,()), ..., (xm,()) ) and
     - a list List( y1, ..., yn ), it returns the list
     List( yn, ..., y1, xm, ..., m1 )
  */
  private def project(l1:List[(T, Unit)], l2:List[T]):List[T] =
    l1 match {
      case Nil => l2
      case (x, _) :: t => project(t, x :: l2)
    }

  val toList = elems.keys


  def +(x:T) =  new.MapSet[T](elems +(x->()))

  def U(other:FinSet[T]) =  {
  	var UMap=elems
  	for(i<-other.toList){
  		UMap=UMap+(i ->())
  	}
  	new MapSet[T](UMap)
  }


  def ^(other:FinSet[T]) =  {
  	var IMap=Map[T,Unit]()
  	for(i <-other.toList){
  		if(elems.contains(i){
  			IMap=IMap+(i -> ())
  		}
  	}
  	new MapSet[T](IMap)
  }

  def \(other:FinSet[T]) =  {
  	var DiffMap=Map[T,Unit]()
  	for(i<-elems){
  		if(!other.contains(i)){
  			DiffMap=DiffMap+(i -> ())
  		}
  	}
  	new MapSet[T](DiffMap)
  }

  def contains(x:T) =  elems.contains(x)
}


/* some test cases for ListSet

val empty = new ListSet[Int]

val s1 = empty + 1

val s2 = empty + 2

val s12 = s1 U s2

val s21 = s2 U s1

s1 == s12 // should return false

s21 == s12 // should return true

s12 U s1 // should return a set equal to s12

val s123 = s12 + 3

val s23 = empty + 2 + 3

val s234 = s23 + 4

s123 ^ s234  // should evaluate to a set equal to s23

s123 \ s234  // should evaluate to a set equal to s1

s12 \ s21  // should evaluate to an empty set

s23 contains 2  // should evaluate to true

s23 contains 4  // should evaluate to false

s23 <= s123  // should evaluate to true

s23 <= s234  // should evaluate to true

s23 <= s23  // should evaluate to true

s1 <= s23 // should evaluate to false

*/


/* same test cases but for MapSet

val empty = new MapSet[Int]

val s1 = empty + 1

val s2 = empty + 2

val s12 = s1 U s2

val s21 = s2 U s1

s1 == s12 // should return false

s21 == s12 // should return true

s12 U s1 // should return a set equal to s12

val s123 = s12 + 3

val s23 = empty + 2 + 3

val s234 = s23 + 4

s123 ^ s234  // should evaluate to a set equal to s23

s123 \ s234  // should evaluate to a set equal to s1

s12 \ s21  // should evaluate to an empty set

s23 contains 2  // should evaluate to true

s23 contains 4  // should evaluate to false

s23 <= s123  // should evaluate to true

s23 <= s234  // should evaluate to true

s23 <= s23  // should evaluate to true

s1 <= s23 // should evaluate to false

*/


/* Same test cases but mixing ListSet and MapSet instances
   In a correct implementation ListSet and MapSet should be
   interchangeable

val empty = new ListSet[Int]

val s1 = empty + 1

val s2 = (new MapSet[Int]) + 2

val s12 = s1 U s2

val s21 = s2 U s1

s1 == s12 // should return false

s21 == s12 // should return true

s12 U s1 // should return a set equal to s12

val s123 = s12 + 3

val s23 = empty + 2 + 3

val s234 = s23 + 4

s123 ^ s234  // should evaluate to a set equal to s23

s123 \ s234  // should evaluate to a set equal to s1

s12 \ s21  // should evaluate to an empty set

s23 contains 2  // should evaluate to true

s23 contains 4  // should evaluate to false

s23 <= s123  // should evaluate to true

s23 <= s234  // should evaluate to true

s23 <= s23  // should evaluate to true

s1 <= s23 // should evaluate to false

*/

## Using Dictionaries
//==================================================
//
// Homework 2, Part A
//
// Name: Kristofer Hult
//
//==================================================


abstract class Dictionary {

  /* put(k,v) adds value v to the dictionary under key k.
     put may be called with the same key multiple times,
     all key->values pairs get stored in the dictionary
  */
  def put(key:String, value: Any):Unit

  /* get(k) returns Some(v) where v is one of the values
     associated with key k in the dictionary, if any.
     It returns None if k is associated to no value.
  */
  def get(key:String):Option[Any]

   /* remove(k) removes one value v associated with key k
      from the dictionary, if any, and returns it as Some(v).
      It returns None if k is associated to no value.
  */
  def remove(key:String):Option[Any]

 /* toList() returns a list containing all the key/value pairs
    in the dictionary.
    If multiple values have the same key k, each is listed
    in a separate pair with k.
   */
   def toList():List[(String,Any)]

 /* toString() returns a string containing all the key/value pairs
     in the dictionary. The string has the form

        Dictionary(key_1 -> value_1, ..., key_n -> value_n)

     where each key_i is a key and each value_i is (the string
     representation of) the corresponding value.
     If multiple values have the same key k, each is present
     in a separate pair with k.
   */
   override def toString():String

  /* getAll(k) returns the list of all the values associated
     with key k in the dictionary.
  */
  def getAll(key:String):List[Any] ={
    var l = List[Any]()
    for ((k,v) <- toList)
      if (k == key) l = Any::l
    l
  }


  /* removeAll(k) removes from the dictionary all the values
     associated with key k in the dictionary, if any.
  */
  def removeAll(key:String) = {
    while (get(key) != None)
      remove(key)
}


class ListDictionary extends Dictionary {
  /* the dictionary is implemented using a list of key/value pairs */
  private var d = List[(String,Any)]()

  /* put(k,v) adds value v to the dictionary under key k.
     put may be called with the same key multiple times,
     all key->values pairs get stored in the dictionary
  */
  def put(key:String, value: Any):Unit={
  	d=(key, value)::d
  }

  /* get(k) returns Some(v) where v is one of the values
     associated with key k in the dictionary, if any.
     It returns None if k is associated to no value.
  */
  def get(key:String):Option[Any]= {
    for ((a,x) <- d)
      if (a == key) return Some(x)
    None
  }

  def remove(key:String):Option[Any]

 /* toList() returns a list containing all the key/value pairs
    in the dictionary.
    If multiple values have the same key k, each is listed
    in a separate pair with k.
   */
def toList():List[(String,Any)]={
    var l = List[(key,value)]()
    for (a <- d; element <- a)
	    l = element::l
    l
  }

 /* toString() returns a string containing all the key/value pairs
     in the dictionary. The string has the form

        Dictionary(key_1 -> value_1, ..., key_n -> value_n)

     where each key_i is a key and each value_i is (the string
     representation of) the corresponding value.
     If multiple values have the same key k, each is present
     in a separate pair with k.
   */
   override def toString():String={
   	var d=toList();
    def toStringSecondary(l:List[(key,value)]):String =
      l match {
        case Nil => ""
        case (k,v)::Nil => k + " -> " + v
        case (k,v)::t => k + " -> " + v + ", " + toStringSecondary(t)
      }

    "Dictionary(" + toStringSecondary(d) + ")"
  }
   }


}


## Using Variables
/*==================================================

    Homework 1

    Name: Kristofer Hult

  ==================================================
*/

//---------
// Part 1
//In the following problems do not dene methods recursively. Instead, use mutable variables and
//while or for loops as needed in method denitions. You may use auxiliary methods if needed.
//---------

/* Problem 1.1 */
def mul (m: Int, n: Int):Int =
{
for(i <- 1 to m){  //for loop that starts at 1 and goes until the value given for m
  if(m==0 || n==0){ //if m or n is zero the result will be zero
    0
  }
  else{
    var x:Int+=x+n// adds value of n until it reaches the value of m, gives result of n * m
}
}
}

/* Problem 1.2 */
def concatAll (l: List[String]) :String=
{
for(i <- 0 to l.length){		//for loop that starts at zero and goes to the length of list l
  var combination: string +=l[i] //combines the list together to form a word
}
}
/* Problem 1.3 */
def isIn (x: Int, l: List[Int]) :Boolean
{
for(i <- 0 to l.length){//for loop that starts at zero and goes to the length of list l

  if (x=l[i])			{		//checks to see if x is equal to the ith place in list l. returns true if it is in and goes to i+1 if not.
   true
  }
}
}
/* Problem 1.4 */
def squareAll (l: List[Int]) :List[Int]=
{
for(i <- 0 to l.length){	// starting with 0 this loop takes each element
  h::(l[i]*l[i])				//in the list and multiplies it by itself
}
}
//---------
// Part 2
//In the following problems do not use any mutable variables (i.e., variables declared with var) or
//any mutable predened types such as arrays, mutable sets, and so on. You may dene methods
//recursively this time. Do not use the if operator in Problems 1-4 below.
//---------

/* Problem 2.1 */
def mul (m: Int, n: Int) :Int=
{
	n match{
		case 0 => 0// if n is zero the answer is zero
		case _=>	m match{
								case 0 => 0		//if m is zero answer is zero
								case _ => n+mul(m-1,n) // adds n to n until m is zero
		}
	}
}

/* Problem 2.2 */
def concatAll (l: List[String]) :String=
{
for(i <- 0 to l.length){		//for loop that starts at zero and goes to the length of list l
  var combination: string +=l[i] //combines the list together to form a word
}
}
/* Problem 2.3 */
def isIn (x: Int, l: List[Int]) :Boolean
{
for(i <- 0 to l.length){//for loop that starts at zero and goes to the length of list l
		x match{
			case l[i] => true //returns true if x = l[i]
			case _ => Nil
		}
}
}


/* Problem 2.4 */
def squareAll (l: List[Int]) :List[Int]=
{
for(i <- 0 to l.length){	// starting with 0 this loop takes each element
  h::(l[i]*l[i])				//in the list and multiplies it by itself
}
}
/* Problem 2.5 */
def remove (x: Int, l: List[Int]) :List[Int]=
{
	l.remove(x) // takes list l and removes x from list

}
/* Problem 2.6 */
//For each method write in a Scala comment a concise description in English of its functionality,
//along the lines of the descriptions provided for the methods in the previous problems (given
//this and that, it returns so and so). Just describe the input-output behavior of the method,
//not the internal algorithm.
def m(l1:List[Int], l2:List[Int]):List[Int] = // takes two lists of integers
 (l1, l2) match {
  case (Nil, _) => l2		// if list 11 is empty return list l2
  case (_, Nil) => l1		// if list 12 is empty return list l1
  case (h1 :: t1, h2 :: t2) => {
   if (h1 < h2)
    h1 :: m(t1, l2)		// if head of list l1, h1, is greater than the head of list l2, h2, return h1 and recursive call m(t1, l2) and repeat the process
   else
    h2 :: m(l1, t2)		// if head of list l2, h2, is greater than the head of list l2, h1, return h1 and recursive call m(l1, t2) and repeat the process
 }										// END RESULT is one list of the lowest values to highest values from lists l1 and l2
}
def s(l:List[Int]) = {
 def s_aux(l0:List[Int], l1:List[Int], l2:List[Int]):(List[Int], List[Int]) =
  l0 match {
   case Nil => (l1, l2) //If list l0 is empty return (l1, l2)
   case x :: Nil => (x :: l1, l2) // if there is nothing after x it adds l1 and l2 to a list with x at the front
   case x1 :: x2 :: t => s_aux(t, x1 :: l1, x2 :: l2) // if no match it returns to the start.
  }
 s_aux(l, Nil, Nil)
}

/* Problem 2.7 */
def pair (list1: List[Int], list2: List[Int]) :List[(Int,Int)]=

/* Problem 2.8 */
def mergeSort (l: List[Int]) :List[Int]=
	//==================================================
	//
	// Homework 2, Part B
	//
	// Name: Kristofer Hult
	//
	//==================================================


	//================================================
	// Vec
	//================================================

	class Vec private (private val elems:Array[Double]) {
	val length = elems.length

	def this(x:Double) = this(Array(x))

	def apply(i:Int) = elems(i)

	def ++(other:Vec) = {
	val r_length = length + other.length
	val r_elems = new Array[Double](r_length)
	for (i <- 0 to length - 1) r_elems(i) = elems(i)
	for (i <- 0 to other.length - 1) r_elems(length + i) = other.elems(i)
	new Vec(r_elems)
	}

	def +(other:Vec) = {
	val r_elems = new Array[Double](length)
	for (i <- 0 to length - 1) r_elems(i) = elems(i) + other.elems(i)
	new Vec(r_elems)
	}

	def *(other:Vec) = {
	var p = 0.0
	for (i <- 0 to length - 1)
	p = p + (elems(i) * other.elems(i))
	p
	}

	override def toString = {
	var s = "<" + this.apply(0)
	for (j <- 1 to length - 1)
	s = s + ", " + this.apply(j)
	s + ">"
	}

	// overrides the default definition of == (an alias of equals)
	override def equals(other:Any):Boolean = other match {
	// if other is an instance of Vec then ...
	case o:Vec =>
	for (j <- 0 to length - 1)
	if (this.apply(j) != o.apply(j)) return false
	true
	// otherwise return false
	case _ => false
	}
	}


	//================================================
	// Matrix
	//================================================

	// Suggestion: for testing purposes it is convenient
	// to implement toString first


	// (The main constructor of) Matrix takes as input
	// an array of n > 0 vectors all of the same length
	class Matrix private (a:Array[Vec]) {

	// Public constructor
	def this(v:Vec) = this(Array(v))
	def this(x:Double) = this(new Vec(x))

	// the array is stored as is in the private field rows
	// the element at position (i,j) in the matrix is stored
	// as the j-th element of the i-th vector in rows
	private val rows = a

	// integer field h stores the height of the matrix
	val h = {rows.length}

	// integer field w stores the width of the matrix
	val w = {rows(0).length }

	/* given i in [0 .. h-1] and j in [1 .. w-1],
	apply(i,j) returns the matrix element at position (i,j)
	*/
	def apply(i:Int, j:Int) = {
	rows(i).apply(j)
	}
	/* given a matrix other with other.w == w,
	/(other) returns a new matrix m such that
	- m.h == h + other.h
	- m.w == w
	- for all i in [0 .. h-1] and j in [0 .. w-1], m(i,j) == this(i,j)
	- for all i in [h .. r.h-1] and j in [0 .. w-1], m(i,j) == other(i,j)
	*/
	def /(other:Matrix) = {
	val mLength = h + other.h
	val vectors = new Array[Vec](mLength)

	for (i <- 0 to h - 1) {
	vectors(i) = new Vec(apply(i, 0))
	for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j))
	}
	for (i <- 0 to other.h - 1) {
	vectors(i + h) = new Vec(other.apply(i, 0))
	for (j <- 1 to w - 1) vectors(i + h) ++= new Vec(other.apply(i, j))
	}
	new Matrix(vectors)
	}

	/* given a matrix other with other.h == h,
	++(other) returns a new matrix m such that
	- m.h == h
	- m.w == w + other.w
	- for all i in [0 .. h-1] and j in [0 .. w-1], m(i,j) == this(i,j)
	- for all i in [0 .. h-1] and j in [w .. r.w-1], m(i,j) == other(i,j)
	*/
	def ++(other:Matrix) = {
	val mLength = w + other.w
	val vectors = new Array[Vec](h)

	for (i <- 0 to h - 1) {
	vectors(i) = new Vec(apply(i, 0))
	for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j))
	for (j <- 0 to other.w - 1) vectors(i) ++= new Vec(other.apply(i, j))
	}
	new Matrix(vectors)
	}
	/* given a matrix other with other.h == h and other.w == w,
	+(other) returns a new matrix m such that
	- m.h == h
	- m.w == w
	- for all i in [0 .. h-1] and j in [0 .. w-1],
	m(i,j) == this(i,j) + other(i,j)
	*/
	def +(other:Matrix) ={
	val vectors = new Array[Vec](h)
	for (i <- 0 to h - 1) {
	vectors(i) = new Vec(apply(i, 0))
	for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j) + other.apply(i, j))
	}
	new Matrix(r_vecs)
	}

	/* given a j in [0 .. w-1],
	col(j) returns a vector v whose elements come
	from the j-th column of the matrix, i.e.,
	- v.length == h
	- for all i in [0 .. h-1] , v(i) == this(i,j)
	*/
	private def col (j:Int) = {
	var c = new Vec(rows(0)(j))
	for (i <- 1 to h - 1)
	c = c ++ new Vec(rows(i)(j))
	c
	}

	/* transpose returns a new matrix m such that
	- m.h == w
	- m.w == h
	- for all i in [0 .. m.h-1] and j in [0 .. m.w-1], m(i,j) == this(j,i)

	Suggestion: use method col
	*/
	def transpose = {
	val vectors = new Array[Vec](h)
	for (i <- 0 to h - 1) r_vecs(i) = col(i)
	new Matrix(vectors)
	}


	/* given an i in [0 .. h-1], rowToString(i)
	returns a string of the form \| d1 d2 ... dw \|
	where d1, ..., dw are the (the string representation of)
	the elements in row i
	*/
	private def rowToString(i:Int) = {
	var s = "\| "
	for (j <- 0 to w - 1)
	s = s + this.apply(i,j) + " "
	s ++ "\|"
	}

	/* toString returns a string of the form

	\| d_00 d_01 ... d_0q \|
	\| d_10 d_11 ... d_1q \|
	\| . . . \|
	\| . . . \|
	\| . . . \|
	\| d_p0 d_p1 ... d_pq \|

	where d_ij is the (the string representation of) this(i,j)
	*/
	override def toString = {
	var out:String = "";
	for (i <- 0 to h - 1) out ++= rowToString(i) + "\n"
	out
	}

	// overrides the default definition of == (an alias of equals)
	override def equals(other:Any):Boolean = other match {
	// if o is an instance of Matrix then ...
	case o:Matrix =>
	for (i <- 0 to h - 1; j <- 0 to w - 1)
	if (this(i,j) != o(i,j)) return false
	true
	// otherwise return false
	case _ => false
	}
	}


	// A few test cases you could try
	val m1 = new Matrix(1) ++ new Matrix(2) ++ new Matrix(3)
	val m2 = new Matrix(4) ++ new Matrix(5) ++ new Matrix(6)
	val m3 = m1 / m2 / m1
	val m4 = m1 ++ m2


	val m = new Matrix
	//==================================================
	//
	// Homework 3
	//
	// Name: Kristofer Hult
	//
	//==================================================

	/* Generic abstract class for finite sets */
	abstract class FinSet[T] protected () {
	/* returns a list consisting of the set's elements */
	def toList:List[T]

	/* given a value x, it retuns a new set consisting of x
	and all the elemens of this (set)
	*/
	def +(x:T):FinSet[T]

	/* given a set other, it returns the union of this and other,
	i.e., a new set consisting of all the elements of this and
	all the elements of other
	*/
	def U(other:FinSet[T]):FinSet[T]

	/* given a set other, it returns the intersection of this and other,
	i.e., a new set consisting of all the elements that occur both
	in this and in other
	*/
	def ^(other:FinSet[T]):FinSet[T]

	/* given a set other, it returns the difference of this and other,
	i.e., a new set consisting of all the elements of this that
	do not occur in other
	*/
	def \(other:FinSet[T]):FinSet[T]

	/* given a value x, it retuns true if and only if x is an element of this
	*/
	def contains(x: T):Boolean

	/* given a set other, it returns true if and only if this is included
	in other, i.e., iff every element of this is an element of other
	*/
	def <=(other:FinSet[T]):Boolean = {
	case o:FinSet[T] => (this <= o)
	case _ => false
	}

	override def toString = "{" ++ (toList mkString ", ") ++ "}"

	// overrides the default definition of == (an alias of equals)
	override def equals(other:Any):Boolean = other match {
	// if other is an instance of FinSet[T] then ...
	case o:FinSet[T] =>
	// it is equal to this iff it includes and is included in this
	(this <= o) && (o <= this)
	case _ => false
	}
	// Note: compiling the method equals above may produce this warning:
	// "there were 1 unchecked warnings; re-run with -unchecked for details"
	// You can ignore it
	}


	/* Generic concrete class implementing finite sets internally
	as lists with no repetitions
	*/
	// Precoditions: the input list l has no repeated elements
	class ListSet[T] private (l: List[T]) extends FinSet[T] {
	def this() = this(Nil)

	// invariant: elems is a list with no repetitions
	// storing all of the set's elements
	private val elems = l

	/* this method can be useful in implementing some of the methods
	from FinSet. Given a value x and a list l with no repetitions,
	it returns a list with no repetitions consisting
	of x and all the elements of l
	*/
	private def add(x:T, l:List[T]):List[T] = l match {
	case Nil => x :: Nil
	case y :: t => if (x == y) l else y :: add(x, t)
	}

	val toList = elems /* returns a list consisting of the set's elements */


	def +(x: T) = {
	new ListSet[T](this.add(x, elems))/* given a value x, it retuns a new list consisting of x
	and all the elemens of this (set)
	*/
	}


	def U(other:FinSet[T]) = {
	/* given a list other, it returns the union of this and other,
	i.e., a new list consisting of all the elements of this and
	all the elements of other
	*/
	var UList=List[T]()
	for(i<-other.toList){
	UList=this.add(i,UList)
	}
	new ListSet[T](UList)
	}

	def ^(other:FinSet[T]) = {
	/* given a list other, it returns the intersection of this and other,
	i.e., a new list consisting of all the elements that occur both
	in this and in other
	*/
	var IList=List[T]()
	for(i<-other.toList){
	if(elems.contains(i){
	IList=i::IList
	}
	}
	new ListSet[T](IList)
	}

	def \(other:FinSet[T]) = {
	/* given a list other, it returns the difference of this and other,
	i.e., a new list consisting of all the elements of this that
	do not occur in other
	*/
	var DiffList=List[T]()
	for(i<-elems){
	if(!other.contains(i)){
	DiffList=i::DiffList
	}
	}

	}


	def contains(x:T) = {
	/* given a value x, it retuns true if and only if x is an element of this
	*/
	for(i<-other.toList){
	if(x==toList[i])
	}
	}



	/* Generic concrete class implementing finite sets internally
	as immutable Maps from T to Unit
	*/
	class MapSet[T] private (m: Map[T, Unit]) extends FinSet[T] {
	def this() = this(Map())

	// invariant: the pair (x, ()) is in the map elems if and
	// only if x is an element of the set
	private val elems = m

	/* This method can be useful in implementing toList. Given
	- a list List( (x1,()), ..., (xm,()) ) and
	- a list List( y1, ..., yn ), it returns the list
	List( yn, ..., y1, xm, ..., m1 )
	*/
	private def project(l1:List[(T, Unit)], l2:List[T]):List[T] =
	l1 match {
	case Nil => l2
	case (x, _) :: t => project(t, x :: l2)
	}

	val toList = elems.keys


	def +(x:T) = new.MapSet[T](elems +(x->()))

	def U(other:FinSet[T]) = {
	var UMap=elems
	for(i<-other.toList){
	UMap=UMap+(i ->())
	}
	new MapSet[T](UMap)
	}


	def ^(other:FinSet[T]) = {
	var IMap=Map[T,Unit]()
	for(i <-other.toList){
	if(elems.contains(i){
	IMap=IMap+(i -> ())
	}
	}
	new MapSet[T](IMap)
	}

	def \(other:FinSet[T]) = {
	var DiffMap=Map[T,Unit]()
	for(i<-elems){
	if(!other.contains(i)){
	DiffMap=DiffMap+(i -> ())
	}
	}
	new MapSet[T](DiffMap)
	}

	def contains(x:T) = elems.contains(x)
	}



	/* some test cases for ListSet

	val empty = new ListSet[Int]

	val s1 = empty + 1

	val s2 = empty + 2

	val s12 = s1 U s2

	val s21 = s2 U s1

	s1 == s12 // should return false

	s21 == s12 // should return true

	s12 U s1 // should return a set equal to s12

	val s123 = s12 + 3

	val s23 = empty + 2 + 3

	val s234 = s23 + 4

	s123 ^ s234 // should evaluate to a set equal to s23

	s123 \ s234 // should evaluate to a set equal to s1

	s12 \ s21 // should evaluate to an empty set

	s23 contains 2 // should evaluate to true

	s23 contains 4 // should evaluate to false

	s23 <= s123 // should evaluate to true

	s23 <= s234 // should evaluate to true

	s23 <= s23 // should evaluate to true

	s1 <= s23 // should evaluate to false

	*/


	/* same test cases but for MapSet

	val empty = new MapSet[Int]

	val s1 = empty + 1

	val s2 = empty + 2

	val s12 = s1 U s2

	val s21 = s2 U s1

	s1 == s12 // should return false

	s21 == s12 // should return true

	s12 U s1 // should return a set equal to s12

	val s123 = s12 + 3

	val s23 = empty + 2 + 3

	val s234 = s23 + 4

	s123 ^ s234 // should evaluate to a set equal to s23

	s123 \ s234 // should evaluate to a set equal to s1

	s12 \ s21 // should evaluate to an empty set

	s23 contains 2 // should evaluate to true

	s23 contains 4 // should evaluate to false

	s23 <= s123 // should evaluate to true

	s23 <= s234 // should evaluate to true

	s23 <= s23 // should evaluate to true

	s1 <= s23 // should evaluate to false

	*/


	/* Same test cases but mixing ListSet and MapSet instances
	In a correct implementation ListSet and MapSet should be
	interchangeable

	val empty = new ListSet[Int]

	val s1 = empty + 1

	val s2 = (new MapSet[Int]) + 2

	val s12 = s1 U s2

	val s21 = s2 U s1

	s1 == s12 // should return false

	s21 == s12 // should return true

	s12 U s1 // should return a set equal to s12

	val s123 = s12 + 3

	val s23 = empty + 2 + 3

	val s234 = s23 + 4

	s123 ^ s234 // should evaluate to a set equal to s23

	s123 \ s234 // should evaluate to a set equal to s1

	s12 \ s21 // should evaluate to an empty set

	s23 contains 2 // should evaluate to true

	s23 contains 4 // should evaluate to false

	s23 <= s123 // should evaluate to true

	s23 <= s234 // should evaluate to true

	s23 <= s23 // should evaluate to true

	s1 <= s23 // should evaluate to false

	*/
	//==================================================
	//
	// Homework 2, Part A
	//
	// Name: Kristofer Hult
	//
	//==================================================


	abstract class Dictionary {

	/* put(k,v) adds value v to the dictionary under key k.
	put may be called with the same key multiple times,
	all key->values pairs get stored in the dictionary
	*/
	def put(key:String, value: Any):Unit

	/* get(k) returns Some(v) where v is one of the values
	associated with key k in the dictionary, if any.
	It returns None if k is associated to no value.
	*/
	def get(key:String):Option[Any]

	/* remove(k) removes one value v associated with key k
	from the dictionary, if any, and returns it as Some(v).
	It returns None if k is associated to no value.
	*/
	def remove(key:String):Option[Any]

	/* toList() returns a list containing all the key/value pairs
	in the dictionary.
	If multiple values have the same key k, each is listed
	in a separate pair with k.
	*/
	def toList():List[(String,Any)]

	/* toString() returns a string containing all the key/value pairs
	in the dictionary. The string has the form

	Dictionary(key_1 -> value_1, ..., key_n -> value_n)

	where each key_i is a key and each value_i is (the string
	representation of) the corresponding value.
	If multiple values have the same key k, each is present
	in a separate pair with k.
	*/
	override def toString():String

	/* getAll(k) returns the list of all the values associated
	with key k in the dictionary.
	*/
	def getAll(key:String):List[Any] ={
	var l = List[Any]()
	for ((k,v) <- toList)
	if (k == key) l = Any::l
	l
	}


	/* removeAll(k) removes from the dictionary all the values
	associated with key k in the dictionary, if any.
	*/
	def removeAll(key:String) = {
	while (get(key) != None)
	remove(key)
	}



	class ListDictionary extends Dictionary {
	/* the dictionary is implemented using a list of key/value pairs */
	private var d = List[(String,Any)]()

	/* put(k,v) adds value v to the dictionary under key k.
	put may be called with the same key multiple times,
	all key->values pairs get stored in the dictionary
	*/
	def put(key:String, value: Any):Unit={
	d=(key, value)::d
	}

	/* get(k) returns Some(v) where v is one of the values
	associated with key k in the dictionary, if any.
	It returns None if k is associated to no value.
	*/
	def get(key:String):Option[Any]= {
	for ((a,x) <- d)
	if (a == key) return Some(x)
	None
	}

	def remove(key:String):Option[Any]

	/* toList() returns a list containing all the key/value pairs
	in the dictionary.
	If multiple values have the same key k, each is listed
	in a separate pair with k.
	*/
	def toList():List[(String,Any)]={
	var l = List[(key,value)]()
	for (a <- d; element <- a)
	l = element::l
	l
	}

	/* toString() returns a string containing all the key/value pairs
	in the dictionary. The string has the form

	Dictionary(key_1 -> value_1, ..., key_n -> value_n)

	where each key_i is a key and each value_i is (the string
	representation of) the corresponding value.
	If multiple values have the same key k, each is present
	in a separate pair with k.
	*/
	override def toString():String={
	var d=toList();
	def toStringSecondary(l:List[(key,value)]):String =
	l match {
	case Nil => ""
	case (k,v)::Nil => k + " -> " + v
	case (k,v)::t => k + " -> " + v + ", " + toStringSecondary(t)
	}

	"Dictionary(" + toStringSecondary(d) + ")"
	}
	}


	}
	/*==================================================

	Homework 1

	Name: Kristofer Hult

	==================================================
	*/

	//---------
	// Part 1
	//In the following problems do not dene methods recursively. Instead, use mutable variables and
	//while or for loops as needed in method denitions. You may use auxiliary methods if needed.
	//---------

	/* Problem 1.1 */
	def mul (m: Int, n: Int):Int =
	{
	for(i <- 1 to m){ //for loop that starts at 1 and goes until the value given for m
	if(m==0 \|\| n==0){ //if m or n is zero the result will be zero
	0
	}
	else{
	var x:Int+=x+n// adds value of n until it reaches the value of m, gives result of n * m
	}
	}
	}

	/* Problem 1.2 */
	def concatAll (l: List[String]) :String=
	{
	for(i <- 0 to l.length){ //for loop that starts at zero and goes to the length of list l
	var combination: string +=l[i] //combines the list together to form a word
	}
	}
	/* Problem 1.3 */
	def isIn (x: Int, l: List[Int]) :Boolean
	{
	for(i <- 0 to l.length){//for loop that starts at zero and goes to the length of list l

	if (x=l[i]) { //checks to see if x is equal to the ith place in list l. returns true if it is in and goes to i+1 if not.
	true
	}
	}
	}
	/* Problem 1.4 */
	def squareAll (l: List[Int]) :List[Int]=
	{
	for(i <- 0 to l.length){ // starting with 0 this loop takes each element
	h::(l[i]*l[i]) //in the list and multiplies it by itself
	}
	}
	//---------
	// Part 2
	//In the following problems do not use any mutable variables (i.e., variables declared with var) or
	//any mutable predened types such as arrays, mutable sets, and so on. You may dene methods
	//recursively this time. Do not use the if operator in Problems 1-4 below.
	//---------

	/* Problem 2.1 */
	def mul (m: Int, n: Int) :Int=
	{
	n match{
	case 0 => 0// if n is zero the answer is zero
	case _=> m match{
	case 0 => 0 //if m is zero answer is zero
	case _ => n+mul(m-1,n) // adds n to n until m is zero
	}
	}
	}

	/* Problem 2.2 */
	def concatAll (l: List[String]) :String=
	{
	for(i <- 0 to l.length){ //for loop that starts at zero and goes to the length of list l
	var combination: string +=l[i] //combines the list together to form a word
	}
	}
	/* Problem 2.3 */
	def isIn (x: Int, l: List[Int]) :Boolean
	{
	for(i <- 0 to l.length){//for loop that starts at zero and goes to the length of list l
	x match{
	case l[i] => true //returns true if x = l[i]
	case _ => Nil
	}
	}
	}


	/* Problem 2.4 */
	def squareAll (l: List[Int]) :List[Int]=
	{
	for(i <- 0 to l.length){ // starting with 0 this loop takes each element
	h::(l[i]*l[i]) //in the list and multiplies it by itself
	}
	}
	/* Problem 2.5 */
	def remove (x: Int, l: List[Int]) :List[Int]=
	{
	l.remove(x) // takes list l and removes x from list

	}
	/* Problem 2.6 */
	//For each method write in a Scala comment a concise description in English of its functionality,
	//along the lines of the descriptions provided for the methods in the previous problems (given
	//this and that, it returns so and so). Just describe the input-output behavior of the method,
	//not the internal algorithm.
	def m(l1:List[Int], l2:List[Int]):List[Int] = // takes two lists of integers
	(l1, l2) match {
	case (Nil, _) => l2 // if list 11 is empty return list l2
	case (_, Nil) => l1 // if list 12 is empty return list l1
	case (h1 :: t1, h2 :: t2) => {
	if (h1 < h2)
	h1 :: m(t1, l2) // if head of list l1, h1, is greater than the head of list l2, h2, return h1 and recursive call m(t1, l2) and repeat the process
	else
	h2 :: m(l1, t2) // if head of list l2, h2, is greater than the head of list l2, h1, return h1 and recursive call m(l1, t2) and repeat the process
	} // END RESULT is one list of the lowest values to highest values from lists l1 and l2
	}
	def s(l:List[Int]) = {
	def s_aux(l0:List[Int], l1:List[Int], l2:List[Int]):(List[Int], List[Int]) =
	l0 match {
	case Nil => (l1, l2) //If list l0 is empty return (l1, l2)
	case x :: Nil => (x :: l1, l2) // if there is nothing after x it adds l1 and l2 to a list with x at the front
	case x1 :: x2 :: t => s_aux(t, x1 :: l1, x2 :: l2) // if no match it returns to the start.
	}
	s_aux(l, Nil, Nil)
	}

	/* Problem 2.7 */
	def pair (list1: List[Int], list2: List[Int]) :List[(Int,Int)]=

	/* Problem 2.8 */
	def mergeSort (l: List[Int]) :List[Int]=