Introduction to Algorithms, 3rd Edition

Thomas H. Cormen

Mentioned 95

Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor.The first edition became a widely used text in universities worldwide as well as the standard reference for professionals. The second edition featured new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming. The third edition has been revised and updated throughout. It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, substantial additions to the chapter on recurrence (now called "Divide-and-Conquer"), and an appendix on matrices. It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks. Many new exercises and problems have been added for this edition. As of the third edition, this textbook is published exclusively by the MIT Press.

More on Amazon.com

Mentioned in questions and answers.

This was asked of me in an interview and this is the solution I provided:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

Is there a more efficient way to do this?

Edit: Corrected length methods.

This problem is related to the mergesort algorithm, in which two sorted sub-arrays are combined into a single sorted sub-array. The CLRS book gives an example of the algorithm and cleans up the need for checking if the end has been reached by adding a sentinel value (something that compares and "greater than any other value") to the end of each array.

I wrote this in Python, but it should translate nicely to Java too:

def func(a, b):
    class sentinel(object):
        def __lt__(*_):
            return False

    ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], []
    i, j = 0, 0

    for k in range(len(a) + len(b)):
        if ax[i] < bx[j]:
            c.append(ax[i])
            i += 1
        else:
            c.append(bx[j])
            j += 1

    return c

How is it different from asymptotic analysis? When do you use it, and why? I've read some articles that SEEM to have been written well like these:

http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

...but may be I'm dumb, so can anyone please simplify it for me?

The best reference I've found so far for understanding the amortized analysis of algorithms, is in the book Introduction to Algorithms, third edition, chapter 17: "Amortized Analysis". It's all there, explained much better than what can be found in a Stack Overflow post. You'll find the book in the library of any decent University.

Can you recommend me a book or (better!) a site with many hard problems and exercises about data structures?

I'm already answering project Euler questions, but these questions are about interesting, but uncommon algorithms. I hardly used even a simple tree. Maybe there is a site with exercises like: hey, you need to calculate this: ... . Do it using a tree. Now do it using a zipper. Upload your C (Haskell, Lisp, even Pascal or Fortress go) solution. Oh, your solution is so slow!

Self-education is very hard then you trying to learn very common, fundamental things. How can I help myself with them without attending to courses or whatever?

If you want an enlightening alternative for learning algorithms you can always try: Rabhi F., Lapalme G. Algorithms.. a functional programming approach.

The authors challenge more traditional methods of teaching algorithms by using a functional programming context, with Haskell as the implementation language. This leads to smaller, clearer and more elegant programs which enable the programmer to understand the algorithm itself more quickly and to use that understanding to explore alternative solutions. Placing the emphasis on program development rather than the mathematical properties of algorithms, the book uses a succession of practical programming examples to develop in the reader problem-solving skills which can be easily transferred to other language paradigms.to other language paradigms.

As for a site with (hard) exercises you can always try to solve, I recommend: spoj .

Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest and Stein is a good intro to algorithms and data structures. It has many exercises at the end of each chapter. most of them are simple, but there are some more difficult.

This has to be a duplicate.

I'd recommend the MIT open courseware site here. There's algorithms courses in the "Electrical Engineering and Computer Science" section some way down the page.

6.006 - Introduction to Algorithms
6.046J - Introduction to Algorithms (SMA 5503)

I recommend the latter. The materials are on the site. The videos are probably best accessed from YouTube here - search for "mit algorithms". The textbook is well respected. Third edition is just out, second edition matches the course. The first edition was also included as part of Dr Dobbs Algorithms and Data Structures CD ROM.

Niklaus Wirth has an Algorithms and Data Structures book available for download from his personal site. I have the Modula 2 print version, and while it's not a a substitute for Cormen (or aho hopcroft ullman, etc) it's a nice book to have.

http://www.youtube.com/watch?v=QMV45tHCYNI

CS 61B: Data Structures - Fall 2006

Instructor: Jonathan Shewchuk

Fundamental dynamic data structures, including linear lists, queues, trees, and other linked structures; arrays strings, and hash tables. Storage management. Elementary principles of software engineering. Abstract data types. Algorithms for sorting and searching. Introduction to the Java programming language.

Also you can read this book for Algorithms..

http://www.amazon.com/Data-Structures-Algorithms-Made-Easy/dp/1466304162

Apart from the aforementioned Cormen, Leiserson and Rivest, there is also a very new book by Peter Brass, "Advanced Data Structures". It has relatively ugly example code in C, and the author is somewhat fanatic about performance (for example, he doesn't use recursion), but the theoretical content of that book is brilliant and unique, it hardly intersects with Cormen. I expect it to become a classic.

I've always been a largely independent learner gleaning what I can from Wikipedia and various books. However, I fear that I may have biased my self-education by inadvertent omission of topics and concepts. My goal is to teach myself the equivalent of an undergraduate degree in Computer Science from a top university (doesn't matter which one).

To that end, I've purchased and started reading a few academic textbooks:

As well as a few textbooks I have left over from classes I've taken at a mediocre-at-best state university:

My questions are:

  • What topics aren't covered by this collection?
  • Are there any books that are more rigorous or thorough (or even easier to read) than a book listed here?
  • Are there any books that are a waste of my time?
  • In what order should I read the books?
  • What does an MIT or Stanford (or UCB or CMU ...) undergrad learn that I might miss?

Software engineering books are welcome, but in the context of academic study only please. I'm aware of Code Complete and the Pragmatic Programmer, but I'm looking for a more theoretical approach. Thanks!

I think you can use most of the other books for reference and just absorb Programming Pearls in its entirety. Doing so would make you better than 90% of the programmers I've ever met.

The "Gang of Four" Design Patterns book. The Design Patterns course I took in college was probably the most beneficial class I've ever taken.

First, I wouldn't worry about it. But if you'd like a book to learn some of the abstract CS ideas, I'd recommend The Turing Omnibus or Theoretical Introduction to Programming.

If I were deciding between hiring two programmers and neither had much experience, but one had a CS degree and the other didn't, I'd hire the one with the CS degree. But when you get to comparing two programmers with a dozen years of experience, the degree hardly matters.

Even i'm in the same plane: studying computer science in my free time after work; These are some of the books i have in my shelf right now

  1. Applying UML and patterns - Larman
  2. Introduction to algorithms - Cormen
  3. Discrete mathematics and its applications - Rosen
  4. Software Engineering
  5. Advanced Programming in the UNIX Environment

Will udpate this list further as soon as i finish them... :-)

File Structures: An object oriented approach with C++

A lot of good info about block devices and file structuring which you won't find in any of the books you listed. It got a few critical reviews on Amazon because people didn't like his code examples, but the point of the book is to teach the concepts, not give cut and paste code examples.

Also make sure to get a book on compilers

Biggest two omissions I see:

For operating systems I prefer the Tanenbaum instead of the Silberschatz but both are good:

And about the order, that would depend on your interests. There aren't many prerequisites, automata for compilers is the most obvious one. First read the automata book and then the dragon one.

I don't know all the books you have, but the ones I know are good enough so that may mean the others are decent as well.

You are missing some logic and discrete math books as well.

And let's not forget some database theory books!

I'd like to automatically place 100-200 bubble labels so that the following requirements are met:

  • Labels should not overlap
  • Labels should preferably not overlap bubbles
  • Label should be close to bubble
  • Preferred label position (top left, top, bottom, right etc.) should be respected to some extent
  • Font-size can vary

Are there any helpful libraries / algorithms for this? (preferably JavaScript or PHP)

(The label placement in the image does not meet these requirements)

enter image description here

This can be formulated as a Linear Programming problem. You want to maximize or minimize a function (representing the "weight" or "goodness" of the solution) subject to certain constraints (your requirements). You'll need to formalize your requirements as values. Something like this:

Variables:
x1 = 1 if Labels overlap, 0 otherwise
x2 = some measure of "how much" a label overlaps a bubble
x3 = distance from label to bubble //Label should be close to bubble
x4 = distance between ideal and actual label position
x5 = difference between actual and ideal font size


minimize x1 + 10*x2 + x3 + 20*x4 + 5*x5

subject to constraints:
    x1   = 0  // labels can never overlap
    x2   < /* maximum amount a label is allowed to overlap a bubble */
    ...
    x5   < 6 // font size does not vary by more than +/- 6 pts.

I made up the coefficients and the constraints, you can use them to tune the result based on which features are most important to you. Coefficients increase the value of a requirement (in this case, f4 is weighted most so it 'most important'. The constraints are hard limits that cannot be violated.

Since this is a well-known problem, you can now solve it using a number of methods. The Simplex algorithm is popular. There is a whole chapter in Cormen et. al about these problems.

I know there are quite a bunch of questions about big O notation, I have already checked:

to name a few.

I know by "intuition" how to calculate it for n, n^2, n! and so, however I am completely lost on how to calculate it for algorithms that are log n , n log n, n log log n and so.

What I mean is, I know that Quick Sort is n log n (on average).. but, why? Same thing for merge/comb, etc.

Could anybody explain me in a not too math-y way how do you calculate this?

The main reason is that Im about to have a big interview and I'm pretty sure they'll ask for this kind of stuff. I have researched for a few days now, and everybody seem to have either an explanation of why bubble sort is n^2 or the unreadable explanation (for me) on Wikipedia

For some algorithms, getting a tight bound for the running time through intuition is close to impossible (I don't think I'll ever be able to intuit a O(n log log n) running time, for instance, and I doubt anyone will ever expect you to). If you can get your hands on the CLRS Introduction to Algorithms text, you'll find a pretty thorough treatment of asymptotic notation which is appropriately rigorous without being completely opaque.

If the algorithm is recursive, one simple way to derive a bound is to write out a recurrence and then set out to solve it, either iteratively or using the Master Theorem or some other way. For instance, if you're not looking to be super rigorous about it, the easiest way to get QuickSort's running time is through the Master Theorem -- QuickSort entails partitioning the array into two relatively equal subarrays (it should be fairly intuitive to see that this is O(n)), and then calling QuickSort recursively on those two subarrays. Then if we let T(n) denote the running time, we have T(n) = 2T(n/2) + O(n), which by the Master Method is O(n log n).

I heard the only difference between dynamic programming and back tracking is DP allows overlapping of sub problems. (fib(n) = fib(n-1)+ fib (n-2)). Is it right ? Are there any other differences ? Also I would like know some common problems solved using these techniques.

Dynamic problems also requires "optimal substructure".

According to Wikipedia:

Dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems which are only slightly smaller and optimal substructure.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

For a detailed discussion of "optimal substructure", please read the CLRS book.

Common problems for backtracking I can think of are:

  1. Eight queen puzzle
  2. Map coloring
  3. Sodoku ?

DP problems:

  1. This website at MIT has a good collection of DP problems with nice animated explanations.
  2. A chapter from a book from a professor at Berkeley.

I am looking for a book that explains how a discrete math concept like, say, set theory, is used while doing programming. My preference is towards books that are easy to understand. For me, that means they use more English and less Mathematical notations and spend less time proving some theorems. I am quite comfortable with high-school mathematics and I have basic understanding of terms and concepts used in discrete mathematics (i.e. I know what a set is and how probability of two independent events occurring together is calculated, etc)

I can also understand languages like Haskell, Lisp, Ruby, Perl (and all C-based languages).

I really enjoyed reading Discrete Mathematics and Its Applications by Kenneth Rosenbook cover

The English is simple and easy to read, very well structured with lot of exercises.

You don't need advanced math to get it.

I think this one will be useful for you: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&s=books&qid=1305883750&sr=1-1 It's using pseudocode for explaining basic concepts of programming which you can use in any programming language you'd like.

http://www.amazon.com/Haskell-Logic-Maths-Programming-Computing/dp/0954300696/ref=sr_1_1?ie=UTF8&s=books&qid=1305773493&sr=1-1

I highly recommend this book. I haven't finished it yet, but it has so far been a thoroughly enjoyable experience for learning both advanced mathematics and Haskell. It is a course-style text with unanswered questions and exercises, but I emailed the author and he quickly replied with the answers in pdf format.

P.S. It is heavy on the mathematical notation, but I only completed Calc I (10 years ago!) and am able to work through it without too much issue.

Up until now I've mostly concentrated on how to properly design code, make it as readable as possible and as maintainable as possible. So I alway chose to learn about the higher level details of programming, such as class interactions, API design, etc.

Algorithms I never really found particularly interesting. As a result, even though I can come up with a good design for my programs, and even if I can come up with a solution to a given problem it rarely is the most efficient.

Is there a particular way of thinking about problems that helps you come up with an as efficient solution as possible, or is it simple a matter of practice and/or memorizing?

Also, what online resources can you recommend that teach you various efficient algorithms for different problems?

Introduction To Algorithms is a great book to get you thinking about efficiency of different algorithms/data structures.

The authors of the book also teach an algorithms course on MIT . You can find most lectures here

I am trying to solve a dynamic programming problem from Cormem's Introduction to Algorithms 3rd edition (pg 405) which asks the following:

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes).

Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac.

Well, I could solve it in two ways:

First solution:

