Walkthrough —
This document is a clear, student-friendly step-by-step walkthrough of the solution file you
provided. Each question is broken down into explicit steps, code examples, explanations,
and testing tips so students can follow, compile, and test on their own.
1 — Power functions (recursive + iterative), driver, makefile, DAG (30 pts)
Goal: compute base^exp where exp is a nonnegative integer.
1(a) Implement `power` — recursive and iterative
Step 1 — Recursive version (corrected & complete):
int power_recursive(int base, int exp) {
if (exp == 0) return 1; // base case
return base * power_recursive(base, exp - 1);
}
Explanation: if the exponent is 0, return 1; otherwise, multiply the base by power(base,
exp-1).
Step 2 — Iterative version:
int power_iterative(int base, int exp) {
int ans = 1;
for (int i = 0; i < exp; i++) {
ans *= base;
}
return ans;
}
Explanation: start with ans = 1 and multiply by base exp times.
1(b) Time & space complexity — quick comparison
- Both naive versions above: Time = O(exp) (linear in the exponent).
- Space: recursive uses O(exp) stack frames; iterative uses O(1) additional space.
- Improvement: Exponentiation by squaring (binary exponentiation) gives O(log exp) time.
Idea: if exp is even: power(base,exp)=power(base*base,exp/2); if odd:
base*power(base,exp-1).
1(c) Driver program (main.c) — using command-line args
Step 4 — Files layout:
- power.h — prototype(s)
- power.c — implementation(s)
- main.c — driver (reads argv, calls power)
- Build produces executable power
Step 5 — Example power.h:
#ifndef POWER_H
#define POWER_H
int power_recursive(int base, int exp);
int power_iterative(int base, int exp);
int power_fast(int base, int exp); // optional: binary exponentiation
#endif // POWER_H
Step 6 — Example main.c:
#include <stdio.h>
#include <stdlib.h>
#include "power.h"
int main(int argc, char *argv[]) {
if (argc != 3) {
printf("Error, expected usage is ./power [base] [exponent]\n");
return EXIT_FAILURE;
}
int base = atoi(argv[1]);
int exponent = atoi(argv[2]);
printf("Result of %d^%d = %d\n", base, exponent, power_iterative(base, exponent));
return EXIT_SUCCESS;
}
Notes: atoi converts strings to integers (no deep validation here). Use power_iterative or
power_recursive or power_fast as desired.
1(d) Trace variables for power(4,2) (recursive)
Step 7 — Stack trace (call sequence):
Call: power_recursive(4,2)
1. power_recursive(4,2) -> 4 * power_recursive(4,1)
2. power_recursive(4,1) -> 4 * power_recursive(4,0)
3. power_recursive(4,0) -> return 1
Return unwind: power_recursive(4,1) returns 4; power_recursive(4,2) returns 16
Result: 16. Each stack frame holds base, exp, and return address.
1(e) Makefile (debuggable with -g)
Step 8 — Example Makefile:
CC = gcc
CFLAGS = -g -Wall
TARGET = power
OBJECTS = main.o power.o
all: $(TARGET)
$(TARGET): $(OBJECTS)
$(CC) $(CFLAGS) -o $(TARGET) $(OBJECTS)
main.o: main.c power.h
$(CC) $(CFLAGS) -c main.c
power.o: power.c power.h
$(CC) $(CFLAGS) -c power.c
.PHONY: clean
clean:
rm -f $(OBJECTS) $(TARGET)
1(f) DAG for the makefile
Step 9 — DAG explanation (text/ASCII):
Dependencies:
- main.o depends on main.c and power.h
- power.o depends on power.c and power.h
- power (executable) depends on main.o and power.o
ASCII DAG:
main.c power.c power.h
| | |
+---> main.o |
\ |
\ power.o
\ /
\ /
\ /
\/
power (executable)
2 — Dynamic memory allocation (25 pts)
Step 10 — Static allocation region: stack
Answer: stack (function data areas are statically allocated and reclaimed on function
entry/exit).
Step 11 — malloc allocates from: heap
Answer: heap.
2(c) Complete code for Figures (dynamic allocation)
Step 12 — Example corrected code snippets:
int *nump = (int *)malloc(sizeof(int));
*nump = 110;
char *letp = (char *)malloc(sizeof(char));
*letp = 'T';
planet_t *planetp = (planet_t *)malloc(sizeof(planet_t));
planet_t blank = {"", 0, 0, 0, 0};
*planetp = blank;
Notes: malloc returns void * — casting is optional in C but shown here for clarity. Initialize
structures via an assigned blank struct as above.
2(d) Statements requested (answers)
Step 13 — Quick answers:
1. Print character through letp:
printf("%c\n", *letp);
2. Scan a new value into location of nump:
scanf("%d", nump);
3. Store "Mars" in structure name:
strcpy(planetp->name, "Mars");
(Ensure planetp->name is large enough.)
4. Print the name:
printf("%s\n", planetp->name);
5. nump becomes a dynamically allocated array of 25 ints zeroed:
nump = (int *)calloc(25, sizeof(int));
6. letp becomes an 80-char string:
letp = (char *)malloc(80 * sizeof(char));
7. Free memory:
free(nump);
free(letp);
free(planetp);
3 — Linked lists and operators (20 pts)
Step 14 — Operator for bytes of a type: sizeof
Step 15 — Definition fill-in: linked list, list head
Step 16 — Debugging/executable only: set breakpoints with gdb
Step 17 — Order of boolean tests (short-circuiting):
Answer: No — they are not always the same. Example:
If cur_nodep is NULL then cur_nodep->digit is invalid. Use cur_nodep != NULL &&
cur_nodep->digit != target to be safe. Always test pointer for NULL first.
4 — Pointer review (20 pts)
Step 18 — Table summary (short answers):
a. SIZE — Not a pointer (macro).
b. inp — Yes — output parameter (file pointer passed around).
c. nump — Yes — output parameter (stores numerator read).
d. denomp — Yes — output parameter (stores denominator read).
e. num_list — Yes — array (array name decays to pointer to element 0).
f. den_list — Yes — array.
g. fracp — Yes — file pointer (FILE *).
h. i — No — simple int.
i. slash — No — char.
j. status — No — int.
Note: remember arrays decay to pointers in many contexts, but their type is still array.
5 — Recursive count_special_char (10 pts)
Step 19 — Function (cleaned up):
int count_special_char(const char *str, int index) {
if (index >= (int)strlen(str)) return 0;
int count = count_special_char(str, index + 1);
if (!isalnum((unsigned char)str[index])) count++;
return count;
}
Notes: Cast to unsigned char before isalnum to avoid undefined behavior with negative char
values. Using index >= strlen(str) is safer.
Step 20 — main() sample run:
int main(void) {
const char *test_string = "MyCS222_Hw!#3";
int result = count_special_char(test_string, 0);
printf("String: \"%s\"\n", test_string);
printf("Number of special characters: %d\n", result);
return 0;
}
Expected Output:
String: "MyCS222_Hw!#3"
Number of special characters: 3
Explanation: `_`, `!`, `#` are non-alphanumeric -> counted as special characters.
Quick testing checklist for students (how to run everything)
Step 21 — Compile & run:
1. Save power.h, power.c, main.c, Makefile.
2. Run make in terminal -> creates power.
3. Run sample: ./power 4 2 -> should print Result of 4^2 = 16.
4. To test recursive special-char program: save file (e.g. count_special.c) and compile:
gcc -Wall -Wextra -g -o count_special count_special.c
./count_special -> check output.
Step 22 — Debugging tips:
- Use gdb ./power then run 4 2 to debug.
- Use valgrind ./power (if installed) to check memory leaks for dynamic allocation code.
- If segmentation fault occurs, check pointer nullity and test ordering (see 3d).