Computer Science Study Guide

Casting and Conversions in Java

2012-03-28T21:23:00.000-07:00

Integer to string
int i=1234;
String s = String.valueOf(i);

String to Integer
String s = "5678";
int i = Integer.parseInt(s);

Character to string
char ch = 'a';
String s = Character.toString(ch);

Character to integer
char ch = '7';
int i = Character.getNumericValue(ch);

Find Two Numbers in an Array that Sum to a Particular Value

2012-01-23T21:29:00.000-08:00

We know that subset sum problem is np complete. But if we consider only subsets of size two, we can solve this problem in polynomial time.

Usually people tend to come up with n**2 solution. We can have a solution of order n if we use hashmaps

Algorithm

Iterate the array from i=0 to arraylength-1:
           if(hashMap does not contain key(sum - a[i]){
                insert ( a[i], sum[a-i])
           }
           else
           {
                return (a[i], sum-a[i])
            }

Logic:

After reading a value, check if its pair value (sum - a[i]) is already read.
If pair value is not read, insert the value read, and its pair value as key,value combination.
Otherwise return value and its pair value.

Android: Mediaplayer prepare() method crashes.

2011-06-14T14:48:00.000-07:00

If you tried to run voice recording with code from android developer site, you might have encountered this problem - prepare() method crashes. If you read logcat you can see that it is because of file permission problems. Device drive fails to create the file mentioned in the code.

Here is the work around:

Audio record is using a file that is not on the driver yet. So create a file named audio.3gp in your local file system. File can be empty.
On eclipse, open DDMS by Window> open perspective > DDMS
Open window > show view > File Explorer
Select data > local > temp
Click on 'push a file onto folder' button on the right top corner to bring up file select dialog.
Select audio.3gp created in the local file system. It will be added to data > local > temp in the device.

Change name of the file in code to "data/local/tmp/audio.3gp"
Now device driver can see the file and your project should run fine.

Andriod Emulator - Trouble shooting

2011-05-30T21:09:00.000-07:00

Problem:

When I use MapActivity, I can see grid of the map and zoom controls. But I cannot see the map.

Causes:
1. You have not set up mapkey in xml file properly. Check this to find out how.
or
2. Your map does not have a default location to show. Set up default location as follows:
On windows command line, type
telnet localhost 5554
geo fix -120.62 35.29
This will set a location for map to show.

or
3. You do not have internet connection

I cleaned up build and I cannot find R.java anymore

Causes:
There should be some error in one of the xml files. Correct it. Once xml files are correct, building project will create R.java automatically.

How can I find logcat on Android emulator
Open DDMS by
Go to windows > Open Perspective > DDMS

Then open logcat by
Window > Show view > logcat

Emulator is taking the whole screen. How can I resize emulator

Go to Window> Android SDK and AVD Manager
Select emulator and click on edit.
Enter width and height at Resolution fields under Skin to set new resolution.

Android error: error: Error: No resource found that matches the given name (at 'drawable' with value '@drawable/....').

2011-05-27T11:36:00.000-07:00

I have been getting this error and I could not figure out what is the problem. Finally figured out the reason.

This error means that R.java does not have a reference to the image file in question.
Check R.java under gen folder and find out if it has a location reference to the image file you added. If it does not, these are the possible reasons.

1. You forgot to add image file to res drawable folder
2. You added image file to a wrong drawable folder. There are three drawable directories, namely
drawable-hdpi, drawable-ldpi, drawable-mdpi. Try to add image to all three directories and one of them will work depending on the resolution size of your image.

3. You have another file in the folder with the same name. Rename one of them so that there are no name conflicts.

Rational Functional Tester- isEnabled() method on buttons throws exception.

2011-04-19T21:12:00.000-07:00

Problem: When using isEnabled method on a button disabled already throws ObjectNotFound exception.

Solution: Use buttonname(null,DISABLED).isEnabled() instead of buttonname().isEnabled()

SMTP trouble shooting : error 500 5.5.1 "Command unrecognized"

2011-03-20T18:43:00.000-07:00

I am able to set up connection with mail server .I get response from mail server while sending HELO message. But I get error 500 5.5.1 Command unrecognized"" when I send all other messages. I am sure it is not syntax error that causing the problem.

Solution :

Try appending your messages with carriage return and line feed.
Example,

"HELO mailserver_name\r\n";
"MAIL FROM:\r\n";
"RCPT TO:\r\n"

In SMTP, error messages starting with 500 is due to syntax errors in messages sent. Focus on the message you are sending while you are debugging.If that does not work, using telnet, try to send the same messages and make sure that mail server responds correctly. Refer RFC 821 for further reference.

REPLY CODES BY FUNCTION GROUPS

500 Syntax error, command unrecognized
[This may include errors such as command line too long]
501 Syntax error in parameters or arguments
502 Command not implemented
503 Bad sequence of commands
504 Command parameter not implemented

211 System status, or system help reply
214 Help message
[Information on how to use the receiver or the meaning of a
particular non-standard command; this reply is useful only
to the human user]

220 Service ready
221 Service closing transmission channel
421 Service not available,
closing transmission channel
[This may be a reply to any command if the service knows it
must shut down]

250 Requested mail action okay, completed
251 User not local; will forward to
450 Requested mail action not taken: mailbox unavailable
[E.g., mailbox busy]
550 Requested action not taken: mailbox unavailable
[E.g., mailbox not found, no access]
451 Requested action aborted: error in processing
551 User not local; please try
452 Requested action not taken: insufficient system storage
552 Requested mail action aborted: exceeded storage allocation
553 Requested action not taken: mailbox name not allowed
[E.g., mailbox syntax incorrect]
354 Start mail input; end with .
554 Transaction failed

How to set environmental variables in windows XP

2011-02-12T14:15:00.000-08:00

Note: Following procedures set system environmental variables permanently. For temporary settings use 'set name=value' in command line.

Option 1

Right click on My Computer.
Select properties.
Click on Advanced tab
Click on Environmental variables
Click on new under system variables
Enter name and value of environmental variable
Click ok.

Option 2

Click on Start > Control Panel > System
A window opens.
Click on Advanced tab
Click on Environmental variables
Click on new under system variables
Enter name and value of environmental variable
Click ok.

Logical and Vector Timestamps in Distributed Systems - Example

2010-12-07T21:33:00.000-08:00

Logical Time Stamp

Example 1

Vector Timestamps
Example 1

Example 2

Simple MapReduce Program Example in Python

2010-12-03T22:27:00.000-08:00

Given a set of integers, compute the sum of their square values.
(Assumption: You already know how to run a map reduce program using an input file and how to check the output)

mapper.py

#!/usr/bin/env python

import sys

# input comes from STDIN (standard input)
for line in sys.stdin:
    # remove leading and trailing whitespace
    line = line.strip()
    # split the line into numbers
    numbers = line.split()
    for number in numbers:
        num = int(number)
        square = num*num
        print '%s\t%s' % (1,square)

reducer.py

#!/usr/bin/env python

import sys

#sum initialized to zero
sum=0
# input comes from STDIN
for line in sys.stdin:
    # remove leading and trailing whitespace
    line = line.strip()
    # parse the input we got from mapper.py
    word, square = line.split('\t', 1)
    # convert square(currently a string) to int
    try:
        square = int(square)
        sum=sum+square
    except ValueError:
        # count was not a number, so silently
        # ignore/discard this line
        pass
#print sum of squares
print '%s'% (sum)
___________________________________________________________________
input.txt
1 2 3 4

output/part-0000
30

NP completeness exam questions

2010-12-03T09:49:00.000-08:00

Consider a reduction of problem A to problem B. What is the most precise claim you
can make about problem B for each of the following situations?

a) A is NP-complete and the reduction is in polynomial time.
NP-hard. (At least as hard as NP-complete problem.)

