Entity Relationship Diagram Drawing Tool

I'm using Mac OS X Lion v10.7 and the program I'm using to draw ER diagram is Dia (or download it from here). It's open source and support all platforms (Windows, Mac, and Linux). For the current version of Mac OS X I'm using, it asked me to install additional program called XQuartz (or you can download it from here) and re-login before I could use Dia.

Alternatively, you can use this online tool https://www.draw.io/

How I download the old version of OSX

The old versions of OSX such as Lion v10.7 is available on AppStore but you have to purchase it. I download it free from here

Create Clonezilla Live Partition (not a whole USB drive)

I used Tuxboot from within Ubuntu to create Clonezilla Live USB drive. Then, I have an external hard disk drive with multiple partitions. I used Disk Utility in Mac OSX Lion to clone the Clonezilla Live USB drive to one of the partitions but it failed.

Then, I used Carbon Copy Cloner to clone the entire USB drive to the partition instead and it worked.

Checking for Windows update takes forever

In Control Panel, I clicked the Check for Updates button and it took forever. According to https://www.youtube.com/watch?v=WFfc22x3I_s, there are 4 methods. I think the 4th method is the best but it might be affected by the previous methods too so you might need to do all the methods orderly.

1. Run Command Prompt as Adminstrator and execute the following command:
> ipconfig /flushdns

2. Download and install Windows Client Update based on your machine architecture (32 bits or 64 bits). Type the following command in the Comand Prompt to see it:
> wmic os get osarchitecture

3. Stop the windows update service by running the following command adn then download and install Windows Update Diagnostic
> net stop wuauserv

4. Install Windows update offline by downloading it from here http://download.wsusoffline.net/ and run it then:
- Under Windows tab, select "x64 Global (Multilingual updates)" checkbox
- For Options checkbox, select "Include Service Packs" and "Include Windows Defender definitions"
And then click Start button. It will start Command Prompt program and download the necessary updates.
- Go to the installation files again and then client directory and run UpdateInstaller.exe. When the program starts, check Automatic reboot and recall checkbox and click Start button.

Install Khmer Unicode Keyboard on Mac OSX Lion v10.7

Installing Khmer Unicode Keyboard

Khmer font was added by default on Mac OSX Lion v10.7 but you have to enable it by go to
- System Preferences then Language & Text
- Under Input Sources tab, check Khmer from the "Select input sources to use." pane.

Or you can also download the keyboard layout and install it from Cambosastra website (read its instruction).  

Problems

1. The Khmer keyboard layout come within OSX maps 'F' key to letter 'ផ' instead of 'ថ' so you should use the layout from Cambosastra team instead by selecting 'Khmer V2' in Keyboard preferences.

2. In Microsoft Word, the Apple's Khmer font named "Khmer Sangam MN" is broken; It does not display correctly when you type. You should install another font such as Koh Santepheap. You can download it from here too.

Create shortcut key to switch between languages

- Go to System Preferences then Keyboard and click on Keyboard Shortcuts tab
- Then, click on Keyboard & Text at the right sidebar and check "Select the previous input source" and then modify its shortcut key to Shirt + Command + Space. Then, make sure "Select next source in Input menu" is unchecked. Then, change the shortcut

- After that, click on Spotlight then check "Show Spotlight search field" and change its shortcut key to Command + Space and make sure "Show Spotlight window" is unchecked

References

- http://www.cambosastra.org/how-to-set-up-khmer-unicode-for-mac/

Depth First Search, Breadth First Search and Uniform Cost Search Algorithms

Before knowing Uniform Cost Search (UCS) algorithm, we should know about Depth First Search (DFS) and Breadth First Search (BFS).

DFS is an algorithm to search a graph for a path from one vertex (node) to another. It just tells you if there is a path or not, nothing more. There can be many paths from one vertex to another. It will just choose one that it meets first; it doesn't care about how long the path is. The pseudocode to implement this algorithm uses an array variable to store the nodes that have been already explored so that the search won't go back to the already explored nodes. We still another (Map) variable to trackback the path or to know the parent or preceding node of the current node. There can be more than parent or preceding nodes but there is only one that the search crosses to reach the current node.

BFS is also an algorithm to search for a path in a graph or tree. It is based on DFS but it can find the shortest path. In processing, DFS uses stack data structure but BFS uses queue data structure. In the pseudocode from my teacher below looks like it does not have anything to do with path cost. And the only difference between it and DFS's pseudocode is frontier variable uses queue, not stack.

UCS use priority queue to store the explored nodes and their cumulative path costs so that it can find the shortest path. I'm not sure how BFS is different from UCS. The algorithm below is from my teacher. In the third line from top and another third line from bottom, it should have said cumulative PATH-COST instead of only PATH-COST.

My homework is to implement DFS, BFS and then UCS in R programming. The source code can be found here https://github.com/vathanakmao/ai-assignments

Heapsort Algorithm

What is heap?

Heap is an untidy pile of mass of things, for example, a heap of clothes/rubbish. In data structure, a heap is tree-based data structure that satisfies the heap property: if A is a parent of node B then the key (the value) of node A is ordered with the respect of the key of node B with the same ordering applying to the heap.

Heap can be divided into 2 categories: max heap and min heap. In max heap, the max-heap property means that the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In min heap, the min-heap property means that the keys of parent nodes are always less than or equal to those of the children and the lowest key is in the root node.

Algorithm

The items are stored in an array but we logically convert it to a tree.

The below algorithm of how to find the indices of the left and right children of a (parent) node. For example, node 16 has two children, node 14 and node 10.

The max-heapify operation (function) makes sure the child nodes are not greater than their parents but it doesn't go through all the nodes, just one path straight down to the children. We need another function to call this function in a loop (build-max-heap operation).

Below is the example of how max-heapify operation make change to the tree.



The build-max-heap operation (function) makes sure all nodes in the binary tree satisfy the max-heap property. In other words, the keys of child nodes must be less than or equals to the key of parent node.



Below is the example of how the build-max-heap operation make change to the tree.

























The heapsort() function below will sort the tree completely.



Below is the example of how the tree is sorted step by step.




I have implemented it in Java for learning purpose. You can find the source code here: https://github.com/vathanakmao/sort-algorithms.git





References
Book: Introduction to Algorithms (3rd edition), Thomas H. Cormen, Charles E. Leiserson, ...