Three Homework Problems

September 18, 2015

We have three simple exercises today to help beginning programmers with their homework; all three exercises have appeared on beginning-programmer forums in the last week:

1) Write a recursive function to find the sum of the first n odd integers. For instance, if n = 2, the first two odd integers are 1 and 3, and their sum is 4.

2) Write a function to count the frequence of characters in a string. For instance, given the string “hello” the function should return counts of 1, 1, 2 and 1 for h, e, l and o.

3) Write functions that encrypt and decrypt messages in a Caesar cipher. Input consists of upper-case letters and spaces; the “key” is an integer giving the number of letters to shift. For instance, the message ATTACK AT DAWN with a shift of 5 is enciphered as FYYFHP FY IFBS.

Your task is to solve the three homework exercises given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: