Counting Comparisons in QuickSort [Java]

Compute the total number of comparisons used to sort the given input file by QuickSort.

(Programming Question from coursera.org)

Download Input Text File here -> QuickSort

The file contains all of the integers between 1 and 10,000 (inclusive) in unsorted order (with no integer repeated). The integer in the ith row of the file gives you the ith entry of an input array.

Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we’ll ask you to explore three different pivoting rules.
You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add m−1 to your running total of comparisons. (This is because the pivot element will be compared to each of the other m−1 elements in the subarray in this recursive call.)

WARNING: The Partition subroutine can be implemented in several different ways, and different implementations can give you differing numbers of comparisons. For this problem, you should implement the Partition subroutine as it is described in the video lectures (otherwise you might get the wrong answer).

DIRECTIONS FOR THIS PROBLEM:

For the first part of the programming assignment, you should always use the first element of the array as the pivot element.

 

Code:-


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;


public class Comparisons {
	
	static long noOfComparisons;
	public static void main(String args[]) throws IOException {

		BufferedReader bfr = new BufferedReader(new FileReader("QuickSort.txt"));
		int n =10000;
		int[] A = new int[n];
		String str = bfr.readLine();
		int i = 0;
		while (str != null) {
			A[i] = Integer.parseInt(str);
			i++;
			str = bfr.readLine();
		}
		
		QuickSort(A,0,A.length-1);
		
		System.out.println(noOfComparisons);
		
	}

	private static void QuickSort(int[] a, int l, int r) {
		
		int pivot;
		if(r>l){
			add(r-l);
		pivot =Partition(a,l,r);
		
		QuickSort(a, l, pivot-1);
		QuickSort(a, pivot+1, r);
		}
	}

	private static void add(int i) {
		noOfComparisons+=i;
		
	}

