Data Structures & Algorithms
Week 1.2 COMP1511 Code Gap
In this lecture
You need to understand slightly more about C to complete COMP2521
for statements (looping) asserts
There will be some relaxing of style requirements compared to the strict styleguide of COMP1511 (e.g. we will allow multiple returns). However, your code must adhere to the COMP2521 style guide at all times.
= For=Loops
Ways of combining initialization, condition, and increment in one line
; cond; incr) { }
1 #include
3 int main(int argc, char* argv[]) {
4 intsum=0;
6 while(i<10){
7 sum=sum+i;
10 printf("%d\n", sum); 11 }
#include
8 printf(“%d\n”, sum); 9}
int main(int argc, char* argv[]) {
int sum = 0;
for (int i = 0; i < 10; i++) {
Switch Statements
Switch statements make it easier to handle branching when dealing with equality comparisons where one side is always the same.
1 2 3 4 5 6 7 8 9
#include
int main(int argc, char* argv[]) {
char input;
scanf(“%c\n”, &input);
if (input == ‘W’) {
printf(“Up\n”);
else if (input == ‘A’) {
printf(“Left\n”);
else if (input == ‘S’) {
printf(“Down\n”);
else if (input == ‘D’) {
printf(“Right\n”);
printf(“Not valid\n”);
1 #include
3 int main(int argc, char* argv[]) {
4 char input;
5 scanf(“%c\n”, &input);
6 switch (input) {
7 case ‘W’: printf(“Up\n”); break;
8 case ‘A’: printf(“Left\n”); break;
9 case ‘S’: printf(“Down\n”); break;
10 case ‘D’: printf(“Right\n”); break;
11 default: printf(“Not valid\n”);
w a te rfa ll
Switch Statements
Now let’s write this as pseudocode – a method of describing the flow of program logic without having to use a particular programming langauge syntax.
1 switch (v) {
2 case CASE1:
3 STATEMENT1;
5 case CASE2:
6 STATEMENT2;
9 case CASEn:
10 STATEMENTx;
12 default:
13 STATEMENTy;
Exercise 1
Write a function monthName(int) that
accepts a month number 1=Jan … 12=Dec returns a string containing the month name assume that the string will be read-only
use a switch to decide on the month
Suggest an alternative approach using an array.
Exercise 2
Write a program that prints integer sequences (one per line):
seqq 1 -3 10 gives an error
prints 12345678910 prints 5678910
prints 10987654321 prints 14710
prints 14710 prints 1 0 -1 -2 -3
Package the core part as a function:
1. void seq(int start, int step, int finish) {…} main checks errors and sets up args for seq()
Asserts are statements that given a condition, will crash the program if the condition is not true. We them for testing.
7 return 0; 8}
void test_is_even() {
if (is_even(2) != 1) {
printf(“Failed is_even(2)\n”);
if (is_even(3) != 0) {
printf(“Failed is_even(3)\n”);
int main(int argc, char* argv[]) {
test_is_even();
#include
int is_even(int num) {
if (num % 2 == 0) {
8 return 0; 9}
void test_is_even() {
assert(is_even(2) == 1);
assert(is_even(3) == 0);
int main(int argc, char* argv[]) {
test_is_even();
#include
#include
int is_even(int num) {
if (num % 2 == 0) {
Data Structures & Algorithms
Week 1.3 Compilation & Makefiles
In this lecture
Compilation in the real world isn’t as straightforward as -you were led to believe in 1511
GCC compilation make & Makefiles
Compilers are programs that:
convert program source code to executable form
“executable” might be machine code or bytecode The Gnu C compiler (gcc):
du is much s lo w e r
links object files and libraries to produce executables
applies source-to-source transformation (pre-processor)
compiles source code to produce object files
python help understand
Note that dcc and 3c are wrappers around gcc:
Providing more checking and more detailed/understandable error messages Better run-time support (e.g. array bounds, use of dynamic memory)
Not suitable to prepare you for the real world
GCC Compilation Stages
For a single file
-E: Pre-processor
-c: Compiles C code
-o: Links to make executables
GCC Compilation Stages
For multiple files
T brackets – l
Pre – compiling
processing
brackets -0 bralktets\.co
stalk.e /grant. ,
GCC Compilation Stages
1 gcc -c Stack.c
2 # produces Stack.o, from Stack.c and Stack.h
3 gcc -c bracket.c
4 # produces bracket.o, from bracket.c and Stack.h
5 gcc -o rbt bracket.o Stack.o
6 # links bracket.o, Stack.o and libraries
7 # producing executable program called rbt
GCC includes
For very large projects, compilation can get complex:
Have to run many commands, or long commands
If not careful, ends up recompiling EVERYTHING instead of
only the files that have changed.
If we only modify file1.c, the -X is unnecessary.
file2.c X file2.o
For our previous compilations, we can now define a file that tells GCC how to keep track of dependencies for compilation
programming
1 target: 2
4 target: 5
source1, source2 …
commands to build target from sources (indented with a tab)
source1, source2 …
commands to build target from sources (indented with a tab)
source1, source2 …
commands to build target from sources (indented with a tab)
7 target: 8
make compiles code, driven by dependencies defined in a Makefile.
The target is rebuilt if older 2
than any source (applied recursively)
looks for a
Sources can also be targets
make compiles code, driven by dependencies defined in a Makefile. The target is rebuilt if older than any source (applied recursively)
1 2 3 4 5 6 7 8 9
rbt : brackets.o Stack.o
gcc -o rbt brackets.o Stack.o
brackets.o : brackets.c Stack.h
gcc -Wall -Werror -c brackets.c
Stack.o : Stack.c Stack.h
gcc -Wall -Werror -c Stack.c
rm -f *.o rbt
can contain variables
1 2 3 4 5 6 7 8 9
FLAGS=-Wall -Werror
rbt : brackets.o Stack.o
$(CC) -o rbt brackets.o Stack.o
brackets.o : brackets.c Stack.h
$(CC) $(FLAGS) -c brackets.c
Stack.o : Stack.c Stack.h
$(CC) $(FLAGS) -c Stack.c
rm -f *.o rbt
Data Structures & Algorithms
Week 1.4 Recursion
Why? (alternative
to for& While
In this lecture
While you don’t need recursion to solve a number of problems, its a programming technique that can substantially simplify your source code
– Wall – Wevvov – o factorial=factorial . [ Recursion
identical it
Recursion is a programming pattern where a function calls itself.
Typically, this happens during some kind of “looping”.
For/while loops are “iterative” solutions to looping, while
recrusion is a “recursive” solution
elf it is return 7
Base Case Recursive Case
1 #include
3 int factorial(int n) {
4 int product = 1;
5 for(inti=1;i<=n;i++){
11 int main(int argc, char* argv[]) { 12 printf("%d\n", factorial(8)); 13 }
product *= i;
8 return product; 9}
calls actorial
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
int main(int argc, char* argv[]) {
printf("%d\n", factorial(8));
1 #include
return 7 ☒ factorial 17- 1)
factorial return 8←
(8) ☒ factorial
(8) ] Henna 8 * factorial (8-1)
return 6 ☒ €
return 7 ☒
factorial (6-1)
works backwards cripples )
720×7=5040
5040×8=40320
,, factorial ( O)
mmm ,*www.a,, ,.ua
[next number = sum
A base case is what stops recursion going on forever…
Base Case Recursive Case
1 #include
Find tint 3 Fibonacci numbers
3 int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n – 1) + fibonacci(n – 2); —
int main(int argc, char* argv[]) {
printf(“%d\n”, fibonacci(8));
1 #include
3 int fibonacci(int n) {
4 if (n == 1) return 0;
5 if (n == 2) return 1;
prevPrev = 0;
current = 0;
(int i = 2; i < n; i++) {
current = prevPrev + prev;
prevPrev = prev;
{standard algorithm
14 return current;
prev = current;
17 int main(int argc, char* argv[]) {
18 printf("%d\n", fibonacci(8));
-Iteration
✗ too long
lite ra l expressions
fibl37-fiblbtfib.lt) ←
-fib(2)= fib(1) fib/O) ←1- I Cibll)= 7 fiblo)=O
fib(4)= fibc3)+ fib(2)
fib(2)= GDII) 1- fib10) t tr
New command:
/ then → . fib " " /
time infront BUT , iterative is a lot
" tim e . / fib FASTER_
Recursion -
simplify an process
Does it user more memory? Or less?
Is it faster? Or slower?
pro ;→ length -1-1
Let's take a look at a linkedlist example.
1 int length_iterative_1511(struct node *head) {
→ - point fin d length
2 struct node *current = head;
3(start)int length = 0; pointing u n til NULL 4 while (current != NULL) {
5 current = current->next;
6 length++; (counter)
10 int length_iterative_2521(struct node *head) {
( for 100ps) for (struct node *current = head; current != NULL; current = current->next) {
int length = 0; –_
length++; }
int length_recursive(struct node *head) {
if (head == NULL) {
/recursive
return 0; }
If NOT NULL
-return 1 + length_recursive(head->next); }