CS1010 (2011 Sem 2)
PE 2, Ex 1 link
Task 1
When reading the reference solution, you may find it helpful to think of j as
the position of the next character to match, having matched the previous (ie j-1) character
Task 2
See here for an alternative solution that hopefully is easier to understand.
Task 3
See here for a solution that tests your understanding of loops, especially the termination conditions.
Week 11 link
Q2
As discussed in class:
/*
* Base case: n is a single-digit number
* return n
*
* Inductive step:
* Let:
* a = rightmost digit of n
* m = rest of digits in n
* return a + sum_digits(m)
*/
// Return sum of digits in n
// Precond: n >= 0
int sum_digits(int n)
{
if (n / 10 == 0)
return n;
else
return (n%10) + sum_digits(n/10);
}Q4
As discussed in class:
/*
* Base case: n is < 100 (n is a 2-digit or 1-digit number)
* return n
* Inductive step:
* Let:
* a = rightmost pair of digits in n
* m = rest of the digits/pairs in n
* if a > largest_digit_pairs(m):
* return a
* else
* largest_digit_pairs(m)
*/Q5
/*
* Base case 1: size = 0
* do nothing! (since nothing to reverse)
*
* Base case 2: size = 1
* do nothing! (reversing it would give back the original array)
*
* Inductive step: (for size >= 2)
* Let:
* head = arr[0]
* tail = arr[size - 1]
* body = arr + 1, size - 1
*
* swap head and tail
* call reverse_array on body
*/
void reverse_array(int arr[], int size)
{
if (size == 0)
;
else if (size == 1)
;
else {
swap(&arr[0], &arr[size-1]);
reverse_array(arr+1, size - 2);
}
}(definition of swap is omitted)
Be sure to bump up NUM (size of array), otherwise the sample array in the question wouldn't work.
Q6
First, let us remind ourselves what ne(x,y) computes:
number of unique NE-paths between two points separated by x rows (north) and y columns (east).
In this case, it seems easier to come up with the recursive step:
ne(x,y) = ne(x-1,y) + ne(x,y-1)
This is interpreted as saying: the number of (x,y) paths is given by:
- paths after taking one step north (ne(x-1,y)), and
- paths afer taking one step east (ne(x,y-1))
Now we define the base cases to ensure that we terminate:
if (x==0 || y==0) return 1;Why 1? Let's say x is 0; that would mean we can't go north, so there is only 1 path - go east. Similarly for y=0.
Note that the recursive step may lead to calls with negative x,y, so it may be safer to say
if (x<=0 || y<=0) return 1;even though ne called with negative x,y doesn't make any sense. Alternatively, we could add ifs to guard against negative x,y before calling ne(x-1,y) etc, at the expense of some readability.
The code:
int ne(int x, int y)
{
/* be safe, not sorry! */
if (x <= 0 || y <= 0)
return 1;
return ne(x-1, y) + ne(x, y-1);
}Additional exercise
A robot can take steps of size 5, 3, 2, or 1. Write a program to compute the number of ways the robot can walk n steps.
(If you are spending too much time, try a different approach!)
Week 10 link
Q3
This is an example where the things being sorted is different from the things being compared.
Week 09 link
Q1
'\062' is the octal (base 8) representation of the decimal number 50, which is the ASCII character '2'.
'\x41' is the hexadecimal (base 16) representation of the decimal number 65, which is the ASCII character 'A'.
Q4
The string "pineapple" is itself 9 characters long; including the NUL \0 character, we would need an array of size 10. So the strcpy is unsafe.
Below is a carefully-constructed program to illustrate that strcpy may write outside of the array's allocated memory:
char fruitname[15], x='a';
strcpy(fruitname, "a big pineapple");
printf("fruitname='%s', x=%d\n", fruitname, (int) x);(fruitname is chosen to be size 15, so that x sits nicely right after it.)
The string "a big pineapple" is exactly 15 characters; but to store it, we would need 16, to accomodate the trailing NUL. Thus, the NUL byte is writen by strcpy into x, giving x=0 in the output.
Q5
No NUL byte for the strings board[0] and board[1].
Q6
fruit1, fruit2, str1, str2 are string literals and may not be allocated in writable memory space. Thus, writing to them (like with strcpy) may not succeed.
At compile time, string literals are used to create an array of static storage duration of sufficient length to contain the character sequence and a null-termination character. It is unspecified whether these arrays are distinct. The behavior is undefined if a program attempts to modify string literals but frequently results in an access violation because string literals are typically stored in read-only memory
— https://www.securecoding.cert.org/confluence/display/seccode/STR30-C.+Do+not+attempt+to+modify+string+literals
Q7
Consider this snippet:
while (str[i]) {
...
i++
}Assuming str is a NUL-terminated string, this will loop through the characters in str and terminate upon encountering NUL (since NUL=0 which evaluates to "false").
Q11
Apart from using multiple scanf("%s") to read in words individually, you may read in the full sentence (with fgets) and then use strtok (introduced in Q3). (Got this idea from QW)
Week 08 link
Q2: scanf("%c")
See Week 06 for issues associated with scanf() on characters and possible solutions.
Q3a
Visualization:
n-1 th n th n+1 th
m-1 th | | y | |
m th | z | x=y+z| |
m-2 th | | | |where:
- x: sum[m][n]
- y: sum[m-1][n]
- z: sum[m][n-1]
Q3b
Interpretation: each cell is summed with the cell in its "reflection" along x=y diagonal.
Week 07 link
General array iteration idioms
It's useful to keep in mind these idioms, so that the you don't have to re-analyze when you encounter a for/while loop.
with the
forconstruct:for (i=0; i<=SIZE-1; i++) { /* do something with arr[i] */ }
also:
for (i=0; i<SIZE; i++) { /* do something with arr[i] */ }
Both forms are equivalent.
with the
whileconstruct:i = SIZE; while (i--) { /* do something with arr[i] */ }
Note that the order of this form is different from the above ones; it goes through the array backwards.
Q1a
Diff from our discussion:
--- Week7_Q1a.c Fri Mar 2 00:32:10 2012
+++ Week7_Q1a-ours.c Wed Mar 7 13:57:49 2012
@@ -2,13 +2,13 @@
int main(void)
{
- float[5] values;
+ float values[5];
int i;
- for (i=1; i<=5; i++)
+ for (i=0; i<=4; i++)
values[i] = 2.5*i;
- for (i=1; i<=5; i++)
+ for (i=0; i<=4; i++)
printf("%f ", values[i]);
printf("\n");Q1b
I said in class that it is possible, by adding '{' and '}' to the first for loop, like this:
--- Week7_Q1a-ours.c Wed Mar 7 13:57:49 2012
+++ Week7_Q1b-ours.c Wed Mar 7 23:50:00 2012
@@ -5,11 +5,11 @@
float values[5];
int i;
- for (i=0; i<=4; i++)
+ for (i=0; i<=4; i++) {
values[i] = 2.5*i;
- for (i=0; i<=4; i++)
printf("%f ", values[i]);
+ }
printf("\n");
return 0;Clearly, this is incorrect, as the question's printf() intends to print all the elements, not element-by-element, like the above. (Thanks to QW for pointing this out)
Q1c
Diff from our discussion:
--- Week7_Q1c.c Wed Mar 7 14:40:24 2012
+++ Week7_Q1c-ours.c Fri Mar 2 12:25:46 2012
@@ -1,23 +1,22 @@
#include <stdio.h>
-float sumArray(float, int);
+float sumArray(float[], int);
int main(void)
{
- float prices[6], total;
- prices = { 10.2, 5.3, 4.4, 6.8, 7.7, 9.5 };
+ float prices[6]= { 10.2, 5.3, 4.4, 6.8, 7.7, 9.5 }, total;
- sumArray(prices[6], 6);
+ total = sumArray(prices, 6);
printf("Total = %f\n", total);
return 0;
}
-float sumArray(float arr, int size)
+float sumArray(float arr[], int size)
{
int i;
float sum = 0.0;
for (i=0; i<size; i++)
- sum += prices[i];
+ sum += arr[i];
return sum;
}Q2
The infinite loop is due to i being set to 0 arr[4] = 0 is executed. Moral of the story: only "use" [0-4] what you "declared"!
--- Q2.c Wed Mar 7 14:03:43 2012
+++ Q2-ours.c Fri Mar 2 12:28:21 2012
@@ -4,7 +4,7 @@
{
double arr[] = { 1.1, 2.2, 3.3, 4.4 };
int i;
- for (i = 0; i < 4; i++) {
+ for (i = 0; i <= 4; i++) {
printf("%d\n", i);
arr[i] = 0;
}Of course, the infinite loop that we observe is coincidental - generally, we cannot predict the program's behaviour if operations like accessing arr[4] are done.
Q3
Simple animation to better visualize this program
Q4
I mentioned that arrays and pointers are equivalent. This is incorrect.
When we say
int arr[5];
int *p;
p = arr;the compiler actually generates a pointer to the first element of arr:
p = &arr[0];This is due to the "decaying" rule. Read more here:
http://c-faq.com/aryptr/aryptrequiv.html
http://www.eskimo.com/~scs/cclass/notes/sx10e.html
Q5
Hopefully you haven't forgotten your MA1100/CS1231. When dealing with arrays, being able to find the negative of a universal (which is an existential) will help you "break" iteration early.
For example, Q5 wants a program to return 1 if:
$$ \forall i: arr[i] < 0 $$
The negative of this statement is then:
$$ \exists i : arr[i] \ge 0 $$
So our program should return 0 the moment we encounter an arr[i] >= 0.
(Note that the worst-case running time of your program would still be O(n). More on this next time.)
Q6
It asks
what is the property you have "abstracted" out to check?
implying that there is some similarity between Q5 and Q6. However, in Q6, your code either has to "lookahead" or "lookbehind", so the iteration condition would be different from Q5.
The universal-to-existential strategy in Q5 is still applicable.
Week 06 link
Q2: Behaviour of program when n=100
Aston was right. To see why, consider the factorization of 100, which is 2^2 x 5^2. The powers of each factor are 0, 1, 2. So we have 3 x 3 ways of choosing those powers. Excluding the number itself, we get 3 x 3 - 1 = 8, which agrees with the result of running the program.
Q3: reading characters
The issue is that stdin is buffered. For a visualization of this, refer to slide 5.
The three solutions we talked about were:
- terminate input with EOF (Ctrl-D). No modification of the program required.
- write a function on top of
scanf(), ignoring whitespace characters (usingisspace()from<ctype.h>) - use
scanf(" %c"). This works because:
A directive composed of one or more white-space characters shall be executed by reading input until no more valid input can be read, or up to the first byte which is not a white-space character, which remains unread.
— fscanf
Last week's additional ex 1
Week 05 link
How can Q4e be interpreted?
(asked by YM)
The purpose of Q4 is to actually type and run your code. However, some of them can be interpreted in an interesting manner.
For example, we see in Q4d that Q4c can be used to "draw" all segments of length >= 1. We also saw in Q4c that it also gives us the number of edges in a complete graph of size 6:
We may wonder if Q4e also has an interesting interpretation. It seems there is one.
Let's put a * every time execution reaches the innermost loop body (line 6: count++). For example, when x=1 and y=3, the z loop runs from 1 to 3, giving us:
x=1, y=3 * * *With that notation defined, let's look at the y and z loops when x=1. y loops from 1 to 5, giving us:
x=1, y=1 *
x=1, y=2 * *
x=1, y=3 * * *
x=1, y=4 * * * *
x=1, y=5 * * * * *and when x=2,
x=2, y=2 *
x=2, y=3 * *
x=2, y=4 * * *
x=2, y=5 * * * *Repeating this all the way to x=4:
x=4, y=4 *
x=4, y=5 * *and finally with x=5:
x=5, y=5 *Thus, count is just the sum of the sum of integers from 1 to n, where n=y-x+1. Recall that the sum of integers from 1 to k is
$$ \sum_{j=1}^k j = \frac{k^2 + k}{2} $$
The sum of these sums is thus:
Indeed, substituting n=5 gives us 35, agreeing with the output of the code snippet.
Notes for Q5
Q5 illustrates the problem-solving approach that I've been emphasizing. To see how, let's magine you're in PE, and the task statement reads:
Write a program that takes in two integers, and outputs the largest possible integer that divides both of them.
For most of us, after some guessing, what we'd probably come up with would look like Adam's code. Yes, it may not be efficient, but it does give us the right answer.
So, at least aim for a correct algorithm; after that try to find something better.
If you're interested, a simple to understand proof of validity of Euclid's algorithm can be found on page 3 of this document.
Additional Ex 1
Last week's additional Ex 2
Lab 1 link
As I mentioned, the purpose of this lab is to give additional practice for coding on sunfire, as well as to pick up good style and habits that will stay with your for the subsequent labs.
Overall comments:
- indent with tabs, instead of multiple spaces.
- be consistent with the rest of the code. For example, if the skeleton code puts the "{" on a new line and the function body on another line, do so for your own code. Eg:
void foo(void)
{ /* on a new line */
/* body goes here... */- don't be afraid to use longer names to describe variables and functions.
Ex 4 let's us see how switch-case can be used. Some students used the fall-through switch-case pattern to determine the number of days in a month. Since the months that have 30 or 31 days are (mostly) non-overlapping, this seems like a job appropriate for switch-case. Eg:
switch(month) {
case 1: case 3: case 5: case 7: /* ... */
days_in_month = 31;Week 04 link
Discussion for Q2
Diff for the code resulting from our discussion:
--- Week4_Q2.c Fri Feb 3 09:52:50 2012
+++ Week4_Q2-ours.c Fri Feb 3 12:39:04 2012
@@ -1,14 +1,16 @@
#include <stdio.h>
+void func(int);
+
int main(void)
{
- void func(5);
- void func(3-7);
+ func(5);
+ func(3-7);
return 0;
}
-void func(y)
+void func(int y)
{
if (y<0)
printf("Nothing\n");Discussion for Q5a
Diff for the code resulting from our discussion:
--- Week4_Q5a.c Fri Feb 3 09:52:50 2012
+++ Week4_Q5a-ours.c Fri Feb 3 12:51:28 2012
@@ -7,9 +7,9 @@
float value;
printf("Enter value: ");
- scanf("%f", &value);
+ scanf("%f", value);
- if (0 < value < 1)
+ if ((0 < value)&&(value < 1))
printf("%f is between 0 and 1\n", value);
else
printf("%f is not between 0 and 1\n", value);Discussion for Q5c
Here I will paste a snippet of the code resulting from our discussion, instead of a diff, since it's not easy to see what's going on from the diff.
/*...*/
printf("Enter 3 integers: ");
scanf("%d %d %d", &a, &b, &c);
if (a <= b && b <= c)
printf("The values are in non-decreasing order.\n");
else
printf("The values are not in non-decreasing order.\n");
/*...*/Additional Ex 1
In Q5c, we are provided with code that handles 3 integers, and asked to reduce the redundancy/duplication of code.
But what if we have 2 integers? Or 4? Can we extend the code to handle n different integers?
In class I introduce some imaginary operations on the object which I called a "list".
(Note that these functions and types are not "standard", I made it up for this exercise, so you can't use it elsewhere.)
list_head(the_list)gives us the first item in the list. So if we have a list(-5, 6, 9, 12), it would give us-5.list_rest(the_list)gives us the rest of the list. So for the list above, it would give us(6, 9, 12).But for a list with only 1 item like
(2), it would give an empty list.
Below is a sample session on how to work on this exercise.
$ cp ~rctay/cs1010/dg04/q5-ext/skeleton.c my-q5.c
$ # edit...
$ ~rctay/cs1010/dg04/q5-ext/compile -Wall my-q5.c
$ a.out
Enter next int: -5
Enter next int: 6
Enter next int: 9
Enter next int: 12
Enter next int: done
the integers are in non-decreasing order
$ echo 2 8 8 15 15 | a.out
Enter next int: Enter next int: Enter next int: Enter next int: Enter next int: Enter next int: the integers are in non-decreasing orderAdditional Ex 2
Download and try out the questions in the slides, we will discuss this in the next DG session.
Week 03 link
What we covered:
Algorithm design (Q3)
Q3 is a good introduction to algorithm design. To score well in this course, you would have to design algorithms under stress while being contrained by time (ie during PE and exams).
Try and solve a simple case.
Come out with any method. Don't worry about being "slow" or not efficient*, just come with a method.
Extend your method to handle the problem space.
*analysing algorithms for speed and resource-requirements will be done later in the course.
Even if your algorithm doesn't handle all cases correctly, marks will be given for a partially correct solution. Marks may also be awarded if the idea of the algorithm is correct but its implementation (C syntax) is wrong.
Whitespace and indentation
“Programs should be written for people to read, and only incidentally for machines to execute.”
— SICP, Preface to 1st Ed
Q8 shows how whitespace is important. Having well-indented code helps the examiner understand your program. If the examiner can't understand it, then you may not get the full mark even if your algorithm is correct.
Later on in the course the concept of modularity, another best practice, will be introduced.
Sample answer for Q9b:
The value of num1 will be displayed as 123.099998 instead of 123.100000.
The reason is that not all numerical values can be represented accurately in computers, due to the finite number of bits used to represent a value. For details, students may look up IEEE 754 Floating-Point Representation, but that is not within the scope of CS1010. For our purpose, it suffices to say that some values cannot be represented accurately, as shown above. That is the inherent limitation of computers.
We may use double instead of float to improve accuracy, but still the inaccuracy cannot be eliminated totally.
This has implications when we do comparison of real numbers in an ‘if’ condition or a loop condition which we will cover later.
Questions that I didn't answer in class
What does %3.2i do?
(asked by HW)
Refer to your preferred printf reference, as well as try this out:
printf("got '%3.2i'!\n", 2);
printf("got '%3.2i'!\n", 12);
printf("got '%3.2i'!\n", 102);
printf("got '%3.2i'!\n", 1023);What is yes | rm <file>?
If you recall, the reason why we have to run this is due to rm being paranoid and asking for confirmation for each file being deleted, which can slow down your work.
Understanding this command is a little complicated, as it involves a pipe (done with the | symbol), so here I present a simpler way to do the same thing.
If you look carefully, you'll realise that rm is actually aliased to rm -i (run alias to see this). Thus, a simpler alternative would just be
$ /bin/rm <file> ...What is more? (extra)
(asked by QW)
more is pager, so it chops up output so that you can scroll through it a page at a time. But you shouldn't use more, you should use less, because its more than more. :)
Lab 0 link
This is just a trial lab to familiarise yourselves with Unix/ssh/vim/gcc etc, as well as CodeCrunch. You should also have used scp to download your code.
Using the sample input and output
Almost always, we will provide you with sample output that your program is expected to produce when some sample input (also given).
First, download the sample input and output files with wget.
Continually work in this cycle:
Feed the program with the sample input, and capture its output (for later use).
$ a.out <sample.input >myoutputThe
>myoutputspecifies which file to save the output into; you should not be running$ a.out <sample.input >sample.outputBecause that just overwrites the sample output and you'd have nothing to check against.
Check whether the produced output was expected.
$ diff -u sample.input myoutputNotice that the arguments to diff is of the order
<expected> <actual>
Any differences? If so, start from the top. You'll have to delete the output file, since sunfire complains about overwriting the file. You can use
$ /bin/rm myoutputto avoid the irritating confirmation prompt from
rm.
Whitespace and spelling
CodeCrunch reads the output of your program and tried to match it with its own expected output, much like diff does. The exact test cases are not revealed, however.
But not to worry, the CodeCrunch grade will not affect your CA grade.