# Thread: driller for software systems

Incoming! Sorry in advance if these aren't pure "software systems and methodology" problems.

Q1) Define "expression compatible", "name compatible", and "structural compatability"

Q2) List the four key ingredients in object-oriented programming.

Q3) In a sequential file of 512B records, how many bytes must be read from the drive to acquire the contents of the 111th record?

Q4) Suppose an indexed file has records of 512B each, and each record pointer requires 4B. The index is implemented as a B-tree, wherein each node can store up to 512B of pointers to child nodes. If the B-tree contained exactly two levels (including the root), then what is the maximal number of records it can contain? What would the file's size be?

Q5) Can recursion be used to implement any iterative function? Can iteration be used to implement any recursive function? If not, give counterexamples.

Q6) What is the value of f(n) in big-O notation?
Code:
```function f(n) {
if (n <= 1) return 1;
return f(n/2) + 2*f(n/4);
}```
Q7) A specification requires the implementation of the following functionality: test-and-set memory, semaphores, monitors, critical regions, and mutexes. Which of these functions is most primitive (ie: cannot be implemented "on top of" the other functions)? Which is the least primitive? What is the hierarchy of primitiveness among these functions?

Q9) Is wound-wait an effective solution to deadlock? How about wait-die? Is either preemptive?

Q10) How do you know when an object is safe to garbage collect?

Q11) If a system stores arrays in row-major order, and an array of 4-byte words A starts at location 0x8000, give a formula for the location of element A[x][y]. How about if it's in column-major order?

Q12) What does the following program print?
Code:
```int x = 1;
function f(i) {
int x = 2;
I *= 3;
for (int j = 1; j <= i; j++)
g(j);
}

function g(j) {
print j+x;
}
f(x);```
Consider four scenarios: dynamic scope with pass-by-value, dynamic scope with pass-by-reference, static scope with pass-by-value, static scope with pass-by-reference.

Q13) Convert to postfix and prefix: 3*4+3-7/(8+2)

Q14) Evaluate the expression in Q13, assuming integer division. Then do the same, assuming that the system always performs floating point division.

Q15) What printout does the following code snippet generate, assuming >> is a logical right shift operator on 8-bit 2's complement integers, and & is a bit-wise AND operator?
Code:
```int x = -23;
int m = 0x1;
for (int I = 0; I < 8; i++) {
if (m & x == 1) then
print i
x = x >> 1
}```
Q16) Why might a compiler make two passes through a source file?

Q17) What "independent" code compilation?

Q18) What is a "capability"?

Q19) What is the difference between "protection" and "security"?

Q20) Suppose a software system uses access control lists to control access to files. By default, each file is inaccessible to all users. If Bob is a member of the "vsusers" group, how many files below can he access? Assume that lines later in an ACL override earlier lines.

Code:
```file1
allow vsusers
file2
allow vsusers
deny Bob
file3
allow Bob
deny vsusers
file4
deny Bob
file5
allow all
deny vsusers
allow Bob```
Q21) What is a profiler good for?

Q22) What is a linker good for?

Q23) What is the difference between a distributed file system and a networked file system?

Q25) What are the tradeoffs between state-ful networking protocols and state-less networking protocols?

Q26) What is a one-way hash good for?  Reply With Quote

2. [/SIZE]Q1) Define "expression compatible", "name compatible", and "structural compatability"
Name compatible = two variable are compatible if they are declared from the same type
Structural compatability= two variables are compatible if they have same structure, (two struct can be compatible if the contain same things in them)
Expression compatible = No idea,

Q2) List the four key ingredients in object-oriented programming.

1. Abstract data types
2. Inheritances
3. Polymorphism
4. Dynamic Binding

Q3) In a sequential file of 512B records, how many bytes must be read from the drive to acquire the contents of the 111th record?

assuming read has to sequential as in tape-drive we'll need to read 512*111B
Assuming read from a random access drive