	private static int Partition(int[] a, int l, int r) {

		
		int p=a[l];
		int i =l+1;
		
		for(int j=l+1;j<=r;j++){
			if(a[j]

Output: 162085

Problem2:
Use Last element as pivot .

Solve this problem using same Partition function by swapping first and last element and then using same first element as pivot.

.......
.......

private static int Partition(int[] a, int l, int r) {
		
		Swap(a,l,r);
		
		int p=a[l];
		int i =l+1;
.......
.......

Output: 164123

Counting Inversions in Java

Given array A[1… n], for every i < j, find all inversion pairs such that A[i] > A[j]
(i, j form an inversion if A[i] > A[j])

Example
2 4 1 3 5
The sequence 2, 4, 1, 3, 5 has three inversions (2,1), (4,1), (4,3).

Problem

Find the number of inversions in the file given (every row has a single integer between 1 and 100,000) . Assume your array is from 1 to 100,000 and ith row of the file gives you the ith entry of the array.

Code– O(n log n)

 

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Inversions {
	public static void main(String args[]) throws IOException {

		BufferedReader bfr = new BufferedReader(new FileReader("input.txt"));
		int n = 100000;
		int[] A = new int[n];
		String str = bfr.readLine();
		int i = 0;
		while (str != null) {
			A[i] = Integer.parseInt(str);
			i++;
			str = bfr.readLine();
		}

		Pair a = sortAndCount(A);
		System.out.println(a.x);
	}

	private static Pair sortAndCount(int[] a) {
		if (a.length == 1) {
			return new Pair(a, 0);
		} else {
			int[] leftArray = new int[a.length / 2];
			System.arraycopy(a, 0, leftArray, 0, leftArray.length);
			int[] rightArray = new int[a.length - leftArray.length];
			System.arraycopy(a, leftArray.length, rightArray, 0,
					rightArray.length);
			Pair x = sortAndCount(leftArray);

			Pair y = sortAndCount(rightArray);
			Pair z = MergeAndCountSplitInv(x.Array, y.Array, a.length);

			return new Pair(z.Array, x.x + y.x + z.x);
		}

	}

	private static Pair MergeAndCountSplitInv(int[] B, int[] C, int n) {
		long total = 0;
		int[] D = new int[n];
		int i = 0;
		int j = 0;
		for (int k = 0; k < n; k++) {
			if (j == C.length || i != B.length && B[i] < C[j]) {
				D[k] = B[i];
				i++;
			} else if (i == B.length || j != C.length && C[j] < B[i]) {
				D[k] = C[j];
				j++;
				total += B.length - i;
			}
		}
		return new Pair(D, total);
	}
}

class Pair {
	Pair(int[] A, long l) {
		this.Array = A;
		this.x = l;
	}

	public int[] Array;
	public long x;
}


Download Input File
Output : 2407905288

Delete Folder Options menu in Windows Explorer

Steps to Disable Tools->Folder Options in Windows explorer.

(Can be used to prevent access to various options available)

  • Open Registry . (Type “regedit” in Run)
  • Go to  HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer
  • Select and open NofolderOptions Dword and set Value to 1

  • Log Off /Restart Windows

 

If  “NofolderOptions”  Dword is not present then create a new DWORD value with following settings:

Name:NoFolderOptions

Type:REG_DWORD

Data: 1 (disable) /0 ( enable)

 

This removes folder options for User. To disable for all users edit key in HKEY_LOCAL_MACHINE.

 

Get You Tube’s New Layout before Official release.

You tube is changing its layout but the  new design has not been released officially.

You can get new design as follows:

For Chrome:

  • Go to YouTube Homepage
  • Press Ctrl+Shift+J to open Developer Tools
  • Click on the “Console” Tab and paste the following
document.cookie="VISITOR_INFO1_LIVE=ST1Ti53r4fU";
  • Press “Enter” and reload YouTube homepage to get new Layout

For Firefox:

document.cookie="VISITOR_INFO1_LIVE=ST1Ti53r4fU";
  • Press “Enter” and reload YouTube homepage to get new Layout.

 

New Layout

 

Changing Language / Locale in CentOS

CentOS supports multiple languages

To change language in CentOS

  • Go to System>Administration>Language
  • Provide root password if not logged in as root
  • Select a language and click OK

You can also change language from login screen.

To start Language Selection tool from Terminal type

system-config-language

and provide root password.

Changing Locale

  • To see list of available locales type following in terminal

locale -a

  • Now to change the locale type

export LANG=<some_locale>

For Example to change to Japanese locale do the following

export LANG=ja_JP.utf8

Type locale in terminal to confirm the change.

This sets the locale to Japanese for CURRENT CONSOLE only.

Applications started from this console will open in Japanese locale, If you open a new console or start application from somewhere else then it will open in default system Language.

***glibc detected*** malloc(): memory corruption: 0x0916c100 *** error

 

 

Memory corruption error comes when you are doing something on memory which is not available.

Like Writing,Reading and freeing.

Some common examples are

  • Reading/writing to memory out of the bounds of a dynamically allocated array
  • Attempting to write a memory which was never allocated
  • Attempting to free a memory already freed
  • Writing to a freed memory
  • Writing to an unallocated memory

Fix:

  • Check the above common mistakes
  • Check all malloc() expressions in your code
  • Check if data is copied to an allocated memory whose allocated length is less than data(ex. in memcpy() statements)
  • This error usually comes while allocating memory to arrays like
pointer = (char *) malloc(strlen(Array_B));

the above statement overflows by 1 byte. You should use-

pointer = (char *) malloc(strlen(Array_B)+1);

to avoid any memory corruptions.

 

 

Eclipse hanging on startup, Repair Corrupt Workspace

 

Eclipse can hang on start up due to various reasons like system crash , Updating a plugin etc. which corrupts the workspace.

You can check .log file (in your <workspace>/.metadata directory) for error logs like

!MESSAGE The workspace exited with unsaved changes in the previous session;
refreshing workspace to recover changes

 

Here are few quick fixes that may work (Make a backup of your Workspace and Try each step independently)

  • Removing .snap File
  1. Open <workspace>\.metadata\.plugins\org.eclipse.core.resources directory
  2. Remove .snap file in the directory
  3. Restart Eclipse

 

  • Remove .indexes Folder
  1. Remove the <workspace>\.metadata\.plugins\org.eclipse.core.resources\.root\.indexes directory
  2. Restart Eclipse

 

  • Remove “org.eclipse.ui.workbench”  folder
  1. Open <workspace>\.metadata\.plugins directory
  2. Remove “org.eclipse.ui.workbench” folder
  3. Restart Eclipse

 

If nothing works then you can start Eclipse with -clean option and import each project into new workspace.

 

[hr]

Install Java Plugin on Firefox ,CentOS [Linux]

Steps to manually install java plugin on firefox in CentOS and other Linux Distributions

 

  • Download JRE from Here
  • Extract the download file (See tutorial for .bin files)
  • Go to ‘plugins‘ directory in mozilla folder (/usr/lib/mozilla/plugins)
cd /usr/lib/mozilla/plugins
  • Create a Symbolic Link to libnpjp2.so (<JRE>/lib/i386/libnpjp2.so)
ln -s <JRE>/lib/i386/libnpjp2.so)

where <JRE> is path to your extracted JRE directory.

Remove any old symbolic links of java plugins present in plugins directory like libjavaplugin-oji.so

rm libjavaplugin-oji.so
  • Restart Firefox
  • Check if JRE has been properly installed from this Test Page (you can also type about:plugins in address bar and check if Java Plugin is installed)

Open .djvu file on CentOS (Linux)

DjVu is a file format designed primarily  to store scanned documents . It compresses documents to smaller size as compared to PDF files.

You can convert files to DjVu format with this  online tool.

Following Steps will help you install djvu viewer on CentOS and other Linux Distributions with yum install command.

To install djvu with yum you must have rpmforge.repo file in /etc/yum.repos.d/ directory.

If the file is not present then make a file named rpmforge.repo, open it with Text Editor and paste the following in it.

 

# Name: RPMforge RPM Repository for Red Hat Enterprise 5 - dag
# URL: http://rpmforge.net/
[rpmforge]
name = Red Hat Enterprise $releasever - RPMforge.net - dag
#baseurl = http://apt.sw.be/redhat/el5/en/$basearch/dag
mirrorlist = http://apt.sw.be/redhat/el5/en/mirrors-rpmforge
#mirrorlist = file:///etc/yum.repos.d/mirrors-rpmforge
enabled = 1
protect = 0
gpgkey = file:///etc/pki/rpm-gpg/RPM-GPG-KEY-rpmforge-dag
gpgcheck = 1

 

Now install djvu viewer with following command

yum install djvulibre.i386

 

If the above does not work then search for djvu package with

yum search djvu

and install the library present with yum install.

Moving WordPress to new Host and Domain

[toc]

Changing Settings

  • Go to Administration Screen of your wordpress
  • Select Settings and click “General”
  • Change the “WordPress Address(URL)” and “Site Address(URL)” to your new domain

Downloading Files

  • Download all files/folders from your wordpress Directory using any method like
  1. If you have FTP Access to your server then download files using ftp clients like FileZilla
  2. Using cPanel’s FileManager or other FileManger option provided with your Host. Create an archive and download whole directory containing wordpress files

Database Backup

Editing wp-config.php

  • Open wp-config.php in your downloaded wordpress directory with text editor like Notepad++
  • Change the following to new settings of your web-host
/** The name of the database for WordPress */
define('DB_NAME', 'wordpress');

/** MySQL database username */

define('DB_USER', 'root');

/** MySQL database password */

define('DB_PASSWORD', 'root');

/** MySQL hostname */

define('DB_HOST', 'localhost');
  • Save the file

Uploading Files

  • Upload the files to your web-host using FileZilla or
  • Create an Archive and upload using FileManager provided by web-host
  • Extract the files (You can delete the archive after extracting)

Fixing Broken Links

  • After moving your wordpress blog/site you will notice that images,other media or attachments are broken and point to your old URLs
  • Easiest way to fix broken links after moving wordpress is by using Velvet Blues Update URLsPlugin. You just need to enter Old url,New Url and it will automatically fix all the broken links.
  • Another Method to do the same is using Search and Replace Plugin
  • If nothing works you can open the .sql file downloaded after backup and open it with text editor like Notepad++. Now Find and Replace all the  occurrences of Old Url with your new Url .