b) A is in polynomial time and the reduction is also in polynomial time.
B could be anything.

c) A is NP-complete and the reduction is in Pspace.
B could be anything.

d) A is in nondeterministic polynomial time and the reduction is in polynomial time.
B is at least as hard as A, but nothing more can be said.

e) A requires exponential time and the reduction is in polynomial time.
B must requires polynomial time for deciding.

f) A is Pspace complete and the reduction is in Pspace.
B could be anything.
_______________________________________________________________________
Suppose you could reduce an NP complete problem to a polynomial time problem in
polynomial time. What would be the consequence?
What if the reduction required exponential time?

If we could reduce an NP-complete problem to a problem in P, then NP will
be equal to P. If the reduction required exponential time, then there is not
special consequence. (In fact any NP-complete problem can be reduced to
a polynomial time solvable problem using exponential time reduction.)
_______________________________________________________________________

True-Sat problem is NP-complete

2010-12-01T15:26:00.000-08:00

TRUE-SAT = {boolean expressions E in conjunctive normal form that
                   (1) are true when all variables are set true, AND ALSO
                   (2) have some other truth assignment that makes E true}
            This can also be stated (in Garey-Johnson notation) as:
             Instance: Set of clauses C₁,C₂,....C_k over the boolean variables u₁,u₂,....u_m
             Question:
                     (1) are all C_i true when u₁,u₂,....u_m are set to true, and
                     (2) is there another satisfying truth assignment (not all variables set to true)?