Q4) Suppose an indexed file has records of 512B each, and each record pointer requires 4B. The index is implemented as a B-tree, wherein each node can store up to 512B of pointers to child nodes. If the B-tree contained exactly two levels (including the root), then what is the maximal number of records it can contain? What would the file's size be?

With 512B worth of pointers to other children nodes, we can have 455 pointers to other children using 9 BITS to identify a child, which means each node has 454 pointers to data records, so
with two levels we have 454 (root) + 455*454 = 207024 records can that be identified

Q5) Can recursion be used to implement any iterative function? Can iteration be used to implement any recursive function? If not, give counterexamples.

Recursion can be used to implement iteration (many functional languages do) but the reverse in not necessarily true or at least very hard.

Q6) What is the value of f(n) in big-O notation?
Code:
```function f(n) {
if (n <= 1) return 1;
return f(n/2) + 2*f(n/4);
}```
f(n) = O(n^(lg(3)) <- not a tight bound

Q7) A specification requires the implementation of the following functionality: test-and-set memory, semaphores, monitors, critical regions, and mutexes. Which of these functions is most primitive (ie: cannot be implemented "on top of" the other functions)? Which is the least primitive? What is the hierarchy of primitiveness among these functions?

test-and-set is the most primitive
monitors are build on top of almost everything else

Mutual Exclusion
Hold and wait
No preemtion
Circular Wait

Q9) Is wound-wait an effective solution to deadlock? How about wait-die? Is either preemptive?

Yes they are, but lead to unnecessary deaths
wound-wait is preemtive, because older guys kill the young ones effectively preemting them
wait-die on the other hand process instead of waiting they kill themseves, so they willingly release their resources

Q10) How do you know when an object is safe to garbage collect?

If it cannot be reached from a root i.e. it cannot be reached from any of the references in the program

Q11) If a system stores arrays in row-major order, and an array of 4-byte words A starts at location 0x8000, give a formula for the location of element A[x][y]. How about if it's in column-major order?

row major
A[x][y] = 0x8000 + x*4*100 + y*4
column major
A[x][y] = 0x8000 + y*4*200 + x*4

Q12) What does the following program print?
Code:
```int x = 1;
function f(i) {
int x = 2;
i*= 3;
for (int j = 1; j <= i; j++)
g(j);
}

function g(j) {
print j+x;
}
f(x);```
Consider four scenarios: dynamic scope with pass-by-value, dynamic scope with pass-by-reference, static scope with pass-by-value, static scope with pass-by-reference.

Dynamic scope
Pass by value: 3 4 5
Pass by reference: 3 4 5
Static scope
Pass by value: 2 3 4
Pass by reference: 4 5 6

Q13) Convert to postfix and prefix: 3*4+3-7/(8+2)

Postfix
3 4 * 3 + 7 8 2 + / -
Prefix
- + * 3 4 3 / 7 + 8 2

Q14) Evaluate the expression in Q13, assuming integer division. Then do the same, assuming that the system always performs floating point division.

Integer arith. value = 15
Floating point arith. value = 15 - 0.7 (0.7 cannot be represented accurately in the computer) so the answer is going to be ~ 14.3
[/SIZE]  Reply With Quote

3. Dude, Alba, you're fast. So fast that I haven't even created an answer key yet!

Q4 Is that 512 the capacity of a node, or specifically for pointers to OTHER nodes??
Each node has 512B worth of pointers to children, as well as a certain number of 512B records. So our nodes are big. This is a B tree.  Reply With Quote

4. Q5) Can recursion be used to implement any iterative function? Can iteration be used to implement any recursive function? If not, give counterexamples.

I believe recursive function can always be implemented with an iterative function and a stack. Imagine how recursion is done in the background. Push stack frame (activation record) as you call the function recursively, then pop it when reaching the base case. All that could be simulated with a stack of some ADT for the stack frame.  Reply With Quote

5. Q15) What printout does the following code snippet generate, assuming >> is a logical right shift operator on 8-bit 2's complement integers, and & is a bit-wise AND operator?

