Exercise 2 (by Mikael Eriksson, TA HT2015)

Converting a partial sequence of consequtive digits within a string into a number? (In case you didn't figure out for lab 1)



How to document a function with IN, OUT, DEPENDENCIES, EFFECTS.

Or with the simpler PRE and POST.

Do pop with and without global variables, for the abobe.

Without:

function [ out ] = pop( stack )

% INPUT: stack (cell array)

% OUPUT: new stack with top element removed

% DEPENDENCIES: None

% EFFECTS: None

%

stack(end) = [];

out = stack;

end



NOTA BENE: You are from NOW ON (lab 2 and on) EXPECTED to document your funcitons with pre- and post, or the more detailed IN, OUT, DEPENDENCIES, EFFECTS! This should also help you to do good modularization = good partition into separate functions, ”separation of concerns”.



Good idea: Try formulating the above for any functions that come up in the exercises



From Exercises 1:



% If the program below executed with

% cheers(3)

% what will it print out

function cheers(n)

if n == 1

disp('Hurray')

else

disp('Hip ')

cheers(n-1);

end



This functions does not *return* any output, but it has effects! Recursive case vs base case. Illustration of ”stack overflow”. Above example is artificial (simple to transform into iteration, show how). More interesting case will be seen in lab2: Quick sort and recursion in the form of ”divide and conquer”!



Documentation for above function:

% IN: n is non negative integer

% OUT: Nothing

% EFFECT: Will display Hip Hip Hip.... Hurray

% DEPENDENCIES: Nothing

or

% Pre-conditions: n is a non negative integer

% Post-conditions: Hip Hip... Hurray has been displayed



Sorting:

Selection sort

Insertion sort

Bubble sort



Shell sort (www.youtube.com/watch?v=M9YCh-ZeC7Y)



Quick sort





Reading a file in Matlab: google ”matlab reading number file”, and (if you want) ”matlab file selector”



Time complexity (Problem 1 of exercises 2):

If you know the time spent for algorithm is g(N) seconds, for input size N, then how large problem can you solve within T=1000 seconds?



Solution: Solve the equation: g(N) = 1000,

N is inverse function of g of 1000.

Inverses:



g(N)

INV(g(N))

T = 10^3

T = 10^4

2^N is inverse of?

log2(T)

10

13

1/2*N^3 is inverse of?

(2T)^1/3 = O(T^1/3)

...

...

5N^2


...


100N

T/100





Scan through Exercies 2, and stop at anything interesting.

Code from lecture 3 (151117)

/*

Stuff that we played around with on appcs15,

lecture 3, 151117

Use at your own risk! ^^

miker AT kth.se

*/


#include <stdio.h>


int factorial(int x) {

if (x>1) {

return x*factorial(x-1);

}

else

return (1);

}


void powers(int number) {

printf("%d\n", number);

return;

int n = 0;

int pow = 1;

while (pow < 100) {

printf("%3d %3d\n", n, pow);

n = n + 1;

pow *= 2;

}

}


int foo() {

int fac = 1;

int n = 11;

int i;

for (i=1 ; i<=n ; i++) {

fac = fac*i;

printf("%d\n", fac);

}

return fac;

}


void decrease(int *i) {

i += 1000;

(*i)--;


printf("%p ", i);

}


main() {

int i=1;

printf("%d ", i);

decrease(&i);

printf("%d\n", i);

}


main2(){

int result;

powers(19.934);

return 0;

int n;

int i, j;

printf("Enter n: ");

scanf("%d", &n);

printf("You entered %d\n", n);

printf("The factorial of n is: %2d \n", factorial(n));

}


[Remember showing ”flow chart” for for-loop. The condition acts as a branching point (the diamond in flow chart syntax).]