The C Programming Language

Announcements

Adventure Due Tonight
Course Evals Today
Finals Next Week

Section	Class Time	Final Exam Day	Final Exam Date	Final Exam Time
1	09:10 AM	Wednesday	11 Dec	8:00AM - 11:00AM
2	10:20 AM	Thursday	12 Dec	8:00AM - 11:00AM

Introduction

Goal: Introduce a New Language: C
Topics:
- Algorithimically “Interesting”
- Technically “Interesting”
- Systems programming as both
- What is computer science?

Introduction

Codebase: We will use code from Spring ’23 CS 271
Folder: We will use the “sort” folder, which contains
- make.py
- sort.c
- sort.py
- test.sh
- times.out

git clone https://github.com/cd-public/cs271wu.git

Cloning into 'cs271wu'...
remote: Enumerating objects: 246, done.
remote: Counting objects: 100% (73/73), done.
remote: Compressing objects: 100% (65/65), done.
remote: Total 246 (delta 29), reused 6 (delta 4), pack-reused 173 (from 1)
Receiving objects: 100% (246/246), 11.08 MiB | 17.48 MiB/s, done.
Resolving deltas: 100% (84/84), done.

ls cs271wu/sort

make.py  sort.c  sort.py  test.sh  times.out

Algorthmically Interesting

Correctness: We previously introduced “algorithmically correct”
Interesting: I say something is algorthmically interesting when:
- I have an interesting problem
- I can (relatively) easily find a technically correct solution
- I could find a better solution, but it is non-obvious
Interesting like a crossword puzzle - easy to write answers, hard to think of them.

Sorting is Algorthmically Interesting

Insertion Sort: Sorting by inserting elements is slow! But correct…
Merge Sort: Sorting by merging is fast! But may be confusing…
Quick Sort: AIs do best with quicksort, which is kinda fast but very easy.

quicksort = lambda arr: arr if len(arr) <= 1 else quicksort([x for x in arr[1:] if x <= arr[0]]) + [arr[0]] + quicksort([x for x in arr[1:] if x > arr[0]])

quicksort([5, 2, 8, 1, 9, 4, 7, 3, 6])

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Sorting is Algorthmically Interesting

Insertion Sort: Sorting by inserting elements is slow! But correct…
Merge Sort: Sorting by merging is fast! But may be confusing…
Tim Sort: The built-in Python sort is a combination of inserts and merges… why?

cat cs271wu/sort/test.sh

( python make.py ; gcc sort.c ; time ./a.out ; time python sort.py ; rm *.txt ; rm a.out ) 2>times.out

Technically Interesting

Correctness: We previously introduced “technically correct”
Interesting: I say something is technically interesting when:
- I have an interesting problem
- I can (relatively) easily imagine a technically correct solution
- I would have a hard time actually writing that solution down
Interesting like knitting a pattern - I need precise control following specific guidelines to achieve my goals.

Technically Interesting

Tim Sort is technically interesting because it is a bit faster than other sorts, but was hard to write.
We test it:

from time import time
from random import randint

ten_thousand_random_ints = [randint(0, 100000) for _ in range(10000)]

Technically Interesting

AI should in theory be smart or good at things I guess, I don’t know.
Time it.

ten_thousand_random_ints = [randint(0, 100000) for _ in range(10000)]
start = time()
quicksort(ten_thousand_random_ints)
end = time()
end-start

0.031879425048828125

Technically Interesting

Tim Sort is very, very fast in practice.
Time it.

ten_thousand_random_ints = [randint(0, 100000) for _ in range(10000)]
start = time()
sorted(ten_thousand_random_ints)
end = time()
end-start

0.0017609596252441406

Technically Interesting

Both AI Quick Sort and Tim Sort use known algorithms, they differ only in technique…
And Tim Sort is ~30x faster.
How much more can technique speed us up?

( python make.py ; gcc sort.c ; time ./a.out ; time python sort.py ; rm *.txt ; rm a.out ) 2>times.out

real    0m0.366s
user    0m0.349s
sys     0m0.016s

real    0m1.302s
user    0m1.239s
sys     0m0.049s

Technically Interesting

My hand-written C merge sort is much faster than the state-of-the-art Python Tim Sort.
I am ~4x faster just by working in another language.
Imagine if I implemented Tim Sort.

1.302/0.366

3.557377049180328

Technically Interesting

This is what C looks like

// sort.c

// sort a million integers

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIL 1000000
#define DEBUG 0

void print_arr(int *arr, int len)
{
    if (DEBUG) {
        int i ;
        fprintf(stderr,"{ ") ;
        for (i = 0 ; i < len - 1 ; i++ )
        { 
            fprintf(stderr,"%u, ", arr[i]) ;    
        }
        fprintf(stderr,"%u }\n", arr[i]) ;
    }
    return ;
}

void csort(unsigned *list, unsigned *work, int frnt, int back )
{
    int midl = (frnt + back) / 2, i = frnt , j = frnt, k ;
    k = midl ;
    if (DEBUG) {fprintf(stderr,"frnt=%d, back=%d\n",frnt,back);}
    if ( frnt + 1 == back )
    {
        if ( work[frnt] > work[back] )
        {
            midl = list[frnt] ;
            work[frnt] = work[back] ;
            work[back] = work[frnt] ;
        }
        return ;
    }
    memcpy( work + frnt , list + frnt , sizeof(unsigned) * (back - frnt) ) ;
    csort( work , list , frnt , midl ) ;
    csort( work , list , midl , back ) ;
    while ( j < midl && k < back )
    {
        if (work[j] < work[k])
        {
            list[i++] = work[j++] ;
        } else {
            list[i++] = work[k++] ;
        }
    }
    while ( j < midl )
    {
        list[i++] = work[j++] ;
    }
    while ( k < back )
    {
        list[i++] = work[k++] ;
    }
    return ;
}

int main()
{
    int i = 0 ;
    size_t bsize = 16 ; 
    unsigned list[MIL], work[MIL];
    char *buf = (char *)malloc(bsize*sizeof(char)) ;
    FILE *fp ;
    
    fp = fopen("onem.txt", "r") ;
    for( i = 0; i < MIL ; i++ )
        {
            getline(&buf, &bsize, fp) ;
            list[i] = atoi(buf) ;
        }
    fclose(fp);
    
    csort( list , work , 0 , MIL ) ;
    
    fp = fopen("incm.txt", "w") ;
    for( i = 0; i < MIL ; i++ )
        {
            fprintf(fp, "%u\n", list[i]) ;
        }
    fclose(fp) ;
    
    return 0 ;
}

Computer Science

Computer science is the study of the…
- Technically Interesting: Cool emergent things from the physical sciences and electrical engineering domains
  - Rocks that think
- Algorithmically Interesting: Cool abstract applications of work from mathematics, philosophy, and linguistics
  - Thoughts that rock
I love both, and hope you can come to love both as well!

Thank you!

Adventure Due Tonight
Course Evals Today
Finals Next Week

Section	Class Time	Final Exam Day	Final Exam Date	Final Exam Time
1	09:10 AM	Wednesday	11 Dec	8:00AM - 11:00AM
2	10:20 AM	Thursday	12 Dec	8:00AM - 11:00AM