First, Show TRUE_SAT is in NP. (This is left as an exercise)
Then show TRUE-SAT is NP-hard.
If an expression is not true when all variables are true, then it is surely not in TRUE-SAT.

To show TRUE-SAT is NP-complete, we reduce SAT to it. Suppose we are given an expression E with variables a,b,c.

Convert E to E' as follows:
Test if E is true when a = T, b=T and c=T.
If so, we know E is satisfiable, then add (a U a') to E.
                 E' = E U ( a U a' )
         // E satisfies first condition. a U a' satisfies the second condition.
Otherwise
                E' = E U ( a U b U c )
                //Adding a U b U c satisfies first condition. If E is in SAT, that satisfies the second condition.
Therefore, TRUE_SAT accepts only when E is in SAT. Hence TRUE-SAT is reducible to SAT and TRUE-SAT is NP-complete.

PageRank Algorithm Using Mapreduce

2010-11-29T12:09:00.000-08:00

Description - http://en.wikipedia.org/wiki/PageRank

Examples of pagerank calculation - http://pagerank.suchmaschinen-doktor.de/index/examples.html

Formula for pagerank calculation:

PR(A) = (1 - d) + d * SUM ((PR(I->A)/C(I))

Where:

PR(A) is the PageRank of your page A.
d is the damping factor, usually set to 0,85.
PR(I->A) is the PageRank of page I containing a link to page A.
C(I) is the number of links off page I.
PR(I->A)/C(I) is a PR-value page A receives from page I.
SUM (PR(I->A)/C(I)) is the sum of all PR-values page A receives from pages with links to page A..

Inputs and Outputs of Mapper and Reducer - https://wiki.umiacs.umd.edu/ccc/images/e/ea/CLuE-Jagannathan.pdf

Video lecture

Factorization of a Number is in NP. Why?

2010-11-25T14:54:00.000-08:00

Factoring a number seems to be trivial. The fact is that factorization when done in binary takes non-polynomial time.

For more information check http://en.wikipedia.org/wiki/Integer_factorization

Polynomial Reduction Example

2010-11-17T22:30:00.000-08:00

Show that WRITE_ONE_TM = {M : M is a Turing machine that writes a 1 on its tape } is undecidable.

Let us assume that WRITE_ONE_TM is decidable. Then there exists a Turing machine WRITE_ONE_TM, which can tell you if a given Turing Machine M will write a 1 on its tape on input z.

Let us look at how WRITE_ONE_TM works.

M is the input to WRITE_ONE_{TM .}

If M writes a 1 on its tape , WRITE_ONE_TM accepts. – Yes instance

If M does not write a 1 on its tape, WRITE_ONE_TM rejects. – No instance.

If M writes a 1 on its tape at any time of its computation, WRITE_ONE_TM decides yes. It does not matter what M does before it writes 1 on its tape.

M might have 10000 transitions before it writes 1 on its tape. Still WRITE_ONE_TMshould be able to decide whether M will write 1 on its tape.

M might compute what is 5+7 before it writes 1 on its tape. Still WRITE_ONE_TMshould be able to decide whether M will write 1 on its tape.

M can watch a youtube video and then write a 1 on its tape. Still WRITE_ONE_TMshould be able to decide whether M will write 1 on its tape.

( just kidding)

M might simulate another Turing Machine and then write a 1 on its tape. Still WRITE_ONE_TMshould be able to decide whether M will write a1 on its tape.

Suppose M is simulating another machine T on input w on M’s tapes and if T accepts w, M is writing a 1 on its tape. Still WRITE_ONE_TMshould be able to decide whether M will write a1 on its tape.

Did you hear that?

Isn’t that a solution to decidability of A_TM. Whenever you have to decide if a TM T will accept or reject w, all you have to do is:

Construct a new TM, M such that

· It simulates T on input w on M’s tape

· If T accepts w, write a 1 on M’s tape.

· Feed M to WRITE_ONE_TM

· If WRITE_ONE_TMdecides yes, T accepts w.

But we already know that A_TM is undecidable. So it is not possible that WRITE_ONE_TM can be decidable if it can solve A_TM.

Hence WRITE_ONE_TMis undecidable.

Number of full nodes in a binary tree c++

2010-11-02T11:49:00.000-07:00

A FULL node in a binary tree is a node that has exactly two non-null children. Write a RECURSIVE function that returns the number of full nodes in a binary tree.

# include <iostream >
#include <stdio.h >

using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
};

