Tutorial Sheet 4

ESC111 - Fundamentals of Computing

August 26, 2024

Revision Topics
1. For Loop syntax

for (init_expr; stopping_expr;update_expr) {

// code to be excuted in the loop
}

• The update expression and the stopping expression usually involve loop variable.
• Update expression and stopping expression are executed after each iteration.
• If the stopping expression evaluates to false, the loop is exited.
• All three expressions are optional.
• The init and update expressions can be any arithmetic/relational/ternary/empty
expression.

2. While Loop syntax

while (stopping_expr) {
// code to be executed in the loop
}

• Flow of execution: stopping expression → body → stopping expression ...

3. Do-While Loop syntax

do {
// code to be executed in the loop
} while (stopping_expr);

• Flow of execution: body → stopping expression → body ...

1
4. Solving problems using loops
• Break the problem into viable subproblems and use loops to solve those subprob-
lems.
• If the subproblems themselves require loops, use nested loops.
5. Break and Continue
• Purpose:
– Break: Terminates the loop immediately when encountered, and control
passes to the first statement after the loop.
– Continue: Skips the rest of the body of the loop and goes to the next
iteration.
• Usage:
– In nested loops, break and continue work on the innermost loop.
– In switch statements, break is used to prevent fall-through and exit switch
case.
– In do-while loops, continue jumps to the stopping expression.
• Using flags instead of break and continue:
– We can always use flags instead of break and continue. Here is an example
of two equivalent code snippets.
for(int i = 0; i < 10; i++) {
if (i == 5) {
break;
}
printf("%d\n", i);
}

int flag = 0;
for(int i = 0; i < 10 && !flag; i++) {
if (i == 5) {
flag = 1;
}
if (flag == 0) {
printf("%d\n", i);
}
}

6. Arrays
• Defination:
– An array is a collection of elements of the same type stored in contiguous
memory locations.

2
 – The elements of the array are accessed using an index.
• Initialization:
– Static Initialization: int arr[5] = {1,2,3,4,5}
– Size can be implicit: int arr[] = {1,2,3,4,5}
– Arrays can be initialized partially. int arr[5] = {1,2}
• Indexing:
– Example: int arr[5];
– Arrays are 0-indexed, i.e., the first element is at index 0 and the last element
is at index n − 1.
– Index cannot be negative or greater than n − 1.
– Arrays can be accessed using integer expressions, which may include variables,
arithmetic operations, or typecasts.
• Segmentation Fault:
– A segmentation fault occurs when a program tries to access a memory location
that it’s not allowed to.
– Accessing array elements out of bounds often leads to segmentation faults.
– Example:
int arr[5];
arr[5] = 10; // Segmentation fault
arr[-1] = 10; // Segmentation fault

7. Characters

• Characters are stored internally as integers between 0 and 127 using ASCII values.
• Characters can be input using scanf("%c", &c) and c = getchar().
• Characters can be output using printf("%c", c) and putchar(c).
• Take care while using %c and %d in format line. Use scanf("%d %c", &a, &c)
instead of scanf("%d%c", &a, &c).

8. Character arrays and strings

• Char array with \0 (null) character is called a string.

• The word string is not a datatype or even a keyword in C.
• Strings can be initialized in bulk during declaration (not afterward) as:
char str[] = "Hello";

• Strings can be input using scanf("%s", str) and gets(str).

• Strings can be output using printf("%s", str) and puts(str).

3
 9. Delimited strings

• \0 (ASCII value 0) acts as a delimiter for strings.

• Anything stored beyond the first \0 is neglected by C while printing and processing
character arrays as strings.
• \0 automatically inserted by C when we do bulk initialization, gets or scanf.

10. Segfaults with strings

• If character array not long enough (number of user characters + 1 for delimited
\0), then gets and scanf can cause segfault.
• If \0 missing from char array then even printf can cause segfault (by trying to
read beyond end of array).

11. String.h

• strlen: Returns the length of a string, not including the null terminator.
• strcpy: Copies a string from the source to the destination.
• strcmp: Compares two strings lexicographically and returns an integer based on
the comparison.
• strnlen: Returns the length of a string up to a maximum number of characters.
• strncpy: Copies a specified number of characters from the source string to the
destination.
• strncmp: Compares a specified number of characters from two strings lexico-
graphically.
• strupr: Converts all characters in a string to uppercase.
• strlwr: Converts all characters in a string to lowercase.
• strstr: Finds the first occurrence of a substring within a string.
• strcasecmp: Compares two strings lexicographically, ignoring case differences.
• strncasecmp: Compares a specified number of characters from two strings lexi-
cographically, ignoring case differences.
• atoi: Converts a string to an integer.
• EOF: Indicates the end of a file or stream, often used in reading input.

Questions for Discussion

