Skip to content

HW2 - Event Log Sorter

Due Date: July 10th 2026, 05:00 PM

In this assignment you'll build a small toolkit for sorting a log of timestamped events into chronological order. Along the way you'll practice the three ideas from the last few lectures:

  • bit manipulation (Lecture 3): pack a full calendar timestamp into a single 64-bit integer,
  • pointers and out-parameters (Lecture 5): unpack that integer through pointers, and pass a heap array and its size around explicitly, and
  • dynamic memory (Lecture 6): allocate the heap's storage with malloc, hand ownership back to the caller, and free it exactly once.

You'll put these together into an array-based binary heap (a priority queue) and use it to run heapsort. A pre-written main.c then turns your library into a working command-line sorter.

  • Starter code: hw2/ implement your code in events.c.
  • Language standard / flags: clang -Wall -Wextra -Werror -std=c17
  • Submission: see Submitting below.

Getting Started

You already created your homework repository (homework-GITHUB_USERNAME in the uchicago-cmsc14300-sum-2026 organization) for HW1, so there is no new setup. Pull the HW2 starter files from the upstream repository:

$ cd cmsc14300-sum-2026/homework-GITHUB_USERNAME
$ git pull upstream main

This adds an hw2/ directory alongside your hw1/. If you have not set up your repository yet, follow the "Getting Started" section of the HW1 writeup first, then run the command above. If git pull upstream main reports a merge or a conflict, do not force anything - post on Ed and we will help.

Background

Strings of bits, and one integer per timestamp

Recall from Lecture 3 that an integer is just a row of bits, and that we can read or write chosen bits with shifts (<<, >>) and masks (&, |). A uint64_t (from <stdint.h>) is an unsigned integer that is exactly 64 bits wide - room for many small fields side by side.

We will store a full timestamp (year, month, day, hour, minute, second) in the low 40 bits of one uint64_t, laid out from the most-significant field to the least-significant field:

   bit:   39 ............ 26   25 .. 22   21 .. 17   16 .. 12   11 .... 6   5 ...... 0
         [     year (14)    ] [month(4)] [ day (5) ] [hour(5) ] [ min (6) ] [ sec (6)]

Each field gets just enough bits to hold its largest value (a year up to 16383, a month up to 12, and so on). To build the value you shift each field into its position and OR the pieces together; to take it apart you shift back down and mask off the field's width.

The reason for this particular order is the payoff of the whole assignment: because the fields run from most-significant (year) down to least-significant (second), a larger packed number is always a later moment in time. So once your timestamps are packed, comparing two of them is nothing more than comparing two uint64_t values with <. No field-by-field date logic anywhere.

A heap that lives in an array

A binary heap is a complete binary tree stored in a flat array. We use a max-heap: every parent is greater than or equal to its children, so the largest value is always at index 0 (the root). With the tree packed into an array, the parent/child links are pure index arithmetic:

   parent(i) = (i - 1) / 2
   left(i)   = 2*i + 1
   right(i)  = 2*i + 2

Two operations keep the heap in order:

  • sift up: after adding a new element at the end, swap it upward past any smaller parent until it fits.
  • sift down: after removing the root, move the last element to the root and swap it downward past its larger child until it fits.

heap_push uses sift up; heap_pop (remove the max) uses sift down. Repeatedly popping the max yields the values in descending order, and that idea, done in place, is heapsort.

Homework 2 Tasks

Implement every function in starter/events.c. The exact prototype and contract for each is in starter/events.h (including the full bit layout). You may add your own static helper functions (a swap, a sift-up, and a sift-down are natural ones).

Part 1 - Datetime codec (25 pts)

Function Does
uint64_t dt_pack(int year, int month, int day, int hour, int minute, int second) Pack the six fields into one 64-bit value.
void dt_unpack(uint64_t t, int *year, int *month, int *day, int *hour, int *minute, int *second) Recover each field with shifts and masks, writing through the out-pointers to individual variables..
int dt_valid(int year, int month, int day, int hour, int minute, int second) Return 1 if every field is in range (per the layout), else 0.

A correct dt_pack/dt_unpack pair round-trips: unpacking a packed value gives back exactly the fields you started with.

Part 2 - Array-based max-heap (40 pts)

Function Does
uint64_t *heap_create(int capacity) malloc room for capacity timestamps; return the pointer (caller owns it), or NULL on bad capacity / allocation failure.
void heap_free(uint64_t *heap) Free a heap from heap_create (free(NULL) is fine).
void heap_push(uint64_t *heap, int *size, int capacity, uint64_t value) Insert value, sift up, and increase *size. If already full, leave the heap and *size unchanged.
uint64_t heap_pop(uint64_t *heap, int *size) Remove and return the max (the root), decrease *size, and sift down. Assume *size > 0.
uint64_t heap_peek(uint64_t *heap) Return the max without removing it.