The Longest Palindrome Subsequence (LPS) of a string is simply the Longest Common Subsequence of itself and its reverse. (I've build this solution after solving another related question which asks for the Longest Increasing Subsequence of a sequence). Since it's simply a LCS variant, it also takes O(n²) time and O(n²) memory.

Second solution:

The second solution is a bit more elaborated, but also follows the general LCS template. It comes from the following recurrence:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

The pseudocode for calculating the length of the lps is the following:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

It still takes O(n²) time and memory if I want to effectively construct the lps (because I 'll need all cells on the table). Analysing related problems, such as LIS, which can be solved with approaches other than LCS-like with less memory (LIS is solvable with O(n) memory), I was wondering if it's possible to solve it with O(n) memory, too.

LIS achieves this bound by linking the candidate subsequences, but with palindromes it's harder because what matters here is not the previous element in the subsequence, but the first. Does anyone know if is possible to do it, or are the previous solutions memory optimal?

Here is a very memory efficient version. But I haven't demonstrated that it is always O(n) memory. (With a preprocessing step it can better than O(n2) CPU, though O(n2) is the worst case.)

Start from the left-most position. For each position, keep track of a table of the farthest out points at which you can generate reflected subsequences of length 1, 2, 3, etc. (Meaning that a subsequence to the left of our point is reflected to the right.) For each reflected subsequence we store a pointer to the next part of the subsequence.

As we work our way right, we search from the RHS of the string to the position for any occurrences of the current element, and try to use those matches to improve the bounds we previously had. When we finish, we look at the longest mirrored subsequence and we can easily construct the best palindrome.

Let's consider this for character.

  1. We start with our best palindrome being the letter 'c', and our mirrored subsequence being reached with the pair (0, 11) which are off the ends of the string.
  2. Next consider the 'c' at position 1. Our best mirrored subsequences in the form (length, end, start) are now [(0, 11, 0), (1, 6, 1)]. (I'll leave out the linked list you need to generate to actually find the palindrome.
  3. Next consider the h at position 2. We do not improve the bounds [(0, 11, 0), (1, 6, 1)].
  4. Next consider the a at position 3. We improve the bounds to [(0, 11, 0), (1, 6, 1), (2, 5, 3)].
  5. Next consider the r at position 4. We improve the bounds to [(0, 11, 0), (1, 10, 4), (2, 5, 3)]. (This is where the linked list would be useful.

Working through the rest of the list we do not improve that set of bounds.

So we wind up with the longest mirrored list is of length 2. And we'd follow the linked list (that I didn't record in this description to find it is ac. Since the ends of that list are at positions (5, 3) we can flip the list, insert character 4, then append the list to get carac.

In general the maximum memory that it will require is to store all of the lengths of the maximal mirrored subsequences plus the memory to store the linked lists of said subsequences. Typically this will be a very small amount of memory.

At a classic memory/CPU tradeoff you can preprocess the list once in time O(n) to generate a O(n) sized hash of arrays of where specific sequence elements appear. This can let you scan for "improve mirrored subsequence with this pairing" without having to consider the whole string, which should generally be a major saving on CPU for longer strings.

Ok, so this is something that's always bothered me. The tree data structures I know of are:

  • Unbalanced binary trees
  • AVL trees
  • Red-black trees
  • 2-3 trees
  • B-trees
  • B*-trees
  • Tries
  • Heaps

How do I determine what kind of tree is the best tool for the job? Obviously heaps are canonically used to form priority queues. But the rest of them just seem to be different ways of doing the same thing. Is there any way to choose the best one for the job?

The same as any other data structure, you have to know the characteristics (complexity of search, insert, and delete operations) of each type of tree, and the requirements of the job you're selecting a tool for. The tree that has the best performance for the type of operations you'll do most often is usually the best tool for the job.

You can usually find the general characteristics for any kind of data structure on Wikipedia. Introduction to Algorithms also has at least a section (in some cases a whole chapter) on most of the data structures you've listed, so it's another good reference.

Is there any good resource (book, reference, web site, application...) which explains how to compute time complexity of an algorithm?

Because, it is hard to make the things concrete in my mind. Sometimes it is talking about an iteration has time complexity of lg n; and then according to the another loop it becomes n.lg n; and sometimes they use big omega notation to express it, sometimes big-o and etc...

These things are quite abstract to me. So, I need a resource which has good explanation and a lot of examples to make me see what's goin on.

Hopefully, I explained my problem clearly. I am quite sure that everyone who just started to study algorithms has also the same problem with me. So, maybe those experienced guys can also share their experience with us. Thanks...

The classic set of books on the subject is Knuth's Art of Computer Programming series. They're heavy on theory and formal proofs, so brush up on your calculus before you tackle them.

I think the best book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.

Here is it on Amazon.

I came across places where floors and ceilings are neglected while solving recurrences.

Example from CLRS (chapter 4, pg.83) where floor is neglected:

enter image description here

Here (pg.2, exercise 4.1–1) is an example where ceiling is ignored: (EDIT: I gather from public opinion that this is somewhat fishy.)

enter image description here

In fact in CLRS (pg.88) its mentioned that:

"Floors and ceilings USUALLY do not matter when solving recurrences"

My questions:

  1. Here does "usually" means ALL cases ? If yes, i can just forget them all the time.
  2. If not, then when do floors and ceilings really count while solving recurrences ?

Note: This ain't a homework problem. I thought about it while I was refreshing my DS and algo concepts.

The floor and ceiling functions satisfy the following inequalities for all x:

  • x−1 < ⌊x⌋ ≤ x

  • x < ⌈x⌉ < x+1

Thus, in the first example, we have ⌊n / 2⌋ ≤ n / 2. Also, since the logarithm is a monotone increasing function, we know that lg ⌊n / 2⌋ ≤ lg(n / 2). Putting these together, we get the first inequality 2(cn / 2⌋ lg ⌊n / 2⌋) ≤ cn lg(n / 2) + n.

The second example actually contains an error: c lg ⌈n / 2⌉ + 1 is never less than but can be equal to c lg(n / 2) + 1. However, it is true that c lg ⌈n / 2⌉ + 1 ≤ c lg(n / 2 + 1) + 1, which we can then bound from above by, say, c lg(n / 2) + 2 (assuming that n ≥ 2) and thus derive the desired conclusion that T(n) ∈ O(lg n).

In fact, the second example contains other errors too: even with the assumptions stated in the following paragraph (which you did not quote), the last = sign should be ≤.

(Ps. Phew, this was a real pain to type without LaTeX. That, if nothing else, is why questions like these are better asked on math.SE.)

In Introduction to Algorithms(CLRS), Cormen et al. talk about solving the Rod-cutting problem as follows(page 369)

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] and s[0....n] be new arrays
    r[0] = 0

    for j = 1 to n:
        q = -infinity   

        for i = 1 to j:
            if q < p[i] + r[j - i]:  // (6)
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q

    return r and s

Here p[i] is the price of cutting the rod at length i, r[i] is the revenue of cutting the rod at length i and s[i], gives us the optimal size for the first piece to cut off.

My question is about the outer loop that iterates j from 1 to n and the inner loop i that goes from 1 to n as well.

On line 6 we are comparing q (the maximum revenue gained so far) with r[j - i], the maximum revenue gained during the previous cut.

When j = 1 and i = 1, it seems to be fine, but the very next iteration of the inner loop where j = 1 and i = 2, won't r[j - i] be r[1 - 2] = r[-1]?

I am not sure if the negative index makes sense here. Is that a typo in CLRS or I am missing something here?

I case some of you don't know what the rod-cutting problem is, here's an example.

Here's the key: for i = 1 to j

i will begin at 1 and increase in value up to but not exceeding the value of j.

i will never be greater than j, thus j-i will never be less than zero.

Yes, this will be a home work (I am self-learning not for university) question but I am not asking for solution. Instead, I am hoping to clarify the question itself.

In CLRS 3rd edition, page 593, excise 22.1-5,

The square of a directed graph G = (V, E) is the graph G^2 = (V, E^2) such that (u,v) ∈ E^2 if and only if G contains a path with at most two edges between u and v. Describe efficient algorithms for comput- ing G2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.

However, in CLRS 2nd edition (I can't find the book link any more), page 530, the same excise but with slightly different description:

The square of a directed graph G = (V, E) is the graph G^2 = (V, E^2) such that (u,w) ∈ E^2 if and only if for some v ∈ V, both (u,v) ∈ E and (v,w) ∈ E. That is, G^2 contains an edge between u and w whenever G contains a path with exactly two edges between u and w. Describe efficient algorithms for comput- ing G^2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.

For the old excise with "exactly two edges", I can understand and can solve it. for example, for adjacency-list, I just do v->neighbour->neighbour.neighbour, then add (v, neighbour.neighbour) to the new E^2.

But for the new excise with "at most two edges", I am confused.

What does "if and only if G contains a path with at most two edges between u and v" mean?

Since one edge can meet the condition "at most two edges", if u and v has only one path which contains only one edge, should I add (u, v) to E^2?

What if u and v has a path with 2 edges, but also has another path with 3 edges, can I add (u, v) to E^2?

Yes, that's exactly what it means. E^2 should contain (u,v) iff E contains (u,v) or there is w in V, such that E contains both (u,w) and (w,v).

In other words, E^2 according to the new definition is the union of E and E^2 according to the old definition.

Regarding to your last question: it doesn't matter what other paths between u and v exist (if they do). So, if there are two paths between u and v, one with 2 edges and one with 3 edges, then (u,v) should be in E^2 (according to both definitions).

I got a list of string data. 10,20,30 are the line numbers

10. string 1
20. string 2
30. string 3

and if user types in "23 string data". 23 is the line number user wants to insert into. The data should become like that

10. string 1
20. string 2
23. string data
30. string 3

and if user types in "40 string data". The data should become like that

10. string 1
20. string 2
23. string data
30. string 3
40. string data

I'm relatively new in C's data structure. Which data structure should I use to store this kind of data efficiently? My current direction is to implement dynamic array or linked list. However, below are the list of problems I experienced.

Problem with dynamic array:

  1. Using the line number as the index and create sufficient space to ensure array length is always more or equal to the highest line number. Waste a lot of memory for un-used index.
  2. Printing out the data would be an issue. Eg. index 0-9 doesn't have memory allocated. Accessing it will cause an error. Need to find ways to know which index are used?

Problem with linked list:

  1. I cannot jump index(not sure). How do identify which line comes after another and insert line in between easily?

The best solution for this task is to use dictionary data type. Of course, depending on nature of keys (number of lines) you can perform optimization via appropriate hash table.

Of course, c library don't have implementation of dictionary. But you can create your own, based on red black tree. Cormen explained such data structure easily https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

Note: if your collection has small size or you will rarely modify structure, then you can just use linked list.

I had an interview question a while back that I never got a solution for. Apparently there is a "very efficient" algorithm to solve it.

The question: Given an array of random positive and negative numbers, find the continuous subset that has the greatest sum.

Example:

[1, -7, 4, 5, -1, 5]

The best subset here is {4, 5, -1, 5}

I can think of no solution but the brute-force method. What is the efficient method?

You can answer this question from CLRS, which includes a tip:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem.

Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far.

Knowing a maximum sub array of A[1..j], extend the answer to find a maximum subarray ending at index j+1 by using the following observation:

a maximum sub array of A[1..j+1] is either a maximum sub array of A[1..j] or a sub array A[i..j+1], for some 1 <= i <= j + 1.

Determine a maximum sub array of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j.

max-sum = A[1]
current-sum = A[1]
left = right = 1
current-left = current-right = 1
for j = 2 to n
    if A[j] > current-sum + A[j]
        current-sum = A[j]
        current-left = current-right = j
    else
        current-sum += A[j]
        current-right = j
    if current-sum > max-sum
        max-sum = current-sum
        left = current-left
        right = current-right
return (max-sum, left, right)

I'm interested in teaching myself different data structures, something I currently know very little about. My plan is to implement a few key structures so I understand how they work. I'm looking for suggestions on important data structures to start with.

I'm primarily interested in data structures that are relevant to search applications (e.g. Google / Lucene) and the general trade-off between delayed computation and precomputation. I'm also interested in distributed data structures -- data structures that can scale across hundreds / thousands of servers -- and probabilistic data structures -- data structures that help finding an approximate answer but do not need to always be correct.

Wikipedia has a list of data structures. I am currently considering:

  • Hash table
  • B+-Tree
  • R-Tree
  • KD-Tree
  • Radix-Tree
  • Bloom filter

Are there better choices?

Finally, is there any (major) problem with implementing these structures in a language like F#?

Very ambitious. I voted your question up just for its scope.

MIT has an on-line algorithms and data structures course. The companion book is a classic. I'm not sure if it addresses the distributed and probabilistic features, but they'll give you an excellent grounding in the fundamentals.

I'd add red-black tree, hash tables, patricia trie, and skip lists to your agenda.

Good luck.

My boss just told me that he learned about fast VB6 algorithms from a book and that the shortest way to write things is not necessarily the fastest (e.g. builtin methods are sometimes way slower than selfwritten ones because they do all kinds of checking or unicode conversions which might not be necessary in your case).

Now I wonder, is there a website with info on fast different constructs are in various languages, esp. Java/C#/Python/… (also C++ but there are so many compilers which probably differ a lot).

E.g. is there a difference between

if (a()) b();

and

a() && b();

Another example: is a = a * 4 maybe compiled to the same code as a <<= 2?

I could test this myself, of course, writing both then running them 100000 times and comparing the runtime, but I'd also like to learn about new ways to write things, maybe even things that I hadn't considered before. Thanks for your answers!

I would say these are likely to be the kind of micro-optimizations that wouldn't make a difference and aren't worth the effort.

Algorithm choice does matter, but the books you should be reading should be more like this or this.

If you really want to see whether the bit hacks you've cited make a difference, I'd recommend getting a performance baseline on the code you want to change first. Make your changes and remeasure performance the same way. If you get a result that says it's worth it, by all means continue.

You're better off profiling your code and finding out where the slowest part of your code lives and where the most work is being done. Guessing rarely works when optimizing.

In Introduction to Algorithms p169 it talks about using tail recursion for Quicksort.

The original Quicksort algorithm earlier in the chapter is (in pseudo-code)

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

The optimized version using tail recursion is as follows

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Where Partition sorts the array according to a pivot.

The difference is that the second algorithm only calls Quicksort once to sort the LHS.

Can someone explain to me why the 1st algorithm could cause a stack overflow, whereas the second wouldn't? Or am I misunderstanding the book.

I read a lot of blogs and forum posts about mathematics in programming and made a conclusion for myself that basic mathematics is needed in programming. I'm not a good mathematician. But is it somehow possible to improve my logical and algorithmic thinking without going deep into science of mathematics? Are there any exercises or some books that could help me to improve these skills so that I could become an good architect?

Thank you in advance.

Work through Project Euler.

The beginning of CLRS Algorithms has a bit on number theory, discrete math, combinatorics, probability, graph theory, and other really useful stuff. It's teaching exactly what is applicable to algorithms, and skipping everything else.

The emphasis on what constitutes "Discrete Mathematics" in Computer Science undergraduate curriculums has shifted in the past forty years. It used to be that such courses would cover material such as abstract algebra and go into concepts such as 'sorts' and 'kinds', which is useful for algebraic specification of programs. If that is the sort of math you think you will enjoy, then buy an old book on Discrete Maths, like this one: Discrete Mathematics in Computer Science (1977) $5 shipped!

I don't believe the ridiculously expensive Susanna Epps book contains similar material, and should know, since that hideously overpriced book is what I had to use in my freshman Discrete Maths class (2003) -- I can't believe the price has almost doubled since its outrageous price even then!

I'd say that the math you need depends on the problems you're asked to solve.

The problems you're asked to solve depend on the math skills you have.

Anyone who says you only need 4th grade math is also telling you that you cannot reasonably expect to have a chance to solve more challenging problems.

I would point out that computers have changed mathematics and applications. My engineering education consisted of a lot of calculus and closed-form solutions using pencil and paper.

My first career meant applying discrete, numerical analogs to those techniques on computers.

If you want to do that kind of work, it's best to learn a lot about numerical methods and linear algebra.

Google's Page Rank was a $25B eigenvalue problem when this paper was published. Google's market cap is $144B today.

Computer graphics are very mathematically intensive. If you like graphics, better learn matricies well.

Statistics are terribly important, especially when you have oceans of data available to you on the web. Learn R and basic statistics cold.

Read something like "Programming Collective Intelligence" to see what kinds of novel problems will require some sophisticated math.

If you want to solve those kinds of problems, best to get busy.

I was wondering if we can somehow modify the Quick sort algorithm to produce the worst case time complexity of O(n logn). Although this can be done by permuting data and then assuming that we will get the average case complexity rather than worst case. But this is not a full proof solution as we can again land into worst case after permuting. Is there any other way around that you can suggest.

Well, Yes we can bring it down to O(nlogn). All the algorithms I have seen that try to bring this down are based on choosing your pivot point. If you can "intelligently" choose your pivot point it can be brought down.

Options 1. Intro Sort . It is no longer a "pure" quick sort now. It uses merge sort later on. 2. Choosing the median as a pivot. Now finding the median might take a huge amount of time if done in the normal way BUT there is a mention in the Introduction to Algorithms.

Here is something straight from the horse's mouth Introduction to Algorithms

  1. Divide the array into [n/5] groups with each group having 5 elements
  2. Find median of each group using insertion sort and then pick the median from this list
  3. Then you will need to recursively try and find the median of [n/5] medians calculated from each group.
  4. Partition the array around this median

There are some more complex stuff in this algorithm that I have hidden. You can go through it in the same book if you want. Usually, I don't try to use this algorithm. I use a randomized selection operation to find the pivot and work on with that.

Possible Duplicate:
Plain English explanation of Big O

I can't find any sufficient help for learn or understand about O-notation, and how learn about time or space complexity. So please suggest me , where can I start this. Its really need to me, for now these time.So please give me solution quick. Thanks a lot in advance.

Algorithms

Introduction to Algorithms

Also http://en.wikipedia.org/wiki/Big_O_notation

Also, there are some great lectures out there on youtube and itunesU

"Concrete Mathematics: A Foundation for Computer Science (2nd Edition)" would be another book recommendation I'd toss out there. Big O isn't that difficult but it can take a while to get the hang of what it is trying to convey.

I am trying to grasp the explanation of the closest pair point problem in various literatures. While the basic approach is the same in all of them, divide-solve-combine (divide and conquer), and get linear time merge (combine/conquer), the actual implementation is subtly different among the articles and books.

The linear-time-merge is key here which tries to limit the number of points to be compared.

The way the points are being considered in the Kleinberg book is a bit different the way points are considered in this Wikipedia article or Cormen book.

Anyway, for the later two, we find nice explanations for the number of points to be considered here, and here, including many others.

For the problem in hand, please take a look at these slides (slide 32) for the Kleinberg book. The claim of 11 point gap is in the same slide. A more detailed explanation can be found here in page 6, section 6.2.5.6.

However, in the same page of the above mentioned slides (slide 32), we find a claim something like, "Still true if we replace 12 with 7."

I have failed to find an explanation of the above claim.

Please see the figure below,

enter image description here

If we consider the red point to be compared with those in the right half, the points in the right half should be in the shaded half circle. I have tried to put the extreme ones in blue. Still they are |5-(-2)|+1 = 8 and |5-15|+1 = 11 apart.

What is it I might be missing here?

I am using std::thread and gcc as my compiler in implementing the parallel-merge as described in Cormen's Introduction to Algorithms.

I think I got the code to work. It passes all randomly seeded arrays that are not too big. However, when I try to merge two arrays that are large (1e6 elements each), I get the following termination:

terminate called without an active exception
terminate called recursively
terminate called recursively

Using gdb doesn't help: it becomes corrupted during the run.

I am pretty certain that the run has failed due to too many threads spawned.

What can I do to confirm that this error is due to too many std::threads spawned?

NOTES

  1. Code works up to n=1e4, fails by n=1e5
  2. #define DEBUG if you want to see output, but I don't recommend this except for small n like 10 or 50.
  3. STRBUF_SIZE/use of fprintf is ugly, but iostream doesn't flush well in threads - this is hacky, but works (no need to focus here).
  4. I tried following Barnes53's suggestion by using a try/catch block around the threads, but this didn't work, apparently.
  5. I know that spawning a gazillion threads is a bad thing - at this point, I am just trying to implement what's in the book and to see if it works, and perhaps discover what its limitations are.

UPDATE

  1. GManNickG's answer below helped: not every run, but during some runs of 1e5, I can see that, indeed, resources are gone.
  2. I will probably look into some kind of k-way parallel sort, where I can control the number of threads spawned, if this algorithm is not salvageable.

CODE

#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <thread>
#include <cmath>
#include <cstring>
#include <cassert>

#define STRBUF_SIZE 1024

class Random
{
public:
    Random( unsigned int seed=::time(nullptr))
        : m_seed( seed )
    { }
    // between [ 0 .. n-1 ]
    unsigned int rand_uint( unsigned int n )
    {
        return static_cast<unsigned int>
                     (static_cast<float>(n) * rand_r( &m_seed ) / RAND_MAX);
    }
    unsigned int getSeed() const { return m_seed; }
private:
    unsigned int m_seed;
};

template<typename T>
char* dump( char* line, T it1, T it2 )
{
    char buf[80];
    line[0] = '\0';
    for( T it=it1; it!=it2; ++it )
    {
        sprintf( buf, "%u ", *it );
        strcat(  line, buf );
    }
    return line;
}

template< typename T, class It >
It binary_search_it( It beg, It end, const T& value )
{
    auto low  = beg;
    auto high = std::max( beg, end );   // end+1
    while( low < high )
    {
        auto mid = low + std::distance( low, high ) / 2;
        if ( value <= *mid )
            high = mid;
        else
            low = mid + 1;
    }
    return high;
}

template< class InputIt, class OutputIt >
void p_merge( 
    char const*  msg, 
    unsigned     depth,
    unsigned     parent_lvl_id,
    unsigned     lr,
    InputIt  p1, InputIt  r1, 
    InputIt  p2, InputIt  r2, 
    OutputIt p3, OutputIt r3
    )
{
#ifdef DEBUG
    char buff[STRBUF_SIZE];
#endif
    unsigned sum_prev  = pow( 2, depth ) - 1;
    unsigned lvl_id    = 2*parent_lvl_id + lr;
    unsigned thread_no = sum_prev + lvl_id + 1;

    unsigned limit0    = sum_prev + 1;
    unsigned limit1    = pow( 2, depth+1 ) - 1;

#ifdef DEBUG
    char msg_dep[256];
    sprintf( msg_dep, "%s [%2d] %-10d [%d,%d]", msg, depth, thread_no, limit0, limit1 );
    fprintf( stderr, "%s\n", msg_dep );
#endif

    if ( thread_no<limit0 || thread_no>limit1 )
    {
        fprintf( stderr, "OUT OF BOUNDS\n" );
        exit( 1 );
    }

    auto n1 = std::distance( p1, r1 );
    auto n2 = std::distance( p2, r2 );
#ifdef DEBUG
    fprintf( stderr, "%s dist[v1]=%2ld   : %s\n", msg_dep, n1, dump( buff, p1, r1 ) );
    fprintf( stderr, "%s dist[v2]=%2ld   : %s\n", msg_dep, n2, dump( buff, p2, r2 ) );
#endif
    if ( n1<n2 )
    {
        std::swap( p1, p2 );
        std::swap( r1, r2 );
        std::swap( n1, n2 );
#ifdef DEBUG
      fprintf( stderr, "%s swapped[v1]   : %s\n", msg_dep, dump( buff, p1, r1 ));
      fprintf( stderr, "%s swapped[v2]   : %s\n", msg_dep, dump( buff, p2, r2 ));
#endif
    }
    if ( n1==0 )
    {
#ifdef DEBUG
      fprintf( stderr, "%s done              \n", msg_dep );
#endif
        return;
    }
    auto q1 = p1 + n1 / 2;   // midpoint
    auto q2 = binary_search_it( p2, r2, *q1 );  // <q1   q2[q1]   >=q1
    auto q3 = p3 + std::distance( p1, q1 ) + std::distance( p2, q2 );
    *q3 = *q1;

#ifdef DEBUG
    fprintf( stderr, "%s q1[median]=%u  : %s\n", msg_dep, *q1, dump( buff, p1, r1 ));
    fprintf( stderr, "%s q2[fulcrum]=%u : %s\n", msg_dep, *q2, dump( buff, p2, r2 ));
    fprintf( stderr, "%s q3(copied)=%u  : %s\n", msg_dep, *q3, dump( buff, p3, r3 ));
#endif

#ifdef DEBUG
    auto d1 = std::distance( p1,   q1-1 );
    auto d2 = std::distance( q1+1, r1   );
    fprintf( stderr, "%s q1[dist_L]=%ld  : %s\n", msg_dep, d1, dump( buff, p1, r1 ));
    fprintf( stderr, "%s q1[dist_M]=%ld  : %s\n", msg_dep, d2, dump( buff, p1, r1 ));
#endif


    try {
        std::thread t1{ 
            [&](){ p_merge( "LESS", depth+1, lvl_id, 0, p1, q1,   p2, q2,   p3, r3 ); } 
        };
        std::thread t2{ 
            [&](){ p_merge( "MORE", depth+1, lvl_id, 1, q1+1, r1, q2, r2, q3+1, r3 ); } 
        };
        t1.join();
        t2.join();
    }
    catch( ... )
    {
        fprintf( stderr, "OK - I am dying during a std::thread spawn\n" );
        exit( 1 );
    }

#ifdef DEBUG
    fprintf( stderr, "%s synchronized\n", msg_dep );
#endif
}

int
main( int argv, char* argc[] )
{
    // ok up to 1e4, fails by 1e5
    unsigned n = 1e5; 
    Random   r;
    std::vector<unsigned> v1( n ), v2( n ), v3( 2 * n );

#ifdef DEBUG
    fprintf( stderr, "SEED = %u\n", r.getSeed() );
#endif

    std::generate( v1.begin(), v1.end(), [&]() { return r.rand_uint(n); } );
    std::generate( v2.begin(), v2.end(), [&]() { return r.rand_uint(n); } );

#ifdef DEBUG
    char buff[STRBUF_SIZE];
    fprintf( stderr, "%s\n", dump( buff, v1.begin(), v1.end() ));
    fprintf( stderr, "%s\n", dump( buff, v2.begin(), v2.end() ));
#endif

    std::sort( v1.begin(), v1.end() );
    std::sort( v2.begin(), v2.end() );

    p_merge( "TOP ", 0, 0, 0,
        v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(), v3.end() );

    assert( std::is_sorted( v3.begin(), v3.end() ));

#ifdef DEBUG
    fprintf( stderr, "FINAL : %s\n", dump( buff, v3.begin(), v3.end() ));
#endif
}

You can catch std::system_error and check if the code is resource_unavailable_try_again:

#include <atomic>
#include <iostream>
#include <system_error>
#include <thread>
#include <vector>

class thread_collection
{
public:
    thread_collection() :
    mStop(false)
    {}

    ~thread_collection()
    {
        clear();
    }

    template <typename Func, typename... Args>
    bool add(Func&& func, Args&&... args)
    {
        try
        {
            mThreads.emplace_back(std::forward<Func>(func),
                                  std::cref(mStop),
                                  std::forward<Args>(args)...);
        }
        catch (const std::system_error& e)
        {
            if (e.code().value() == std::errc::resource_unavailable_try_again)
                return false; // not possible to make more threads right now
            else
                throw; // something else
        }

        return true; // can keep going
    }

    void clear()
    {
        mStop = true;
        for (auto& thread : mThreads)
        {
            if (thread.joinable())
                thread.join();
        }

        mThreads.clear();
        mStop = true;
    }

    std::size_t size() const
    {
        return mThreads.size();
    }

private:
    thread_collection(const thread_collection&);
    thread_collection& operator=(const thread_collection&);

    std::atomic<bool> mStop;
    std::vector<std::thread> mThreads;
};

void worker(const std::atomic<bool>& stop)
{
    while (!stop)
        std::this_thread::yield();
}

int main()
{
    thread_collection threads;

    try
    {
        while (threads.add(worker))
            continue;

        std::cout << "Exhausted thread resources!" << std::endl;
    }
    catch (const std::exception& e)
    {
        std::cout << "Stopped for some other reason: " << e.what() << std::endl;
    }

    std::cout << "Made: " << threads.size() << " threads." << std::endl;
    threads.clear();
}

(Run this at your own risk!)

According §30.3.1.2/4, this is the error code used to indicate thread creation failure:

Error conditions:
resource_unavailable_try_again — the system lacked the necessary resources to create another thread, or the system-imposed limit on the number of threads in a process would be exceeded.

Note this could be thrown by your own arguments being copied to the resulting thread. To guarantee against this, you need to pre-construct your arguments, then no-throw move them to your thread function.

That said, you're much better off putting a limit on thread creation anyway. There's no point in having more threads running than cores can execute. Use std::thread::hardware_concurrency to get that number.

I have a very simple question regarding BSTs. I have seen multiple definitions of BSTs regarding duplicate entries. Some define BSTs as not allowing duplicate entries, others that node's left child is <= to the nodes value and the right child is greater than the node's value, and some definitions are the opposite of that ( left child is < than the node, right child is >=).

So my question is what is the official definition (if one exists) for BSTs regarding duplicate entries? For example what would a BST look like after inserting the values : 3, 5, 10, 8, 5, 10?

Thank you in advance for clarifying the definition and answering my question!

One of the well-known books in the algorithm and data structure area is the CLRS book, also known as the bible of data structures and algorithms:

enter image description here

According to the definition of this book, the duplicate entries are placed in the right tree of the node that contains the same key. As an example, take a look at the insertion algorithm of BSTs adopted from this book:

enter image description here

I have been working on RTOS and Linux driver development for quite some time. Now I am interviewing at semiconductor companies and failing to answer questions about algorithms on strings, and time and space complexity. I have not studied discrete maths and algorithms during my as I have an electronics background.

How can I overcome this gap?

Start with something simple like: Algorithms in a Nutshell (good starting point for interview like questions)

alt text

Or Algorithms For Interviews When you feel you know the above book, then you can think of diving into introduction to Algorithms.

Introduction to Algorithms is a great algorithms book (and also happens to be listed 6th on the great influential book question)

It is easy to implement linked list in c++ where you have pointers. But how are they implemented in other languages (like java,python,etc). I don't want to use built-in class(which are supported in JAVA) for linked-list but what i want is how to replace pointers to create linked-list?

You may find a good answer in this book - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - I'll summarize what I recall for you.

Basically you'll have two arrays of equal size (hopefully larger than n where n=number of elements you want to store). We'll call them Array A and Array B.

Array A[i] holds the data value. Array B[i] holds the 'next' value 'k' such that A[i]->next = A[k].

Hopefully this helps.

I've been trying to read and understand the contents of this book: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844

But I'm finding the contents to be challenging purely because I don't understand the mathematical or pseudo code notation. Are there any resources or books I should read / study in order to help me understand the content? I think I'm looking for the missing mathematical link in my life. I need something to bridge the gap between school and college level.

Thanks Chris

Be sure to read the first sections and the appendix at the end of the book, which has some mathematical background explained.

A good, not easy, but suitable for high school student, introduction to mathematics used in computer science is Concrete Mathematics, by Knuth, Graham & Patashnik.

I would like to know which lines of my code are using most of the time of execution. I am doing a planner algorithm, and to solve a specific problem I made, the computer needs 5 minutes to find the solution.

I am using a lot of recursion methods, I would like to know where is the most time wasted, so I can look into that lines and try to fix or refactor the code to see if it helps.

I know that there are Cyclomatic Complexity Methods. But I don't know how to use it on Eclipse. I am using Helios. Tried to install metrics2 and it just pops up errors on my Eclipse.

EDITED: SMALLER NEW QUESTION:

http://s7.postimg.org/frd8yjql5/diag.png What does this means? Look at the Heap Size.. Always up and down.. does this affects CPU Speed? Thanks!

First start with an abstract analysis, only then go into detail and measure.

Abstract analysis

For the analysis, I would look at the complexity of your algorithm in the big O notation. That is the abstract analysis of runtime (whereas metrics like Cyclomatic Complexity look at code quality).

For algorithm analysis, I find Cormen's book "Introduction to algorithms" very good.

When you have an understanding of the complexity of your algorithm, you are able to check whether alternative algorithms would be better or where to do algorithmic improvements.

Measurement

Avoid premature optimization: Only when you are sure you have a good algorithm, you should go into detail and measure.

To check whether your theoretical analysis was correct and to look at the technical implementation (mainly to search for hotspots and optimize those), you can use macro benchmarking tools and profilers like JVisualVM.

Just wondering if in a question there is talk about the Running time of an algorithm, does it mean the same as Time Complexity or is there any difference between the two?

From CLRS 2.2 pg. 25

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. It is convenient to define the notion of step so that it is as machine-independent as possible.

Now from Wikipedia

... time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform.

Notice that both descriptions emphasize the relationship of the size of the input to the number of primitive/elementary operations.

I believe this makes it clear both refer to the same concept.

In practice though you'll find that enterprisey jargon rarely matches academic terminology, e.g., tons of people work doing code optimization but rarely solve optimization problems.

I am new to this community and have already got a lot of -1 votes so I am trying my best to improve the way I can ask a question.

Recently I tried this problem at CodeChef. This is the Problem Definition.

This is probably the easiest task of this problem set. To help you understand the task let us define two key functions: f(n,k), (with k <= n) which gives the number of ways we can draw a sample of k objects from a set of n-distinct objects where order of drawing is not important and we do not allow repetition. G(x1, x2, x3, ... , xn) is the largest integer that perfectly divides all of {x1, x2, x3, ... , xn}. Given an integer N, your task is to compute the value of Y where Y = G( f(2*N,1), f(2*N,3), f(2*N,5), ... , f(2*N,2*N-1)).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first and the only line of each test case contains a single integer denoting the given N as described in the problem statement.

Output

For each test case, output a single line containing the value of Y. Constraints

1 ≤ T ≤ 10000 2 ≤ N ≤ 1011

Example

Input:

3

6

5

4

Output:

4

2

8

Now I wrote a code in Java which works perfectly fine but the CodeChef online judge give TLE error, so I tried it a couple of different ways but with no success. So I checked some solution which others had posted and I Didnt have a clue what their algorithm did but magically it always came to the right answer So what my concern is that what books should I refer to improve the way these algorithms are written . P.S. Yes I have read Corman

Some other solution did some normal addition and subtraction and Bang!! their answer were correct This was one such solution

   import java.util.*;
    class Main 
 {
     public static void main(String[] args) {

//public static void main(String[] args) {
    Scanner scan=new Scanner(System.in);
    long T=scan.nextLong();
    long fin;
    while(T>0){
        T--;
        long N=scan.nextLong();
        fin=-(-N^N);
        System.out.println(fin);
}
}
 }

I am also showing what I had attempted :-

           import java.io.BufferedReader;
         import java.io.IOException;
         import java.io.InputStreamReader;
          import java.util.ArrayList;


       class Code1 
       {
static ArrayList<Long> combValues=new ArrayList<Long>();
static ArrayList<Long> input=new ArrayList<Long>();
static ArrayList<Long> output=new ArrayList<Long>();
public static void main(String args[])throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    //System.out.println("Enter the values of 'T' ");
    //System.out.println("Input:");
    int T=Integer.parseInt(br.readLine());
    //System.out.println("Enter the value of 'N' ");
    for(int i=1;i<=T;i++)
    {
        input.add(Long.parseLong(br.readLine()));
    }
    for(int i=0;i<T;i++)
    {
        output.add(computeFX(input.get(i)));
    }
    //System.out.println("Output:");
    for(long i:output)
    {
        System.out.println(i);
    }
}
public static long computeFX(long N)
{
    combValues=new ArrayList<Long>();
    for(int i=1;i<=2*N-1;i+=2)
    {
        combValues.add( factorial(2*N)/(factorial(2*N-i)*factorial(i)));
    }
    return computeGX();
}
public static long computeGX()
{
    boolean flag=false;
    long tempY=0;
    long limit=combValues.get(0);
    outer:for(int i=new Long(limit).intValue();i>=1;i--)
    {
        inner:for(int j=0;j<(combValues.size()/2)+1;j++)
        {
            if(combValues.get(j)%i!=0)
            {   
                flag=false;
                break inner;
            }
            else
            {
                flag=true;
            }
        }
        if(flag)
        {
            tempY=i;
            break outer;
        }
    }
    return tempY;
}
public static long factorial(long n)
{
    long fact=1L;
    for(int i=1;i<=n;i++)
    {
        fact*=i;
    }
    return fact;
}

   }

Okay this question may be subjective but I would really like some suggestion as to where to start from.

You will find the magic in the given solution when you try solving a simple solution on a piece of paper.

Try 6 as input. You want to find G(f(12,1), f(12,3), f(12,5), ... , f(12,11)). Calculate fs, you will get: 12, 220, 792,... then convert them to binary.

The result SHOULD divide all these values, so it can't be greater than the smallest one (in this case 12). So in the binary representations, only look at the four right-most bits (since 12 has only 4 bits). In this e.g. all values greater other than twelve have "1000" as their four right-most bits in binary representation.

So basically you need to find GCD of 12 and 8 ("1000" in binary)! ta da! Now you have a much simpler question which the title of the problem referes to (The Easiest Problem). The rest could be done in multiple ways as the solutions on Code Chef shows.

About your question on how to improve your algorithms skills, beside books like Introduction to Algorithms, you need to solve a lot of problems like this one. A good place to start is Project Euler. Another book you can grasp a lot of knowledge about algorithms is a book called: The Algorithm Design Manual by Steven Skiena.

I'd like to know if there's some faster way to sort such array than quicksort/mergesort.

Maximum array's length is 10^6. Word's length is >=10 and <= 100 and the word can contain a-z and spaces (27 different characters in total). Characters are not unique in the words (they can repeat). All the words in an array are equally long.

The ascii values can be computed so essentially this is an integer sort. Comparison based sorting routines will at best get you O(n lg n) - Merge Sort (with additional space needed for creating two more arrays of size n/2) or O(n^2) at worst (insertion sort, quicksort, but they have no additional space complexity). These are asymptotically slower than a linear sorting algorithm. I recommend looking at CLRS (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844). The chapter on sorting in linear time. O(n) is probably the best you can do in this scenario. Also, this post might help. Sorting in linear time?

I'd check out radix sort. http://en.wikipedia.org/wiki/Radix_sort

I don't understand: why is my insertion sort implementation beating merge sort every time, for any size of n?

    public List<Int32> InsertionSort(List<Int32> elements, Boolean ascending = true)
    {
        for (Int32 j = 1; j < elements.Count; j++)
        {
            Int32 key = elements[j];
            Int32 i = j - 1;

            while (i >= 0 && (elements[i].CompareTo(key) > 0) == ascending)
                elements[i + 1] = elements[i--];

            elements[i + 1] = key;
        }

        return elements;
    }

    public List<Int32> MergeSort(List<Int32> elements, Boolean ascending = true)
    {
        Sort(elements, 0, elements.Count - 1);

        return elements;
    }

    private void MergeSort(List<Int32> elements, Int32 startIndex, Int32 count)
    {
        if(startIndex < count)
        {
            Int32 half = (startIndex + count).Divide(2, RoundMethod.Floor);
            Sort(elements, startIndex, half);
            Sort(elements, half + 1, count);
            Merge(elements, startIndex, half, count);
        }
    }

    public List<Int32> Merge(List<Int32> elements, Int32 lowerBound, Int32 half, Int32 upperBound)
    {
        Int32 i = 0;
        Int32 j = 0;

        Int32 lowerElementsCount = half - lowerBound + 1;
        Int32 upperElementsCount = upperBound - half;

        List<Int32> left = new List<Int32>();
        while (i < lowerElementsCount)
            left.Add(elements[lowerBound + i++]);

        List<Int32> right = new List<Int32>();
        while (j < upperElementsCount)
            right.Add(elements[half + j++ + 1]);

        left.Add(Int32.MaxValue);
        right.Add(Int32.MaxValue);

        i = 0;
        j = 0;

        for (int k = lowerBound; k <= upperBound; k++)
            if (left[i] <= right[j])
            {
                elements[k] = left[i];
                i++;
            }
            else
            {
                elements[k] = right[j];
                j++;
            }

        return elements;
    }

Here are my results:

SORTING 1 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (1513 ticks)
INSERTION-SORT: TIME SPENT: 0ms (1247 ticks)

SORTING 10 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (2710 ticks)
INSERTION-SORT: TIME SPENT: 0ms (3 ticks)

SORTING 100 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (273 ticks)
INSERTION-SORT: TIME SPENT: 0ms (11 ticks)

SORTING 1000 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (3142 ticks)
INSERTION-SORT: TIME SPENT: 0ms (72 ticks)

SORTING 10000 ELEMENTS
MERGE-SORT: TIME SPENT: 18ms (30491 ticks)
INSERTION-SORT: TIME SPENT: 0ms (882 ticks)

And the code for testing:

    static void Main(string[] args)
    {
        for (int i = 1; i < 100000; i*=10)
        {
            List<Int32> elements = GetFilledList(i, 0, Int32.MaxValue, false);
            Console.WriteLine("SORTING {0} ELEMENTS", elements.Count);

            Stopwatch sw = new Stopwatch();

            //MERGE SORT
            sw.Start();
            new MergeSort().Sort(elements);
            sw.Stop();
            Console.WriteLine("MERGE-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);

            //INSERTION SORT
            sw.Restart();
            new InsertionSort().Sort(elements);
            sw.Stop();
            Console.WriteLine("INSERTION-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);
            Console.WriteLine();   
        }

        Console.ReadKey();
    }

In case anyone wondering I got these algorithms from Introduction to Algorithms, Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (Author)

EDIT:

    static List<Int32> GetFilledList(Int32 quantity, Int32 lowerBound, Int32 upperBound, Boolean mayRepeat = true)
    {
        List<Int32> numbers = new List<Int32>();

        Random r = new Random();
        for (int i = 0; i < quantity; i++)
        {
            Int32 numero = r.Next(lowerBound, upperBound); 

            while(!mayRepeat && numbers.Contains(numero))
                numero = r.Next(lowerBound, upperBound);

            numbers.Add(numero);
        }

        return numbers;
    }

because, after the merge sort, the objects in elements are already sorted. do another

elements = GetFilledList(i, 0, Int32.MaxValue, false);

before the

sw.Restart();

I have been trying to wrap my brain around how to write code for rotation of binary tree. I looked at http://en.wikipedia.org/wiki/Tree_rotation and enfuzzled.com I have been staring at this for 2 hours and have looked at it multiple times earlier. I still see problems in the wikipedia article and cannot understand the other one completely e.g.

Both these lines mentioned in the wikipedia article cannot be true at once

Let P be Q's left child. Set P to be the new root.

Can anyone please help?Thanks

According to your comments to the question you are looking for the guidance for the rotation algorithm. Here is LEFT-ROTATE algorithm from an excellent book http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844.

alt text

I would like to know what's the complexity of the following algorithm and, most importantly, the step by step process which leads to deducing it.

I suspect it's O(length(text)^2*length(pattern)) but I have trouble solving the recurrence equation.

How would the complexity improve when doing memoization (i.e. dynamic programming) on the recursive calls?

Also, I would appreciate pointers to techniques/books which would help me learn how to analyze this kind of algorithms.

In Python:

def count_matches(text, pattern):
  if len(pattern) == 0: return 1

  result = 0
  for i in xrange(len(text)):
    if (text[i] == pattern[0]):
      # repeat the operation with the remaining string a pattern
      result += count_matches(text[i+1:], pattern[1:])

  return result

In C:

int count_matches(const char text[],    int text_size, 
                  const char pattern[], int pattern_size) {

  if (pattern_size == 0) return 1;

  int result = 0;

  for (int i = 0; i < text_size; i++) {
    if (text[i] == pattern[0])
      /* repeat the operation with the remaining string a pattern */
      result += count_matches(text+i, text_size-(i+1), 
                              pattern+i, pattern_size-(i+1));
  }

  return result;  
}

Note: The algorithm intentionally repeats the matching for every substring. Please don't focus in what kind of matching the algorithm is performing, just on its complexity.

Apologies for the (now fixed) typos in the algorithms

I'm afraid your algorithm is incorrect for a pattern matching. Mainly because it will search for a sub-sub-string in the rest of the text once it will find that a first character matches. For example for the text "abbccc" and a pattern "accc", your algorithm will return a result equal to 1.

You should consider implementing the "Naive" Algorithm for pattern matching, which is very similar to what you were trying to do, but without recursion. Its complexity is O(n*m) where 'n' is the text length, and 'm' is the pattern length. In Python you could use the following implementation:

text = "aaaaabbbbcccccaaabbbcccc"
pattern = "aabb"
result = 0

    index = text.find(pattern)
    while index > -1:
        result += 1
        print index
        index = text.find(pattern, index+1)

return result

Regarding books on the subject, my best recommendation is Cormen's "Introduction to Algorithms", which covers all the material on algorithms and complexity.

1a.)The loop is below and I want to find it's running time. Here is the loop

sum = 0
for (int i =0; i < N; i++){
    for(int j = i; j >= 0; j--)
          sum ++

The first for loops runs in O(n) which is easy, however for the 2nd I think it also runs in O(n) time because whenever j = i, this loop will run i times.

So I wrote down this has a running time of O(n^2).

1b. )Moreover, can someone also explain what is meant, when a problems asks for a "theta bound"?

Theta bound means that it is a tight asymptotic bound, that bounds the running time both from above and below. In your example, N^2 is both a lower and upper bound on the running time, and hence it is a theta bound on the running time.

More formally:

there exists k1 and k2 such that:

N^2 * k1 <= N(N+1)/2 <= N^2 * k2

for N > some value N0.

Ps. This book gives a pretty good explanation of the different asymptotic bounds: http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1295777605&sr=8-1

All,

I am a mid level python developer with a master's degree in Web Technologies, and while I consider my self a decent programmer, I always have trouble with algorithm complexity related questions.

Anyone suggest a good book to explain how to derive the O notation of an algorithm, and what common solutions to complex algorithms can be used?

I am currently reading "Uncle Bob's" The Clean Coder: A Code of Conduct for Professional Programmers (a well worth read by the way, I highly recommend it), and in it he dedicates a chapter to explain how spending 20 hours outside of work a week improving your craft is the only way to become a better programmer. So I thought I'd start with algorithm complexity and move to Big Table and Closure afterwards.

Introduction to Algorithms by Thomas Cormen seems to be the go-to manual for the industry. It covers a wide range of topics including sorting, data structures, advanced design and analysis, and graph algorithms.

Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor.

Analysis of Algorithms, Jeffrey McConnell, very simple book: link

Can someone check with me if I'm using the rule right in the last step (7)?

UPDATE:

Numbers inside the parentheses are the number of elements (weight(?)) of each set that takes part in the Union. Uppercase letters are names of sets.

As I understand this: we are using as our rank the number of elements? This is getting confusing, each one is using different terms for the same stuff.

We have Unions:

  1. U(1,2,A)
  2. U(3,4,B)
  3. U(A,B,C)
  4. U(5,6,D)
  5. U(7,8,E)
  6. U(D,C,F)
  7. U(E,F,G)

enter image description here

void combine(int x,int y)
{
    int xroot=find(x),yroot=find(y);
    if(rank[xroot]<rank[yroot]) 
        parent[xroot]=yroot;
    else if(rank[xroot]>rank[yroot]) 
    parent[yroot]=xroot;
    else 
    {///rank of both is equal..
        parent[yroot]=xroot;
        rank[xroot]++;
    }
}

Using rank, you see the size of set, not sum of vertices, so step 6 is wrong.

But why the size?
Because if we make root of bigger set the root of smaller set , we need to update parents of smaller number of nodes.

For the best explanation, I would recommend CLRS (Introduction to Algorithms).

Hope it helps you!

here is the of quick sort algorithm from the MITOcw(Introduction To Algorithms ) lecture

QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
     QUICKSORT(A,p,r-1)
     QUICKSORT(A,r+1,q)

PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
    if A[j] <= x
       then i = i+1
            swap A[i] with A[j]
swap A[p] with A[i]
return i

and here its C++ implementation on an integer array

#include <iostream>

using namespace std;

void quickSort(int *,int,int);

int partition(int *, int,int);

int main()
{
    int A[10]={6,10,13,5,8,3,2,25,4,11};
    int p=0,q=10;

    cout<<"======Original======="<<endl;
    for(int f=0; f<10; f++)
        cout<<A[f]<<endl;

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(int f=0; f<10; f++)
        cout<<A[f]<<endl;
}


void quickSort(int *A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
                              // is reducing the value of r and hence value of q becomes
                              // less than p recursively. How can I separate both calls
                              // one for left and one for right sub array of the pivot. 
        quickSort(A,(r+1),q);
    }
}


int partition(int *A, int p,int q)
{
    int x= A[p];
    int i=p;
    int temp;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            temp= A[j];
            A[j]=A[i];
            A[i]=temp;
        }

    }

    temp= A[p];
    A[p]=A[i];
    A[i]=temp;

    return i;
}

code doesn't yield sorted array although the first two runs of quickSort function gives desired output. that is it place the first pivot element to its correct position

Your consideration is wrong. The value of r does not change, since it is given as value to the Quicksort function(not a reference). You handle the ranges with p,q such that p is the first index in the range and q the first index not in the range.

Thus, your calls were wrong:

r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1] 
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]

