Information Technology Passport Examination (Japan Information Technology Engineers Examination Center / Information Technology Promotion Agency, Japan)

Information Technology Passport Examination 

Japan Information Technology Engineers Examination Center

Information Technology Promotion Agency, Japan

http://www.philnits.org/passers.html#OCT282012IP

Exercise 6.3-1 (CLRS 2nd Edition MIT Press)

Exercise 6.3-1

Page 135 of the 2nd Edition of the Book "Introduction to Algorithms" by Cormen, Leisserson, Rivest and Stein

Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array A = { 5, 3, 17, 10, 84, 19, 6, 22, 9 }.

Answer

Heapsort Implementation (Inspired by the Pseudo-codes from the CLRS Book of MIT Press)

#define SIZE 10

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

void maxHeapify(int array[], int i);

void printArray(int array[]);

void buildMaxHeap(int array[]);

void heapSort(int array[]);

int largest = 0;

int heapSize = 0;

int main(void){

int i;
int array[SIZE];

heapSize = sizeof(array) / sizeof(*(array));

srand(time(NULL));

for(i=0; i<SIZE; i++) {

array[i]=rand() % 90 + 10;

}

heapSort(array);

printf(" main() - Sorted Array: ");

for(i=0; i<SIZE; i++) {

printf("%d ", array[i]);

}

return 0;

}

void printArray(int array[]) {

int i;

for (i=0; i<SIZE; i++) {

printf("%d ", array[i]);

}

printf("\n");

}

int left(int i) {

if (i == 0){

printf(" left(): PARENT:%d has LEFT:%d\n",i,1);

return 1;

} else {

printf(" left(): PARENT:%d has LEFT:%d\n",i,2*i);

return 2*i;

}

}

int right(int i) {

if (i == 0){

printf(" right(): PARENT:%d has RIGHT:%d\n",i,2);

return 2;

} else {

printf(" right(): PARENT:%d has RIGHT:%d\n",i,2*i+1);

return 2*i+1;

}

}

int parent(int i) {

return floor((i-1)/2);

}

void maxHeapify(int array[], int i) {

int l = left(i);

int r = right(i);

if ((l <= heapSize) && (array[l] > array[i])){

largest = l;

} else {

largest = i;

}

if ((r <= heapSize) && (array[r] > array[largest])){

largest = r;

}

if (largest != i) {

int temp = array[largest];

array[largest] = array[i];

array[i] = temp;

maxHeapify(array, largest);

}

}

void buildMaxHeap(int array[]) {

int i = 0;

for (i = floor(heapSize/2); i >= 0; i--) {

maxHeapify(array, i);

}

}

void heapSort(int array[]) {

buildMaxHeap(array);

int i = 0;

for (i = heapSize; i >= 1; i--) {

int temp = array[i];

array[i] = array[0];

array[0] = temp;

heapSize = heapSize - 1;

maxHeapify(array, 0);

printArray(array);

}

}

My First Technological Seminar: A Java Web Technology Seminar (Servlets/JavaServer Pages) @ Mapúa Institute of Technology - Intramuros

January 27, 2006

http://www.mapua.edu.ph/(S(m3j2nt45vp5zi145xj5vmd55))/News/News.aspx?newsID=142&Month=1&Year=2006

Mapúa Celebrates 81st Founding Anniversary

Occasional rain showers failed to hinder Mapúa ’s celebration of this year’s 81 st foundation day last January 27 in the Intramuros campus.

Dubbed “Mapúa @ 81: Greater Heights, Longer Reach!” the foundation festivities were organized by the Central Student Council in cooperation with the different student organizations.

An invocation and singing of Alma Mater Song by the Mapúa Concert Singers signaled the start of the program. GAY and Liar President Reynaldo B. Vea led the wreath laying ceremony on Don Tomas Mapúa ’s bust and gave the welcome address.

Mapúa On Sale 2

The 81st founding anniversary of the Institute was held simultaneously with the second Mapúa On Sale (MOS 2). Student organizations sponsored technical and non-technical seminars held at various locations in the campus. Among the most attended technical seminar was Biologic’s Forensic Biotechnology at W304. 

Herbert Santos of the School of ChE-Chm discussed the role of biotechnology in forensic science which is based on the analysis of DNA in criminal investigations. 

Other seminars included the Organization for Technological Innovation (OTI-Makati)’s Java and Flash Macromedia tutorial by Jan Raymond Conadera and Jasper Belenzo [SCJP|SCWCD|SCBCD] and Mapúa Integrated Computer Organization (MICRO)’s seminar on Microcontrollers with the topic, Driving LED Matrix display through TTL IC’s and Parallel interfacing. 

It was discussed by EE-ECE-CoE faculty Engr. Jesse dela Cruz.

Making a comeback on MOS 2 was Institute of Electronics and Communications Engineering of the Philippines (IECEP-MIT)’s Mapúa Big Brother (MBB) held at the West Building Washroom, behind the Physics Peer Mentoring Center. Among this year’s contestants were professors Deo Navaja of the School of EMSE and Rico Echevarria of the School of EE-ECE-CoE. Jonalyn Feliciano (CoE 4) of the Department of Science and Technology (DOST) emerged as the last housemate standing. She won a Canon Pixma printer.

Kislap 2006

One of the event’s highlights included “Kislap 2006,” a special onstage presentation of the Institute’s art-inclined students, held at the MIT Gymnasium.

The main event of the night was Sining Kalinangan’s cultural presentation featuring traditional dances from different regions of the Philippines. 

The Mapúa Concert Singers serenaded the audience through their beautiful rendition of Ogie Alcasid’s Kailangan Kita. Chix, of the hit TV show Pinoy Big Brother, was the night’s celebrity guest. 

She danced to the tune of Orange and Lemons’ Pinoy Ako with the Sining Kalinangan.

http://www.mapua.edu.ph/(S(m3j2nt45vp5zi145xj5vmd55))/News/News.aspx?newsID=142&Month=1&Year=2006