## 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;
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;
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);

}