int FullNodes(TreeNode* root){


    if(root == NULL)        //if tree is empty
        return 0;
    if(root->left == NULL && root->right == NULL)         //leaf nodes
        return 0;
    if(root->left!=NULL && root->right != NULL)             // Full Nodes
        return 1 + FullNodes(root->left) + FullNodes(root->right);

    if(root->left==NULL && root->right != NULL)           //Nodes with no left child
        return FullNodes(root->right);

    if(root->left!=NULL && root->right == NULL)          // Nodes with no right child
        return FullNodes(root->left);

}
/*---------------------------------TEST---------------------------------*/

//Function to insert into binary tree
void insert(TreeNode*& root, int num){

    if(root == NULL){
        root = new TreeNode();
        root->value = num;
        root->left = NULL;
        root->right = NULL;

    }
    else if(num < root->value){
        insert(root->left,num);
    }
    else
        insert(root->right,num);
}

int main(){

//creates a tree
    TreeNode* tree = NULL;
    insert(tree, 8);
    insert(tree, 5);
    insert(tree,10);
    insert(tree, 3);
    insert(tree, 9);
    insert(tree, 6);


//Full Node count test
    cout << FullNodes(tree); //8 and 5 are full nodes . So output is 2

    return 0;
}

MPI Programming Exam Questions

2010-10-18T10:48:00.000-07:00

Feel free to give answers to unanswered questions as comments

1. Sum of prime factors :

http://people.sc.fsu.edu/%7Ejburkardt/presentations/fdi_2008_lecture8.pdf#page=16

Add up the prime numbers from 2 to N.
Each of P processors will simply take about 1/P of the range of
numbers to check, and add up the primes locally.
When it's done, it will send the partial result to processor 0.

2. Deadlock avoidance when using blocking send and receive in order.

http://www.cs.ucsb.edu/~hnielsen/cs140/mpi-deadlocks.html

In MPI, when does a non-blocking recv message return?

What is an MPI communicator? What is MPI_COMM_WORLD?

Two processors must be in a common "communicator group" in order to communicate. This is simply a way for the user to organize processors into sub-groups. All processors can communicate in the
shared group known as MPI_COMM_WORLD.

In MPI, what is a process rank?

True or false: In MPI you set the number of processes when you write the source code.

No. Number of processes are given on execution.

Give a short piece of pseudocode that illustrates the master/slave programming model.

Explain if the following MPI code segment is correct or not, and why:
Process 0 executes:

