Software Design & Development Marathon [2012] (3 Viewers)

[ahdil33]

Do people want real (as in, not HSC-level) algorithms questions? They probably won't be much help for SDD specifically -- they test high-level mathematical reasoning more than anything else.

Here are three nice ones off the top of my head. The first 2 could in theory come up in an SDD exam, I guess. There are lots of approaches for the third one, some easier than others.

EASY: Write a function that finds the sum of all multiples of 3 or 5 below a given n. (source: adapted from Project Euler question 1)

EASY-MODERATE: Write a function that, given n, finds the nth fibonacci number. Start at 1,1,2,3.... (source: classic)

HARD: You are given an n*n grid G of integers, where in any row r, and in any column c, . Efficiently determine whether a given integer k is in the grid. (Source: one of the UNSW third-year algorithms course practice papers)

EDIT: ahdil if you're interested in computing at UNSW you should give these a go. I'll see you next year

Haha thanks these look very interesting! yep I guess I will be

 

[SpiralFlex]

Goldy your first/third question isn't clear to me. Give me an example of input/output. Thanks

For your second one, we notice that for a given Fibonacci sequence,

0, 1, 1, 2, 3, 5, 8....We can generalise this case into a series of cases.

Fn=0 for n=0, Fn=1 for n=1, but otherwise Fn-1+Fn-2 for n>1, n belongs to the set of real integers.

For this I assumed we started at 0.

BEGIN
Function Fib(n)
    IF n < 2
        RETURN n
    ELSE
        RETURN fib(n - 1) + fib(n - 2)
END

Alternatively you could somehow implement binets formula into the code?



P.S: Where can I find more questions like these?

 

[GoldyOrNugget]

For question 1, if the input was 20, the multiples of 3 or 5 below 20 are 3, 5, 6, 9, 10, 12, 15, 18, and the sum of these is 78.

Your solution to q2 is correct, but its runtime is exponential in proportion to its input. If I implement it and try to evaluate n=100...

>>> def fib(n):
...     if n < 2:
...             return n
...     else:
...             return fib(n-1) + fib(n-2)
... 
>>> fib(10)
55
>>> fib(100)

The program hangs indefinitely. The solution I have in mind will be able to calculate fib(10^6) in less than a second. The maths solution will probably work but I consider it cheating especially considering the floating-point precision errors that will inevitably be introduced with sqrt(5).

For question 3, if you choose any row and read it from left to right, you will get an increasing sequence. Similarly, if you choose any column and read it from top to bottom, you will get an increasing sequence. Here's a sample 5*5 grid.

5	6	9	10]	11
7	8	11	12	13
10	11	15	16	17
13	14	16	17	20
14	15	18	21	25

 

[GoldyOrNugget]

The Australian Informatics training site is orac.amt.edu.au. It has all the past problems and you can submit source-code solutions for them in many common languages.

http://projecteuler.net/ is an international problem-solving site where you work out the answers on your own and submit a numerical solutions. They are often of a slightly more mathematical nature than informatics. The first three problems are:

1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

2. By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

3. Find the largest prime factor of a composite number. (they give you a number)

 

[sddmoustache]

BEGIN
Function Fib(n)
    IF n < 2
        RETURN n
    ELSE
        RETURN fib(n - 1) + fib(n - 2)
END

Wait, how can a function call itself?? Is that legit? We didn't learn this in class...

 

[GoldyOrNugget]

Wait, how can a function call itself?? Is that legit? We didn't learn this in class...