Here is the complete example. I used std::swap to change elements and ans std::vector instead of an array.

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>&,int,int);

int partition(vector<int>&, int,int);

int main()
{
    vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q=10;

    cout<<"======Original======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;    

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;   
}


void quickSort(vector<int>& A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,r);  
        quickSort(A,r+1,q);
    }
}


int partition(vector<int>& A, int p,int q)
{
    int x= A[p];
    int i=p;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(A[i],A[j]);
        }

    }

    swap(A[i],A[p]);
    return i;
}

Live example: ideone

I am new to C. I have no idea about how to write a C function which creates an empty queue and return a void pointer.

void* queue_open(void)

I also want to know how to write a C function which puts an element at end of a queue.

void queue_put(void *p, void *elementp)

Thanks for your help!

If you are coming from an object oriented background (as your method signatures seem to indicate).

Object oriented idea -> good way to do it in C

Object creation -> malloc a struct, then pass it into an initialization function

struct queue* q = (struct queue*)malloc(sizeof(struct queue));
queue_initialize(q);

if you want, you can wrap this in a function, like so

struct queue* queue_construct() {
  struct queue* q = (struct queue*)malloc(sizeof(struct queue));
  queue_initialize(q);
  return q;
}

Note that these pointer shouldn't point to void*, let C do at least some of the type checking for you.

