## 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.

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

}