262: Programming and Data Structures
=====================================

Continuation of foundational CS concepts, covering elementary file handling and abstract data types.

Topics
------

- Linked lists, stacks, queues, and trees
- Abstract data type (ADT) design
- File I/O in C
- Dynamic memory management

Projects
--------

Sparse Matrix (`262/list.c <https://github.com/aclark4life/cs/blob/main/262/list.c>`_)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

A 2D linked-list implementation of a sparse matrix. Each non-zero element is stored as a node
with row/column coordinates, linked both horizontally and vertically to enable efficient traversal
without allocating memory for zero entries.

For example, the matrix::

       col0  col1  col2  col3
  row0 [  0     0     3     0  ]
  row1 [  0     0     0     0  ]
  row2 [  7     0     0     0  ]
  row3 [  0     0     0     5  ]

is stored as three nodes linked in two dimensions:

.. code-block:: text

                     HEAD
                    /    \
             (row=0,col=2,val=3) ──next_row──▶ (row=2,col=0,val=7) ──next_row──▶ (row=3,col=3,val=5)
                    │                                  │                                  │
               next_col                          next_col                           next_col
                    │                                  │                                  │
                   NULL                              NULL                               NULL

Only the three non-zero entries are allocated; all zero cells consume no memory.

.. code-block:: c

   struct element {
     int value;
     int row;
     int col;
     struct element *next_row;
     struct element *next_col;
   };

   struct element *insert_row(struct element *new_node, struct element *head) {
     struct element *current = head;
     struct element *prev = head;

     while (current->next_row != head) {
       current = current->next_row;
       if (new_node->row == current->row && new_node->col == current->col) {
         current->value = new_node->value;
         free(new_node);
         return (NULL);
       }
       if (new_node->row < current->row) {
         new_node->next_row = current;
         prev->next_row = new_node;
         return (new_node);
       }
       prev = current;
     }
     current->next_row = new_node;
     new_node->next_row = head;
     return (new_node);
   }

Statistics Calculator (`262/avg.c <https://github.com/aclark4life/cs/blob/main/262/avg.c>`_)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Reads a list of integers from a file or stdin and computes the mean and standard deviation.

.. code-block:: c

   for (i = 0; i < num_values; i++)
       sum += values[i];
   mean = sum / num_values;

   for (i = 0; i < num_values; i++)
       sum_sq_diff += pow(values[i] - mean, 2);
   stdev = sqrt(sum_sq_diff / (num_values - 1));

   printf("Mean: %f\n", mean);
   printf("Standard Deviation: %f\n", stdev);

Character Frequency Counter (`262/counter.c <https://github.com/aclark4life/cs/blob/main/262/counter.c>`_)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Reads a text file and counts the frequency of each letter, outputting percentages sorted by
frequency — an early exploration of frequency analysis.

.. code-block:: c

   /* count letters */
   for (; (fscanf(infile, "%c", &letter)) != EOF;)
       counts[(unsigned char)(toupper(letter) - 'A')]++;

   /* sort by frequency (selection sort) */
   for (i = 0; i < 26; i++)
       for (j = i + 1; j < 26; j++)
           if (counts[i] < counts[j]) {
               temp_count = counts[i]; counts[i] = counts[j]; counts[j] = temp_count;
               temp_char = char_codes[i]; char_codes[i] = char_codes[j]; char_codes[j] = temp_char;
           }

   for (i = 0; i < 26; i++)
       fprintf(stderr, "%c = %5.2f\n", char_codes[i], ((float)counts[i] / sum) * 100);

Roach Simulator (`262/roach.c <https://github.com/aclark4life/cs/blob/main/262/roach.c>`_)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Simulates a random walk of a "roach" on a 2D grid, tracking which squares have been visited.
Demonstrates random number generation, 2D arrays, and simulation loops.

.. code-block:: c

   /* 7 possible move directions as (Δrow, Δcol) */
   int imove[] = {-1, 0, 1, 1, 1, 0, -1};
   int jmove[] = { 1, 1, 1, 0,-1,-1,-1};

   /* pick a random move; retry if it would leave the grid */
   do {
       move = rand() % 7;
       imaybe = ibug + imove[move];
       jmaybe = jbug + jmove[move];
   } while (imaybe < 0 || imaybe >= cols || jmaybe < 0 || jmaybe >= rows);

   count[imaybe][jmaybe]++;
   ibug = imaybe;
   jbug = jmaybe;

Trapezoidal Integration (`262/trapezoid.c <https://github.com/aclark4life/cs/blob/main/262/trapezoid.c>`_)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Implements numerical integration of a quadratic function using the trapezoidal rule, illustrating
how continuous mathematics can be approximated computationally.

.. code-block:: c

   /* integrate ax² + bx + c from lower_bound to upper_bound in `number` sub-intervals */
   base = (upper_bound - lower_bound) / number;
   for (count = 0; count < number; count++) {
       left_height  = a * pow(lower_bound, 2)        + b * lower_bound        + c;
       right_height = a * pow(lower_bound + base, 2) + b * (lower_bound+base) + c;
       answer += base * (left_height + right_height) / 2.0;
       lower_bound += base;
   }
   printf("AREA OF TRAPEZOID: %f\n", answer);