Implement a method -> create a function that takes a struct pointer to the "almost this" struct.

struct user* user = ... whatever we do here ...;
queue_add(q, (void*)user);

As far as how to actually implement a queue, I suggest a good data structures or algorithms book, as there are many ways to go about it; and, the specific techniques you choose will have different impacts on performance and reliability. There's no one best way, it depends heavily on how the queue is to be used, and which aspects of performance are more important.

The book I recommend is Introduction to Algorithms. This book is overkill for most situations, with very detailed listings of nearly every major data structure you are likely to encounter in the first few years of programming. As such, it makes a great reference, despite its attempt at a language neutral approach, which now looks odd when compared to common programming languages.

Once you understand what is going on, you can do it in nearly any language.

I am starting data structures in C++ and while reading, I came up to the following snippet,

template <class Node_entry>
struct Node {
// data members
Node_entry entry;
Node<Node_entry> *next;
// constructors
Node( );
Node(Node_entry, Node<Node_entry> *link = NULL);
};

Can anyone please elaborate why the author choose a structure and not a class for the implementation of the singly linked list? Thanks.

From algorithms and data structures point of view, there is no difference between doing it using structure or classes! Books that are talking about algorithms or data structure don't care about OOP, for example, in Introduction to Algorithms they are using pascal and sometimes pseudo code. The important thing is to deliver the idea. The author may choose to use structures because he doesn't want to bother the reader about OOP principles and best practices, he doesn't want you to say hey why he defined this field public and not private with setters and getters. by this way you are getting far from data structure and algorithms.

