Monthly Archives: July 2014
Today’s lectures & main take-away messages
Heaps as Data Structures: (1) if you find yourself doing repeated minimum (or maximum) computations, consider a heap and (2) choosing the right data structure can decrease an algorithm’s running time
Intro to Greedy Algorithms: (1) Greedy algorithms are one of the major algorithm design paradigms along with divide & conquer, randomized, and dynamic programming. (2) Comparing Greedy to Divide & Conquer, greedy algorithms are generally easier to apply while you need the right insight to find how to decompose for D & C, easier to calculate Big O classification since often one aspect of the algorithm dominates, but typically non-trivial to prove correctness.
Optimal Caching as an…
View original post 117 more words
Suppose you want to find the minimum value in an array. Well, the Swift standard library has you covered:
Ok that’s cool. But suppose you have an array of strings of integers and you want the minimum numeric value.
Well, I guess you could map them to
Int and then use the same function:
Nope, compiler error.
String.toInt returns an
Int?, because maybe the string isn’t a number.
Fair enough. I happen to know with my intimate knowledge of the problem domain that we can just ignore non-numeric values. So maybe filter those out?
Nope, more compiler errors, because now we have only non-
nil values, but they’re still optionals and an
Int? doesn’t conform to
Comparable. So maybe another
map to force-unwrap the results (force unwrap is OK because the filter will guarantee no non-nil elements):1
Ok that compiles now and does return the minimum numeric…
View original post 457 more words
his implementation support Member( ), Insert( ), and Delete( ) functions. Populate the linked list with n random, but unique values. Each value should be between 0 and 2^16– 1. Then perform m random Member, Insert, and Delete operations on the link list. Let mMember, mInsert, and mDelete be the fractions of operations of each type. You may use any values within 0 and 2^16– 1 while performing these three operations.
However, to simplify the implementation, a new value inserted into the list cannot be a value already in the list (it may be a value that was initially added to the list, but later removed).
As a example I have use RIGHT-ROTATE to present the steps of the rotations. LEFT-ROTATE is also semantic.
- y = x.left // set y
- x.left = y.right // turn y’s right sub tree into x’s left sub tree
- if y.right ≠ NULL
- y.right.parent = x
- y.parent = x.parent // link x’s parent to y
- if x.parent == NULL
- T.root = y
- else if x == x.parent.left
- x.parent.left = y
- x.parent.right = y
- y.right = x // put x on y’s right
- x.parent = y
- Assume that the n items are distinct.