MPI_Recv(&yourdata, 1, MPI_FLOAT, 1, tag, MPI_COMM_WORLD, &status);
MPI_Send(&mydata, 1, MPI_FLOAT, 1, tag, MPI_COMM_WORLD);

Process 1 executes:

MPI_Recv(&yourdata, 1, MPI_FLOAT, 0, tag,MPI_COMM_WORLD, &status);
MPI_Send(&mydata, 1, MPI_FLOAT, 0, tag, MPI_COMM_WORLD);

Both are blocking receives waiting for each other to send. System is deadlocked.

Suppose that process 0 has variable A, and process 1 also has a variable A. Write MPI-like pseudocode to exchange these values between the processes.

          P0:
send(P1,A)
          recieve(P0,A)

          P1:
recieve(P1,A)
          send(P0,A)

Explain the purpose of each of the library calls listed.

· MPI_Init

· MPI_Finalize

· MPI_Comm_rank

· MPI_Comm_size

· MPI_Send

· MPI_Recv

· MPI_Barrier

· MPI_Bcast

· MPI_Scatter

· MPI_Gather

· MPI_Reduce

What is an MPI derived datatype and when would you use one? Give an example.
In MPI, when does a blocking recv message return?
Blocks until it receives message
True or false: You can write a program using MPI that will run across all of the cores of your multicore computer in parallel. Also, if this is possible, indicate if you think this is a good way to write the program. You must justify your answer to receive credit.
Discuss marshalling in MPI.
When does a blocking send return.

MPI uses buffering by default. Send returns when message is saved in receivers buffer. Process calling MPI_Send can continue even if destination has not received the message.

16. Programming question 1 : http://www.cs.usfca.edu/~peter/cs220/mt1_old_key#page=6.pdf
17. Programming question2 : http://www.cs.usfca.edu/~peter/cs220/mt1_key#page=4.pdf

3 bit up counter using D flipflops

2010-10-06T23:16:00.000-07:00

Memory management questions

2010-09-29T12:08:00.000-07:00

Assume you have a small virtual address space of size 64 KB. Further assume that this is a system
that uses paging and that each page is of size 8 KB.
(a) How many bits are in a virtual address in this system?

16 (1-KB of address space needs 10 bits, and 64 needs 6; thus 16).

(b) Recall that with paging, a virtual address is usually split into two components: a virtual page number (VPN) and an offset. How many bits are in the VPN?

3. Only eight 8-KB pages in a 64-KB address space.

(c) How many bits are in the offset?

16 (VA) - 3 (VPN) = 13.
Alternately: an 8KB page of course requires 13 bits to address each byte (213 = 8192).

(d) Now assume that the OS is using a linear page table, as discussed in class. How many entries does this linear page table contain?

One entry per virtual page. Thus, 8.

Now assume you again have a small virtual address space of size 64 KB, that the system again uses paging, but
that each page is of size 4 bytes (note: not KB!).

(a) How many bits are in a virtual address in this system?

Still 16. The address space is the same size.

(b) How many bits are in the VPN?

14.

(c) How many bits are in the offset?

Just 2 (4 bytes).

(d) Again assume that the OS is using a linear page table. How many entries does this linear page table
contain?
2**14, or 16,384.
____________________________________________________________________________________

Consider the following segment table:

Segment  Base  Length
    0   219    600
    1  2300     14
    2    90    100
    3  1327    580
    4  1952     96

What are the physical addressed for the following logical addresses?

(a) 0,430

(b) 1,10

(d) 3,400

(e) 4,112

(a) 219 + 430 = 649
(b) 2300 + 10 = 2310
(c) illegal reference; traps to operating system
(d) 1327 + 400 = 1727
(e) illegal reference; traps to operating system

___________________________________________________________________________

Consider a paging system with the page table stored in memory.

(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?

(b) If we add associative registers, and 75% of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)

400 nanoseconds. 200 ns to access the page table plus 200 ns to access the word in memory.
250 nanoseconds. 75% of the time it's 200 ns, and the other 25% of the time it's 400ns, so the equation is:
```
e.a. = (.75*200)+(.25*400)
```
________________________________________________________________________