I am struggling to work out how to change a maxHeap to a minHeap. I currently have a maxHeap algorithm working but I would like to know how to change it. This is the maxHeap I have used:

public static int [][] fixheap(int heap[][], int n, int i){
    int j=2*i;
    int weight = heap[i][0];

    while (j<=n){
        if((j<n) && heap[j][0] < heap[j+1][0])
            j++;
        if(weight >= heap[j][0]) break;
        else 
        heap[j/2][0] = heap[j][0]; 

        j=j*2;
    }

    heap[j/2][0]= data;

    return heap;
}

public static void makeheap(int heap[][], int n){

    for (int i=n/2; i>=0; i--){
        fixheap(heap, n ,i);
    }   
}

I have tried reversing certain signs that seem relevant however, I have not found the minHeap. Any help would be great, thanks.

The only difference between a min and max heap is the comparator. If you have a functioning max-heap structure, you should only have to flip the comparator.

Check out Introduction to Algorithms on Amazon. The max-heap structure is described in great detail and is available in the preview or "Look Inside" feature.

I had been given a homework to do a program to sort an array in ascending order.I did this:

#include <stdio.h>
int main()
 {
    int a[100],i,n,j,temp;
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    for(i=0;i<n;++i)
      {
       printf("%d. Enter element: ",i+1);
       scanf("%d",&a[i]);
     }
    for(j=0;j<n;++j)
    for(i=j+1;i<n;++i)
     {
         if(a[j]>a[i])
          {
             temp=a[j];
             a[j]=a[i];
             a[i]=temp;
         }
    }
    printf("Ascending order: ");
    for(i=0;i<n;++i)
        printf("%d  ",a[i]);
    return 0;
}

The input will not be more than 10 numbers. Can this be done in less amount of code than i did here? I want the code to be as shortest as possible.Any help will be appreciated.Thanks!

If you know the range of the array elements, one way is to use another array to store the frequency of each of the array elements ( all elements should be int :) ) and print the sorted array. I am posting it for large number of elements (106). You can reduce it according to your need:

#include <stdio.h>
#include <malloc.h>
int main()
{
    int t, num, *freq = malloc(sizeof(int)*1000001);
        for(int i = 0; i < 1000001; i++)
            freq[i] = 0;
    scanf("%d",&t);

    for(int i = 0; i < t; i++)
    {
        scanf("%d", &num);
        freq[num]++;
    }
    for(int i = 0; i < 1000001; i++)
        if(freq[i])
            while(freq[i]--)
                printf("%d\n", i);
}  

This algorithm can be modified further. The modified version is known as Counting sort and it sorts the array in Θ(n) time.

Counting sort:1

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in Θ(n) time. Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. For example, if 17 elements are less than x, then x belongs in output position 18. We must modify this scheme slightly to handle the situation in which several elements have the same value, since we do not want to put them all in the same position.

In the code for counting sort, we assume that the input is an array A[1...n] and thus A.length = n. We require two other arrays: the array B[1....n] holds the sorted output, and the array C[0....k] provides temporary working storage.

The pseudo code for this algo:

for i ← 1 to k do
c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]
// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1  

1. Content has been taken from Introduction to Algorithms by Thomas H. Cormen and others.

I happened to read on Wikipedia that the amortized time per operation on a disjoint set (union two elements, find parent of a specific element) is O(a(n)), where a(n) is the inverse Ackermann function, which grows very fast.

Can anyone explain why this is true?

There is a proof of the fact in Introduction to Algorithms. It's a fairly popular read it seems, and your city or school library might have a copy. I've also seen copies floating about on the Internet but the legality of those is probably questionable.

EDIT: a chunk of the proof appears to be readable on Google Books.

I have a bunch of objects with level, weight and 0 or more connections to objects of the next levels. I want to know how do I get the "heaviest" path (with the biggest sum of weights).

I'd also love to know of course, what books teach me how to deal with graphs in a practical way.

My book recommendation is Steve Skiena's "Algorithm Design Manual". There's a nice chapter on graphs.

The most common way to traversing graphs is using a Depth-first search. If your graph does cycle you should use the Deep-limited search where you can assign a deep threshold and avoid stackoverflows

Once you get those "deepest paths" you can calculate the distance between them.

Any decent book will cover graphs but I really recommend Cormen's Introduction to Algorithms where the author does a fantastic job explaining details about those algorithms.

There are also entries on wikipedia about graph traversing

I'm a self taught Ruby on Rails engineer, and I'm looking to improve my CS understanding. However, most books about data structures and algorithms are written in Java/C/C++/etc, which I don't know. Is there text on these topics using Ruby? Or do you feel Java is similar enough to Ruby that I could survive through a book?

Is there any recommended text for someone coming from my background?

P.S. Recently I've been looking at Objective C, so I'm not completely blind to statically typed languages.

There's a bunch of books on algorithms that are not tied to specific language. Check

http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402 http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844

I also recommend fundamental, still non-finished classics

http://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043

I'm attempting to learn the workings of the Quicksort algorithm. I'm doing this by reading the CLR algorithms book. I can't seem to figure out how the algorithm works for an array of the same numbers and I wasn't able to find any examples online. For example what would the progression of the quicksort algorithm be for this:

{5h, 5i, 5j, 5k, 5m, 5n}

where the characters (h,i,j,k,m,n) are merely there to differentiate between the various 5's Thanks in advance for your assistance!

That damn book could have been much easier to digest had they used sensible variable names, but I guess they didn't want to diverge from the normal single letter variable convention used for all the math.

I tried to keep their function and variables names and pretty much copy the code, including the "arrays start at 1" convention they use. I mimicked the non random pivot version.

demo: http://jsfiddle.net/p7R99/

or just put the following in a .html file

<pre id="out">
</pre>

<script>
function QUICKSORT(A, p, r) {
    if (p < r) {
        var q = PARTITION(A, p, r);
        output("q=" + q + " and A=" + arr(A) + "\n");
        QUICKSORT(A, p, q - 1);
        QUICKSORT(A, q + 1, r);
    }
}

function PARTITION(A, p, r) {
    var x = A[r];
    var i = p - 1;
    for (var j = p; j < r - 1; j++) {
        if (intval(A[j]) <= intval(x)) {
            i = i + 1;
            swap(A, i, j);
        }
    }
    swap(A, i + 1, r);
    return i + 1;
}

function intval(str) {
    return parseInt(str, 10);
}



function swap(A, i, j) {
    var tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

function output(msg) {
    var ele = document.getElementById("out");
    ele.innerHTML += msg;
}
function arr(A) {
    return A.slice(1).join(" ");
}


var A = [undefined, "5h", "5i", "5j", "5k", "5m", "5n"];
QUICKSORT(A, 1, A.length);
</script>

result

q=1 and A= 5i 5j 5k 5m 5n 5h
q=6 and A= 5i 5j 5k 5m 5h 5n
q=4 and A= 5i 5j 5m 5k 5h 5n
q=2 and A= 5j 5i 5m 5k 5h 5n

I'm running Eclipse in Linux and I was told I could use Xdebug to optimize my program. I use a combination algorithm in my script that takes too long too run.

I am just asking for a starting point to debug this. I know how to do the basics...break points, conditional break points, start, stop, step over, etc... but I want to learn more advanced techniques so I can write better, optimized code.

The first step is to know how to calculate the asymptotic memory usage, which means how much the memory grows when the problem gets bigger. This is done by saying that one recursion takes up X bytes (X = a constant, the easiest is to set it to 1). Then you write down the recurrence, i.e., in what manner the function calls itself or loops and try to conclude how much the memory grows (is it quadratic to the problem size, linear or maybe less?)

This is taught in elementary computer science classes at the universities since it's really useful when concluding how effective an algorithm is. The exact method is hard to describe in a simple forum post, so I recommend you to pick up a book on algorithms (I recommend "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein - MIT Press).

But if you don't have a clue about this type of work, start by using get_memory_usage and echoing how much memory you're using in your loop/recursion. This can give you a hint about were the problem is. Try to reduce the amount of things you keep in memory. Throw away everything you don't need (for example, don't build up a giant array of all data if you can boil it down to intermediary values earlier).

I'm working on teaching myself basic programming.
One simple project is to find the index of recurrences of a substring within a string. So for example, in string "abcdefdef" and substring "def", I would like the output to be 3 and 6. I have some code written, but I'm not getting the answers I want. Following is what I have written


Note:I'm aware that there may be easier way to produce the result, leveraging built-in features/packages of the language, such as Regular Expressions. I'm also aware that my approach is probably not an optimal algorithm. Never the less, at this time, I'm only seeking advice on fixing the following logic, rather than using more idiomatic approaches.

import string

def MIT(String, substring): # "String" is the main string I'm searching within
    String_list = list(String)
    substring_list = list(substring)
    i = 0
    j = 0
    counter = 0
    results = []
    while i < (len(String)-1):
        if [j] == [i]:
            j = j + 1
            i = i + 1
            counter  = counter + 1
            if counter == len(substring):
                results.append([i - len(substring)+1])
                counter = 0
                j = 0
                i = i+1
        else:
            counter = 0
            j = 0
            i = i+1
    print results
    return

My line of reasoning is as such. I turn the String and substring into a list. That allows for indexing of each letter in the string. I set i and j = 0--these will be my first values in the String and substring index, respectively. I also have a new variable, counter, which I set = to 0. Basically, I'm using counter to count how many times the letter in position [i] is equal to the element in position [j]. If counter equals the length of substring, then I know that [i - len(substring) + 1] is a position where my substring starts, so I add it to a list called results. Then I reset counter and j and continue searching for more substrings.

I know the code is awkward, but I thought that I should still be able to get the answer. Instead I get:

>>> MIT("abcdefghi", "def")
[[3]]
>>> MIT("abcdefghi", "efg")
[[3]]
>>> MIT("abcdefghi", "b")
[[1]]
>>> MIT("abcdefghi", "k")
[[1]]

Any thoughts?

The main/major problem are the following:

  • for comparison, use: if String[i] == substring[j]
  • you increment i twice when you found a match, remove the second increment.
  • the loop should go till while i < len(String):

and of course it won't find overlapping matches (eg: MIT("aaa", "aa"))

There are some minor "problems", it's not really pythonic, there is no need for building lists, increment is clearer if written i += 1, a useful function should return the values not print them, etc...

If you want proper and fast code, check the classic algorithm book: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 . It has a whole chapter about string search.

If you want a pythonic solution without implementing the whole thing check the other answers.

Is there a good tutorial to understand how one calculates the running time and space for a given piece of code? I am looking at these coding books and the questions tell the running time however there is no explanation of how it gets that. I know the basic concept of Big Oh but are there some basic rules or tricks to figure out the memory and space requirements?

I might not be looking at the right place but any help or a link to some helpful tutorial would be great!

Thanks

Get Introduction to Algorithms. It's all there.

They also produced video lectures of the part you are interested in: http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/ Scroll down for the video.

i was going through the Introduction to Algorithms by Cormen chapter 14 (augmented data structures) in which he was talking about interval tree. Below is what he mentioned about the design approach behind interval tree.

Step 1: Underlying data structure

We choose a red-black tree in which each node x contains an interval x:int and the key of x is the low endpoint, x:int:low, of the interval. Thus, an inorder tree walk of the data structure lists the intervals in sorted order by low endpoint.

This can be done by declaring a node having min and max. The comparableTo function should compare only x.int.low.

Step 2: Additional information

In addition to the intervals themselves, each node x contains a value x.max, which is the maximum value of any interval endpoint stored in the subtree rooted at x.

Step 3: Maintaining the information

We must verify that insertion and deletion take O(logN) time on an interval tree of n nodes. We can determine x.max given interval x.int and the max values of node x’s children:

x:max = max(x.int.high; x.left.max; x.right.max)

Step 4: Developing new operations

The only new operation we need is INTERVAL-SEARCH.(T, i), which finds a node in tree T whose interval overlaps interval i. If there is no interval that overlaps i in the tree, the procedure returns a pointer to the sentinel T:nil.

I can implement this by AVL tree but out of curiosity want to know whether can we augment existing libraries in java like TreeSet or other collection entity to fit to above design. If yes can you please help in a sample code or example. Thanks in advance.

My interval tree implementation with AVL tree.

public class IntervalTreeAVL<T>{
    private static class TreeNode<T>{
        private T low;
        private T high;
        private TreeNode<T> left;
        private TreeNode<T> right;
        private T max;
        private int height;
        private TreeNode(T l, T h){
            this.low=l;
            this.high=h;
            this.max=high;
            this.height=1;
        }
    }
    private TreeNode<T> root;
    public void insert(T l, T h){
        root=insert(root, l, h);
    }
    private TreeNode<T> insert(TreeNode<T> node, T l, T h){
        if(node==null){
            return new TreeNode<T>(l, h);
        }
        else{
            int k=((Comparable)node.low).compareTo(l);
            if(k>0){
                node.left=insert(node.left, l, h);
            }
            else{
                node.right=insert(node.right, l, h);
            }
            node.height=Math.max(height(node.left), height(node.right))+1;
            node.max=findMax(node);
            int hd = heightDiff(node);
            if(hd<-1){
                int kk=heightDiff(node.right);
                if(kk>0){
                    node.right=rightRotate(node.right);
                    return leftRotate(node);
                }
                else{
                    return leftRotate(node);
                }
            }
            else if(hd>1){
                if(heightDiff(node.left)<0){
                    node.left = leftRotate(node.left);
                    return rightRotate(node);
                }
                else{
                    return rightRotate(node);
                } 
            }
            else;
        }
        return node;
    }
    private TreeNode<T> leftRotate(TreeNode<T> n){
        TreeNode<T> r =  n.right;
        n.right = r.left;
        r.left=n;
        n.height=Math.max(height(n.left), height(n.right))+1;
        r.height=Math.max(height(r.left), height(r.right))+1;
        n.max=findMax(n);
        r.max=findMax(r);
        return r;
    }
    private TreeNode<T> rightRotate(TreeNode<T> n){
        TreeNode<T> r =  n.left;
        n.left = r.right;
        r.right=n;
        n.height=Math.max(height(n.left), height(n.right))+1;
        r.height=Math.max(height(r.left), height(r.right))+1;
        n.max=findMax(n);
        r.max=findMax(r);
        return r;
    }
    private int heightDiff(TreeNode<T> a){
        if(a==null){
            return 0;
        }
        return height(a.left)-height(a.right);
    }
    private int height(TreeNode<T> a){
        if(a==null){
            return 0;
        }
        return a.height;
    }
    private T findMax(TreeNode<T> n){
        if(n.left==null && n.right==null){
            return n.max;
        }
        if(n.left==null){
            if(((Comparable)n.right.max).compareTo(n.max)>0){
                return n.right.max;
            }
            else{
                return n.max;
            }
        }
        if(n.right==null){
           if(((Comparable)n.left.max).compareTo(n.max)>0){
                return n.left.max;
            }
            else{
                return n.max;
            } 
        }
        Comparable c1 = (Comparable)n.left.max;
        Comparable c2 = (Comparable)n.right.max;
        Comparable c3 = (Comparable)n.max;
        T max=null;
        if(c1.compareTo(c2)<0){
            max=n.right.max;
        }
        else{
            max=n.left.max;
        }
        if(c3.compareTo((Comparable)max)>0){
            max=n.max;
        }
        return max;
    }


TreeNode intervalSearch(T t1){
        TreeNode<T> t = root;
        while(t!=null && !isInside(t, t1)){
            if(t.left!=null){
                    if(((Comparable)t.left.max).compareTo(t1)>0){
                    t=t.left;
                }
                else{
                    t=t.right;
                }
            }
            else{
                t=t.right;
            }
        }
        return t;
    }
    private boolean isInside(TreeNode<T> node, T t){
        Comparable cLow=(Comparable)node.low;
        Comparable cHigh=(Comparable)node.high;
        int i = cLow.compareTo(t);
        int j = cHigh.compareTo(t);
        if(i<=0 && j>=0){
            return true;
        }
        return false;
    }
}

