1

For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm:

def algo_X(A):
    i = 0
    j = len(A)-1
    while i < j:
        if A[i] != A[j]:
            k = i + 1
            while k < j:
                if A[i] == A[k]:
                    A[k], A[j] = A[j], A[k]
                    break
                elif A[j] == A[k]:
                    A[k], A[i] = A[i], A[k]
                    break
                else:
                    k += 1
            if k == j:
                return False
        i += 1
        j -= 1
    return True

This algorithm returns True if the elements of list passed as argument can be manipulated (swapped) in order to create a new list, which, if we read from the left or from the right, has the same order of elements (palindrome). Else returns False. For example, this list ['a', 'a', 'b', '2', 'b', 'b', ‘2’] can be ordered so that we have a list with the same elements in the same positions, if we read at the same time from the left and from the right: ['a', 'b', '2', 'b', '2', 'b', ‘a’].

Note that this is my interpretation of the algorithm, they did not tell us what this algorithm was supposed to do.

If I am not wrong, this algorithm, in the worst case (and average case), is O(n2), and Ɵ(n) in the best case.


The exercise specifically states that I don't have necessarily to change the list (like in algo_X), but just to return True or False specifying respectively if the list can be made a palindrome or not.

We cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don't "know" exactly the time complexity of those functions. I will edit my question


To make a better algorithm for the worst case, I thought I could use merge sort, whose time complexity is always n*log(n), plus a loop, which would not make the algorithm worse, asymptotically.

This is my merge function for my merge sort function:

def merge(A, B):
    ls = []
    a, b = 0, 0
    while a < len(A) and b < len(B):
        if A[a] <= B[b]:
            ls.append(A[a])
            a += 1
        else:
            ls.append(B[b])
            b += 1
    while a < len(A):
        ls.append(A[a])
        a += 1
    while b < len(B):
        ls.append(B[b])
        b += 1
    return ls

This is my merge sort function:

def merge_sort(A):
    if len(A) < 2:  # basic condition
        return A
    L = merge_sort(A[0:len(A)//2])
    R = merge_sort(A[len(A)//2:])
    return merge(L, R)

Finally, here's my alternative, which returns True, if the list can be made a palindrome, False otherwise:

def better_algo_x(A):
    if len(A) < 2:
        return True
    sorted_A = merge_sort(A)
    odd_groups = 0
    current = sorted_A[0]
    c = 1  # Used to count the number of characters that are equal between them
    for i in range(1, len(sorted_A)):
        if current == sorted_A[i]:
            c += 1
        else:
            if c % 2 == 1:
                odd_groups += 1
            if odd_groups > 1:
                return False
            current = sorted_A[i]
            c = 1
    # for the last group of characters
    if c % 2 == 1:
        odd_groups += 1
    if odd_groups > 1:
        return False
    return True

I have a few questions:

  • Are my functions correct?

  • Is my analysis of the time complexity of the algorithm algo_X correct?

  • Does my better_algo_x do what it is supposed to do?

  • Does it do it in n*log(n) in the worst case?

  • Can I still improve it? How?

  • Do you know (other) better alternatives for algo_X?

Of course, some questions might seem silly, but I would like to hear the opinion of some experts. Of course, I have tried my algorithms.

1

Yes, your analysis and algorithms are correct. But it can be made better by trading off memory for performance IF the amount of possible characters in string is limited (eg. it is not full Unicode). Basically, you can use hash-map to keep count of every character in O(n)*O(1) and then go through the list in O(1) (because the count of all possible characters is always the same). Meaning O(n)*O(1)+O(1) = O(n) in worst case.

def isPalindromic(A):
    hashArray = array.array('I', [0] * 256)

    for ch in A:
        ascii = ord(ch)
        hashArray[ascii] += 1

    notEven = 0
    for count in hashArray:
        if (count > 0 and count % 2 == 1):
            notEven += 1

    return notEven <= 1 #one can be even, then it will be in the center
  • First of all, thanks for the answer! I forgot to say: we cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don't "know" exactly the time complexity of those functions. I will edit my question. – nbro Mar 14 '15 at 11:11
  • @Rinzler My algorithm is not using any such function. Arrays are core construct in any language. – Euphoric Mar 14 '15 at 18:06
  • But you have to import them, and behind the scenes array is a class, with a __init__ method, where some "unknown" operations are performed. Because of this, I should just use known time complexity operations: loops, assignments, accessing elements of a list... – nbro Mar 14 '15 at 18:10
  • @Rinzler With your definition, even using Python, which uses a GC and can do anything while interpreting your code. You should be using C if you really want to be sure operations you are making have defined complexities. Also, "accessing elements of a list" has much less defined complexity than "accessing elements of an array". Hell, in C, you would have to use array, because list is a library structure with not clearly defined complexity. – Euphoric Mar 14 '15 at 18:17
  • Of course I could have used C, but the problem is that my professors decided to use Python, since everybody in our class knows Python. They simply said that we should not use libraries (apart from sys to read some input). – nbro Mar 14 '15 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.