Tuesday, May 25, 2010

Laporan ISA(Instruction Set Architecture)

Laporan mengenai mikro instruksi dalam level ISA dapat didownload disini
READ MORE - Laporan ISA(Instruction Set Architecture)

Thursday, May 20, 2010

Mikroinstruksi ISA (MIC-1)

Dalam mikro instruksi ini kita dapat memahami prinsip dan cara kerja mikro instruksi pada level arsitektur mikro, dalam sebuah mikroprosesor.

Level arsitektur mikro berada diatas level logika digital, arsitektur ini akan mengimplementasikan level ISA(Instruction Set Architecture). Pada level ISA akan ditemukan kumpulan register yang membentuk memori lokal, serta rangkaian ALU(Aritmethmetic Logic Unit) yang mampu menjalankan operasi-operasi aritmatika sederhana.

Secara umum bentuk dari data flow arsitektur mikro adalah

Untuk mengetahui langkah-langkah dalam ISA dapat digunakan simulasi dengan java platform yaitu mic-1
untuk pemakaiannya: 
- Extract file rar 
- Atur posisi dari folder mic-1 dan folder JVM pada directory C:
- Buka folder mic-1 dan jalankan simulator-mic1win.exe
- Setelah extrack buka file env.bat dengan notepad
- Edit isi file untuk directorinya seperti berikut:
@echo off
rem
rem  env.bat
rem

rem  This batch file sets the environment variables necessary for running
rem  the mic1 software.

rem  1) comment out the following 4 commands

echo   NOTE: YOU NEED TO EDIT THE FILE ENV.BAT BEFORE YOUR mic1
echo   SOFTWARE will WORK CORRECTLY.

pause                         
goto end

rem  2) Set the path to point to the bin directory of the JDK

path c:\JVM\bin;%path%

rem  3) Set the classpath to point to the classes.zip file from the mic1
rem     distribution

set CLASSPATH=c:\mic-1\classes.zip

:end





Download  mic-1

Java development kit 1.1.8
READ MORE - Mikroinstruksi ISA (MIC-1)

Sunday, May 16, 2010

Laporan Filter

Laporan Elektronika II tentang filter
download
READ MORE - Laporan Filter

Laporan Memori (1)

Laporan Organisasi dan Arsitektur Komputer tentang memori (1)
download
READ MORE - Laporan Memori (1)

Monday, May 10, 2010

Know your Self To Get What you Want

Emotion is created by motion 
anthony robbius
Emosi yang ada pada manusia dan tergambarkan dalam perilaku sehari-hari merupakan hasil dari aktivitas yang dilakukan. Dan untuk mengendalikan dan mengatur emosi maka kita juga perlu untuk mengatur dan mengendalikan aktivitas sehari-hari agar dapat membuat emosi yang positif.

Your outer world is the reflection of your inner world
– joe vitule
Sesuatu yang terlihat dari seseorang(perilaku, sikap, sifat) adalah cerminan pribadi diri yang telah terbentuk akibat aktivitas dan informasi yang telah masuk ke dalam pikiran.

Cara kerja pikiran manusia
RAS(reticular activating system) adalah filter dari informasi yang masuk ke pikiran sehingga tidak semua informasi masuk begitu saja ke dalam pikiran.
Pikiran manusia mampu memilah informasi yang masuk memalui filter yaitu moral dan kesadaran diri. Sehingga tidak semua informasi dapat masuk begitu saja ke dalam otak, sehingga kadang kita begitu mudahnya melupakan suatu hal. Selain itu pikiran memiliki kapasitas memori bawah sadar yang lebih besar dibandingkan memori sadar. Sering kali kita belajar untuk melakukan sesuatu dengan menggunakan pikiran sadar kita namun amat mudah untuk terlupakan. Namun begitu informasi tentang apa yang kita pelajari itu masuk ke dalam memori pikiran bawah sadar kita maka informasi itu akan tersimpan dan kita tanpa sadar dapat menggunakan informasi itu begitu saja tanpa perlu berpikir terlebih dahulu. Contoh saat belajar mengendarai motor/ mobil akan sangat sulit tapi begitu bisa maka akan sangat mudah dilakukan.

The most important part of your prayer is what you fell not is what you say 
pence pillgrim
Saat berdoa dan menginginkan sesuatu kita harus benar-benar menginginkannya dan bersungguh-sungguh disertai perasaan yang kuat sehingga akan menimbulkan semangat untuk dapat benar-benar mendapatkan apa yang kita ingikan

Fokus pada solusi bukan fokus pada masalah
Untuk dapat menyelesaikan suatu permasalahan yang terjai haruslah fokus pada solusi bukan pada masalah. Pikirkan bagaimana mengatasi masalah bukannya berpikir masalah yang semakin berlarut-larut dan akan menjerumuskan diri.
The law of attract = like attract like
Dalam kehidupan manusia berlaku hukum diatas dimana sesuatu yang sama akan cenderung bersama-sama atau menarik yang sama untuk berkumpul dan berinteraksi.

FEAR = False Evidence Appear Real
Khawatir terhadap sesuatu yang tidak terjadi(tidak nyata). Khawatir seperti ini hendaknya dihilangkan agar dapat berpikir cerah untuk masa depan tanpa menghawatirkan sesuatu yang tidak nyata/ hanya kekhawatiran semata. Orang akan berhasil jika mampu dan berani mengalahkan ketakutan dan kekhawatiran dalam dirinya.

Untuk mencapai tujuan/ keinginan
Do'a + yakin
Do'a disertai usaha(inspire action), ikhlas, dan tawakal
Yakin yaitu tenang, sabar, fokus, dan bersyukur

 
Source : kuliah kewirausahaan
READ MORE - Know your Self To Get What you Want

Monday, May 3, 2010

IMPROVING QUICKSORT(HOURS 14)


Quicksort emang dapat mengurutkan data dengan cepat namun quicksort akan kurang efisien jika dihadapkan pada data yang ter-invers(terbalik) ataupun dengan data yang jumlahnya sedikit, karena itu diperlukan peningkatan kinerja dari quicksort agar dapat menangani masalah tersebut serta mempercepat kinerja quicksort.
Data terbalik

Masalah pada data terbalik adalah pada pivot. Pada bab sebelumnya pivot yang dipilih adalah indeks terbesar dari array data, masalah ini dapat ditangani dengan memilih pivot pada median(tengah) data. Sehingga diperoleh 2 bagian yang lebih mudah dalam pembagian selanjutnya.
Median-of-Three Partitioning
  • Pilih nilai indeks awal, tengah, dan akhir
  • Urutkan ketiga nilai tersebut
  • Pilih median dari 3 nilai tersebut sebagai pivot
  • Lakukan quicksort
Implementasinya dalam c++

//quickSort2.cpp

//demonstrates quick sort with median-of-three partitioning

#include <iostream>

#include <vector>

#include <cstdlib> //for random numbers

#include <ctime> //for random numbers

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double>(theVect); //vector of doubles

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) : nElems(0) //constructor

{

theVect.resize(max); //size the vector

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theVect[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theVect[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort array

{

recQuickSort(0, nElems-1); //call recursive sort

}

//--------------------------------------------------------------

void recQuickSort(int left, int right) //recursive sort

{

int size = right-left+1;

if(size <= 3) //manual sort if smallmanualSort(left, right);

else //quicksort if large

{

double median = medianOf3(left, right);

int partition = partitionIt(left, right, median);

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

} //end recQuickSort()

//--------------------------------------------------------------

double medianOf3(int left, int right)

{

int center = (left+right)/2;

//order left & center

if( theVect[left] > theVect[center] )

swap(left, center);

//order left & right

if( theVect[left] > theVect[right] )

swap(left, right);

//order center & right

if( theVect[center] > theVect[right] )

swap(center, right);

swap(center, right-1); //put pivot on right

return theVect[right-1]; //return median value

} //end medianOf3()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theVect[dex1]; //A into temp

theVect[dex1] = theVect[dex2]; //B into A

theVect[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

//partition a range

int partitionIt(int left, int right, double pivot)

{

int leftMark = left; //right of first elem

int rightMark = right - 1; //left of pivot

while(true)

{

while( theVect[++leftMark] < pivot ) //find bigger

; // (nop)

while( theVect[--rightMark] > pivot ) //find smaller

; // (nop)

if(leftMark >= rightMark) //if pointers cross, break; // partition done

else //not crossed, so

swap(leftMark, rightMark); //swap elements

} //end while(true)

swap(leftMark, right-1); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void manualSort(int left, int right)

{

int size = right-left+1;

if(size <= 1)

return; //no sort necessary

if(size == 2)

if( theVect[left] > theVect[right] )

swap(left, right);

return;

}

else //size==3, so 3-sort left, center (right-1) & right

{

if( theVect[left] > theVect[right-1] )

swap(left, right-1); //left, center

if( theVect[left] > theVect[right] )

swap(left, right); //left, right

if( theVect[right-1] > theVect[right] )

swap(right-1, right); //center, right

}

} //end manualSort()

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

time_t aTime;

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create the array

srand( static_cast<unsigned>(time(&aTime)) ); //seed randoms

for(int j=0; j<maxSize; j++) //fill array with

{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main()

Handling Small Partitions

Algoritma quicksort standar tidak dapat bekerja mengurutkan bagian dengan 3 data atau lebih sedikit dari itu. Dalam hal ini jumlah tersebut disebut dengan cutoff point


Menggunakan insertion sort untuk bagian data yang kecil

Insertion sort dapat dipakai untuk menangani bagian data yang kecil dimana insertion sort akan dipakai saat bertemu dengan cutoff point.
  • Insertion sort dilakukan sebagai bagian dari quicksort setelah mencapai data sedikit(cutoff point)
  • Metode:
  1. Quicksort dilanjutkan insertion sort untuk data sedikit
  2. Quicksort kemudian sort dihentikan untuk data sedikit( mencapai cutoff point). Lalu dilakukan insertion sort secara keseluruhan
Listing untuk mengangani data kecil

//quickSort3.cpp

//demonstrates quick sort; uses insertion sort for cleanup

#include <iostream>

#include <vector>

#include <cstdlib> //for rand()

#include <ctime> //for rand()

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double> theArray; //array theArray

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) //constructor

{

theArray.reserve(max); //change size of vector

nElems = 0; //no items yet

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theArray[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theArray[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort the array

{

recQuickSort(0, nElems-1);

// insertionSort(0, nElems-1); //(another option)

}

//--------------------------------------------------------------

void recQuickSort(int left, int right) //recursive quicksort

{

int size = right-left+1;

if(size < 10) //insertion sort if small

insertionSort(left, right);

else //quicksort if large

{

double median = medianOf3(left, right);

int partition = partitionIt(left, right, median);

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

} //end recQuickSort()

//--------------------------------------------------------------

double medianOf3(int left, int right)

{

int center = (left+right)/2;

//order left & center

if( theArray[left] > theArray[center] )

swap(left, center);

//order left & right

if( theArray[left] > theArray[right] )

swap(left, right);

//order center & right

if( theArray[center] > theArray[right] )

swap(center, right);

swap(center, right-1); //put pivot on right

return theArray[right-1]; //return median value

} //end medianOf3()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theArray[dex1]; //A into temp

theArray[dex1] = theArray[dex2]; //B into A

theArray[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

int partitionIt(int left, int right, double pivot)

{

int leftMark = left; //right of first elem

int rightMark = right - 1; //left of pivot

while(true)

{

while( theArray[++leftMark] < pivot ) //find bigger

; // (nop)

while( theArray[--rightMark] > pivot ) //find smaller; // (nop)

if(leftMark >= rightMark) //if pointers cross,

break; // partition done

else //not crossed, so

swap(leftMark, rightMark); //swap elements

} //end while(true)

swap(leftMark, right-1); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void insertionSort(int left, int right) //insertion sort

{

int in, out;

//sorted on left of out

for(out=left+1; out<=right; out++)

{

double temp = theArray[out]; //remove marked item

in = out; //start shifts at out

//until one is smaller,

while(in>left && theArray[in-1] >= temp)

{

theArray[in] = theArray[in-1]; //shift item to right

--in; //go left one position

}

theArray[in] = temp; //insert marked item

} //end for

} //end insertionSort()

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create array

time_t aTime; //seed random numbers

srand(static_cast<unsigned>( time(&aTime) ));

for(int j=0; j<maxSize; j++) //fill array with

{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main() 


Sumber : Kuliah Logika dan Pemrograman Sistem II

READ MORE - IMPROVING QUICKSORT(HOURS 14)

QUICKSORT (HOURS13)


Pada bab sebelumnya telah dibahas mergesort dimana dapat mengurutkan dengan cepat namun memerlukan ruang lebih banyak untuk melakukan pengkopian array-array yang akan diurutkan. Sehingga memerlukan banyak memori. Sementara quicksort sama cepat dengan mergesort hanya keunggulannya memerlukan sedikit memori.
Inti dari quicksort

  • data dibagi 2 bagian dengan 1 titik bagi
  • mengulangi pembagian pada masing masing bagian
Proses mengurutkan(mergesort)

  • bagi data menjadi 2 dengan jumlah sama
  • urutkan masing-masing bagian
  • lakukan penggabungan(merge)
Partition

quicksort bekerja dengan membagi data menjadi bagian-bagian(partition) dan proses ini dilakukan berulang-ulang pada masing-masing bagian. Untuk melakukan partition dimulai dengan memilih titik/nilai acuan(pivot) untuk kemudian membandingkan data dengan pivot tersebut sehingga diperoleh 2 bagian data yaitu data yang lebih besar dari pivot dan data yang lebih kecil dari pivot.


Setelah didapat 2 bagian seperti pada gambar diatas maka masing-masing bagian akan dibagi lagi dengan menentukan pivot pada masing masing bagian sehingga data akan terurut.

Proses program dasar quicksort

  1. tentukan pivot sebagai index bagain terbesar
  2. Ki(data bagian terkiri) digeser ke kanan sampai ki > pivot
  3. Ka(data bagian terkanan) digeser ke kiri sampai ka < pivot
  4. Jika ka > ki maka nilai di ka dan ki ditukar
Proses jalannya quicksort
  1. pivot array 70, data dibandingkan
  2. diambil bagian kiri pivot 50, data dibandingkan
  3. diambil pivot 40, data dibandingkan
  4. diambil pivot 20, data dibandingkan
  5. diambil bagian kanan
  6. diambil pivot 110, data dibandingkan
  7. diambil pivot 100, data dibandingkan
  8. diambil pivot 80, data dibandingkan
  9. didapatkan array yang terurut
listing quicksort

//quickSort1.cpp

//demonstrates simple version of quick sort

#include <iostream>

#include<vector>

#include<cstdlib> //for random numbers

#include<ctime> //for random numbers

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double>(theVect); //vector of doubles

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) : nElems(0) //constructor

{

theVect.resize(max); //size the vector

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theVect[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theVect[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort array

{

recQuickSort(0, nElems-1); //call recursive sort

}

//-------------------------------------------------------------- void

recQuickSort(int left, int right) //recursive sort

{

if(right-left <= 0) //if size <= 1, return; // already sorted

else //size is 2 or larger

{

double pivot = theVect[right]; //rightmost item

//partition range

int partition = partitionIt(left, right, pivot);

recQuickSort(left, partition-1); //sort left side

recQuickSort(partition+1, right); //sort right side

}

} //end recQuickSort()

//--------------------------------------------------------------

int partitionIt(int left, int right, double pivot)

{

int leftMark = left-1; //left (after ++)

int rightMark = right; //right-1 (after --)

while(true)

{ //find bigger item

while( theVect[++leftMark] < pivot )

; // (nop)

//find smaller item

while(rightMark > 0 && theVect[--rightMark] > pivot)

; // (nop)

if(leftMark >= rightMark) //if pointers cross,

break; // partition done

else //not crossed, so

swap(leftMark, rightMark); // swap elements

} //end while(true)

swap(leftMark, right); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theVect[dex1]; //A into temp

theVect[dex1] = theVect[dex2]; //B into A

theVect[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

time_t aTime;

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create array

srand( static_cast<unsigned>(time(&aTime)) ); //seed randoms

for(int j=0; j<maxSize; j++) //fill array with{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main()

Output

A=69 0 70 6 38 38 24 56 44 26 73 77 30 45 97 65

A=0 6 24 26 30 38 38 44 45 56 65 69 70 73 77 97


 

sumber : Kuliah Logika dan Pemrograman Sistem II
READ MORE - QUICKSORT (HOURS13)

Applied Recursion(Hours 12) part 2

Mergesort
Teknik pengurutan mergesort lebih cepat dan efisien dibandingkan dengan bubble sort dan insertion sort. Insertion sort dan bubble sort memerlukan waktu O(N2) sedangkan mergesort memerlukan waktu O(N*logN). Sebagai contoh jika N adalah 10.000 data yang diurutkan maka N2 adalah 100.000.000 sementara N*logN hanya 40.000. jika sorting data ini memerlukan waktu 40 detik dengan mergesort maka dengan insertion sort akan memerlukan waktu hampir 28 jam.
Penggabungan 2 array
Inti dari mergesort adalah menggabungkan 2 buah array yang telah terurut dimana array A dan B akan digabungkan menjadi array C dengan data yang telah terurut
Langkah-langkah mergesort
Langkah ke 9 dan ke 10 kosong karena array B telah habis untuk dibandingkan dengan array A. Maka setelahnya sisa array A hanya langsung dipindah ke array C.

Listing mergesort
//merge.cpp
//demonstrates merging two arrays into a third
#include <iostream>
using namespace std;
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void merge( int[], int, int[], int, int[] );
void display(int[], int); //prototypes
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
int main()
{
int arrayA[] = {23, 47, 81, 95}; //source A
int arrayB[] = {7, 14, 39, 55, 62, 74}; //source B
int arrayC[10]; //destination
merge(arrayA, 4, arrayB, 6, arrayC); //merge A+B––>C
display(arrayC, 10); //display result
return 0;
} //end main()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void merge( int arrayA[], int sizeA, //merge A and B into C
int arrayB[], int sizeB,
int arrayC[] )
{
int aDex=0, bDex=0, cDex=0;
while(aDex < sizeA && bDex < sizeB) //neither array empty
if( arrayA[aDex] < arrayB[bDex] )
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] = arrayB[bDex++];
while(aDex < sizeA) //arrayB is empty,
arrayC[cDex++] = arrayA[aDex++]; //but arrayA isn't
while(bDex < sizeB) //arrayA is empty,
arrayC[cDex++] = arrayB[bDex++]; //but arrayB isn't
} //end merge()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––-
void display(int theArray[], int size) //display array
{
for(int j=0; j<size; j++)
cout << theArray[j] << " ";
cout << endl;
}
Output
7 14 23 39 47 55 62 74 81 95

Sorting dengan penggabungan
Ide dari mergesort adalah membagi array menjadi 2 bagian, kemudian tiap bagian diurutkan lalu dilakukan merge atau penggabungan sehingga didapatkan array terurut
Pada gambar diatas array dibagi menjadi masing-masing 2 bagian untuk kemudian urutkan dan digabungkan menjadi 4 bagian kemudian array terurut 4 bagian tersebut digabungkan kembali menjadi array yang terurut. dengan kata lain cara diatas adalah menggunakan pembagian kelipatan 2 yaitu dengan urutan 2,4,8,...dst hingga pada akhirnya array akhir terurut dengan N data.

Program mergesort dengan rekursif
//mergeSort.cpp
//demonstrates recursive merge sort
#include <iostream>
#include <vector>
using namespace std;
////////////////////////////////////////////////////////////////
class DArray
{
private:
vector<double>(theVect); //vector of doubles
int nElems; //number of data items
void recMergeSort(vector<double>, int, int);
void merge(vector<double>, int, int, int);
public:
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
DArray(int max) : nElems(0) //constructor
{
theVect.resize(max); //size vector
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void insert(double value) //put element into array
{
theVect[nElems] = value; //insert it
nElems++; //increment size
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void display() //displays array contents
{
for(int j=0; j<nElems; j++) //for each element,
cout << theVect[j] << " "; //display it
cout << endl;
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void mergeSort() //called by main()
{ //provides workspace
vector<double>(workSpace);
workSpace.resize(nElems);
recMergeSort(workSpace, 0, nElems-1);
}
}; //end class DArray
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void DArray::recMergeSort(vector<double> workSpace,
int lowerBound, int upperBound)
{
if(lowerBound == upperBound) //if range is 1,
return; //no use sorting
else
{ //find midpoint
int mid = (lowerBound+upperBound) / 2;
//sort low half
recMergeSort(workSpace, lowerBound, mid);
//sort high half
recMergeSort(workSpace, mid+1, upperBound);
//merge them
merge(workSpace, lowerBound, mid+1, upperBound);
} //end else
} //end recMergeSort()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void DArray::merge(vector<double> workSpace, int lowPtr,
int highPtr, int upperBound)
{
int j = 0; //workspace index
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1; //# of items
while(lowPtr <= mid && highPtr <= upperBound)
if( theVect[lowPtr] < theVect[highPtr] )
workSpace[j++] = theVect[lowPtr++];
else
workSpace[j++] = theVect[highPtr++];
while(lowPtr <= mid)
workSpace[j++] = theVect[lowPtr++];
while(highPtr <= upperBound)
workSpace[j++] = theVect[highPtr++];
for(j=0; j<n; j++)
theVect[lowerBound+j] = workSpace[j];
} //end merge()
////////////////////////////////////////////////////////////////
int main()
{
const int maxSize = 100; //array size
DArray arr(maxSize); //create "array"
arr.insert(64); //insert items
arr.insert(21);
arr.insert(33);
arr.insert(70);
arr.insert(12);
arr.insert(85);
arr.insert(44);
arr.insert(3);
arr.insert(99);
arr.insert(0);
arr.insert(108);
arr.insert(36);
arr.display(); //display items
arr.mergeSort(); //merge-sort the array
arr.display(); //display items again
return 0;
} //end main()

Output
64 21 33 70 12 85 44 3 99 0 108 36
0 3 12 21 33 36 44 64 70 85 99 108

Jumlah operasi yang dilakukan jika N adalah kelipatan dari 2











Jumlah maksimum dan minimum pembandingan jika digunakan array yang sudah terurut dan array yang tidak terurut dalam mergesort
sumber : Kuliah Logika dan Pemrograman Sistem II
READ MORE - Applied Recursion(Hours 12) part 2

Sunday, May 2, 2010

Applied Recursion(Hours 12) part 1

Pemakaian rekursi pada bab ini ada 2 macam yaitu

  • The Towers of Hanoi puzzle
  • Mergesort
The Towers of Hanoi puzzle

Adalah sebuah puzze kuno dimana terdiri dari piringan silinder(disk) yang berbeda diameter yang disusun menjadi piramid dalam 1 kolom. Diharuskan untuk memindahkan kolom disk ke kolom lain dengan syarat bahwa disk yang lebih besar tidak boleh berada diatas disk yang lebih kecil. Pada gambar ditunjukkan semua disk berawal dari kolom A. Diharuskan memindahkan semua disk ke kolom C. Hanya 1 disk yang dapat di pindah dalam 1 waktu dan tidak boleh ada menempatkan disk yang lebih besar diatas disk yang lebih kecil.
Langkah untuk menyelesaikan puzzle ini adalah

Urutan pemindahan disk

  1. Disk 1: A ke B
  2. Disk 2: A ke C
  3. Disk 1: B ke C
  4. Disk 3: A ke B
  5. Disk 1: C ke A
  6. Disk 2: C ke B
  7. Disk 1: A ke B
  8. Disk 4: A ke C
  9. Disk 1: B ke C
  10. Disk 2: B ke A
  11. Disk 1: C ke A
  12. Disk 3: B ke C
  13. Disk 1: A ke B
  14. Disk 2: A ke C
  15. Disk 1: B ke C
Jadi untuk memindah 4 disk dari kolom A ke C diperlukan 15 langkah

Setelah diketahui untuk memindahkan 4 disk diperlukan 15 langkah maka untuk memindahkan 5 disk dapat dilakukan seperti pada gambar diatas yaitu dengan memindahkan 4 disk ke kolom B(15 langkah) lalu memindahkan disk terbesar(disk ke 5) ke kolom C (1 langkah) lalu memindahkan 4 disk dari kolom B ke kolom C(15 langkah). Jadi untuk memindahkan 5 disk dari kolom A ke kolom C diperlukan 15+1+15 = 31 langkah
 
rumus umum jumlah langkah yang diperlukan untuk menyelesaikan puzzle ini adalah

jumlah langkah = 2n-1

dengan n adalah jumlah piringan disk



implementasi dalam pemrograman C++

//towers.cpp

//solves Towers of Hanoi puzzle

#include <iostream>

using namespace std;

void doTowers(int, char, char, char); //prototype

//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

int main()

{

int nDisks; //number of disks

cout << "Enter number of disks: "; //get # of disks

cin >> nDisks;

doTowers(nDisks, 'A', 'B', 'C'); //solve it

return 0;

}

//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

void doTowers(int topN, char src, char inter, char dest)

{

if(topN==1) //display

cout << "Disk 1 from " << src << " to " << dest << endl;

else

{

doTowers(topN-1, src, dest, inter); //src to inter

cout << "Disk " << topN //display

<< " from " << src << " to " << dest << endl;

doTowers(topN-1, inter, src, dest); //inter to dest

}

}


 

Output

Enter (3 disks): s=A, i=B, d=C

Enter (2 disks): s=A, i=C, d=B

Enter (1 disk): s=A, i=B, d=C

Base case: move disk 1 from A to C

Return (1 disk)

Move bottom disk 2 from A to B

Enter (1 disk): s=C, i=A, d=B

Base case: move disk 1 from C to B

Return (1 disk)

Return (2 disks)

Move bottom disk 3 from A to C

Enter (2 disks): s=B, i=A, d=C

Enter (1 disk): s=B, i=C, d=A

Base case: move disk 1 from B to A

Return (1 disk)

Move bottom disk 2 from B to C

Enter (1 disk): s=A, i=B, d=C

Base case: move disk 1 from A to C

Return (1 disk)

Return (2 disks)

Return (3 disks)

Disk 1 from A to C

Disk 2 from A to B

Disk 1 from C to B

Disk 3 from A to C

Disk 1 from B to A

Disk 2 from B to C

Disk 1 from A to C


 

Berlanjut ke part 2

sumber : Kuliah Logika dan Pemrograman Sistem II
READ MORE - Applied Recursion(Hours 12) part 1

Arithmetic And Logic Unit

Laporan Praktikum tentang Arithmetic Logic Unit 1 bit sederhana
download
READ MORE - Arithmetic And Logic Unit

Negative Feedback Amplifier

Laporan praktikum elektronika II tentang negative feedback amplifier
download
READ MORE - Negative Feedback Amplifier