I was practicing the recursion tree method using this link: http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html .. 1st example was okay but in the second example he calculates the height of the tree as log(base 3/2) n .. Can anyone tell me how he calculated height ? May be a dumb question but i can't understand! :|

Let me try explain it. The recursion formula you have is T(n) = T(n/3) + T(2n/3) + n. It says, you are making a recursion tree that splits into two subtrees of sizes n/3, 2n/3, and costs n at that level.

If you see the height is determined by height of largest subtree (+1). Here the right-subtree, the one with 2n/3 element will drive the height. OK?

If the above sentence is clear to you, lets calculate height. At height 1,we will have n*(2/3) elements, at height 2, we have n*(2/3)^2 elements,... we will keep splitting till we have one element left, thus at height h

 n*(2/3)^h <= 1
 (take log both side)
 log(n) + h*log(2/3) <= 0
 (log is an increasing function)
 h*log(3/2) >= log(n)
 h >= log(n)/log(3/2)
 h >= log3/2 (n)

I would suggest reading Master Method for Recursion from Introduction to Algorithms - CLRS.

I was reading through Introduction to algorithms i came across this problem about In-order Traversal of binary search tree without using a stack or recursion. Hint says to assume that testing of pointers for equality is a legitimate operation.I'm stuck finding the solution to this problem. Please give me some direction. I'm not looking for the code. Just give me the right direction.

Exact duplicate here

My copy of The Design and Analysis of Computer Algorithms has arrived today. In the first chapter, the author introduced Turing Machines. I have two other algorithms textbooks, Introduction to Algorithms and The Algorithm Design Manual, but none of them talks about Turing machines, even though they are famous on the subject of algorithms and data structures.

I would like to understand What is the relation between Turing Machine and Algorithm/Datastructure. Is is really important to understand Turing machines to become expert in algorithms?

Turing machines are just theoretical tools to analyze computation, ie. we can specify an algorihm by creating a turing machine which computes it. They are very useful in the study of computability, that is, if it is possible at all to compute a function. Turing machines and several other formal language constructs are discuessed in the classic book by Hopcroft and Ullmann. Turing machines also appear when discussing NP-completeness for instance in this book, by Garey and Johnson.

Both books and turing machines in general are pretty theoretical. If you are interested in algorihhms in an academic way, I'd recommend them. However, if you want a practical understanding of algorihms implemented on real computers and run on real data then I'd say that it's only important to have a cursory understanding of turing machines.

The reason that Turing machines are of importance when describing data structures and algorithms is that they provide a mathematical model in which we can describe what an algorithm is. Most of the time, algorithms are described using high-level language or pseudocode. For example, I might describe an algorithm to find the maximum value in an array like this:

Set max = -infinity
For each element in the array:
    If that element is greater than max:
        Set max equal to that element.

From this description it's easy to see how the algorithm works, and it would be easy to translate it into source code. However, suppose that I had written out this description:

Guess the index at which the maximum element occurs.
Output the element at that position.

Is this a valid algorithm? That is, can we say "guess the index" and rigorously define what it means? If we do allow this, how long will it take to do this? If we don't allow it, why not? What's different about the first description from the second?

In order to have a mathematically rigorous definition of an algorithm, we need to have some formal model of how a computer works and what it can and cannot do. The Turing machine is one common way to formally define computation, though there are others that can be used as well (register machines, string rewriting systems, Church's lambda calculus, etc.) Once we have defined a mathematical model of computation, we can start talking about what sorts of algorithmic descriptions are valid - namely, those that could be implemented using our model of computation.

Many modern algorithms depend critically on the properties of the underlying model of computation. For example, cache-oblivious algorithms assume that the model of computation has some memory buffer of an unknown size and a two-tiered memory. Some algorithms require that the underlying machine be transdichotomous, meaning that the size of a machine word must be at least large enough to hold the size of any problem. Randomized algorithms require a formal definition of randomess and how the machine can use random values. Nondeterministic algorithms require a means of specifying a nondeterministic computation. Algorithms based on circuits must know what circuit primitives are and are not allowed. Quantum computers need a formal definition of what operations are and are not allowed, along with what the definition of an algorithm is given that the output is probabilistic. Distributed algorithms need a formal definition of communication across machines.

In short, it's important to be explicit about what is and is not allowed when describing an algorithm. However, to be a good programmer or to have a solid grasp of algorithms, you don't need to necessarily know Turing machines inside and out, nor do you need to know about the specific details of how you'd encode particular problems using them. What you should know, though, is what the model of computation can and cannot do, and what the cost is per operation. This way, you can reason about how efficient algorithms are, how much of various resources (time, space, memory, communication, randomess, nondeterminism, etc.) they use. But that said, don't panic if you don't understand the underlying model.

There is one other reason to think about the underlying model of computation - discussing its limitations. Every model of computation has its limits, and in some cases you can prove that certain algorithms cannot possibly exist for certain problems, or that any algorithm that would solve some problem necessarily must use some amount of a given resource. The most common example where this comes up in algorithm design the notion of NP-hardness. Some problems are conjectured to be extremely "difficult" to solve, but the formal definitions of what this difficulty is relies on knowledge of Turing machines and nondeterministic Turing machines. Understanding the model is useful in this case because it allows you to reason about the computational feasibility of certain problems.

Hope this helps!

The boost::mpl::push_back documentation states that:

push_back performs an insertion at the end of the sequence with guaranteed O(1) complexity.

Is it complexity of compilation time?

The O(1) refers to complexity during runtime. Usually, procedures which execute in O(1) time are said to execute in constant time. In this case, the documentation claims that the time needed for push_back to execute is constant with respect to the length of the list; that is, its execution time will be a fixed constant time independent of the list's length.

On the other hand, if the documentation had claimed that push_back executed with O(n) complexity, that would have indicated that push_back's execution time could be approximated by a linear function of the list's length, where the list's length here is n. Functions that fall in this complexity category are said to execute in linear time.

Wikipedia has a good introduction to the O(n) notation [1]. A good introductory text is "An Introduction to Algorithms" by Cormen, Lieverson, and Rivest.

This may be a bit OT...

Here's the problem: "N different points with integer coordinates are given in a plane. You are to write a program that finds the maximum number of collinear points (they all belong to the same line)."

Now my question: You don't have to solve this for me, instead I want to know where I can find some materials for learning how to solve problems like this. This is probably geometry related and I'm not really deep into geometry so I'd like to read up some advices, which books are good, where I can find any tutorials for solving such problems etc. etc.

where I can find some materials for learning how to solve problems like this

Unfortunately, solving algorithm problems, like most math problems, is a matter of reaching into your toolbox and using what you know. Very similiar problems may be solved in completely different ways, and there is no rule of thumb for knowing if a problem can be solved one way or the other, or even at all.

The best way to start, then, would be to build up your toolbox:

As long as I've been a programmer I still have a very elementary level education in algorithms (because I'm self-taught). Perhaps there is a good beginner book on them that you could suggest in your answer.

As a general note, Introduction to Algorithms. That book will get you through pretty much everything you need to know about general algorithms.

Edit:

As AndrewF mentioned, it doesn't actually contain minimax specifically, but it's still a very good resource for learning to understand and implement algorithms.

At the moment, I'm studying for a final exam for a Computer Science course. One of the questions that will be asked is most likely a question on how to combine running times, so I'll give an example.

I was wondering, if I created a program that preprocessed inputs using Insertion Sort, and then searched for a value "X" using Binary Search, how would I combine the running times to find the best, worst, and average case time complexities of the over-all program?

For example...

Insertion Sort
Worst Case O(n^2)
Best Case O(n)
Average Case O(n^2)

Binary Search Worst Case O(logn)
Best Case O(1)
Average Case O(logn)

Would the Worst case be O(n^2 + logn), or would it be O(n^2), or neither?
Would the Best Case be O(n)?
Would the Average Case be O(nlogn), O(n+logn), O(logn), O(n^2+logn), or none of these?

I tend to over-think solutions, so if I can get any guidance on combining running times, it would be much appreciated.

Thank you very much.

Based on my limited study, (we haven't reached Amortization so this might be where Jim has the rest correct), but basically you just go based on whoever is slowest of the overall algorithm.

This seems to be a good book on the subject of Algorithms (I haven't got much to compare to): http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1303528736&sr=8-1

Also MIT has a full course on the Algorithms on their site here is the link for that too! http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

I've actually found it helpful, it might not answer specifically your question, but I think it will help get you more confident seeing some of the topics explained a few times.

How good is this book for learning algorithm creation, based on experiences ?

The most common algorithms book I have seen is Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms, which you may see written elsewhere as CLRS or "The MIT Algorithms Text". It's not quite as pervasive as the Dragon Book is for compiler design, but it's close.

Strictly speaking, when talking about algorithms, the programming language you decide to use rarely makes much of a difference. Algorithms are about speeding up the machine's way of thinking of general problems, not a particular way of processing a particular input with a particular implementation.

I have been writing PHP, Ruby, ColdFusion, and javascript (not a language, I know), for several years.

But I am really wanting to get more into the world of Computer Science and writing in lower-level languages.

What are some good resources for starting out? It seems like every book I have gotten has been extremely elementary, and that isn't at all helpful. I need something that skips the basics.

For computer science, I would recommend starting with discrete mathematics. A good book is the Rosen book, which my university uses. From there, you can move on to Concrete Mathematics, Introduction to Algorithms, and Introduction to the Theory of Computation. I can't speak much about Introduction to Algorithms - it's still on my wish list. But the other two are very good. That should cover the basics of computer science.

From there, you can go down any route. Some major fields in computer science are theoretical computer science (logic, automata theory), computational theory (computability theory and complexity theory), algorithms and data structures, computer architectures (parallel processing), operating systems, computer networks, graphics, vision, databases, AI...You would have to decide what interests you the most and investigate that particular topic area in more depth.

I have implemented cryptography and Steganography algorithms in a application and would like to make a time complexity evaluation for these algorithms. I don't have any idea how these tests should be performed.

Is there any testing framework which I can apply or how to make these tests?

Assuming you're not using recursion, you should look at your loops. It's fairly simple to count by inspection the number of times each loop is iterated based on a certain input. The time complexity is given by multiplication of the number of times nested loops are run. If you have more than one set of nested loops, add them all together and this is the time complexity. As an example:

for (int i=0; i<N; ++i)
{
    // Some constant time operation happens here
    for (int j=0; j<N; ++j)
    {
      // Some constant time operation happens here
    }
    // Some constant time operation happens here
} 

This loop will execute in O(N) + O(N2) = O(N + N2) = O(N2) time since the outer constant time portions of the loop are executed in O(N) time, while the inner portion is performed in O(N)*O(N) = O(N2).

If you're using recursion, things are a bit harder to analyze, but it boils down to the same thing ... counting how many times constant time portions of your code get executed. Recommend you read a book on analysis of algorithms (This one is pretty much the standard on the subject) which will help you understand how best to analyze other algorithms as well.

I know the formula for the recurrence relation is T(n)=aT(n/b)+f(n). And given that equation I know how to solve for the BigO. My homework question asked me to write a recursive function to count the number of nodes in a list, which I did but then asked me to write a recurrence relation. Here's my code:

int count(ListNode *l)
{
    if(!l) return 0;
    if(!l->next) return 1;

    return 1 + count(l->getNext());
}

But I am totally lost on how to create/formulate my own recurrence relation formula...how do I find a or b....I don't know where to begin. How do I write the recurrence relation for this function? Thank you.

Your first recurrence relation is normally used to describe running time of divide-and-conquer algorithms. a here shows how many parts you are dividing your data to, 1/b shows what piece of original data is used in each part, and f(n) shows how much time you need on each "level". For example, in QuickSort algorithm you divide your data (array or list) into 2 parts, each of which is exactly half (1/2) of original data, and on each "level" of dividing you need to go through all n elements 1 time. So recurrence relation is

T(n) = 2T(n/2) + n

(which evaluates to O(n * lg(n))) And in binary search you divide data into 2 parts, but take only 1 of them, and time on each "level" is constant, so relation is:

T(n) = T(n/2) + 1

However, your function in C doesn't follow divide-and-conquer strategy. Instead it demonstrates mathematical induction. You define start conditions: if l equals NULL, then length is 0, and if it l->next equals NULL (you also define condition for 1 element in list). Then you define a kind of inductive step - you define how to compute function for nth element, if you know function value for (n - 1)th element. So, knowing value of a function for 1st element you can apply this rule and get value for 2nd element, then for 3rd and so on.

So you can see that induction method is recurrence algorithm by the nature. Here we have 2 times to consider. First is a time to compute value at the start point (or end point - it depends on the order you are looking at the list). In your function you just return this value, so it is constant (C1). Second is a time to make 1 step. In your function it is also constant (C2). Intuitively you should see that execution time of this algorithm will be:

T(n) = C1, when n = 1 
T(n) = T(n - 1) + C2, when n > 1

Thus, unless n = 1, you define time to execute algorithm on n element through time to execute it on n - 1 elements. In BigO notation any constant is defined as 1 and case of 1 element is not considered, so your final recurrence relation is:

T(n) = T(n - 1) + 1

(which evaluates to T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + n, or O(n))

Further reading:

I'm currently attending the first year of college at Computer Science. I'm having great problems with something named Numerical Methods because I lack at mathematics. I don't have a basis for math concepts. Could any of you please tell me a good book, tutorial site or videos of Numerical Methods for people that don't have a clear basic knowledge of mathematics? I tried looking for something like "Numerical Methods for Dummies", but I didn't find anything equivalent.

Try sniffing around the internet for course notes (lecture notes) from other universities, especially for first year/second year engineering mathematics (for a general grounding) and numerical methods after that.

My university had very good lecture notes, but I can't distribute them. Other universities are more liberal.

You may also want to check out MIT OpenCourseWare, which contains lecture notes and course materials from the Massachusetts Institute of Technology. Some of the lecturers at MIT literally wrote the book on their respective field, so you can't go wrong with anything you find there.

Links to interesting courses on MIT OCW:

I'm going through some potential interview questions, one of which being can you implement a map or a linked list using a tree.

But even after some time googling I don't have a clear idea exactly what a map is, how it differs from an array or a hash table for example. Could anybody provide a clear description.

Can it, and a linked list be written as a tree?

Can it (a map), and a linked list be written as a tree?

Maps are usually represented with arrays. To determine where an entry goes in a map, you need to compute its key. Look here for a better explanation.

Trees (with an undetermined number of nodes) can be implemented using lists (see here for further discussion). Lists are not usually implemented as trees.

I'd encourage you to get this book which is a classic on data structures and will give you alot of really great information.

I'm planning to invest some time every week studying data structures and algorithms.
Do you recommend: "MIT Introduction to Algorithms, 3rd Edition" by Cormen, Leiseson, Rivest and Stein?
AFAIK this book is legendary but I don't know its target audience.

Is this book suitable for my purpose? or it is for academic studies? is it loaded with heavy math?

For Java I recommend Algorithms in Java, Parts 1-4 by Robert Sedgewick. And the companion book Algorithms in Java, Part 5: Graph Algorithms by Robert Sedgewick.

For general studies I also have the Introductions to Algorithms books, it is a good general reference. This Algorithms, Fourth Edition by Robert Sedgewick looks good as well, but probably covers a lot of stuff already in the previously mentioned books.

For Clojure, you will probably need to get a Functional based Algorithm book. Pearls of Functional Algorithm Design looks like it might be a good companion to a the more general procedural books.

I read Computer Algorithms by Horowitz and Sahni, its quite easy to follow with enough examples and pseudo codes.

In addition to Cormen, I'd recommend reading Purely Functional Data Structures, if you're using both Java and Clojure.

I need a data structure that holds unique values (like a set), but also sorts them (like a priority queue) and allows random access for binary searching (like an array). Which type of data structure would fit these needs? I could live without the sorting (I can always sort it myself at the end)

That sounds like a balanced binary tree, with a restriction of uniqueness in its insert operation, and implementing the OS-SELECT operation (see: Introduction to Algorithms, chapter 14 in the 3rd edition) for retrieving an element given its rank ("index") in O(lg n).

The proposed data structure and augmented operations will allow you to:

  • Hold unique values, performing the insertion operation in O(lg n)
  • Keep the elements sorted, with a O(lg n) search operation
  • Access an element given its rank in O(lg n)

In my Data Structures Class, we're looking at recurrence relations like T(n) and big O problems O(n). I'd appreciate any resources for learning these, my textbook doesn't cover T(n), and the professor skips over lots of steps.

I haven't seen a good, step-by-step method for solving these things. I realize that every problem is unique, but there has to be some sort of framework for doing these.

Thanks.

Check Concrete Mathematics - A Foundation for Computer Science, it's a brilliant book with lots of examples and exercises.

Another great book is Introduction to Algorithms. It has a pretty thorough section on solving recurrence relations.

You are right, there is a generalized method for solving simple recurrence relations called the Master Theorem. (The explanation in Introduction to Algorithms is much better than the Wikipedia page.) It doesn't work for every case, but it solves a lot of common ones.

I've been looking an answer for a while and I was wondering if anyone knows how to define explicitly (from scratch) a hash function in C#. I understand that there are pre-defined data structures that have List abilities, but I'm trying to understand the underlying structures of these objects.

Can anyone help with this? For example, if you have two arrays, how would you be able to create a hash table from this?

The Wikipedia articles on hash tables and hash functions are ridiculously good. You could also check out Volume 3 of TAOCP. Lastly, a peek in Reflector at System.Collections.Hashtable would probably be an edifying experience.

If you have more specific questions, we can probably provide more detailed insight.

To be able to hash two arrays, it sort of depends on what kind of data the arrays are holding. For example, if you mean to be hashing arrays of strings you'll need an extra step to encode the strings and integers before hashing them because what you'll essentially need is to convert your input into an index for your hash table, given a hash function. Of course, when you are 'converting your input' you have to solve the problem of collisions among your keys. In other words, you have to try and minimize the number of keys that hash to the same value, which is why Number Theory (specifically, the use of prime numbers) becomes particularly useful.

I assume that when you ask to know how to 'create a hash table' from two arrays you mean for the data in the two arrays to be the keys of the table. In that case, I can't see why you would need to refer to two arrays instead of a bigger array that contains the elements of the two arrays unless you are dealing with a statically-typed programming language and the two arrays can have different types. In this case, you will need to come up with a scheme to convert the elements into integers. If you want to convert a string s of length n where s[i] is the ith character in the string (referring to its ASCII value) into an integer, for example, you can look at how Java's hashCode() function does the job It essentially evaluates a polynomial with a prime base so as to avoid having different strings hash to the same integer. And the reason why the base is 31, other than the fact that it is prime, is because multiplying by 31 is close to a power of 2 so 31 can be done efficiently mostly with bit-shifting.

Once you have all your elements in the form of integers, you get to the real meat of the problem. There are basic tricks from which we can make elaborate combinations of, provided that the components of the combinations are relatively prime with one another so that we can scale to the entire hash table. Two of the basic methods are the division method and the multiplication method. These methods on their own, especially the division method, are insufficient because someone could eventually determine the function that hashed your keys. I would try to explain common ways of constructing hash functions, but I probably wouldn't explain them nearly as well as CLRS. On the other hand, I can give you a list of properties to satisfy:

  • You should minimize collisions
  • Your function should be able to hash a key to any slot
  • (so as to not violate simple uniform hashing)
  • Your function should be hard to reverse-engineer

Bear in mind that in order to satisfy that last property typically some component(s) of the hash function should at least cause the slots they map the keys to to appear random. Due to this constraint we will still have a non-zero probability of having a collision, so your next problem to solve would be collision resolution.

I've events which all have a starting and ending date, some of them are crossing other and I need to determine which are the one I could apply to knowing I want to apply to a maximum of events?

For example, I may have 3 events like this :

  1. from 2013-01-01 to 2013-01-23
  2. from 2013-01-15 to 2013-01-21
  3. from 2013-01-22 to 2013-01-24

I want to apply to a maximum of events so I won't apply to first because it is crossing the two others.

So the result should be 2. & 3.

I think I need to visit some sort of graph but I dunno where to start.

Any feedbacks are welcome.

Just sort events by their end point, then greedily select events with a smallest end date, such that they don't have a conflict with previously selected ones. This is one a first problems that you can see in the greedy concept. e.g Is the first problem discussed in the greedy part of the Introduction to algorithm book.

I want to cover the equivalent of a typical CS undergrad course in material, so I'm making a list of books to cover the typical topics. I've split the list into topics that, from the research I did, I think are compulsory and optional. I would like some help to confirm if the topics are split correctly, and if the books are of the correct level. Also, please let me know if I left out any important topics, or if any are beyond undergrad level.

Thank you for your time!

Edit regarding the on hold status: I do not believe this question is off-topic as I am not asking for a recommendation for books - I am asking if the topics I have listed are indicative of a typical CS course, and if any important topics are missing. The books links are only there in case the books I have chosen are not correct for the topic, and can be removed if necessary.


COMPULSORY

Operating Systems: Operating System Concepts

Networks: Computer Networking: A Top-Down Approach

Discrete Mathematics: Concrete Mathematics

Data Structures and Algorithms: Introduction to Algorithms

Computer Architecture: Computer Systems: A Programmer's Perspective

Automata Theory: Introduction to the Theory of Computation

Compilers: Engineering a Compiler was recommended to me over the dragon book.

Database Theory: An Introduction to Database Systems

Programming Language Concepts and Design: Programming Language Pragmatics

OPTIONAL

Cryptography: Cryptography Engineering: Design Principles and Practical Applications

Functional Programming: Learn You a Haskell for Great Good!

Artificial Intelligence: Artificial Intelligence: A Modern Approach

Computer Graphics: Real-Time Rendering

Your list is very good on the subjects directly related to computer science. However, it is light on math. In my own B.Sc. in Computer Science I also had a ton of calculus, linear algebra, algebra (groups, rings, etc), statistics, analytic geometry and numerical analysis. Some applications of computer science rely heavily on those:

  • Machine learning depends on lots of linear algebra, calculus, and statistics;
  • Computer graphics depends a lot on analytic geometry and linear algebra;
  • Scientific computation relies on calculus and numerical analysis.

I never used much of the ton of Algebra I had, but I hear it is important for cryptography. :-)

For a programmer developing more regular applications your list is very good, but for those interested in these more specialized areas (which are still pretty important), these subjects are vital.

Reading algorithms by self using Robert Sedwick book in C++

A recursive function that divides a problem of size N into two independent (nonempty) parts that it solves recursively calls itself less than N times.

If the parts are one of size k and one of size N-k, then the total number of recursive calls that we use is T(n) = T(k) + T(n-k) + 1, for N>=1 with T(1) = 0.

The solution T(N) = N-1 is immediate by induction. If the sizes sum to a value less than N, the proof that the number of calls is less than N-1 follows from same inductive argument.

My questions on above text are

  1. How author came with solution T(N) = N-1 by induction? Please help me to understand.
  2. What does author mean by "If the sizes sum to a value less than N, the proof that the number of calls is less than N-1 follows from same inductive argument" ?

I am new to mathematical induction so having difficulty in understanding.

Thanks for your time and help

First of all, we do not "came with the solution by induction", we use induction to prove our initial guess. Now, In order to guess we can use methods like Recursion tree.
In your problem, the worst case is for k=1, since it will results the most number of recursions. We also know the cost at each level :

T(n) = T(1) + T(n-1) + 1 => T(n) = T(n-1) + 1

Now we have to find the cost of T(n-1) and add that to cost T(n)=1.
We guess the final result is N-1. In this step we use induction to prove our guess.

Update :
Cost of T(n) is 1 ( T(1) is zero, plus T(n-1) that will be calculated, plus 1 => 1 ), cost of T(n-1) is also one ( with same logic ). We go down by depth of n-1. The last one is T(1) which is zero. ( draw a tree, it will help you to understand ).
This method to guess order of growth called recursion tree. Now you can prove it by induction.

For more information about how to apply induction to prove the hypothesis, refer to text books like CLRS.

Say I have two arrays, energy (E) and score (S), and they could have elements like this:

E = {1 , 3 , 4, 7};
S = {16, 10, 5, 1};

What I want is the best score with the best energy. What data structure can support inserting items in a way that I don't have have an item with less energy and less score than another item i.e. for any i,j where i!=j => score[i] > score[j] || energy[i] > energy[j]

When inserting, I do three steps:

1- if any item has more or equal score and energy, return;

2- if any item has less or equal score and energy, remove this item;

3- insert the required item.

Here are some examples: 1- insert e=8, s=1. The arrays become:

E = {1 , 3 , 4, 8};
S = {16, 10, 5, 1};
                ^

2- insert e=5, s=6. The arrays becomes:

E = {1 , 3 , 5, 8};
S = {16, 10, 6, 1};
             ^

3- insert e=5, s=11. The arrays becomes :

E = {1 , 5 , 8};
S = {16, 11, 1};
         ^    (3,10) is removed because (5,11) has more energy and more score than it.

What data structure can support this in (hopefully) O(logn) time?

My solution to this problem is to use a max-heap that stores a pair structure as the value of its nodes. If you're not familiar with heaps, the CLRS book, chapter 6 has the best discussion I've read of them.

The max-heapfiy method of a heap bubbles up the max to the top, such that any particular node's children all have lower value than their parent. You can use this property as a condition for removing subnodes and maintaining the heap property. In your case, it sounds like you may be deleting entire subtrees when both energy and score of the inserted node are greater than a particular child, and only deleting a single node when either energy or score is greater.

The following code is in accordance with the CLRS (Corman, Leiserson, Rivest, Stein — 'Introduction to Algorithms') textbook which is supposed to do merge sorting.

I am unable to identify the mistake that is happening, although I know there is something wrong happening in the mergesort() function. I think merge() is functionally intact.

/* Merge sort as per CLRS */
#include <stdio.h>
#include <stdlib.h>

void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1+1)*sizeof(int));
int* ri = malloc((n2+1)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
    l[i] = a[p+i-1];
for(i = 0 ; i < n2 ; i++)
    ri[i] = a[q+i];
l[n1] = 9999;
ri[n2] = 9999;
i = 0;
j = 0;
int k;
for ( k = p ; k <= r ; k++){
    if( l[i] < ri[j] ){
        a[k] = l[i];
        i++;
    }
    else{
        a[k] = ri[j];
        j++;
    } 
}
}

void mergeSort(int* a,int p,int r){
if( p < r){

    int q = ( p + r ) / 2;
    mergeSort(a,p,q);
    mergeSort(a,p+1,r);
    merge(a,p,q,r);
}

else return;

}

