🔒 Locked

CS exercises

Started by silverphyre673 Apr 9, 2005 at 3:29 AM 29 replies 3.8k views

Original Post

Apr 9, 2005 at 3:29 AM

I'm back from california! I visited berkely CS building yesterday just before I left and found their entrance exams for CS61 a. They were actually really easy, a bunch of recursion problems like this: write a function, sum, that calculates the sum of two non-negative integers, a and b, recursively. You can't use the + or - operators, or use any looping (for, while, etc.). You can only decrement or increment by 1, using some pre-defined functions add1 and sub1, and you have one other function, iszero, which returns whether the argument passed to it is zero. It took me 5 minutes to do this, and their exam from 2002, using recursion, and having only two functions, MOTHER and FATHER which return the mother and father of a person in a family tree, recursively print out each ancestor of a person on a family tree without using any loops. This took me 20 minutes out of the 45 allowed. What I'd like is to start a thread of exercises and challenges like these, where you post the challenge here, and people can work on them at home, just for fun and practice. If you are interested and have a good idea, go ahead! I just want some ideas for what to work on, and ways to build skills in topics like, though not limited to, recursion. A note: these should, for the average joe shmoe non-pro, still lives in parents house (aka me), take between twenty and 45 minutes. Thanks!

ToohrVyk

238

ToohrVyk

Apr 9, 2005 at 5:24 AM

You are given two functions to work on a list:

getCurrent( ) returns the current integer in the list, zero if the list is empty
getNext( ) returns the next integer in the list

You are to find which sequence of consecutive elements in the list has the highest value for the sum of its elements, and return that highest value. You are allowed to use any method.

For instance, on the sequence: -1 2 18 -3 13 the sequence (2, 18, -3, 13) has a sum of 30, which is the maximum you can get here, so you would return 30.

silverphyre673

Author

silverphyre673

Apr 9, 2005 at 11:54 AM

will GetNext() loop around to the beginning of the list if you called it when you were on the last element of the list i.e

(0, 4, 3, -1, 2)

if you called it when the current element was 2, would it move the current position to 0, or give an error?

nilkn

122

nilkn

Apr 9, 2005 at 12:14 PM

My solution to the first problem:

#include "stdafx.h"using std::cout;using std::cin;void add1(int& num){	num++;}void sub1(int& num){	num--;}bool iszero(int num){	return (num == 0);}int sum(int a, int b){	static int i = 0;	static int res = a;	if (iszero(a) && !iszero(b)) return b;	if (!iszero(a) && iszero(b)) return a;	if (iszero(a) && iszero(b)) return 0;	add1(res);	add1(i);	if (i < b)		sum(a, b);	return res;}int _tmain(int argc, _TCHAR* argv[]){	int a, b;	cout << "enter nonneg int a: ";	cin >> a;	cout << "enter nonneg int b: ";	cin >> b;	cout << "\nsum: " << sum(a, b) << "\n";	return 0;}

It took me barely over 3 minutes.

ToohrVyk

238

ToohrVyk

Apr 9, 2005 at 12:18 PM

Quote:
Original post by silverphyre673
will GetNext() loop around to the beginning of the list if you called it when you were on the last element of the list i.e

(0, 4, 3, -1, 2)

if you called it when the current element was 2, would it move the current position to 0, or give an error?

Oops, I worded the problem wrong. GetNext() will return 0 if you move past the end, 1 otherwise. And for simplicity's sake, you can assume that the list is placed before the first element, so you start off by calling GetNext().

ToohrVyk

238

ToohrVyk

Apr 9, 2005 at 12:21 PM

And while we're at it, my solution to the first problem:

let rec sum (a) (b) = if (iszero a) then b else sum (sub1 a) (add1 b);;

silverphyre673

Author

silverphyre673

Apr 9, 2005 at 12:58 PM

Here's another one, along the same lines as the sum function:

calculate the exponent of two numbers, a and b, so that it returns a to the power of b. Don't use looping (or, obviously, the cmath library)! Your function must be recursive.

I did the second problem in 20 minutes. Can anybody else figure it out? :)

My code (the implementation for the family tree is up to you):

typedef int PERSON;PERSON ancestors(PERSON p){    PERSON total=1;        std::cout << p << " ";        if (MOTHER(p)!=-1)    {        total+=ancestors(MOTHER(p));    }    if (FATHER(p)!=-1)    {        total+=ancestors(FATHER(p));    }        return total;}

bytecoder

Apr 9, 2005 at 1:22 PM

Quote:

Here's another one, along the same lines as the sum function:

calculate the exponent of two numbers, a and b, so that it returns a to the power of b. Don't use looping (or, obviously, the cmath library)! Your function must be recursive.

I did the second problem in 20 minutes. Can anybody else figure it out? :)

You're on:

def exp(a, b, c=1):    """Calculate a to the bth power without using looping or the cmath library"""    if c==0:        return a**b    else:        return exp(a, b, 0)

