15-122 Misc. Advice and Comments

This is a work in progress. Unfortunately, I do not have the time to work on it.

Table of Contents

Course Material
  1. Why C0?
  2. Why do I need to write "trivial" loop invariants?
  3. Checking for Integer Overflow
  4. Amortized Analysis: How many tokens do you allocate? Is it just a guess?
Specific to C
  1. The C Transition
  2. Valgrind isn't just for leaks
  3. How do I know which header file to #include?
Doing Well
  1. Time Management
  2. Exams
Programming Tools
  1. Emacs
  2. To the Windows Users

Why C0?

Why do I need to write "trivial" loop invariants?

Checking for Integer Overflow

I want to do my best to clear up a very common misconception that I'm seeing come up over and over again. Suppose I have some expression along the lines of

int x = // Some mathematical expression that might cause positive overflow.

It is NOT universally true that I can check for overflow with

if (x < 0) println("OVERFLOWBAD!");

This was okay when we were checking for overflow when we were adding two numbers. Since overflow obeys modular arithmetic, it is the case that overflow here will always give a negative number. However, this is a special case. In other cases, the expression being evaluated can wrap back around to positive numbers.

For example, these both overflow:

Coin 0.3.1 'Nickel' (r108, Wed Aug 29 08:36:24 EDT 2012)
Type `#help' for help or `#quit' to exit.
--> 0x7fab36c1 * 3;
2130814019 (int)
--> 0x7e829512 + 0x7fabbaef + 0x7e111111;
2084528402 (int)

In general, a good way to think about overflow is to catch it before it happens, rather than trying to reason about it after the fact. For example, another way we can check for overflow when adding two positive numbers x + y is

if (x > int_max() - y) // Comes from rearranging x + y > int_max(), which we can't actually check.
  // Do something.

Notice that I was able to check for overflow without ever adding x and y. This reasoning can be generalized to apply to other situations. Here int_max() is a function defined in util.c0, returning the maximal integer. Later in C (where we have macros), we will use INT_MAX instead.

As another example, suppose the expression is k = 2 * i + j. This time, our check can be:

if (j > int_max() - 2 * i) ...

Amortized Analysis: How many tokens do you allocate? Is it just a guess?

The C Transition

Over the past few semesters, I've put together many examples that highlight important differences between C0 and C. As these files are heavily commented, they should still be useful to look through

Valgrind isn't just for leaks

How do I know which header file to #include?

Time Management



If you use emacs, here are some lines you may consider adding to your .emacs file (open with emacs ~/.emacs). Each one is pretty self-explanatory.

(column-number-mode) ;; Shows the column number in the status bar.
(show-paren-mode) ;; Highlights the matching paren.
(global-linum-mode) ;; Shows the line numbers in a column on the left.
(add-hook 'before-save-hook 'delete-trailing-whitespace) ;; Trailing whitespace is pure evil.
(setq require-final-newline t) ;; Good practice.
(setq-default indent-tabs-mode nil) ;; Don't indent with tabs.

;; If indent-tabs-mode is off, untabify before saving, just in case another program put them there.
(add-hook 'write-file-hooks (lambda () (if (not indent-tabs-mode) (untabify (point-min) (point-max)))))

;; Highlight things like tabs and long lines. Can you tell that I hate tabs?
(require 'whitespace)
(setq whitespace-style '(face lines tabs tab-mark))
(global-whitespace-mode 1)

To the Windows Users

I think that Windows is a great OS for many things. I'll be the first to admit that your CMU CS coursework is not one of them. While we make every effort to accommodate all major OSes, Windows will never be great for Unix programming. So, you may find it in your best interest to get some sort of Linux setup running. Dual booting is one option and you will find plenty on that from googling (be careful). My preference is to run Ubuntu in a virtual machine using Virtual Box. If you have any questions, I'd be happy to answer. The bottom line is to try things out and see what works best for you.