# Lab Assignment 1

Goals:

1. Understanding of binary search.

2. Understanding of maps/permutations, indirection, and swapping.

Requirements:

1. Write a C program to maintain n counters indexed by 0 .. n-1. n will be the first input value and all counters are initially

valued as zero. The following operations will then appear, one per line, in the input:

a. 0 - terminate execution.

b. 1 - print the counters in ascending index value order as (index, count) pairs. (O(n) time)

c. 2 - print the counters in ascending counter value order as (index, count) pairs. (O(n) time)

d. 3 i - add one to the counter indexed by i. (O(log n) time)

e. 4 i - subtract one from the counter indexed by i. (O(log n) time)

f. 5 i j - determine the number of counters whose values are no smaller than i and no larger than j. (O(log n) time)

The input will be read from standard input (stdin) as either keyboard typing or as a shell redirect (<) from a file.

Prompts/menus are completely unnecessary!

2. Submit your program on Blackboard by 10:45 am on September 25. One of the comment lines should indicate the

compilation command used on OMEGA.

Getting Started:

1. Review binary search and obtain a copy of binarySearchRange.c from the course web page. Code similar to this

will be useful in implementing operations 3, 4, and 5.

2. Your program should dynamically allocate three tables - map, index, and count. (If you wish, the last two tables may

be implemented as an array of structs.) index[i] indicates which of the n counters has its value presently stored as

count[i]. map[i] is used to find the counter with index i, i.e. it is always true that index[map[i]]==i.

Operation 2 may be coded as:

for (i=0;i<n;i++)

printf("%d %d\n",index[i],count[i]);

Operation 1 may be coded as:

for (i=0;i<n;i++)

printf("%d %d\n",i,count[map[i]]);

3. You should implement and completely debug operation 3 before implementing operation 4.

4. Your code must satisfy the indicated time bounds by using binary search when possible.

1. Understanding of binary search.

2. Understanding of maps/permutations, indirection, and swapping.

Requirements:

1. Write a C program to maintain n counters indexed by 0 .. n-1. n will be the first input value and all counters are initially

valued as zero. The following operations will then appear, one per line, in the input:

a. 0 - terminate execution.

b. 1 - print the counters in ascending index value order as (index, count) pairs. (O(n) time)

c. 2 - print the counters in ascending counter value order as (index, count) pairs. (O(n) time)

d. 3 i - add one to the counter indexed by i. (O(log n) time)

e. 4 i - subtract one from the counter indexed by i. (O(log n) time)

f. 5 i j - determine the number of counters whose values are no smaller than i and no larger than j. (O(log n) time)

The input will be read from standard input (stdin) as either keyboard typing or as a shell redirect (<) from a file.

Prompts/menus are completely unnecessary!

2. Submit your program on Blackboard by 10:45 am on September 25. One of the comment lines should indicate the

compilation command used on OMEGA.

Getting Started:

1. Review binary search and obtain a copy of binarySearchRange.c from the course web page. Code similar to this

will be useful in implementing operations 3, 4, and 5.

2. Your program should dynamically allocate three tables - map, index, and count. (If you wish, the last two tables may

be implemented as an array of structs.) index[i] indicates which of the n counters has its value presently stored as

count[i]. map[i] is used to find the counter with index i, i.e. it is always true that index[map[i]]==i.

Operation 2 may be coded as:

for (i=0;i<n;i++)

printf("%d %d\n",index[i],count[i]);

Operation 1 may be coded as:

for (i=0;i<n;i++)

printf("%d %d\n",i,count[map[i]]);

3. You should implement and completely debug operation 3 before implementing operation 4.

4. Your code must satisfy the indicated time bounds by using binary search when possible.

You'll get 1 file (1.7MB)