The heap is a max-heap over the packed timestamps, so the root is always the latest event seen so far.

Part 3 - Heapsort (25 pts)

Function Does
void heapsort(uint64_t *arr, int n) Sort arr[0..n-1] ascending, in place, using max-heap logic.

Finally, let's implement a full sort. The heapsort algorithm works in two phases:

  1. Build a max-heap out of the array. You can use the existing functions to do this.
  2. Next, swap the root (the max) with the last element. This element is now in it's final position, and the heap (not the array) is one smaller. Since we disturbed the remaining heap, we would have to sift to ensure the next root is the next largest. Repeat this step until the heap is empty.

The result is a sorted array in ascending order, because the largest values are placed at the end first.

Once these work, main.c becomes a working sorter:

$ ./app
How many events? 3
Enter 3 event(s) as: YYYY MM DD HH MM SS
2026 07 15 09 30 00
2024 01 01 00 00 00
2026 07 15 09 29 59
In chronological order:
2024-01-01 00:00:00
2026-07-15 09:29:59
2026-07-15 09:30:00

Stretch (Ungraded)

Function Does
uint64_t *heap_push_grow(uint64_t *heap, int *size, int *capacity, uint64_t value) Like heap_push, but when the heap is full, double the backing array with realloc instead of ignoring the value.

Because realloc may move the block, this returns the heap's (possibly new) base pointer and updates *capacity. Return NULL if a needed reallocation fails (the caller keeps the old heap). If you do not attempt the stretch, leave the provided stub in events.c as-is - the extra-credit test will simply score 0, and everything else still builds.

Building and testing

cd hw2/starter
make          # build the app
./app         # run the Event Log Sorter

make test     # build & run the public Criterion test suite
make clean

Trying one function at a time

Running the whole app only tells you whether the entire pipeline works. While you are still building things up, it is much easier to call a single function by hand and print what it returns. For that, create your own scratch driver named try.c in hw2/starter/ with its own main() that calls whichever events.c functions you want to exercise, then build and run it with:

make try      # compiles try.c against events.c into ./try
./try

A minimal try.c might look like:

#include <stdio.h>
#include "events.h"

int main(void) {
    uint64_t t = dt_pack(2026, 7, 15, 9, 30, 0);
    printf("packed = %llu\n", (unsigned long long) t);

    int y, mo, d, h, mi, s;
    dt_unpack(t, &y, &mo, &d, &h, &mi, &s);
    printf("unpacked = %04d-%02d-%02d %02d:%02d:%02d\n", y, mo, d, h, mi, s);
    return 0;
}

Change main() as you go to probe heap_push/heap_pop, heapsort, and so on. try.c is just for you: you do not submit it, and the grader never builds it, so make try fails harmlessly until you create the file. The make clean rule removes the try executable along with the others.

The public tests in test_events.c are a subset of what we grade with - passing them is necessary but not sufficient. Write your own tests and try edge cases: the smallest and largest valid dates, a single-element heap, popping until empty, an already-sorted array, and arrays with duplicate timestamps.

Because you are managing memory by hand, check for leaks and invalid accesses:

valgrind ./app
valgrind ./test_events

A correct solution reports no leaks and no errors.

Rules & academic integrity

  • Do not use qsort. Build the heap and the sort yourself. (<stdlib.h> is fine and needed for malloc/free/realloc; <stdint.h> is needed for uint64_t.)
  • Your code must compile with no warnings under -Wall -Wextra -Werror.
  • One free for every malloc/realloc. No leaks, no use-after-free, no double-free. This is part of your grade and is checked with valgrind.
  • Do not change events.h, main.c, or the Makefile. You submit only events.c, and it must build against the unmodified reference files.
  • You can individually test your code with try.c (see above), but the grader will not see it.
  • Generative AI policy (from the syllabus): do not use an LLM to write or fix your CS143 code, and do not paste course materials or your code into one. The work you submit must be your own. Cite any outside sources you consult (even small ones) in a code comment. If you find yourself stuck, reach out to the instructor on Ed or in person to get unstuck - do not spend more than an hour fighting a problem without asking for help.

Grading

Component Points
Part 1 - datetime codec 25
Part 2 - array-based max-heap 40
Part 3 - heapsort 25
Manual Grading 10
Total 100
Stretch - auto-growing heap Ungraded

The manual grading portion is for code style, comments, and memory safety (no leaks under valgrind). Please see the UChicago CS Style Guide for C for additional details.

Submitting

Submit events.c (the only file you change) to Gradescope under "HW2". Make sure it builds against the unmodified events.h, main.c, and Makefile, and that the stretch stub heap_push_grow is still present even if you did not attempt it. Remember the late policy from the syllabus (3 late days total for the quarter).