int main(int argc, char* argv[]){
int a[] = {9,21,4,15,1,3};

mergeSort(a,0,5);

int i;
for( i = 0 ; i < 6 ; i++){
    printf("%d ",a[i]);
}
return 0;

}
void merge(int *a,int p,int q,int r){
    int n1 = q - p + 1;
    int n2 = r - q;
    int* l = malloc((n1+1)*sizeof(int));
    int* ri = malloc((n2+1)*sizeof(int));
    int i,j;
    for(i = 0 ; i < n1 ; i++)
        l[i] = a[p+i-1];
    for(i = 0 ; i < n2 ; i++)
        ri[i] = a[q+i];

You are writing the elements from index p-1 through index q-1 to l, and the elements from index q through r-1 to ri. If p == 0, you access out of bounds.

You want, however, to sort the elements from index p through r.

void merge(int *a,int p,int q,int r){
    int n1 = q - p + 1;
    int n2 = r - q;
    int* l = malloc((n1)*sizeof(int));
    int* ri = malloc((n2)*sizeof(int));
    int i,j;
    for(i = 0 ; i < n1 ; i++)
        l[i] = a[p+i];
    for(i = 0 ; i < n2 ; i++)
        ri[i] = a[q+i+1];

Also, you should check whether both indices, i and j are smaller than the corresponding end index n1 resp. n2, and when one reaches the end of its part, copy the remaining from the other part to the array. The guard value fails terribly if the array contains large entries.

while(i < n1 && j < n2) {
    if (ri[j] < l[i]) {
        a[k++] = ri[j++];
    } else {
        a[k++] = l[i++];
    }
}
while(i < n1) {
    a[k++] = l[i++];
}
while(j < n2) {
    a[k++] = ri[j++];
}

What conditions does a programming problem need to meet in order to be solved trough dynamic programming? What reasoning do you do in order to find out?

Once you conclude that it indeed has a DP solution then how would you go on about creating a DP algorithm that solves it? What's the logic behind creating such algorithms?

A problem must meet two conditions in order to be solved trough dynamic programming. Citing Introduction to Algorithms, chapter 15:

Optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems.

In The Algorithm Design Manual, chapter 8, the author describes the three steps involved in solving a problem by dynamic programming:

  1. Formulate the answer as a recurrence relation or recursive algorithm.
  2. Show that the number of different parameter values taken on by your recur- rence is bounded by a (hopefully small) polynomial.
  3. Specify an order of evaluation for the recurrence so the partial results you need are always available when you need them.

As usual, the wikipedia contains an extensive discussion on the topic, if you want to dig deeper.

Possible Duplicate:
Learning Algorithms and Data Structures Fundamentals

Hi,

I'm trying to practice my programming. What sort of projects would be helpful to try implimenting real life usage of various data structures?

Thanks,

SEC

I would also recommend you to use a book. Introduction to algorithms by Leiserson et al is quite good. But there are others as well...

http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&s=books&qid=1272317456&sr=8-1

If you want to see some sophisticated data structures and real world algorithms using them, have a look at the lectures by Leiserson. Those are all available online here:

http://videolectures.net/mit6046jf05_introduction_algorithms/

According to CourseEra course on Algorithms and Introduction to Algorithms , a function G(n) where n is the input size is said to be a big oh notation of F(n) when there exists constants n0 and C such that this inequality holds true

F(n) <= C*G(N) ( For all N > N0 )

Now , This mathematical definition is very clear to me .

But as it was taught to me by my teacher today , I am confused!

He said that "Big - Oh Notations are upper bound on a function and it is like the LCM of two numbers i.e. Unique and greater than the function"

I don't think this statement was kind of correct, Is Big Oh notation really unique ?

Morover, Thinking about Big Oh notations , I also confused myself why do we approximate the Big Oh notations to the highest degree term . ( We can easily prove the mathematical inequality though with nice choice of constants ) but what is the real use of it ?? I mean what does it signify? We can even take F(n) as the Big Oh Notation of F(n) for the constant 1 !

I think it shows the dependence of the running time only on the highest degree term! Please Clear my doubts as I might have understood it wrongly from my book or my teacher made an error?

Is Big Oh notation really unique ?

Yes and no. By the pure formula, Big-O is of course not unique. However, to be of use for its purpose, one actually tries to find not just some upper bound, but the lowest upper bound. And this makes a meaningful "Big-O" unique.

We can even take F(n) as the Big Oh Notation of F(n) for the constant 1 !

Yes we probably can do that. However, the Big-O is used to relate classes of functions/algorithms to each other. Saying that F(n) relates to X(n) like F(n) relates to X(n) is what you get by using G(n) = F(n). Not much value in that.

That's why we try to find the unique lowest G to satisfy the equation. G(n) is usually a rather trivial function, like G(n) = n, G(n) = n², or G(n) = n*log(n), and this allows us to compare algorithms more easily because we can easily see that, e.g., G(n) = n is less than G(n) = n² for all n >= something.

Interestingly, most algorithms' complexity converges to one of the simple G(n) for large n. You could also say that, by looking at large n's, we try to separate out the "important" from the not-so-important parts of F(n); then we just omit the minor terms in F(n) and get a simplified function G(n).

In practical terms, we also want to abstract away from technical details. If I have, for instance, F(n) = 4*n and E(n) = 2*n I can use twice as much CPUs for the F algorithm and be just as good as the E one independent of the size of the input. Maybe one machine has a dedicated instruction for sqare root, so that SQRT(x) is a single step, while another machine needs much more instructions to get the result. We want to abstract away from that.

This implies one more point of view too: If I have a problem to solve, e.g. "calculate x(y)", I could present the solution as "result := x(y)", O(1). But that's not considered an algorithm. The specification of the algorithm must include a relevant level of detail to be a) meaningful and b) accessible to Big-O.

after I call new, how can I add more objects to the pointer? (I need it for a class) this is what I mean:

int *a;
a = new int;
a = new int;

Thank you very much!

It sounds like you are trying to write your own vector class that can grow on demand. You can do this as follows:

int * a; // original pointer
a = new int[5]; // just five elements

Now to grow it to 10 elements (make a new array, copy the old contents, reclaim the old array's memory, and reassign the array pointer):

int * tmp = new int[10]; // a new array
memcpy (tmp, a, 5 * sizeof(int)); // copy the old items into the new array
delete [] a; // reclaim the memory from the old array
a = tmp; // reassign a to point to the new, bigger array

See Cormen, Leiserson, Rivest and Stein, Chapter 17.4, for description and analysis of such a "dynamic table."

Follow up Question from: http://codereview.stackexchange.com/questions/30243/how-can-i-improve-upon-my-a-pathfinding-code/

Summary: I asked for help improving my pathfinding code (A*). A user quickly spotted that I was sorting a particular list of nodes a lot and that using IComparible to do so - Apparently very inefficient. He suggested using an OrderedBag, however, I have to code everything myself and can't use code from the internet.

The Question: So, would making a Binary Heap be the most effective way of maintaining ordered data, while still being able to add and remove data quickly. If so, does anyone have any links to point me in the right direction for creating one, and which one to create?

I've heard of a LinkedList - Good idea?

If you are rolling your own as an exercise then yes, a heap is the correct data structure to build an efficient priority queue. Start with a binary heap because its fairly easy. You can always try a more complex heap later if you have time and inclination.

Questions recommending off site resources are off topic btw. The standard print source for simple algorithms and data structures is Introduction to Algorithms. But these days Wikipedia is a good source for pseudo code as well. (Note that the Wikipedia article shows how to build a max heap; you need a min heap. Figuring out how to build a min heap given the code for a max heap is a good exercise.)

This article also gives some good advice on use of binary heaps for A*.

Given Length of Rod and P (Price ) for the first 3 rods. We are to fill in the possible price we can get for the rest of rods. Assuming we can cut the longer pieces as needed.

L = 1     2       3      4       5        6         7          8 
p = 3     8       12 

We basically want to get the maximum price we can get for each missing length price.

My approach I believe that since we are given the best possible price for a rod of length 1,2, and 3 we can generate all possible combinations for the next rods.

For example to get price of rod where L = 4 
price of rod where L = 1 + rod where L =  3 = 15
price of rod where L =  2 + rode where L =  2 = 16
Therefore price of rod wehre L = 4  = 16 since 16 > 15.

For example to get price of rod where L = 5
price of rod where L = 1 + rod where L = 2 and rod where L = 2 = 19
price of rod where L = 3 + rod where L = 2  = 20
price of rod where L = 4 + rod where L = 1 = 19

So this is kind of the approach i am following. However I am not sure if i am correct. I would also like it if someone can verify this approach and also maybe help me derive a formula from this. I am not looking for code as understanding the problem is enough to write the code.

You can check the explanation of a variation of this problem in CLRS (section 15.1, page 360). The problem is called the Rod Cutting problem.

Your approach is correct, and you can formalize it as a recurrence relation.

f(n) = min(f(n - i) + price(i)).    1 <= i <= n - 1

where f(n) is the minimum price to buy a rod of length n. using memoization, this can be calculated in O(n^2).

here is the problem link https://leetcode.com/problems/binary-tree-maximum-path-sum/, and my solution is i can transform from a tree to a array,so i adopt to use preorder tree walk,and i refer kadane's algorithm to find max value in the array,here is my code,when i run the program ,the result always be zero,but in my opnion,it is should be right, i cant figure out why it doesn't work,and by the way ,the problem hint is using dfs,i am not familiar with dfs,can anyone provide some thought in this problem by using dfs method,and tell me how to study dfs well,any papers or notes,videos is ok,thanks in advance!

 int maxPathSum(TreeNode *root) {
  vector<int>res;
  int max;
  if (root){
      res.push_back(root->val);
      maxPathSum(root->left);
      maxPathSum(root->right);
  }
  else{
      return 0;
  }
  max = maxpathsum1(res);
  return max;
}
int maxpathsum1(vector<int>&res){
    int cur,max;
    int len = res.size();
    cur = 0;
    max = 0;
    for (int i=0;i<len-1;i++){
        cur = cur+res[i];
        if (cur<0){
            cur = 0;
        }
        if (max<cur){
            max = cur;
        }
    }
    return max;
}

A dfs is an algorithm for traversing over all nodes in a tree (more generally in a graph), so it can indeed fit to your problem. You can just ran the dfs algorithm, while summing the max path each time between the left sub-tree and the right one + the root node itself. You can find much more on dfs in Coreman's "Introduction to Algorithms" book.

Regarding yours (very similar) solution, you are not using the return value of the recursion in the "maxPathSum" function. You should take this values returned after calling the recursion on "root->left" and "root->right", validate they are positive and sum them into some "max2" variable and use it.

I adapted pseudocode for an optimized binary search tree algorithm from Cormen to run some sample data, but there is a logic error somewhere that is preventing correct output in the root list.

I've checked the code against Cormen several times, and it appears that the problem is in my list indices (subscripts).

But because in this case Cormen uses both zero-based and one-based arrays in the diagrams, I have absolutely no idea how to modify my list indices to correct the problem. It appears the author broke the one-based convention typical of the text for this particular algorithm.

Can anyone with experience in OBST see the adjustment necessary to correct the following Python?

def obst(p,q):
    """Adapted from Cormen, pg. 402"""
    n  = len(q)
    rn = range(n)
    e  = [[99999]*n for _ in rn]
    w  = [[0]*n for _ in rn]
    root = [[0]*n for _ in rn]

    for i in range(1, n):
        e[i][i - 1] = w[i][i - 1] = q[i - 1]


    for l in range(1,n):
        for i in range(1, n-l):
            j = i+l-1
            w[i][j] = w[i][j-1] + p[j] + q[j]
            for r in range(i,j+1):
                t = e[i][r-1] + e[r+1][j] + w[i][j]
                if t < e[i][j]:
                    e[i][j] = t
                    root[i][j] = r
    return (e,root)

if __name__ == "__main__":
    p = [0, 0.15, 0.1, 0.05, 0.1, 0.2]
    q = [0.05, 0.1, 0.05, 0.05, 0.05, 0.1]
    assert len(p) == len(q)
    d = obst(p,q,len(p))
    print(d[1])

EDIT: I changed some indices. According to Cormen, the expected output for the root table alone (which is in the second element of the returned tuple) is as follows:

[
    [0, 0, 0, 0, 0, 0],
    [0, 1, 1, 2, 2, 2],
    [0, 0, 2, 2, 2, 4],
    [0, 0, 0, 3, 4, 5],
    [0, 0, 0, 0, 4, 5],
    [0, 0, 0, 0, 0, 5],
    [0, 0, 0, 0, 0, 0]
]

My output when n is len(p):

[
    [0, 0, 0, 0, 0, 0],
    [0, 1, 2, 3, 4, 0],
    [0, 0, 2, 3, 4, 0],
    [0, 0, 0, 3, 4, 0],
    [0, 0, 0, 0, 4, 0],
    [0, 0, 0, 0, 0, 0]
]

I am attempting to implement heap sort using the psuedo code from the book Intro to Algorithms. The following is what I have:

def parent(i):
    return i/2

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def max_heapify(seq, i, n):
    l = left(i)
    r = right(i)

    if l <= n and seq[n] > seq[i]:
        largest = l
    else:
        largest = i
    if r <= n and seq[r] > seq[largest]:
        largest = r

    if largest != i:
        seq[i], seq[largest] = seq[largest], seq[i]
        max_heapify(seq, largest, n)

def heap_length(seq):
    return len(seq) - 1

def build_heap(seq):
    n = heap_length(seq)
    for i in range(n/2,0,-1):
        max_heapify(seq, i, n)

def sort(seq):
    build_heap(seq)
    heap_size = heap_length(seq)
    for i in range(heap_size,1,-1):
        seq[1], seq[i] = seq[i], seq[1]
        heap_size = heap_size - 1
        max_heapify(seq, 1, heap_size)

    return seq

I am having issues with understanding passing by value or by reference in Python. I have looked at the following question and it seems that I am passing the list by value. My questions is how to return the correctly sorted list either by reference or by value?

arrays are always passed by reference if you want to pass by value use slice

my_func(my_array[:]) #send copy

my_func(my_array) #array is modified inside and changes are reflected in original

I am newbie to understanding Parallel Algorithms. Can someone please explain in simple words [or examples] what Asymptotic Run Time of a Parallel Algorithm means?

Context: If the best known sequential algorithm for a problem π has an asymptotic run time of S(n) and if T(n,p) is the asymptotic run time of a parallel algorithm, then the asymptotic speedup of the parallel algorithm is defined as S(n)/T(n,p) If S(n)/T(n,p) = Ɵ(p), then the algorithm is said to have linear speed up.

The asymptotic run time of a parallel algorithm usually means the time required for an algorithm with p processors to give a correct solution. But, the analysis of an algorithm always depends on the model you are using. A satisfactory answer to your question would become too long. I strongly recommend you to read chapter 27 of Introduction to Algorithms. It is an excellent text to understand the analysis of parallel algorithms. In the first few pages you probably would find the answer to your question.

I have generally seen two versions of the Master theorem.

Version 1:

(from Tim Roughgarden's course)

for recurrence relations of the form,

T(n) <= aT(n/b)+O(n^d)
where a >= 1, b > 1, and d >= 0

there are 3 cases,

case 1: if a=b^d, then T(n) = O(n^dlog(n))
case 2: if a<b^d, then T(n) = O(n^d)
case 3: if a>b^d, then T(n) = O(n^logb(a))

Version 2:

(from CLRS)

for recurrence relations of the form,

T(n) = aT(n/b)+f(n)
where a>=1 and b>1 (both constants)

there are 3 cases:

case 1: if f(n) = O(n^logb(a-ε) for some ε > 0, then T(n) = Θ(n^logb(a))
case 2: if f(n) = Θ(n^logb(a)), then T(n) = Θ(logn*n^logb(a))
case 3: if f(n) = Ω(n^logb(a+ε)) for some ε > 0, and if af(n/b)<=cf(n) for some 
constant c<1 and all sufficiently large n,then T(n) = Θ(f(n))

Question: Which version should one favor and why?

Second version because it does not have a constrain on f(n).

As you see, in the first version your f(n) can be only in a specific form, the second case f(n) is any function, so you can solve recurrences like T(n) = 2 T(n/2) + nlog(n) + n^2 * sin(n)

I wanted to study algorithms and data structures in detail (in the quest of becoming a better programmer :P ), i have been programming for 2-3 years (c++, java, python)

searching on google confused me between two type of books/web-resources

should i go for the books that are language specific like http://www.amazon.com/Data-Structures-Algorithms-Using-Python/dp/0470618299/ref=sr_1_2?ie=UTF8&qid=1320183104&sr=8-2

or a generic book like http://www.amazon.com/Data-Structures-Algorithms-Alfred-Aho/dp/0201000237

these are just examples, the main question is what type of resource should i choose, something language specific or generic? would there be a difference in anyway?

also, suggest a good web-resource/book (free is better) where i can accumulate good amount of knowledge in detail regarding algorithms and data structures. math is no issue

Note: i know there are many similar questions but my doubt is, would your study of algorithms and data structures depend on what programming language you use?

thanks, Shobhit,

There are pluses and minuses to learning about algorithms and data structures in a language-specific way. On the plus side, the examples, exercises, and explanations can be very concrete. Provided you have access to an execution environment for that language, you can experiment on your own with the concepts as you are learning them. This is very powerful.

On the minus side, it is harder to distinguish between the core concepts (e.g., nodes and links in a tree) and the language-specific methods for implementing them (e.g., structs and pointers in C). Other languages may be so different (e.g., Prolog), that the core concepts may be totally unrecognizable if you haven't learned how to separate them from the language-specific aspects of what you have learned. There's also the problem that there are usually lots of language-specific stuff that are entirely a distraction from the core concepts. (malloc/free in C; constructors and destructors in C++, etc., -- unless you're studying memory management algorithms.)

One way to have the benefits of a language-specific presentation and also address its shortcomings is to study the same material presented for two radically different languages. The entire family of Algol-like languages (C, C++, Pascal, Algol, Java, C#, etc.) are basically equivalent for this purpose. I mentioned Prolog before; you might also consider Lisp. Another interesting approach might be a 4GL language like SQL. If you can implement a good balanced tree in a C program and also in an SQL schema and set of queries, then you can be confident that you have mastered the underlying concepts involved in balanced trees.

You should get CLRS to start with. Language agnostic. In terms of algorithms, language doesnt make much difference. It s the theory/concept and how the algorithm works. that s what you need to learn.

Once you learn the concept, you can write the algorithm in any language of your choice.

This is due to the Complexity. Languages doesnt make a difference in terms of algorithms and complexity but the actual algorithm.

In respond to @birryree, Skienna's book, if you ask me is great to prepare for exams. I felt like there were just lot of puzzles. There is also Kleinberg, and computer algorithms. CLRS is the bible.

Most Algorithms and Datastructures book are very language-independent. Some use pseudocode, some don't even have that much code and one of my favourite books used Pascal, of all things.

What is the runtime/memory complexity of the Maximum subarray problem using brute force?

Can they be optimized more? Especially the memory complexity?

Thanks,

Brute force is Omega(n^2). Using Divide and conquer you can do it with Theta(n lg n) complexity. Further details are available in many books such as Introduction to Algorithms, or in various resources on the Web, such as this lecture.

I am looking to implement it in Java, but I need to make specific changes to the code. I do not want to import PriorityQueue, instead for learning purposes I want to reinvent the wheel and do it from scratch but I feel I overcomplicated my code. So I was hoping to get set on the right track.

Maybe here.

http://www.comp.dit.ie/rlawlor/Alg_DS/heaps/PQs%20and%20Heaps.pdf

I guess you can open any book or presentation or tutorial on priority queues. Btw, this is not a complex structure so don't give up at all. I would try implementing a heap, it is quite intuitive and not hard to implement.

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

You might also try some books (the one suggested by Arthur) plus this one.

http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844

5n^5/2 + n^2/5

I tried eliminating the lower order terms and coefficients, not producing a correct answer.

Not sure if I should use logs?

Let f(n) = (5n^5)/2 + (n^2)/5 = (5/2)*n^5 + (1/5)*n^2

The Big O notation for f(n) can be derived from the following simplification rules:

  • If f(n) is a sum of several terms, we keep only the one with largest growth rate.
  • If f(n) is a product of several factors, any constant is omitted.

From rule 1, f(n) is a sum of two terms, the one with largest growth rate is the one with the largest exponent as a function of n, that is: (5/2)*n^5

From rule 2, (5/2) is a constant in (5/2)*n^5 because it does not depend on n, so it is omitted.

Then: f(n) is O(n^5)

Hope this helps. Check Introduction to Algorithms

I do not know how to do either of these problems. However, I did find example code for the AVL tree here: http://users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java

However, I still am unsure how to do this. Can someone please help me out with this?

I need to insert the following keys into an empty AVL tree and show the tree after each insertion. The keys need to be taken as strings of characters not as months. For example, Jul < Jun. DEC, JAN, APR, MAR, JUL, AUG, OCT, SEP, FEB, NOV, MAY, JUN

Insert the following keys into an empty red-black tree and show the tree after each insertion. The keys should be taken as strings of characters not as months. For example, Jul < Jun. DEC, JAN, APR, MAR, JUL, AUG, OCT, SEP, FEB, NOV, MAY, JUN

Go find a whiteboard, bring your textbook and follow the operations exactly as described in your textbook for insertion, deletion etc. Forget about actual code until you understand what is happening. If you don't have a textbook, get this one (possibly at the library) Corman, Leiserson, Rivest and Stein.

No one on StackOverflow is going to be able to help you any better than Googling "How do I implement an AVL Tree?" will until you do this. I promise, whiteboard-fu will help you way more than anything you read on the internet - learn by doing.

For example, strlen() takes about 3*O(n). Why 3? I've wrote a really simple strlen-like function - it works much faster.

int string_len(char s[],int &l)
{ 
 for(l=0;s[l];l++);
return l;
}

Well, some of my friends says, nearly all of string.h algorithms are slower than they should be.

Library functions are generally faster. if not, they are more general than your functions. if not, they are more secure than your.

3O*(n) is a completely wrong expression.

I think all you need is a knowledge base of algorithm analysis, Asymptotic theory and Asymptotic analysis.

also this book will be helpful:

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.

you can find it in: McGraw-Hill - Introduction to algorithms or Amazon.com - Introduction to Algorithms, Third Edition