'CSC517' Category

  • Graph Theory

    October 28, 2014

    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

    September 7, 2014

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

  • A complexity petting zoo

    September 1, 2014

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

  • Interval tree proof

    November 1, 2011

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

  • Search

    November 3, 2006

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

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

  • Midterm

    October 9, 2006

    Good luck on the midterm!

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

  • Comparing full precision integers

    September 22, 2006

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

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