Sponsored Ad:
Page 1 of 4 1234 LastLast
Results 1 to 10 of 31

Thread: driller for software systems

  1. #1
    An Urch Guru Pundit Swami Sage
    Join Date
    Oct 2003
    Location
    USA
    Posts
    508
    Rep Power
    19


    Good post? Yes | No
    Sponsored Ad:
    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?

    Q8) List the conditions which automatically lead to deadlock.

    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[100][200] 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?

    Q24) What are the tradeoffs between user-level threading and kernel-level threading?

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

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

  2. #2
    An Urch Guru Pundit Swami Sage
    Join Date
    Oct 2003
    Location
    Albania
    Posts
    534
    Rep Power
    19


    Good post? Yes | No

    [/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
    512B have to be read


    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

    Q8) List the conditions which automatically lead to deadlock.

    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[100][200] 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]

  3. #3
    An Urch Guru Pundit Swami Sage
    Join Date
    Oct 2003
    Location
    USA
    Posts
    508
    Rep Power
    19


    Good post? Yes | No
    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.

  4. #4
    Trying to make mom and pop proud
    Join Date
    Oct 2003
    Posts
    21
    Rep Power
    17


    Good post? Yes | No
    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.

  5. #5
    An Urch Guru Pundit Swami Sage
    Join Date
    Oct 2003
    Location
    Albania
    Posts
    534
    Rep Power
    19


    Good post? Yes | No
    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

  6. #6
    Trying to make mom and pop proud
    Join Date
    Oct 2003
    Posts
    21
    Rep Power
    17


    Good post? Yes | No
    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)

  7. #7
    An Urch Guru Pundit Swami Sage
    Join Date
    Oct 2003
    Location
    Albania
    Posts
    534
    Rep Power
    19


    Good post? Yes | No
    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.

  8. #8
    An Urch Guru Pundit Swami Sage
    Join Date
    Oct 2003
    Location
    Albania
    Posts
    534
    Rep Power
    19


    Good post? Yes | No
    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
    Q24) What are the tradeoffs between user-level threading and kernel-level threading?
    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

  9. #9
    Trying to make mom and pop proud
    Join Date
    Oct 2003
    Posts
    21
    Rep Power
    17


    Good post? Yes | No
    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.

  10. #10
    An Urch Guru Pundit Swami Sage
    Join Date
    Jul 2003
    Location
    Brazil
    Posts
    1,360
    Rep Power
    22


    Good post? Yes | No
    Can someone elaborate on Q4?

Page 1 of 4 1234 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. driller for mathematics
    By nonevent99 in forum GRE Computer Science
    Replies: 22
    Last Post: 08-18-2010, 05:14 PM
  2. driller for theory
    By nonevent99 in forum GRE Computer Science
    Replies: 18
    Last Post: 03-28-2008, 05:33 PM
  3. Driller on software systems: doubts
    By Nkruti in forum GRE Computer Science
    Replies: 1
    Last Post: 12-03-2003, 12:37 AM
  4. driller for errors !
    By wood in forum GRE Computer Science
    Replies: 2
    Last Post: 11-06-2003, 03:49 PM
  5. driller for hardware
    By nonevent99 in forum GRE Computer Science
    Replies: 18
    Last Post: 11-05-2003, 11:12 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •