• Randomized algorithms and randomized analysis

    October 25, 2006

    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 [...]

  • A tale of three filesystems

    October 24, 2006

    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 [...]

  • mhtml:http: error in IE7

    October 23, 2006

    Software is a rare endeavor where repeated past failures is take as evidence in support of a claim for future success.

  • Midterm

    October 9, 2006

    Good luck on the midterm!

  • Locking in notnice

    October 4, 2006

    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 [...]

  • Sorting lowerbounds and linear time sorts

    October 2, 2006

    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

    October 2, 2006

    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 [...]

  • Relocation

    October 2, 2006

    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 [...]

Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org