The theory of graphs is surprisingly rich. In CSC317 we will learn some basic graph algorithms, guided by what is practical. I would like in these notes to introduce graph theory and provide some background, which is perhaps a bit less relevant for engineering purposes, but might be of interest to some students, and might [...]
ASSERTIONS An assertion is a logical statement that should evaluate to true. Assertions can be just a mind-amge, at most a notation or comment in the coade. They have become so popular that now some languages have assert statements, which are actual code that evaluates the assertion. If the assertion evaluates false the code flow [...]
Preliminary remarks This is a simple introduction to certain complexity classes, hence a “petting zoo”. The actual complexity zoo can be found here. Algorithms are mathematically precise, step-wise procedures for solving problems. The subject of algorithms is concerned with not only how to solve a problem, but how to solve it efficiently. Efficiency often means [...]
An interval tree is a structure for organizing a set of intervals { i=[i.low,i.high] } so that the structure can be maintained dynamically, under insert of new intervals and deletion of existing intervals, and an intersection query can be answered efficiently. The intersection query is: given a query interval q = [q.low,q.high], return any interval [...]
We are discussing two important methods for storing items in a data set in order to support fast finds, inserts, and sometimes additional operations, notably, deletion. The two methods are hashing and trees. Hashing provides very fast, O(1), access to items, but it is not guarenteed. Trees provide acceptibly fast, O(log n), access, support deletion [...]
Traditional data structures and analysis approaches are determinisitic. They emphasis a deterministic model of computation and a determinisitic result of analysis. The model of computation does not play with dice. Given an input, we can know exactly what the program will do. In practice, of course, we hardly ever know this, and this is why [...]
In a certain model it is possible to prove that O(n log n) is optimal for sorting. That is, although it takes O(n log n) to sort, it is impossible to sort any faster than that. The model requires that all we can determine about the elements we wish to sort is to compare them, [...]
Quicksort is interesting because although it is a popular algorithm for sorting, worst case it is not O(n log n). Its runtime depends a lot on the type input given. The implementation of the book will take Theta(n^2) steps on sorted input. However, for a suitably “random” input, the runtime is O(n log n). The [...]
The Linux operating system keeps a tick count in a variable called jiffies. Use of this term for clock ticks seems to be strongly associated with Linux, however, I don’t know if it is a Linus original. In 32 bit Linux, jiffies overflow every 49.7 days, so comparing time values in jiffies requires care. The [...]