;;; Homework 10: Logo ;;; Question 1A ;; triple outputs a three-element sentence containing its inputs to triple :x :y :z output fput :x list :y :z end ;; second outputs the second element of sentence s to second :s output first butfirst :s end ;; leaf constructs a leaf from a letter and a weight to leaf :letter :weight output triple "leaf :letter :weight end ;; leaf? outputs whether or not the input is a leaf to leaf? :v output "leaf = first :v end ;; letter outputs the letter of a leaf to letter :leaf ; *** YOUR CODE HERE *** end ;; weight outputs the weight of a leaf to weight :leaf ; *** YOUR CODE HERE *** end ;; tree constructs a tree from a 0-branch (left) and a 1-branch (right) to tree :branch0 :branch1 output triple :branch0 :branch1 sum weight :branch0 weight :branch1 end ;; branch0 outputs the 0-branch of a tree to branch0 :tree ; *** YOUR CODE HERE *** end ;; branch1 outputs the 1-branch of a tree to branch1 :tree ; *** YOUR CODE HERE *** end ;;; Question 1A Tests make "aleaf leaf "A 8 make "bcd tree leaf "B 3 tree leaf "C 1 leaf "D 1 print leaf? :aleaf ; expect True print leaf? :bcd ; expect False print letter :aleaf ; expect A print weight :aleaf ; expect 8 print weight :bcd ; expect 5 print letter branch0 :bcd ; expect B ;;; Question 1B ;; process_butfirst outputs the first letter of x and the processed rest of x to process_butfirst :x :exp output word first :x run sentence :exp word "" butfirst :x end ;; decode outputs a decoded word to decode :tree :code if empty? :code [output " ] output process_butfirst decode_one :tree :code [decode :tree] end ;; decode_one outputs code with its prefix replaced by a decoded letter to decode_one :tree :code ; *** YOUR CODE HERE *** end ;;; Question 1B Tests make "efgh tree tree leaf "E 1 leaf "F 1 tree leaf "G 1 leaf "H 1 make "abcdefgh tree :aleaf tree :bcd :efgh print decode_one :abcdefgh "10001010 ; expect B01010 print decode :abcdefgh "10001010 ; expect BAC ;;; Question 1C ;; encodings outputs a sentence of letter-encoding pairs to encodings :tree ; *** YOUR CODE HERE *** end ;;; Question 1C Tests show encodings :bcd ; expect [[B 0] [C 10] [D 11]] show encodings :abcdefgh ; expect [[A 0] [B 100] [C 1010] [D 1011] [E 1100] [F 1101] [G 1110] [H 1111]] ;;; Question 1D ;; insert outputs a sentence of trees sorted by increasing weight, including t to insert :t :trees if empty? :trees [output fput :t []] if lessp weight :t weight first :trees [output fput :t :trees] output fput first :trees insert :t butfirst :trees end show insert leaf "B 4 list leaf "A 2 leaf "C 6 ; expect [[leaf A 2] [leaf B 4] [leaf C 6]] ;; Huffman outputs a Huffman encoding tree for sorted input trees to Huffman :trees ; *** YOUR CODE HERE *** end ;;; Quesiton 1D Tests show Huffman [[leaf C 1] [leaf D 1] [leaf B 3] [leaf A 8]] ; expect [[[[leaf C 1] [leaf D 1] 2] [leaf B 3] 5] [leaf A 8] 13] ; Note: Huffman codes are not unique; you may not get this answer exactly. show encodings Huffman [[leaf C 1] [leaf D 1] [leaf B 3] [leaf A 8]] ; expect [[C 000] [D 001] [B 01] [A 1]] ; Note: Huffman codes are not unique; you may not get this answer exactly. ;;; Question 2 make "root3 1.732 ; The square root of 3, approximated to hax :d :k ; *** YOUR CODE HERE *** end