A certain computer provides its users with a virtual memory space of 2**32 bytes. The computer has 2**18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4K bytes. A user process generated the virtual address 11123456. Explain how the system establishes the corresponding physical location.

* The virtual address in binary form is

0001 0001 0001 0010 0011 0100 0101 0110

Since the page size is 2**12, the page table size is 2**20. Therefore, the low-order 12 bits (0100 0101 0110) are used as the displacement into the page, while the remaining 20 bits (0001 0001 0001 0010 0011) are used as the displacement in the page table.

__________________________________________________________________________________

Round robin scheduling questions

2010-09-29T11:53:00.000-07:00

1. Consider N processes sharing the CPU in a round-robin fashion (N>=2). Assume that each context switch takes S msec and that each time quantum is Q msec. For simplicity, assume that processes never block on any event and simply switch between the CPU and the ready queue.

In the following your answers should be functions of N, S and T.

a) Find the maximum value of Q such that no process will ever go more than T msec

Time taken for one process per quantum = quantum,Q+context switch,S

Max wait time, T = N(Q+S)

T = NQ+NS
Q = (T-NS)/N

b) Find the maximum value of Q such that no process will ever go more than T msecs between executing instructions on the CPU?

Max wait time, T = N(Q+S) - Q ie.last instruction just before context switch executes at the end of the quantum of the first time when process executes..
T = NQ+NS-Q
T = Q(N-1)+NS
Q = (T-NS)/(N-1)

2. Suppose that there are two processes, PH and PL, running in a system. Each process is single-threaded. The operating system’s scheduler is preemptive and uses round-robin scheduling with a quantum of q time units.

The scheduler supports two priority levels, HIGH and LOW. Processes at LOW priority will run only if there are no runnable HIGH priority processes. Process PH is a HIGH priority process.
It behaves as described in the following pseudo-code:

while (TRUE) do
compute for tc time units
block for tb time units to wait for a resource
end while

That is, if this process were the only one running in the system, it would alternate between running for tc units of time and blocking for tb units of time. Assume that tc is less than q.

Process PL is a low priority process. This process runs forever, doing nothing but computation. That is, it never blocks waiting for a resource.

a. For what percentage of the time will the low priority process PL be running in this system?Express your answer in terms of tb and tc.

tb/(tb + tc)

b. Repeat part (a), but this time under the assumption that there are two HIGH priority processes (PH1 and PH2) and one LOW priority process (PL). Assume that each HIGH priority process waits for a different resource. Again, express your answer in terms of tb and tc. Your answer should be correct for all tb greater than 0 and all 0 less than tc less than q.

(tb−tc)/(tb+tc) if tc is less than tb

0 if tc greater than or equal to tb
------------------------------------------------------------------------------------------------------------
Suppose a processor uses a prioritized round robin scheduling policy. New processes are assigned an initial quantum of length q. Whenever a process uses its entire quantum without blocking, its new quantum is set to twice its current quantum. If a process blocks before its quantum expires, its new quantum is reset to q. For the purposes of this question, assume that
every process requires a finite total amount of CPU time.
(a) Suppose the scheduler gives higher priority to processes that have larger quanta. Is starvation possible in this system? Why or why not?
No, starvation is not possible. Because we assume that a process will terminate, the worst
that can happen is that a CPU bound process will continue to execute until it completes.
When it finishes, one of the lower priority processes will execute. Because the I/O bound
processes will sit on the low priority queue, they will eventually make it to the head of the
queue and will not starve.
(b) Suppose instead that the scheduler gives higher priority to processes that have smaller quanta. Is starvation possible in this system? Why or why not?
Yes, starvation is possible. Suppose a CPU bound process runs on the processor, uses its
entire quantum, and has its quantum doubled. Suppose a steady stream of I/O bound processes
enter the system. Since they will always have a lower quantum and will be selected for
execution before the process with the doubled quantum, they will starve the original process.
_______________________________________________________________
Assume that 3 processes all with requirements of 1 second of CPU time each and
no I/O arrive at the same time.

a)What will be the average response time (i.e., average time to
completion) for the processes Round Robin (RR) scheduling assuming a timeslice of 0.1 sec and no overhead for context switches (i.e., context switches are free).

Answer: 2.9 seconds

Explanation:

Time for completion for process A =0.28
Time for completion for process B =0.29
Time for completion for process C = 0.30

Average time for completion =0. 29
________________________________________________________________________________________________________

Suppose that the operating system is running a round-robin scheduler with a 50 msec time quantum. There are three processes with the following characteristics:

* Process A runs for 60 msec, blocks for 100 msec, runs for 10 msec and terminates.
* Process B runs for 70 msec, blocks for 40 msec, runs for 20 msec, and terminates.
* Process C runs for 20 msec, blocks for 80 msec, runs for 60 msec, and terminates.

Process A enters the system at time 0. Process B enters at time 10 msec. Process C enters at time 20 msec. Trace the evolution of the system. You should ignore the time required for a context switch. The time required for process P to block is the actual clock time between the time that P blocks and the time that it unblocks, regardless of anything else that is happening.
Answer:

Time Running process Events
0-50 A B enters at time 10. C enters at time 20.
50-100 B
100-120 C C blocks until time 200.
120-130 A A blocks until time 230.
130-150 B B blocks until time 190
150-190 Idle B unblocks at time 190
190-210 B C unblocks at time 200. B terminates at time 210
210-260 C A unblocks at time 230.
260-270 A A terminates at time 270.
270-280 C C terminates at time 280.

_______________________________________________________________________________________________
Consider a variant of the round-robin scheduling algorithm where the entries in the ready queue are pointers to process-control-blocks.

1. What would be the effect of putting two pointers to the same process in the ready queue?

Doubling the time given to that process.
2. What would be the major advantages and disadvantages of this scheme?

Simple scheme which would provide some priority work with minimal modification to scheduler. But, overhead for managing pointers is a nuisance -- what if the process is io waiting or done? Have to remove BOTH pointers from ready queue, etc. Also may increase overhead if same process runs back-to-back -- it was not necessary to switch contexts.
3. How would you modify the basic round-robin algorithm to achieve the same effect without duplicate pointers?

Add a simple quantum indicator to PCB.
_______________________________________________________________________________________________

For each of the following statements, indicate whether you think it is probably true (T) or probably false (F). Then give a brief (one sentence) reason. There is not necessarily a single correct answer to each question, so your one sentence explanation is the most important part of your answer.

1. Small time slices always improve the average completion time of a system.

Probably false: Small time slices will sometimes improve the average response of the system. If the slice is too small, the context switching time will start to dominate the useful computation time and everything (including response time) will suffer.

2. Using a round robin scheduler, a large time slice is bad for interactive users.

Probably true: Large time slices can allow non-interactive processes keep control of the CPU for longer periods of time, causing the interactive processes to be less responsive.

3. Shortest Job First (SJF) or Shortest Completion Time First (SCTF) scheduling is difficult to build on a real operating system.

Probably true: SCTF scheduling requires knowledge of how much time a process is going to take. This requires future knowledge. You might require a user to specify the maximum amount of time that a process could run (and kill it if it exceeds this amount), then use a variant on SCTF.

________________________________________________________________________________

5 Variable Karnaugh Map Solution

2010-09-22T09:52:00.000-07:00

Simplify the Boolean function
F(A,B,C,D,E) = Σ (0,2,4,6,9,11,13,15,17,21,25,27,29,31)

Writing decimals in binary,

Decimal   A   B   C   D   E
     0   0   0     0   0   0
     2   0   0    0   1   0
     4   0   0   1   0   0
     6   0   0   1   1   0
     9   0   1   0   0   1
     11   0   1   0   1   1
     13   0   1   1   0   1
     15   0   1   1   1   1
     17   1   0   0   0   1
     21   1   0   1   0   1
     25   1   1   0   0   1
     27   1   1   0   1   1
     29   1   1   1   0   1
     31   1   1   1   1   1

Construct two Karnaugh maps for variables A,B,C and D when E=0 and E=1

From Karnaugh map E=0, F0 = A'B'E'

From Karnaugh map E=1, F1 = BE+ AD'E

F = F0+ F1

F = A'B'E' + BE + AD'E

Computer Architecture - Counters

2010-09-19T22:45:00.000-07:00

Overview - Types of counters

Recurrence relations examples

2010-09-08T16:43:00.000-07:00

Solve the recurrence relation T(n) = T(n/2) + lg(n) where T(1) = 1 and n = 2k for a nonnegative integer k. Your answer should be a precise function of n in closed form. Note that lg represents the log function base 2.

T(n) = T(n/2) + lg(n)

T(n/2) = T(n/4) + lg(n/2)

T(n/4) = T(n/8) + lg(n/4)

T(n/8) = T(n/16) + lg(n/8)

Substituting for T(n)

T(n) = T(n/2) + lg(n)

= T(n/4) + lg(n/2)+lg(n)

= T(n/8)+ lg(n/4)+ lg(n/2)+lg(n)

= T(n/16)+lg(n/8)+ lg(n/4)+ lg(n/2)+lg(n)

----------------------------------------------------------

----------------------------------------------------------

Suppose n= 2**k

T(n) = 1 + lg (n. n/2 . n/4. . . . . n/2**k-1)

= 1+ lg(2**k . 2**k-1 . 2**k-2 . …… . 2)

= 1+ lg( 2 **(1+2+3+ - - - +k))

= 1 + (1+2+3+ ----+k)

= 1+ k(k+1)/2

______________________________________________________________________________

Solve the recurrence T(n) = T(n-1) + n

T(n)    = T(n-1) + n
T(n-1) = T(n-2) + n-1
T(n-2) = T(n-3) + n-2
T(n-3) = T(n-4) + n -3

T(n) = T(n-1) + n
   = T(n-2) + n-1+n
   =   T(n-3) + n-2+n-1+n
   =   T(n-4) + n-3+n-2+n-1+n
-----------------------------------------------

        Consider n= 2**k
T(n) = T(n-k) + n+n-1+n-2+n-3+ -------------+n-(k-1)
         = T(n-k) + n(n-1) - k(k-1)/2
         = T(n-k) + n**2 - n -lgn(lgn-1)/2

Therefore, asymptotic complexity is n**2

Delete a linked list using recursion in C++

2010-08-31T12:06:00.000-07:00

#include < iostream >
using namespace std;

struct Node{
    int num;
    Node* next;
};

//Here address of pointer to the list is passed so that head of the list will not be a local variable.

void DeleteListRecursion(Node*& list){
    if(list == NULL)
        return;
    else
    DeleteListRecursion(list->next);
    delete(list);
    list = NULL;
}

Node* Insert(int number, Node* list){
    Node* node = new Node;
    node->num = number;
    node->next = list;
    return node;
}

//TEST

int main(){

    Node* list = NULL;

    list = Insert(5,list);
    list = Insert(7,list);
    list = Insert(9,list);
    list = Insert(4,list);
    list = Insert(6,list);
    list = Insert(3,list);

    DeleteListRecursion(list);

    return 0;
}

Data Structures You Should Know

2010-08-28T10:38:00.000-07:00

Big Oh of common algorithms : http://www.mcs.csueastbay.edu/~billard/cs3240/big-oh.html
Binary Search

UnSorted List Using Arrays
UnSorted List Using Linked List
Sorted List Using Arrays
Sorted List Using Linked List

Doubly Linked List
Circular List

Stack Using Arrays
Stack Using LinkedList

Queue Using arrays
Queue Using LinkedList

Recursion Problems

Binary Tree

Graph

Minimum Spanning Tree

Kruskals Algorithm Pseudocode Example
Prim's Algorithm Pseudocode Example

Sorting

Bubble Sort Code Example
Selection Sort Code Example
Insertion Sort Code Example
QuickSort Code Example
MergeSort Code Example
HeapSort Code Example
Radix Sort Code Example

Hashing