Just kidding. If anyone is curious, ** is the to the power of operator in python. It's the same as math.pow(x, y).

Conner McCloud

159

Conner McCloud

Apr 9, 2005 at 1:36 PM

Quote:
Original post by silverphyre673
calculate the exponent of two numbers, a and b, so that it returns a to the power of b. Don't use looping (or, obviously, the cmath library)! Your function must be recursive.

If you solve the addition one, this is trivial, assuming a and b are integers.

int exp(int a, int b){   if(b == 0)      return 1;   return a * exp(a, b-1)}

I believe that took about two minutes, and the first minute and a half were wasted on a stupid mistake. I added code to swap a and b if a was smaller than b, so as to reduce the number of recursive calls. Apparently a^b != b^a, who knew?

CM

ITGER

Apr 9, 2005 at 1:44 PM

Reverse a singly linked list. Without using STL of course. Hahaha.

Edit: Btw connor you can save yourself some recursive calls if you check if the power is even.

ToohrVyk

238

ToohrVyk

Apr 9, 2005 at 3:21 PM

Quote:
Original post by ITGER
Reverse a singly linked list. Without using STL of course. Hahaha.

With the right tool to handle lists recursively, it is a breeze.

let rev (x) =  let rec help (y) = function    | [] -> y    | h::t -> help (h::y) (t)  in help [] (x)

Conner McCloud

159

Conner McCloud

Apr 9, 2005 at 6:20 PM

Quote:
Original post by ITGER
Reverse a singly linked list. Without using STL of course. Hahaha.

reverse(LL x){  if(x.next == 0) return;  reverse(x.next);  LL buf = x.next;  x.next = 0;  add_back(x, buf);}

Fill in the holes as neccessary, but I'm pretty sure the basic algorithm is sound.

CM

sjelkjd

119

sjelkjd

Apr 9, 2005 at 8:52 PM

Quote:
Original post by ITGER
Edit: Btw connor you can save yourself some recursive calls if you check if the power is even.

It doesn't have to be even:

template<typename T>T pow(T base, int exp){ if(exp == 1) return base; T halfpow = pow(base, exp/2); if(exp % 2 == 1)   return T * halfpow * halfpow; else  return halfpow * halfpow;}

sjelkjd

119

sjelkjd

Apr 9, 2005 at 8:59 PM

Here's an interesting problem: perform an in-order traversal of a sorted binary tree, without using recursion.

Zahlman

257

Zahlman

Apr 9, 2005 at 9:00 PM

For the exponentiation:

def exp(a, b):  assert isinstance(a, (int, long)) and isinstance(b, (int, long))   # just a type check, since Python is dynamically typed  if b == 0: return 1  if b == 1: return a  return exp(a, b/2) * exp(a, b - b/2)

sjelkjd

119

sjelkjd

Apr 9, 2005 at 9:26 PM

Quote:

Original post by Zahlman
For the exponentiation:

def exp(a, b):  assert isinstance(a, (int, long)) and isinstance(b, (int, long))   # just a type check, since Python is dynamically typed  if b == 0: return 1  if b == 1: return a  return exp(a, b/2) * exp(a, b - b/2)

But mine runs in O(log2(b)) time =P

Nice Coder

101

Nice Coder

Apr 9, 2005 at 9:34 PM

for a^b

exp(a, b) =ig b = 0 then return 1if b = 1 then return aif b & 1 then   b = b - 1   k = exp(a, b * 0.5)   return a * k * kelse   tmp = exp(a, b * 0.5)   return tmp * tmpend if

Nifty? (toolk the whole of 15 secs to write).

From,
Nice coder

[Edited by - Nice Coder on April 9, 2005 9:34:37 PM]

Zahlman

257

Zahlman

Apr 9, 2005 at 11:52 PM

Quote:
Original post by sjelkjd
Quote:
Original post by Zahlman
For the exponentiation:
def exp(a, b):  assert isinstance(a, (int, long)) and isinstance(b, (int, long))   # just a type check, since Python is dynamically typed  if b == 0: return 1  if b == 1: return a  return exp(a, b/2) * exp(a, b - b/2)
But mine runs in O(log2(b)) time =P

Oh. Lol. Took me a while to get that. :)

# return exp(a, b/2) * exp(a, b - b/2) <-- doh.  c = exp(a, b/2)  return c*c*exp(a, b % 2) # There we go.

silverphyre673

Author

silverphyre673

Apr 10, 2005 at 12:09 AM

Anyone got any NEW ones? :)

They don't have to use recursion, you know. I'm just trying to think of things that would maybe do something useful and teach something at the same time, like the family tree one.

Nice Coder

101

Nice Coder

Apr 10, 2005 at 12:15 AM

n = 2^j * 3^k * 5^l

Find j, k and l, given n.

From,
Nice coder

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.