It is legit. It's called recursion and it's a very common strategy in computer science (if you take CS or software engineering, you'll learn it about halfway through first year). It's not taught in the SDD curriculum so don't worry too much about it.

http://en.wikipedia.org/wiki/Recursion_(computer_science)

 

[sddmoustache]

Urghh, that wiki page doesn't look very appealing. I'm probably not going to do computer science. It's so much maths! -_- Just trying to not fail SDD...

 

[Cyberbully]

It is legit. It's called recursion and it's a very common strategy in computer science (if you take CS or software engineering, you'll learn it about halfway through first year). It's not taught in the SDD curriculum so don't worry too much about it.

http://en.wikipedia.org/wiki/Recursion_(computer_science)

Each weekend Brad Hall works in a local jelly baby shop. The jelly babies are stored in boxes with ten jelly babies in each box. Each time a customer comes in to buy some jelly babies Brad Hall takes them from an already-open box. If there are not enough jelly babies in the current box, Brad Hall completely finishes the box before opening a new box. Brad Hall is not allowed to have any more than one box open at a time, and Brad Hall cannot open a new box unless a customer has purchased some of the jelly babies in that box.

The jelly babies in his shop are particularly famous, so every person who comes in buys at least one jelly baby. However, as they are very expensive, no one ever buys more than nine.

At the start of the day, there are no open boxes. If at the end of the day the currently open box has jelly babies left in it, Brad Hall is allowed to take them home and share them with Brad Hall's friends (or just let Brad Hall eat them if Brad Hall is feeling greedy). Can you write me a program that reads in the series of purchases for the day and prints how many jelly babies Brad Hall will get at the end.

Sample Input
2
9
4
7
8
3
2
5
3
4

Sample Output
3

 

[sddmoustache]

Isn't Brad Hall that UNSW computing guy? He keeps sending me promotional emails...

 

[GoldyOrNugget]

Cyberbully nice try, just because you change a few words in the problem statement doesn't mean I don't recognise it Chocolate Shop from AIO 2008 Senior.

#include <stdio.h>

int main() {
      FILE *fin, *fout;
      long i, amountOfPurchases, amountToAdd, backUpOfTotalBought, totalBought=0;
      fin = fopen("chocin.txt", "r");
      fout = fopen("chocout.txt", "w");
      
      fscanf(fin, "%d \n", &amountOfPurchases);
      
      for (i=0 ; i<amountOfPurchases ; i++) {
            fscanf(fin, "%d \n", &amountToAdd);
            totalBought += amountToAdd;
      }
      
      backUpOfTotalBought = totalBought; // backUp holds the original amount of total bought, because the real value changes in the next while loop
      while (totalBought % 10 != 0) {
            totalBought++;
      }
      
      fprintf(fout, "%d", totalBought-backUpOfTotalBought);
      return(0);
}

 

[Cyberbully]

cyberbully nice try, just because you change a few words in the problem statement doesn't mean i don't recognise it chocolate shop from aio 2008 senior.

#include <stdio.h>

int main() {
      file *fin, *fout;
      long i, amountofpurchases, amounttoadd, backupoftotalbought, totalbought=0;
      fin = fopen("chocin.txt", "r");
      fout = fopen("chocout.txt", "w");
      
      fscanf(fin, "%d \n", &amountofpurchases);
      
      for (i=0 ; i<amountofpurchases ; i++) {
            fscanf(fin, "%d \n", &amounttoadd);
            totalbought += amounttoadd;
      }
      
      backupoftotalbought = totalbought; // backup holds the original amount of total bought, because the real value changes in the next while loop
      while (totalbought % 10 != 0) {
            totalbought++;
      }
      
      fprintf(fout, "%d", totalbought-backupoftotalbought);
      return(0);
}

pseudocode plz
p.s. does not work on sample input cause i deleted a line.
HUR HUR HUR!

 

[GoldyOrNugget]

pseudocode plz
p.s. does not work on sample input cause i deleted a line.
HUR HUR HUR!

I'm not sure of the proper pseudocode conventions for files, but

OPEN input AS SEQUENTIAL FILE
Sum = 0
Current = READ LINE FROM input
WHILE Current != SENTINEL VALUE DO
  Sum = Sum + Current
  Current = READ LINE FROM input
END WHILE

PRINT 9 - ((Sum + 9) MOD 10)
CLOSE input

 

[Cyberbully]

I'm not sure of the proper pseudocode conventions for files, but

OPEN input AS SEQUENTIAL FILE
Sum = 0
Current = READ LINE FROM input
WHILE Current != SENTINEL VALUE DO
  Sum = Sum + Current
  Current = READ LINE FROM input
END WHILE

PRINT 9 - ((Sum + 9) MOD 10)
CLOSE input

ENDWHILE is a whole word innit?

here:

The nuclear/climate-change/rabid-gopher apocalypse has come and gone. Brad Hall is a nomad who spends him days travelling the corridors of K17, armed with nothing but a slingshot and his trusty jelly-baby-gps. The jelly-baby-gps is the last of its kind, an artefact from the old days that allows him to insert objects many times him weight, and carry them around with him, but with one important caveat: he can only remove the most recently inserted object. There exist 26 different types of object, each denoted by an English letter.

K17 consists of offices connected by corridors. The corridors of K17 are all one-way, and one kilometre long. Each corridor is guarded by a tribe of fiercely territorial post-apocalyptic humans. Depending on the tribe, there are different rules for what Brad Hall must do if he wants to use a corridor:

• When Brad Hall traverses a type 1 corridor, he must insert exactly one object, of a type specific to that corridor, into his jelly-baby-gps.
• When Brad Hall traverses a type 2 corridor, he must unload exactly one object, of a type specific to that corridor, from his jelly-baby-gps.
• When Brad Hall traverses a type 3 corridor, he mustn't touch his jelly-baby-gps.
• Brad Hall may not insert or remove objects from his jelly-baby-gps except when directed to by these rules.
• Brad Hall starts at city 1, and wishes to make him way to city N without travelling more than K kilometres.
• Your task is to compute the number of paths Brad Hall can take which satisfy all these conditions.

Input: Each of the following R lines describes a one-way corridor. Depending on the type of the corridor, the format will differ:

• A type 1 corridor from x to y is of the form `x y C', where C is an upper-case letter denoting the type of object Brad Hall must insert into his jelly-baby-gps when traversing this corridor.
• A type 2 corridor from x to y is of the form `x y c', where c is a lower-case letter denoting the type of object Brad Hall must remove from his jelly-baby-gps when traversing this corridor.
• A type 3 corridor from x to y is of the form `x y -'.

Output should consist of a single integer: the number of paths from city 1 to city N of length at most K kilometres, satisfying all the rules, modulo 10007.

 

[GoldyOrNugget]

alright who are you cyberbully -_- i'm not giving you the code to the b-session. solve it yourself

EDIT: unless you're darren, in which case, hi

 

[Cyberbully]

alright who are you cyberbully -_- i'm not giving you the code to the b-session. solve it yourself

EDIT: unless you're darren, in which case, hi

I only respond to "sudo"

 

[GoldyOrNugget]

sudo hostname

 

[Cyberbully]

sudo hostname

We'll need your password to progress!

 

[GoldyOrNugget]

No. I will just think of you as a member of the small set of year 12 NSW informaticians. There's only like 5 of us anyway.

 

[Cyberbully]

No. I will just think of you as a member of the small set of year 12 NSW informaticians. There's only like 5 of us anyway.

How do you know there isn't a secret leak!

 

[GoldyOrNugget]

Meh. I feel bad for taking this thread off-topic now =\ back to SDD!