Code:
```int x = -23;
int m = 0x1;
for (int i= 0; i< 8; i++) {
if (m & x == 1) then
print i;
x = x >> 1
}```
The code above will print the positions of 1s in the representation of -23 in 2s complement, which is 1110 1001
therefore the code will print (counting from left to right) 0 3 5 6 7

Q16) Why might a compiler make two passes through a source file?

To identify variables that are used before their declaration but are still legal. For example when writing a class in C++ one can put the declarations of the variables after the functions are defined. There might be more tho??

Q17) What is "independent" code compilation?

Independent compilation is compilation that may happen in different points in time, each part being compiled does not need any information of other parts being compiles (say in a big project).

Q18) What is a "capability"?
Ability to do 'something' . In what context

More to come soooooooon  Reply With Quote

6. Q16) Why might a compiler make two passes through a source file?
First pass - create the symbol table (figure the addresses)
Second pass - compile the program with help of the symbol table (fill in the addresses)  Reply With Quote

7. samlai

That is a really nice approach indeed, but I don't think that it effectively uses iteration to implement recursion, it merely mimics the way recursion works. What you're basically doing is implementing recursion. For example
Code:
```fact(x)
{
if(x == 1) return 1
return x*fact(x-1);
}

coulde be nicely transformed in the following code
fact(x)
int temp= 1;
for(int I = 2 to I == x; I++)
temp = temp * I;
return temp;
}```
I think this is what is required when using iteration instead of recursion. Two main reasons why iteration is prefered over recursion are:the recusion will run so deep that will get out of stack memory error, or performance.  Reply With Quote

8. Q19) What is the difference between "protection" and "security"?

I think protection is the ability to deny or grant access to a specific resource such as keyboard. A policy + protection = security. Correct ???

Q20) Suppose a software system uses access control lists to control access to files. By default, each file is inaccessible to all users. If Bob is a member of the "vsusers" group, how many files below can he access? Assume that lines later in an ACL override earlier lines.
Code:
```file1
allow vsusers     <- Yes Bob is a vsuser
file2
allow vsusers  <- Yes Bob is a vsuser
deny Bob
file3
allow Bob       <- Yes Bob is a Bob
deny vsusers
file4
deny Bob      <- Sorry bob
file5
allow all      <- Yes Bob is a member of all
deny vsusers
allow Bob```
This depends on the method that the access list is processed, i.e. if scanning stops as soon as permission is granted than that case is shown above (this method is the most commonly used), another method is scan all the list and then decide, grant access if no deny-s for this user where found (slower). That's y someone has to be carefull when implementing ACL-s because the effect that you introduce might not be the one you want.

Q21) What is a profiler good for?
Anyone ???
Q22) What is a linker good for?
The linker brings together into one object file all object code that the current program does not implement but are provided by either the language or his/her own or libraries
Q23) What is the difference between a distributed file system and a networked file system?
Distributed file systems abstract many independed storage devices resident on different machines to one file system. The user does not see the detail, especially location where a file is stored, duplication. Networked file system is a network of independent file systems, use knows where a file is stored and details s/he does not need to know
User level threads reside within a process, OS has not the least clue of them, usually implemented by some library. OS is fully aware of kernel level threads and ..... someone has to explain me the rest !!!!
Q25) What are the tradeoffs between state-ful networking protocols and state-less networking protocols?
statefull networking protocols are reliable at the cost of overhead, stateless protocols on the other hand don't remember a thing and are not reliable, but are faster and cheaper. Needs more elaboration, why don;t you add something if you know

Q26) What is a one-way hash good for?
One way hashing is usually used for storing data that needs to be verified not retrieved, such as paswords. In one way hashing the conversion from A(data) -> B(cypher) is efficient and the B -> A is considered hard or impossible. MD5 is a one way hashing algorithm  Reply With Quote

9. Q21) What is a profiler good for?
Profiler tells you what parts of the program are executed most often. It is very important to pin point where the bottle-neck of the program is when trying to optimize it.  Reply With Quote

10. Can someone elaborate on Q4?  Reply With Quote