Category Archives: Programming
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.
Big data does not have a fixed definition, but it only means BIG data. I’m not trying to be funny. I meant to say it out loud: “bb-iii-ee-gg” data. The enormous amount of data could mean Terrabytes, Petabytes and nowadays I read papers about moving on to Exabytes. This will be a series of posts that set aside the technicalities (mostly) and describe my perspective on the current progress, and also what experts in the field say about the prospective outlook.
This is a hot topic nowadays among the journalists since it has found its use beyond the borders of science, but the research thrust has been there for more than two decades, dating back to the early days of scientific data analysis and visualization. There are doubts on the capabilities of this field, I met a few Data professors and experts who cast doubt on the current hype, I…
View original post 1,062 more words
menacedpromised in the last post: a description of the long path
to a well determined end.
Goal: Writing a small parser for a simple but complete language as a front-end for a for a calculator back-end. With emphasis on “complete”. A simple task one might think, a very simple one. One that could have been described in full in some book I mentioned in another post.
So in medias res, as Caesar wouldn’t have said (he spoke Greek) and of to the very beginning: The Plan. Not that I ever saw it but it is said that The Plan cometh at every beginning.
What is needed for the already briefly described…uhm…purpose, to avoid the repetition of the infamous two words, that are unbeknownst to many programmers, what does the parser need to parse? What do we need to do to enable the poor thing to do so?
View original post 1,108 more words