Convert String to ZigZag Bottom Up

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/zigzag-conversion/. Problem The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Example P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string...

Read More

Growth Rate - The Importance of Asymptotics

It really is true that if algorithm A is o(algorithm B) then for large problems A will take much less time than B. Definition: If (the number of operations in) algorithm A is o(algorithm B), we call A asymptotically faster than B. Example:: The following sequence of functions are ordered by growth rate, i.e., each function is little-oh of the subsequent function. log(log(n)), log(n), (log(n))2, n1/3, n1/2, n, nlog(n), n2/(log(n)), n2, n3, 2n, 4n, n! One way to compare 2 functions, is using L'Hospital rule. Here is good explanation: Growth...

Read More

Asymptotic Notation

Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course. Now we are going to be less precise and worry only about approximate answers for large inputs. The Big-Oh Notation Definition: Let f(n) and g(n) be real-valued functions of a single non-negative integer argument. We write f(n) is O(g(n)) if there is a positive real number c and a positive integer n0 such that f(n)≤cg(n) for all n≥n0. What does this mean? For large inputs (n≤n0), f is...

Read More