[Solved] SOLVED: 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 initiallyvalued 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 thecompilation 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 thiswill 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 maybe implemented as an array of structs.) index[i] indicates which of the n counters has its value presently stored ascount[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
,index[i],count[i]);Operation 1 may be coded as:for (i=0;i<n;i++)printf(%d %d
,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.