3.2 Elementary Data Structures: Arrays

Question 1

What is an array?

Answer 1

An array is a fixed collection of same-type data that are stored contiguously and are accessible by their index.

Question 2

What are two of the more common mistakes programmers make when dealing with arrays in the C language?

Answer 2

Accessing a negative index, accessing an index which goes beyond the size allocated for the array. Since C language doesn’t do array boundary checking, these errors are all too common.

Segmentation fault error, which usually arises when we try to access out of bound elements is just caused because our program tried to reference a memory location which it didn’t have any permission to. C++ also has the same rules in this case.

Perhaps even accessing an uninitialized element in the array might be a common mistake.

Question 3

Discuss the sieve of erastosthenes method for calculating primes.

Answer 3

https://www.geeksforgeeks.org/sieve-of-eratosthenes/

Question 4

How are pointers and arrays related to each other in C?

Answer 4

The name of the array itself generates a pointer to the base address of the array.
Basic pointer arithmetic is also allowed. If the array name is ‘a’ then *(a) is the same as a[0], *(a+1) is the same as a[1] and so on.

Question 5

Why are pointers to arrays particularly useful for large arrays?

Answer 5

This is because whenever we pass an object by value to a function, then its local copy is made inside the function.
When the array size is large, this process of copying the array is expensive, both in terms of memory and time.
So, pointers to arrays are particularly helpful because we can pass the array by reference and the function will work on that same array only, instead of creating a new one.

Question 6

Briefly explain the mechanism for passing command line arguments in C.

Answer 6

Command line arguments are passed to the main in C.
These arguments are “int argc” and “char* argv[]”.
argc is the argument counter. It contains the number of arguments that we have passed from the command line.
argv is the argument vector. It is an array of strings. It contains the actual arguments passed. The first argument (argv[0] ) is always the program name. Rest of the arguments (argv[1] to argv[argc-1]) contain the arguments passed.

Question 7

How is memory dynamically allocated in C?

Answer 7

Memory is dynamically allocated at execution time using the function malloc. It allocates memory for an array of a specified size, and returns a pointer to the base address of the memory allocated. If for some reason (eg. insufficient memory on the heap), the memory allocation fails, then a NULL pointer is returned.

Question 8

How can we imitate dynamic memory allocation for statically allocated arrays?

Answer 8

For doing this, we need to know the maximum possible size of the array.
Then we statically allocate an array of that size.
The user can simply input the size of the array they need according to their requirements, and the program can use that much memory out of the total memory allocated to the array.
This method is not particularly useful because a lot of memory goes to waste, especially if the array size required by the user is much smaller than the total size allocated to it, or if many arrays are needed in the program.

Question 9

What are Bernoulli’s Trials and Normal Distribution?

Answer 9

TODO: Read https://www.math.arizona.edu/~jwatkins/505d/Lesson_10.pdf

Question 10

What alternatives can we use to save memory for an integer array containing only 1s and 0s.

Answer 10

1. char array: An int usually occupies 4 bytes of memory whereas it’s only 1 byte for a char. Since we only need to store 0s and 1s, that can as easily be done using a char array with ‘1’s and ‘0’s as chars. So we only use 0.25 of the memory used by the int array.
2. bit array: We need a way to represent a single bit: a single 1 or a single 0. This can be done in a single bit only. Since an int (4 bytes) contains 32 bits, a bit array will only occupy 1/32 times the space an int array does.
   It is even better than a char array. A char (1 byte) contains 8 bits, so the bit array occupies 1/8 times the size of a char array.

Question 11

How are bit arrays implemented?

Answer 11

http://www.mathcs.emory.edu/~cheung/Courses/255/Syllabus/1-C-intro/bit-array.html
declare int a[N].
a[0] = bit indices (0-31)
a[1] = bit indices (32 - 63)
.
.
a[N] = bit indices (32(N) - 32(N+1)-1 )

Implementation of setBit, clearBit and TestBit are given in the link.