Problem Statement:
In this game, a player rolls a dice up to 10 times. Each roll generates a random number
between 1 and 6. The player’s score is updated based on the roll as follows:
• If the roll is 3, it is ignored, and the player does not get a score for that roll.

4
 • If the roll is 6, the player gets an extra turn, meaning the number of turns remaining
is not reduced by that roll.
• If the score exceeds 30, then it is capped at 30, and the game ends immediately.
Output Format: The game should print the roll and the updated score after each roll.
When the game ends (either after 10 rolls or if the score exceeds 30), the final score should
be printed.
Code:
1 # include < stdio .h >
2 # include < stdlib .h >
3 # include < time .h >
4
5 int main () {
6 int score = 0;
7

8 srand ( time (0) ) ; // Seed for random number generation

9
10 for ( int i = 1; i <= 10; i ++) {
11 int roll = rand () % 6 + 1; // Generate a random number between 1
and 6
12

13 if ( roll == 3) {
14 continue ; // Ignore this roll
15 }
16
17 score += roll ;
18

19 if ( score > 30) {

20 score = 30; // Cap the score at 30
21 printf ( " You rolled a %d , Score : % d \ n " , roll , score ) ;
22 break ; // End the game if score exceeds 30
23 }
24

25 if ( roll == 6) {
26 i - -; // Extra turn , so don ’t count this roll
27 }
28
29 printf ( " You rolled a %d , Score : % d \ n " , roll , score ) ;
30 }
31
32 printf ( " Final Score : % d \ n " , score ) ;
33 return 0;
34 }

Problem Statement:
You are given two sorted arrays, ‘arr1’ and ‘arr2’, of sizes n1 and n2 respectively. Your
task is to merge these two arrays into a single sorted array.
The merged array should contain all elements from both arrays in non-decreasing order.
Input Format:
• The first line contains an integer n1, the size of the first array.
• The second line contains n1 integers, elements of first array in non-decreasing order.
• The third line contains an integer n2, the size of the second array.

5
 • The fourth line contains n2 integers, elements of second array in non-decreasing order.
Output Format:
• Print the merged sorted array in a single line, with each element separated by a space.
1 # include < stdio .h >
2
3 int main () {
4 int n1 , n2 , i , j , k ;
5

6 scanf ( " % d " , & n1 ) ;

7 int arr1 [ n1 ];
8 for ( i = 0; i < n1 ; i ++) {
9 scanf ( " % d " , & arr1 [ i ]) ;
10 }
11

12 scanf ( " % d " , & n2 ) ;

13 int arr2 [ n2 ];
14 for ( i = 0; i < n2 ; i ++) {
15 scanf ( " % d " , & arr2 [ i ]) ;
16 }
17

18 // Create a new array to store the merged result

19 int merged [ n1 + n2 ];
20 i = 0; // Pointer for the first array
21 j = 0; // Pointer for the second array
22 k = 0; // Pointer for the merged array
23

24 // Merge the arrays

25 while ( i < n1 && j < n2 ) {
26 if ( arr1 [ i ] <= arr2 [ j ]) {
27 merged [ k ++] = arr1 [ i ++];
28 } else {
29 merged [ k ++] = arr2 [ j ++];
30 }
31 }
32
33 // Copy remaining elements of arr1 , if any
34 while ( i < n1 ) {
35 merged [ k ++] = arr1 [ i ++];
36 }
37
38 // Copy remaining elements of arr2 , if any
39 while ( j < n2 ) {
40 merged [ k ++] = arr2 [ j ++];
41 }
42
43 // Print the merged array
44 for ( i = 0; i < n1 + n2 ; i ++) {
45 printf ( " % d " , merged [ i ]) ;
46 }
47 printf ( " \ n " ) ;
48
49 return 0;
50 }

6
 Problem Statement:
Given two strings, determine if the second string is an anagram of the first string. An
anagram is a word or phrase formed by rearranging the letters of a different word or phrase,
using all the original letters exactly once.
Assumptions:
• All characters in the strings are lowercase English alphabets.
Input Format:
• The first line contains an integer n, the maximum length of the strings.
• The second line contains the first string of at most n characters.
• The third line contains the second string of at most n characters.
Output Format:
• Print "The second string is an anagram of the first string." if the second
string is an anagram of the first string.
• Print "The second string is not an anagram of the first string." otherwise.
Code:
1 # include < stdio .h >
2 # include < string .h >
3
4 int main () {
5
6 int max_len ;
7 scanf ( " % d " , & max_len ) ;
8

9 char str1 [ max_len ] , str2 [ max_len ];

10 scanf ( " % s " , str1 ) ;
11 scanf ( " % s " , str2 ) ;
12
13 // Initialize flag to determine if the strings are anagrams
14 int isAnagram = 1;
15
16 // Arrays to keep track of character counts for both strings
17 int count1 [26] = {0};
18 int count2 [26] = {0};
19
20 for ( int i = 0; str1 [ i ] != ’ \0 ’; i ++) {
21 count1 [ str1 [ i ] - ’a ’ ]++;
22 }
23 for ( int i = 0; str2 [ i ] != ’ \0 ’; i ++) {
24 count2 [ str2 [ i ] - ’a ’ ]++;
25 }
26

27 // Compare character counts from both strings

28 for ( int i = 0; i < 26; i ++) {
29 if ( count1 [ i ] != count2 [ i ]) {
30 isAnagram = 0; // If counts differ , strings are not anagrams
31 break ; // No need to check further
32 }
33 }
34
35 if ( isAnagram ) {

7
36 printf ( " The second string is an anagram of the first string .\ n " ) ;
37 } else {
38 printf ( " The second string is not an anagram of the first string .\ n
");
39 }
40
41 return 0;
42 }

Practice Problems
1. Given two integers N and B, print the base-B representation of N .
Input: Two numbers N and B
Output: A single number corresponding to N in base-B

2. You are given 2 strings s and t. Find out whether t is a subsequence of string s. A
subsequence is a set of characters of a string obtained by removing a few characters
from the string without changing the order of the remaining characters. For example,
ADF is a subsequence of ABCDEF while CAE is not
Input: The first line contains the string s and the next line contains the string t
Output: Print ”YES” (without the quotes) if t is a subsequence of s and ”NO”
(without the quotes) otherwise

3. You are given M ranges of the form [Li , Ri ], where 1 ≤ i ≤ M and 1 ≤ Li ≤ Ri ≤ N

for some positive integer N . For each integer i from 1, 2, . . . , N find the number of
ranges which include i
Input: The first line contains two space-separated integers N and M respectively.
The following M lines contain 2 space-separated number each. That is, the ith line
contains the two numbers Li and Ri
Output: N space-separated integers, where the ith integer represents the number of
ranges which include i

Common Pitfalls
Loops
1. Forgetting to initialize iterator
1 for ( int i ; i < 10; i ++)
2

i is initialized to a garbage value which may be ≥ 10 leading to an infinite loop.

2. Crossing INT MAX limit leading to an infinite loop

1 for ( int i = 0; i <= INT_MAX ; i ++)
2

8
 A similar pitfall is working with unsigned iterators and comparing them to negative
numbers leading to an infinite loop.

3. Not updating iterator in while loop

1 int i = 0;
2 while ( i < 10) {
3 printf ( " % d \ n " , i ) ;
4 }
5

4. break takes you out of innermost loop

1 int i = 0 , j = 0;
2 while ( true ) { // outer loop
3 if ( i == 10)
4 break ; // takes you out of outer loop
5 j = i;
6 while ( true ) { // inner loop
7 if ( j == 10)
8 break ; // takes you out of inner loop , not outer loop
9 printf ( " % d % d \ n " , i , j ) ;
10 j ++;
11 }
12 i ++;
13 }
14

5. Updating iterator after continue

1 // Buggy code to print even numbers up to 10
2 int i = 1;
3 while ( i <= 10) {
4 if ( i %2)
5 continue ;
6 printf ( " % d \ n " , i ) ;
7 i ++;
8 }
9

Array
1. Out of bound access
1 int a [ n ];
2 a [ -1] = 0; // may give segmentation fault ( SIGSEV )
3 a [ n ] = 0; // may give segmentation fault ( SIGSEV )
4

Strings
1. NULL termination

9
 1 char str1 [] = " hello " ; // NULL automatically added at the last
2 char str2 [] = { ’h ’ , ’e ’ , ’l ’ , ’l ’ , ’o ’ }; // NULL not added at the
last
3

2. Working with a string without NULL character

1 char str [] = { ’h ’ , ’e ’ , ’l ’ , ’l ’ , ’o ’ };
2 int len = strlen ( str ) ; // may give wrong answer as strlen
terminates only when it finds NULL
3

Similar behavior of other string related functions like strcpy and strcmp.

3. Using = to copy string

1 char str1 [6] = " hello " ;
2 char str2 [6];
3 str2 = str1 ; // Correct way is to use strcpy function
4

4. Using == to compare strings

1 char str1 [6] = " hello " ;
2 char str2 [6] = " hello " ;
3 bool same = ( str1 == str2 ) ; // Correct way is to use strcmp
function
4

5. Buffer Overflow
1 char str [5];
2 strcpy ( str , " hello " ) ; // " hello " requires 6 bytes
3

6. Confusing strlen with array size

1 char str [10] = " hello " ; // strlen ( str ) = 5 but sizeof ( str ) = 10
2

10