Forem: Chen Zhang

Fix "aclocal: not found" Error on Ubuntu/Linux

Chen Zhang — Mon, 21 Aug 2023 20:05:45 +0000

Encountered the frustrating "aclocal: not found" error while running a script on Ubuntu/Linux? No worries, here's a quick guide to get you back on track.

Understanding the Error

When you see an error message like the one below while running a script, it means that the 'aclocal' command is missing:

./autogen.sh: 11: aclocal: not found

Step 1: Install Required Packages

To fix this issue, you need to install the necessary packages: autotools-dev and automake. Open a terminal and run:

$ sudo apt-get update
$ sudo apt-get install autotools-dev
$ sudo apt-get install automake

Step 2: Execute the Script Again

Once the packages are installed, run your script again. You should see it executing successfully this time:

$ ./autogen.sh
+ test -d Tools/config
+ aclocal -I Tools/config
+ autoheader
+ automake --add-missing --copy --force-missing
...

Conclusion

The "aclocal: not found" error can be resolved by installing the autotools-dev and automake packages. These packages provide essential tools for the build process and ensure that your scripts run without a hitch.

Happy coding!

Commit Changes to a New Branch with Git

Chen Zhang — Thu, 27 Jul 2023 16:34:05 +0000

To commit local changes to a new branch with git, we can use the following three steps:

Create a new branch

git switch -c new-branch

This will leave our current branch unedited, create a new branch called new-branch, and we still have our uncommitted changes. It’s the parameter -c that tells git to create a new branch with a selected name.

We can use git branch -a command to verify that the new Git branch to be pushed to the remote GitHub repo was indeed created locally.

Set upstream repos

git push -–set-upstream origin new-branch

With a new branch created, the -–set-upstream switch must be run the first time a push is performed. This step tells the new branch which remote repository to use every time it synchronizes its commit history.

Add, Commit, and Push

git add .
git commit -m "First commit on new-branch"
git push origin

Once the remote GitHub repository is set as the upstream target for the new Git branch, push and pull operations can be performed normally with a simple git push origin command.

QuickSelect Algorithm - Find the Kth Smallest Element in an Array

Chen Zhang — Thu, 27 Jul 2023 15:57:54 +0000

What is QuickSelect?

Quickselect is an algorithm for finding the kth smallest element in an unordered list. It's similar to quicksort.

Quickselect works by choosing a "pivot" element and partitioning the data into two groups: one group with elements smaller than the pivot and another group with elements larger. Unlike quicksort, which recursively sorts both groups, quickselect only focuses on the group where the target element should be. This makes it faster on average, although it can be slower in the worst case.

Quickselect is usually done directly on the list, and besides finding the kth smallest element, it also sorts part of the data.

Complexity Analysis

Time complexity: $O (n)$ on average, $O(n^2)$ in the worst case

$T (n) = T (n /2) + O (n) = O (n) + O (n /2) + O (n /4) + ... + O (1) = O (n)$

Space complexity: $O (n)$

Python Implementation

The algorithm can be implemented in Python as follows:

class Solution:
    def findKthSmallest(self, nums, k):
        if not nums or k < 1 or k > len(nums):
            return -1
        return self.partition(nums, 0, len(nums) - 1, k - 1)

    def partition(self, nums, start, end, k):
        # start <= k <= end
        if start == end:
            return nums[k]

        left, right = start, end
        pivot = nums[(start + end) // 2]
        while left <= right:
            while left <= right and nums[left] < pivot:
                left += 1
            while left <= right and nums[right] > pivot:
                right -= 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left, right = left + 1, right - 1

        # left is now bigger than right
        if k <= right:
            return self.partition(nums, start, right, k)
        if k >= left:
            return self.partition(nums, left, end, k)

        return nums[k]

Understanding the Partitioning Choice in Quickselect/Quicksort: Why using `nums[left] < pivot` and `nums[right] > pivot`?

The partition in quickselect/quicksort is designed to accommodate the pivot value by allowing it to be placed either on the left or right side. This flexibility ensures that when a number equals the pivot value (nums[i] == pivot), it can be placed on either side of the partition.

The reason for partitioning the array in this manner is to prevent a situation where all the elements in the array, such as [1, 1, 1, 1, 1, 1] (containing identical elements), end up on a single side. By not assigning the case of nums[i] == pivot to either the left or right side during partitioning, the results of the partitioning process can be somewhat balanced.