Three Homework Problems

September 18, 2015

The n th odd number is 2n−1, so the recursive function counts down from n to zero:

(define (sum-odd n)
  (if (zero? n) 0
    (+ (sum-odd (- n 1)) n n -1)))

> (sum-odd 5)
25

That’s not tail recursive, so the stack will blow out if n is too large. Here’s a tail-recursive version of the function:

(define (sum-odd-aux n sum)
  (if (zero? n) sum
    (sum-odd-aux (- n 1) (+ sum n n -1))))

(define (sum-odd n)
  (sum-odd-aux n 0))

> (sum-odd 5)
25

If you’re cheeky, you might use a mathematical identity to simplify your solution; no recursion required:

(define (sum-odd n) (* n n))

> (sum-odd 5)
25

The normal way to perform a frequency count of characters in a string is to initialize an array of character counts to zeroes, increment the count of the array position corresponding to the character for each character that is seen, then collect the non-zero counts in the output. That’s a little bit ugly in Scheme, because array access and string access functions have such long names:

(define (freq str)
  (let ((counts (make-vector 256 0)))
    (do ((i 0 (+ i 1)))
        ((= i (string-length str)))
      (let ((c (char->integer (string-ref str i))))
        (vector-set! counts c (+ (vector-ref counts c) 1))))
    (do ((i 0 (+ i 1))) ((= 256 i))
      (when (positive? (vector-ref counts i))
        (display (integer->char i)) (display #\tab)
          (display (vector-ref counts i)) (newline)))))

> (freq "hello")
e 1
h 1
l 2
o 1

A more Schemely solution converts the string to a list of characters, sorts them, and collects the non-zero counts; we use the uniq-c function from the Standard Prelude:

(define (freq str)
  (uniq-c char=? (sort char<? (string->list str))))

> (freq "hello")
((#\e . 1) (#\h . 1) (#\l . 2) (#\o . 1))

The Caesar cipher uses modular arithmetic to shift letters up and down the alphabet; we replace in-place any upper-case letters and leave everythihg else intact:

(define (caesar n str)
  (define (rotate c)
    (if (not (char<=? #\A c #\Z)) c
      (integer->char (+ (modulo (+ (char->integer c) n -65) 26) 65))))
  (list->string (map rotate (string->list str))))

> (caesar 5 "ATTACK AT DAWN")
FYYFHP FY IFBS
> (caesar -5 "FYYFHP FY IFBS")
"ATTACK AT DAWN"

Note that enciphering and deciphering use the same function but negate the shift.

You can run the program at http://ideone.com/MCsvSa.

Advertisements

Pages: 1 2

8 Responses to “Three Homework Problems”

  1. FA said

    Scala:

      //  https://programmingpraxis.com/2015/09/18/three-homework-problems-2/
      // 1)
      def sumNOdd(n: Int): Int = if (n < 1) 0 else ((n - 1) * 2 + 1) + sumNOdd(n - 1) // by the way =n*n
    
      // 2)
      def freq(s: String, c: Char): Int = s.filter(_ == c).size
    
      // 3) 
      def caesarEnc(s: String, key: Char): String = s.map(c => if (c != ' ') ((c - 'A' + key - 'A') % ('Z' - 'A' + 1) + 'A').toChar else ' ')
      caesarEnc("ATTACK AT DAWN", 'F')                //> res13: String = FYYFHP FY IFBS
    
      def caesarDec(s: String, key: Char): String = s.map(c => if (c != ' ') ('A' + (c - key + 'Z' - 'A' + 1) % ('Z' - 'A' + 1)).toChar else ' ')
      caesarDec(caesarEnc("ATTACK AT DAWN", 'F'), 'F')//> res14: String = ATTACK AT DAWN
    
    
  2. Jussi Piitulainen said

    I hope this isn’t another formatting disaster, but I flipped out thirty years ago when a homework exercise assumed ASCII encoding without comment (one of my worst overreactions, I walked out of the whole course when my solution was criticized for not making that unstated assumption), and I feel the need of a friendly objection today when a suggested solution assumes that any character fits in an octet. Here’s counting UTF-8 Greek letters from today’s Βικιπαίδεια front page :) In Python 3, copy-pasting in Lubuntu to Firefox from an Emacs running in Red Hat over SSH. Who do we blame if it gets mangled? Everything looks fine to me at the moment, a second before posting.

    text = '''Ο Σαίρεν Κίρκεγκωρ, στα                                                                                
    Δανικά Søren Aabye Kierkegaard, 5                                                                                
    Μαΐου 1813 – 11 Νοεμβρίου 1855),                                                                                 
    ήταν Δανός φιλόσοφος και θεολόγος                                                                                
    του 19ου αιώνα. Θεωρείται ο                                                                                      
    πρώτος υπαρξιστής φιλόσοφος.'''
    
    from collections import Counter
    print(*Counter(c for c in text if c.isalpha())
           .most_common(15),
           sep = '\n')
    

    The output:

    ('ο', 13)
    ('α', 11)
    ('ρ', 7)
    ('ι', 7)
    ('ς', 6)
    ('τ', 6)
    ('ε', 6)
    ('υ', 5)
    ('ν', 5)
    ('e', 4)
    ('φ', 4)
    ('κ', 4)
    ('σ', 4)
    ('ό', 4)
    ('ί', 4)
    
  3. Rutger said
    def sum_odd(n):
    	if n < 1:
    		return 0
    	else:
    		return 2*n-1 + sum_odd(n-1)
    
    def count_frequence(s):
    	from collections import Counter
    	return dict(Counter(s))
    
    def ceasar(s, shift):
    	import string
    	alphabet = list(string.ascii_letters)
    	return "".join(alphabet[(alphabet.index(c)+shift)%len(alphabet)] if c in alphabet else c for c in s)
    
    print sum_odd(2)
    print count_frequence("hello")
    print ceasar("dont attack gallia!", 5)
    # output:
    # 4
    # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
    # itsy fyyfhp lfqqnf!
    
  4. mcmillhj said

    1 in SML, 2 and 3 in Perl:

    (* tail recursive solution that counts upwards from 1 
       O(N) - only touches each odd number up to N
    *)
    fun sumFirstNOdds n = let
        fun loop curr count acc =
            if count = n then acc
            else case (curr mod 2)
                  of 1  => loop (curr + 2) (count + 1) (acc + curr) 
                   | _  => loop (curr + 1) count acc
    in
        loop 1 0 0
    end
    
    (* closed form formula SUM( odd(x) | x >= 1 and x <= N ) = N^2 *)
    fun sumFirstNOdds2 n = n * n;
    
    use strict;
    use warnings;
    
    # O(n) word frequency using ascii ordinal values
    sub frequency {
       my ($s) = @_;
    
       my @ascii_table = (0) x 128;
       foreach my $char ( split //, $s ) {
          $ascii_table[ ord $char ]++;
       }
    
       return @ascii_table;
    }
    
    print join(',', frequency('hello')), "\n";
    # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    # 0,0,1,0,0,1,0,0,0,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    #    'e'   'h'     'l'   'o'
    
    sub encrypt {
       my ($plaintext, $shift) = @_;
    
       my @letters = ('A' .. 'Z');
    
       return join '', map { ($_ ge 'A' && $_ le 'Z') ? $letters[(ord($_) + $shift - ord('A')) % @letters] : $_ } split //, $plaintext;
    }
    
    sub decrypt {
       my ($plaintext, $shift) = @_;
    
       return encrypt($plaintext, -$shift);
    }
    
    print decrypt(encrypt('ATTACK AT DAWN',5),5), "\n";
    # ATTACK AT DAWN
    
  5. Globules said

    A Haskell version, using part of Jussi Piitulainen’s text for the character frequency problem.

    import Data.Char (chr, ord)
    import Data.List (group, sort, sortBy)
    import Data.Ord (Down(..), comparing)
    import Text.Printf (printf)
    
    -- The sum of the first n odd numbers.  A more idiomatic way to write it would
    -- be:
    --       oddSum n = sum [1, 3 .. 2*n-1]
    --
    -- but I interpret the question as asking for explicit recursion.
    oddSum :: Int -> Int
    oddSum n = go (2*n-1)
      where go i | i > 0     = i + go (i-2)
                 | otherwise = 0
    
    -- The number of occurrences of each element of a list, sorted by decreasing
    -- frequency.
    freq :: (Eq a, Ord a) => [a] -> [(a, Int)]
    freq = order . map (\xs@(x:_) -> (x, length xs)) . group . sort
      where order = sortBy (comparing (Down . snd))
    
    -- A pair of functions to perform Caesar encryption and decryption for a given
    -- key.
    caesar :: Int -> (String -> String, String -> String)
    caesar n = let m = n `mod` 26
               in (crypt m, crypt (26 - m))
      where crypt k = unwords . map (cryptWord k) . words
            cryptWord k = map (toChar . rot k . fromChar)
            fromChar x = ord x - ord 'A'
            toChar x = chr (x + ord 'A')
            rot k x = (x + k) `rem` 26
    
    main :: IO ()
    main = do
      -- Sum of odd numbers
      let n = 7
      printf "Sum of the first %d odd numbers: %d\n\n" n (oddSum n)
    
      -- Letter frequencies
      let s = "Ο Σαίρεν Κίρκεγκωρ, στα"
      printf "Letter frequencies for: %s\n" s
      mapM_ (uncurry (printf "  %c %d\n")) (freq s)
      putStrLn ""
    
      -- Caesar encryption and decryption
      let key = 5
          (encrypt, decrypt) = caesar key
          sourceText = "ATTACK AT DAWN"
          cipherText = encrypt sourceText
          plainText  = decrypt cipherText
      printf "Caesar encryption and decryption with key %d.\n" key
      printf "  %s => %s\n" sourceText cipherText
      printf "  %s => %s\n" cipherText plainText
    
    $ ./hmwrk3
    Sum of the first 7 odd numbers: 49
    
    Letter frequencies for: Ο Σαίρεν Κίρκεγκωρ, στα
        3
      ρ 3
      ί 2
      α 2
      ε 2
      κ 2
      , 1
      Κ 1
      Ο 1
      Σ 1
      γ 1
      ν 1
      σ 1
      τ 1
      ω 1
    
    Caesar encryption and decryption with key 5.
      ATTACK AT DAWN => FYYFHP FY IFBS
      FYYFHP FY IFBS => ATTACK AT DAWN
    
  6. Mayur Lokare said

    EX1.
    #include
    int sum(int n)
    {
    if(n==1)
    return 1;
    else
    return (2*n -1)+sum(n-1);
    }
    int main()
    {
    int n;
    printf(“Enter the no of odd integer needed\n”);
    scanf(“%d”,&n);
    printf(“Result = %d\n”,sum(n));
    }

    if you don’t want to use recursive function then simplest method is
    #include
    int main()
    {
    int n;
    printf(“Enter the no of odd integer needed\n”);
    scanf(“%d”,&n);
    printf(“Result = %d\n”,n*n);
    }

  7. Mayur Lokare said

    #include
    int main()
    {
    char str[20];
    int i,j,count=1;
    printf(“Enter the string\n”);
    scanf(“%s”,str);
    for(i=0;str[i];i++)
    {
    for(j=0;j %d\n”,str[i],count);
    count=1;
    }
    }

  8. Mayur Lokare said

    EX 3.
    #include
    int main()
    {
    char str[20];
    int i;
    printf(“Enter the string”);
    scanf(“%[^\n]”,str);
    for(i=0;str[i];i++)
    {
    if(str[i]==’ ‘)
    continue;
    if((str[i]+5)>90)
    str[i] =(str[i]+5-26);
    else
    str[i] = str[i]+5;
    }
    printf(“%s\n”,str);

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: