// Program 1 --- some sorting
// compile: g++ program1.cpp
// usage: a.out 100
// (replace "100" by the array size you want)
//
// Name:
//
// Date submitted:
//
#include<iostream>
#include<math.h>
#include<sys/time.h>
using namespace std;
// Declarations
void bubbleSort(int a[]);
void insertSort(int a[]);
void mergeSort(int a[]);
void mySort(int a[]);
void fillRandom(int a[]);
void check(int a[]);
int N = 0; // Global for array size
int main(int argc, char *argv[]){
int a[1000000]; // array to sort, N < a million
timeval t; // for timing the sorts
int starttime, endtime; // for timing the sorts
N = atoi(argv[1]); // set size of array
// Time a bubble sort
fillRandom(a);
gettimeofday(&t, NULL);
starttime = t.tv_sec;
bubbleSort(a);
gettimeofday(&t, NULL);
endtime = t.tv_sec;
cout << "Bubble Sort time = " << endtime - starttime << endl;
check(a);
// time an insertion sort
fillRandom(a);
gettimeofday(&t, NULL);
starttime = t.tv_sec;
insertSort(a);
gettimeofday(&t, NULL);
endtime = t.tv_sec;
cout << "Insertion Sort time = " << endtime - starttime << endl;
check(a);
// time a merge sort
fillRandom(a);
gettimeofday(&t, NULL);
starttime = t.tv_sec;
mergeSort(a);
gettimeofday(&t, NULL);
endtime = t.tv_sec;
cout << "Merge Sort time = " << endtime - starttime << endl;
check(a);
// time a "my" sort
fillRandom(a);
gettimeofday(&t, NULL);
starttime = t.tv_sec;
mySort(a);
gettimeofday(&t, NULL);
endtime = t.tv_sec;
cout << "My Sort time = " << endtime - starttime << endl;
check(a);
return 0;
}
void bubbleSort(int a[]){
for(int i = 0; i <= N; i++)
for(int j = 0; j < N-1; j++)
if(a[j] > a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
return;
}
void insertSort(int a[]){
}
void mergeSort(int a[]){
}
void mySort(int a[]){
}
void fillRandom(int a[]){
for(int i = 0; i < N; i++)
a[i] = rand();
return;
}
void check(int a[]){
for(int i = 0; i < N-1; i++)
if(a[i] > a[i+1]){
cout << "Failed to sort. See item " << i << endl << endl;
return;
}
cout << "Check passed" << endl << endl;
}
| Assignment: Write the rest of the program below. It allows the user to interact with a heap. The heap will never have more than 20 elements in it. You should write your own additional functions to help perform these heap operations. When the heap is in "heapstate = 0," then it is just a heap, and no attempt should be made to maintain either a min or max heap property thereafter, unless a "min" or "max" command is issued. For consistency, implement the algorithms in the fashion given in the book, so that the heap will look the same for everybody after each command. |
Sample
Transcript: add 1 Added 1 1- add 5 Added 5 1-5- add 2 Added 2 1-5-2- sort Sorting 1-5-2- max Making a max heap 5-1-2- sort Sorting 1-2-5- min Making a min heap 1-2-5- sort Sorting 5-2-1- |
// Program 2 --- some heap practice
// compile: g++ program2.cpp
// usage: a.out
// Name:
//
// Date submitted:
//
#include<iostream>
#include<string>
using namespace std;
#define N 20
// Global Variables
int heapstate = 0; // 0 = heap, 1 = maxheap, 2 = minheap
void add(int A[], int &heapsize, int val){
cout << "Added " << val << endl;
}
int extract(int A[], int &heapsize){
cout << "Extracting" << endl;
}
void make_max_heap(int A[], int heapsize){
cout << "Making a max heap" << endl;
}
void make_min_heap(int A[], int heapsize){
cout << "Making a min heap" << endl;
}
void heapsort(int A[], int heapsize){
if(heapstate == 0) return;
cout << "Sorting" << endl;
}
void print(int A[], int heapsize){
for(int i = 1; i <= heapsize; i++)
cout << A[i] << "-";
cout << endl << endl;
}
int main(){
int A[N+1];
int heapsize = 0;
string command = "";
int val = 0;
// Initialize
// Remember that our arrays start with index 1.
for(int i = 1; i <= N; i++)
A[i] = 0;
do{
cin >> command;
if(command == "add"){
// Add a value to the end of the heap.
// Should maintain the heap property according to heapstate.
cin >> val;
add(A, heapsize, val);
}
if(command == "extract"){
// Should extract A[1] and maintain heap property,
// according to heapstate
cout << "Extracted " << extract(A, heapsize) << endl;
}
if(command == "neither"){
heapstate = 0;
}
if(command == "max"){
heapstate = 1;
make_max_heap(A, heapsize);
}
if(command == "min"){
heapstate = 2;
make_min_heap(A, heapsize);
}
if(command == "sort"){
// Sort into increasing order if heapstate = 1,
// and into decreasing order if heapstate = 2.
heapsort(A, heapsize);
}
print(A, heapsize);
}while(command != "end");
}
| Assignment: You are given an undirected graph, and you should return the number of connected components in the graph. The graph will be given as a list of vertices, followed by a list of edges, as shown in the sample transcript to the right. Each list is terminated with the word "end." Your output should give the number of components, and then a sorted list of sizes of the components, from largest to smallest. Each vertex name will be a single character; in fact, a lower-case letter. Please make sure that your output matches the sample transcript shown to the right, so that my grading scripts can run automatically. You do not need to do error checking on the input. You may assume I enter legitimate graphs. Please write your program in C++ or Java, and make sure it uses no resources other than those given in your textbook. That is, please use no code from the Internet. The input must come from the standard input, and the output must go to the standard output. |
Sample
Transcript: >a.out Please input your vertices: a b c d e end Please input your edges a b a c b c d e end Components: 2 Sizes: 3 2 > |