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 [...]
The difference between file systems and memory is not exactly clear. Some distinguishing features of file systems are: Persistance: the file data outlives the procedures which create or use the data. Sharing: multiple procedures can access the data either simultaneously or sequentially. Protection: the files become security objects, protectable entities. Naming: the file has a [...]
Software is a rare endeavor where repeated past failures is take as evidence in support of a claim for future success.
Good luck on the midterm!
The notnice programs were excellent, however, no one bothered to correctly lock theÂ task list.Â I was at first a bit unsure of whether it needed locking, but thought that it did. Consider the scenario, first you trade a PID for a pointer to a struct task_t. Your code intends to update the prio field [...]
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 [...]
Processes uses memory to store both data and program (instructions). The memory is a linear array of bytes numbered 0 through some maximum value, dependent on chip architecture. A typical maximum is 2^32-1, about 4 Gigabytes. A program is compiled and located in this memory space. Variables and jump addresses for functions and other control [...]