CS 21 25.2 Laboratory Exercise 0

Review on C Programming

Overview

In CS 21, you will be introduced to machine language which is comprised of instructions that computer processors are designed to execute. All computer programs are essentially translated into machine language, directly or indirectly, by compilers and interpreters.

High-level programming languages such as Python provide a high level of abstraction that hides the complexity of the underlying machine instructions from programmers; this allows for the creation of complex programs without requiring programmers to delve into the lower-level details of machine language. Machine language is generally cumbersome for humans to process as it is primarily designed for processors. A more human-readable bridging language called assembly language will be introduced so that the study of machine language is made more comprehensible.

Since all programs are translated into machine language (or equivalently, assembly language), understanding the principles behind low-level programs enables programmers to craft high-level code that results in a more efficient set of machine instructions. Towards this end, you will be writing programs in assembly language; this is relatively more involved as the layers of abstraction of high-level languages that make programming much more manageable are not present at this level.

CS 21 starts off by introducing the C programming language which provides a lower level of abstraction compared to a language such as Python. While fewer abstractions requires more manual effort and attention to detail from the programmer, it enables more fine-grained control in how programs are translated into machine instructions; this makes it ideal for systems programming (e.g., operating systems, limited-resource devices) in which efficient processor execution is usually of greater concern. C shares much more functionally with assembly and machine language than Python does; knowing the fundamentals of C makes the study of assembly and machine language much more manageable, especially coming from a high-level language such as Python.

General Instructions

In this laboratory activity, you are to work on 2 HOPELEx Checkpoint Items that will review your skills on C programming.

Important Reminder

You must finish and show your working checkpoint tasks to your lab handler before the end of the laboratory period. HOPELEx checkpoint items contribute 1% to your lab grade.

At the end of the HOPELEx Checkpoints are take home exercises called the the TakeHOPE items. These are not graded and will not be submitted but will help you prepare for the HOPE.

HOPELEx Checkpoints

Checkpoint Item: Substring Search

Given a string haystack and a substring needle, you are to create a C function that searches for all instances of needle within haystack. The function template is as follows:

int search_haystack(char *needle, char *haystack, int **indices){
   // insert your code here.
}

The function should return the number of times needle was found in the haystack, and it should store the starting indices of each match in the dynamically allocated indices. If no match was found, 0 must be returned and indices must be NULL.

Restrictions

1. The only headers that may be included are:
   • <stdio.h>
   • <stdlib.h>
   • <assert.h>
   • <string.h> - only strlen() is allowed to be used
2. Searching via regular expressions is not allowed.
3. Neither needle nor haystack can be modified.
4. The memory allocation size for indices must exactly correspond to the number of matches.
5. Use zero-indexing for determining the indices of the matches.
6. The substring search is case-sensitive.

Example Usage

int *indices = NULL;
int count = search_haystack("CS", "CS 21 in DCS", &indices);

assert(count == 2);
assert(indices != NULL);
assert(indices[0] == 0);
assert(indices[1] == 10);

Test Cases

You may use these test cases to ensure your function is properly implemented.

needle	haystack	Expected count value	Expected content of *indices
"CS"	"CS 21 in DCS"	2	{0, 10}
"aa"	"aaaa"	3	{0, 1, 2}
"a"	"banana"	3	{1, 3, 5}
"aba"	"abababa"	3	{0, 2, 4}
"test"	"test"	1	{0}
"hello"	"hello world"	1	{0}
"lo"	"hello hello"	2	{3, 9}
"x"	"abcdef"	0	NULL
"gh"	"abcdef"	0	NULL
"abcd"	"abc"	0	NULL
""	"abc"	0	NULL
"abc"	""	0	NULL
" "	"a b c"	2	{1, 3}.
"CS"	"CSCSCS"	3	{0, 2, 4}
"is"	"this is a test"	2	{2, 5}
"ana"	"banana"	2	{1, 3}
"A"	"AaAaA"	3	{0, 2, 4}
"Aa"	"AaAaA"	2	{0, 2}
"00"	"00000"	4	{0, 1, 2, 3}
"end"	"the endend"	2	{4, 7}
"."	"a.b.c."	3	{1, 3, 5}
"--"	"----"	3	{0, 1, 2}
"101"	"01010101"	3	{1, 3, 5}
"010"	"01010101"	3	{0, 2, 4}
"needle"	"finding a needle in a haystack needle"	2	{10, 31}

TakeHOPE Problems

Problem 1: Replacing Substrings

Following the same restrictions as Item 1, implement a function replace_substring that takes a string source as well as substrings target and replacement, and returns a string with all instances of target in source with replacement.

Replacements must be done left-to-right. If target is not found in source, the original source string must be returned. If target is an empty string, the original source string must also be returned.

Tip

The address of a string is the same as the address of the first character of the string in memory.

The end of a string is always the NULL character with a byte value of 0.

Your function must follow the following template:

Restrictions

1. The only headers that may be included are:
2. <stdio.h>
3. <stdlib.h>
4. <assert.h>
5. <string.h> - only strlen() is allowed to be used
6. Searching via regular expressions is not allowed.
7. Neither source, target, nor replacement can be modified.
8. The substring search is case-sensitive.

Example Usage

char* replace_substring(const char *source,
                        const char *target,
                        const char *replacement){
    //insert your code here.
}

You may use the following testcase to validate your code:

int evaluate_replace_string(char *test_string, char *test_result){
    int i = 0;
    while (test_string[i]||test_result[i]){
        if (test_string[i]!=test_result[i]){
            return 1;
        }
        ++i;
    }
    return 0;
}
int main(){
    const char *test_string = "Thirty-three thirsty, thundering thoroughbreds thumped Mr. Thurber on Thursday.";
    const char *test_substring = "th";
    const char *test_replace = "squw";
    char *test_result = "Thirty-squwree squwirsty, squwundering squworoughbreds squwumped Mr. Thurber on Thursday.";
    char* replaced_string = replace_substring(test_string, test_substring, test_replace);
    printf("Test case passed: %s",evaluate_replace_string(replaced_string, test_result) ? "False" : "True");
}

Test Cases

You may use these additional test cases to ensure your function is properly implemented.

s	target	replacement	Expected String replaced_string
"Hello hello CS21!"	"Hello"	"Goodbye"	"Goodbye hello CS21!"
"Hello hello CS21!"	"hEllO"	"goodBye"	"Hello hello CS21!"
"ababABABabab"	"ba"	"cal"	"acalbABABacalb"
"ggGGGggGgGGGGGGgG"	"gg"	"All"	"AllGGGAllGgGGGGGGgG"
"aa aaa aaaa aaaaa"	"aa"	"rt"	"rt rta rtrt rtrta"
"Agree"	"E"	"EEEEEE"	"Agree"
"hello"	"hello"	"Hello World!"	"Hello World!"
"hello"	"hello"	""	""
"run"	"walk"	"sprint"	"run"
"Zero,one"	"o"	"0"	"Zer0,0ne"
"Zer0,0ne"	"0"	"o"	"Zero,one"
"pointer"	""	""	"pointer"
"spa ce dou t"	"space"	"tab"	"spa ce dou t"
"0123456789ABCDEF"	"9AB"	"Gabby"	"012345678GabbyCDEF"
""	"9AB"	"Gabby"	""

Problem 2: Function Calls and Program Stack

For this task, we will look at function calls, the program's call stack, stack frames, and the stack frame's size. This task does not require you to know the full details behind those concepts but it does require you to research them when they appear in the instructions or questions below.

We will use the following code (that computes Fibonacci numbers) as our working example:

#include<stdio.h>

int fib( int i ) {
  printf("fib(%d) : i = %d : &i = %p\n", i, i, &i);
  return (i==1 || i==2) ? 1 : fib(i-1) + fib(i-2);
}

int main() {
  int n = 9;
  printf("main   : n = %d : &n = %p\n", n, &n);
  fib(n);
  return 0;
}

Compile the code with no optimization. For example, if you are using the gcc compiler and your source code is fib.c, you can compile the code without optimization using the -O0 option as follows:

gcc fib.c -O0 -o fib

Tasks and Guide Questions

STEP 1: Compile the program (without optimizations) and then run the program.

STEP 2: Observe the logs produced by the program. There is one 'logging' (printf) instruction in main and one logging instruction in fib. Each call to a function will produce one line of the logs.

Guide Questions:

1. What is the address of the int variable i for the first fib(9) call? You can see this from the first log produced by the fib function (not the main function)
2. What is the address of the int variable i for the first fib(8) call? You can see this from the second log produced by the fib function.
3. What is the address of the int variable i for the first fib(7) call? You can see this from the third log produced by the fib function
4. Can you observe pattern of the change of address of variable i as the sequence of calls to fib continues? Describe the pattern.
5. Look at the address of variable i for the fib(2) and fib(1) calls. What can you observe? Explain this observation.

STEP 3: Store the logs for this run of the program so it can be used for comparison later.

Note:

When a function is called, the program needs to allocate a portion of memory to store the function's arguments and local variables. We can call this portion of memory as the function call's frame. It is common in a program to have functions calling functions. e.g. main calling fib and fib calling itself. The sequence of function calls produces a sequence of frames, one frame for each function call. This sequence of frames is arranged as a stack, called the call stack, where the frame for the most recent function call is on the 'top' of the stack while the frame for the least recently function call is at the 'bottom' of the stack. When a function exits, the frame associated with the function call (aka its stack frame) is released or removed from the call stack. Different functions can have different stack frame sizes due to differing numbers of arguments and/or numbers (or sizes) of local variables.

STEP 4: Change the function fib by adding an (unused) array of characters of size 10.

int fib( int i ) {
  char x[10]; // unused array of 10 characters
  printf("fib(%d) : i = %d : &i = %p\n", i, i, &i);
  return (i==1 || i==2) ? 1 : fib(i-1) + fib(i-2);
}

STEP 5: Compile and run the updated program and observe the produced logs for this run.

Guide Question:

1. How is the pattern of change of address of variable i for this program (with the addtional char x[10]; line) different from pattern produced by the original program (no additional local variables)? Relate this to the idea of the stack frame size.

STEP 6: Changed the function fib by changing the array of characters size to 11.

int fib( int i ) {
  char x[11]; // unused array of 11 characters
  printf("fib(%d) : i = %d : &i = %p\n", i, i, &i);
  return (i==1 || i==2) ? 1 : fib(i-1) + fib(i-2);
}

STEP 7: Compile and run the updated program and observe the produced logs for this run.

Guide Questions:

1. How is the pattern of change of address of variable i for this program (with the char x[11]; line) different from pattern produced by the second program (with the line char x[10];)?
2. How many times does program call function fib?
3. What is the maximum number of stack frames from fib function calls that exist simultaneously on the call stack?

Problem 3: Linked List insert_at

(to follow)