- Transition to Processing
- Primitive Operations
- Algorithms
- Variables
- Debugging in Processing
- Conditions
- Loops
- Functions
- Scope
- Compound Data
- Reference Semantics
- Refactoring
- Transition to Java
- Debugging in Java
- Unit Testing
- Classes - Writing your own Types
- Classes - Functions inside objects
- Recursion
- Searching
- Lists
- ArrayLists vs Recursive Data

- Logic and Proofs
- Relations
- Mathematical Functions
- Matrices
- Binary Numbers
- Trigonomtry
- Finite State Machines
- Turing Machines
- Counting - Inclusion/Exclusion
- Graph Algorithms

- Algorithm Efficiency
- Algorithm Correctness
- Trees
- Heaps, Stack, and Queues
- Maps and Hashtables
- Graphs and Graph Algorithms
- Advanced Trees and Computability

- Command line control
- Transition to C
- Pointers
- Memory Allocation
- IO
- Number representations
- Assembly Programming
- Structs and Unions
- How memory works
- Virtual Memory

- Version Control with Git
- Inheritance and Overloading
- Generics
- Exceptions
- Lambda Expressions
- Design Patterns
- Concepts of Concurrency
- Concurrency: Object Locks
- Modern Concurrency

- System Models
- Naming and Distributed File Systems
- Synchronisation and Concurrency
- Fault Tolerance and Security
- Clusters and Grids
- Virtualisation
- Data Centers
- Mobile Computing

- Transition to Scala
- Functional Programming
- Syntax Analysis
- Name Analysis
- Type Analysis
- Transformation and Compilation
- Control Abstraction
- Implementing Data Abstraction
- Language Runtimes

- Transition to Coq
- Proof by Induction, Structured Data
- Polymorphism and Higher-Order Functions
- More Basic Tactics
- Logical Reasoning in Proof Assistants
- Inductive Propositions
- Maps
- An Imperative Programming Language
- Program Equivalence
- Hoare Logic
- Small-Step Operational Semantics
- Simply-typed Lambda Calculus

- Be able to identify input/output pairs that are good for debugging.
- Be able to debug Java programs with appropriate tools.
- Be able to do paper traces of Java code.

For any given problem, we design a solution and then implement it.

As an example, let’s say that we are writing a program that gives you the number of digits in an integer. We expect the following *input-output mappings*.

Input | Output |
---|---|

1729 | 4 |

1234567890 | 10 |

0 | 0 |

-888 | 3 |

Now, it’s possible that the actual outputs you get from your code are as follows,

Input | Output |
---|---|

1729 | 4 |

1234567890 | 10 |

0 | `1` |

-888 | `4` |

We need to find out why do some inputs have incorrect outputs. So we go through our design and implementation looking for possible bugs. A logical way to do this is to trace every variable at every stage and see where does the program deviate from the expected.

Consider the following code that is supposed to return the product of all integers from 1 to `n`

(n >= 1).

The input-output mappings are -

Input | Expected Output | Actual Output |
---|---|---|

4 | 24 | 0 |

6 | 720 | 0 |

7 | 5040 | 0 |

1 | 1 | 0 |

If you trace the program, you’ll see that the loop executes when `i=1`

and `result`

becomes `result (0) * i (1) = 0`

. And every subsequent time, `result`

becomes `0 * i = 0`

. A trace for `n=4`

using *logic table* is provided below,

i | i < 4 | result |
---|---|---|

1 | true | 0*1 = 0 |

2 | true | 0*2 = 0 |

3 | true | 0*3 = 0 |

4 | false |

Thus, the first bug is `result`

should be initalized to 1 and not 0.

Our partially fixed code:

The new input-output mappings are -

Input | Expected Output | Actual Output |
---|---|---|

4 | 24 | 6 |

6 | 720 | 120 |

7 | 5040 | 720 |

1 | 1 | 1 |

A trace for `n=4`

using *logic table* is provided below,

i | i < 4 | result |
---|---|---|

1 | true | 1*1 = 1 |

2 | true | 1*2 = 2 |

3 | true | 2*3 = 6 (not the expected output) |

4 | false |

It can now be seen that the loop **should** execute for `i=4`

and multiply it into the `result`

but it doesn’t. By changing `i < n`

to `i <= n`

, we fix this problem.

To confirm, we trace once more for `i=4`

.

i | i < 4 | result |
---|---|---|

1 | true | 1*1 = 1 |

2 | true | 1*2 = 2 |

3 | true | 2*3 = 6 |

4 | true | 6*4 = 24 (expected output) |

5 | false |

Debug the following method for which the expected input-output mappings are provided in the javadoc (comment above the method).
**CRITICAL STEP!!!** Write down the actual input-output mappings after every iteration of debugging

Most of the modern Integrated Development Environments (IDEs) have a comprehensive debugging feature that let’s you trace the variables as your program executes.

In the IDE we are using (Eclipse), the debugger relies of placing `breakpoints`

that are like pitstops in car race. The program runs till the next breakpoint where you can see the values of all the variables and when you hit `resume`

, it goes to the next breakpoint.

At this point, it becomes tempting to throw away your notebook, you have everything you need in the programming environment right?

No.

Debugging is still mostly done in your head or on paper, so it is worth revisiting our programming tracing skills. What follows is a set of exercises for you to get familiar with tracing Java code. You should do all these exercises with just a pen/pencil and paper as the skill you are training is to be able to trace a program *without* the aid of a computer.

Trace the flow of the following program and determine the value of `result`

at the end of it.

`a < b`

is `true`

`b % a == 0`

is `true`

`a % 2 == 0`

is `false`

The expression becomes `true && true && false`

This is `false`

Hence, the `else`

block executes and `result`

becomes `b (10)`

.

Trace the flow of the following program and determine the value of `result`

at the end of it.

a == b` is `

false```
,
```

else` executes

`b`

decreases by 5, becomes 5
`a == b`

is `true`

.
`if`

block executes and `result`

becomes `b (5)`

.

Trace the flow of the following program and determine the value of `result`

at the end of it.

| i | i<=7 | i%2 | i%2==1 | result | | — | — | — | — | — | | 1 | true | 1 | true | -3+1 = -2 | | 2 | true | 0 | false | | | 3 | true | 1 | true | -2+3 = 1 | | 4 | true | 0 | false | | | 5 | true | 1 | true | 1+5 = 6 | | 6 | true | 0 | false | | | 7 | true | 1 | true | 6+7 = 13 | | 8 | false | | | |

Trace the flow of the following code -

At the end of the code,
`a = 5`

, `b = 10`

, `c = 2`

, `d = false`

, `result = 10`

.
Explanation -