DS2 ARRAY

Question 1

OBJECT VS BUILT-IN TYPE

Answer 1

object:
-create with new obj()
-addressed via reference that is stored in local variable points to memory address where values are stored
-there are wrapper classes for types (Integer class has parseInt method etc)
type:
-create with type_name variable name= value
-variable points to contents ofmemory address
-can be casted or transformed to a different type (char can become int, double can become float and int etc)

Question 2

ARRAYS

Answer 2

collection of same type items or objects
has index pointer to access position (indexing at 0)
throws ArrayOutOfBoundsException in java
public field length
size is predetermined cant extend or shorten
takes up memory serially

Question 3

ERATOSTHENIS SIEVE

Answer 3

give n>=2 get all primes <n
approach 1:
n length boolean array
start with all positions true
parse it starting from pos 2(assuming 0, 1 are not prime numbers)
every time i is prime find multiplicands<n and set to false
if we encounter false continue

java code:
primes(n){
~boolean[] a = new boolean[n];
~for (int i = 2; i < n; i++){a[i] = true;}
~for(int i = 2; i < n; i++)
~~{if(a[i])
~~~{for(int j = i; j * i < n; j++) //start at j=i cause for j<i previous iterations have already found it//
~~~~{a[i*j] = false;} }}}

time complexity is n/2 + n/3 +…+n/n = n(1/2+…+1/n)= n*lnn so same scale as O(nlogn)

Question 4

TYPES OF ARRAY COPIES
(concerns arrays that contain objects types cannot have a copied reference so a semi-deep type copy is a deep copy)

Answer 4

-shallow copy: copy of reference
is basically 2 names for the same thing
points to same address
if one is altered both are altered
-semi-deep copy: copy of content reference
2 different arrays
contents point to the same address
changing one array doesnt affect the other one but changing something in the contents of one array does
(changing a field of obj a in ar1 changes the field of that object in ar2 but changing ar1[i] doesnt change ar2[i])
-deep copy: use new() when copying contents
only values are the same

Question 5

SIZE CHANGE

Answer 5

arrays are static data structures so to change size we have to copy the contents to a different size array and delete the original
caution with memory leaks especially in c and c++ since memory isnt freed automatically when deleting a reference

Question 6

MULTI-DIMENTIONAL ARRAYS

Answer 6

declare as obj[i][j]
store serially in lines(first line then second etc)
thats why we parse i then j optimally

Question 7

APPLICATION IN GRAPH REPRESENTATION

Answer 7

v : vertices (dots)
e : edges (connectors)
using adjacency matrix
if i and j vertices are connected ar[i][j] and [j][i] set to 1 else set to 0
n^2 memory
O(1) time complexity for adjacency check

Question 8

SPARCE ARRAYS

Answer 8

2-D array majority of contents have value 0
better store as 1-D array with coords and value
k( non zero points) memory instead of n^2

Question 9

TRIANGULAR ARRAYS

Answer 9

above or below diagonal is all 0
there are more effective ways of storing but depends on application and trade offs

Question 10

HONOURABLE MENTIONS

Answer 10

classes Vector and ArrayList are dynamic but slower to parse (get() method)
usually use array when creating data structures like trees