DISCRETE MATH/PROBABILITY QUESTIONS IN JEE ADVANCED 2020 (Math) Paper

JEE Advanced Paper#2 

Q.2  The probability that a missile hits a target successfully is 0.75. In order to destroy the target completely, at least three successful hits are required. Then the minimum number of missiles that have to be fired so that the probability of completely destroying the target is NOT less than 0.95, is _____

Solution:  Let X be random variable that denotes the number of successful hits on firing $n$ missiles. The question is asking for $P(X\ge3) \ge 0.95$.  Let $n$ denote the number of missiles fired. $P(X\ge3)$ is $1 -$ (probability no missile hits the target out of $n$ missiles fired) $+$ (probability that single missile hits the target out of $n$ missiles) $+$ (probability that 2 missile hits target out of $n$ missiles fired)

$ (1 - (P(X = 0) + P(X = 1) + P(X = 2)) \ge 0.95$

$ (P(X = 0) + P(X = 1) + P(X = 2) \le 0.05$

$ ((1/4) ^n + (1/4)^{n-1} \times (3/4) + (1/4)^{n-2} \times (3/4)^{2}) \le 0.05 $

$ 10(9n^{2}-3n+2) \le 4^{n}$

The minimum of n for which the above is satisfied is 6.

Hence answer is 6

Q.13 An engineer is required to visit a factory for exactly four days during the first 15 days of every month and it is mandatory that no two visits take place on consecutive days. Then the number of all possible ways in which such visits to the factory can be made by the engineer during 1-15 June 2021 is _____

Solution: This is a standard problem which you might have come across in some other form. This question is equivalent to finding  set of 4 integers from the set {1,2,3,..., 15} such that no two integers occur consecutively. We can think of this as counting number of binary strings with 15 bits having 4 non-consecutive 1's. There are 11 zeros and we need to put 1 in between, before or after this zeros. This is equivalent to putting a bar/filling the 12 gaps between these zeros. The number of ways it could be done is C(12,4) which is 495.

Hence the answer is 495.

Q.14 In a hotel, four rooms are available. Six persons are to be accommodated in these four rooms in such a way that each of these rooms contains at least one person and at most two persons. Then then number of all possible ways in which this can be done is _____

Solution: There has to be at least one person in each room. We pick one person from 6 person and put in the first room. Likewise for the second room, we can pick from remaining 5. The number of ways we can do this is $6 \times 5 \times 4 \times 3$. There would be remaining two persons and these two persons can be distributed in 4 rooms as $C(4,2) = { 4! \over {2!2!}}=6$. Thus the total number of all possible is ways is $(6 \times 6 \times 5 \times 4 \times 3)/2 = 1080$ (Division by 2 is to account for  over counting (eg: 2,1 and 1,2 in the room are the same.))  

Hence the answer is 1080.

Q.15 Two fair dice, each with faces numbered 1, 2, 3, 4, 5 and 6, are rolled together and the sum of the numbers on the faces is observed. This process is repeated till the sum is either a prime number or a perfect square. Suppose the sum turns out to be a perfect square before it turns out to be a prime number. If p is the probability that this perfect square is an odd number, then the value of 14p is _____

Solution:  Let $P_{ps}$ denote probability the sum is a prime number or square , $P_{s}$ denote probability the sum is a perfect square and $P_{o}$ denote the probability the perfect square is an odd number. Let $P_{ps}^{'}$ denote the complement probability of $P_{ps}$

Then $p$ the probability (as asked in question) is 

$$ ({P_{o} + P_{ps}^{'}P_{o} + P_{ps}^{'2}P_{o} + ....}) /(P_{s} +P_{ps}^{'}P_{s} + P_{ps}^{'2}P_{s} + .... )        =  P_{o}/P_{s}$$ 

The 7 following pairs produce perfect squares (1,3), (2,2) , (3,1) , (3,6) , (4,5), (5,4), (6,3) of which 4 make the odd square. Thus $P_{s} = {7 \over 36}$ and $P_{o} = {4 \over 36}$. Therefore the value of $p$ is $4 \over 7 $. Thus the value of 14p is 8.

Paper #1

Q.5 Let C1 and C2 be two biased coins such that the probabilities of getting head in a single toss are 2/3  and 1/3 , respectively. Suppose α is the number of heads that appear when C1 is tossed twice, independently, and suppose β is the number of heads that appear when C2 is tossed twice,independently. Then the probability that the roots of the quadratic polynomial x2 − αx + β are real and equal, is

(A) 40/81  (B) 20/81  (C) 1/2   (D) 1/4

Solution: Roots are real and equal when discriminant is zero.

$$b^2 - 4ac = 0  => (-\alpha)^2 - 4 (1) (\beta) = 0 => \alpha^2 = 4\beta$$

On two coin tosses, we can have 0,1,2 heads. There are two cases under which the above equation is satisfied. 

• 0 number of heads on two tossing of the  first biased coin $(\alpha$) and 0 number number of heads on tossing of the second biased coin $(\beta$). The probability for this occurrence is $  {1 \over 3} \times {1 \over 3} \times {2 \over 3} \times {2 \over 3} = {4 \over 81} $.
• 2 heads on two tossing of the first biased coin $(\alpha)$ and 1 head on two tossing of the second biased coin $(\beta)$. The probability for this occurrence is ${ 2 \over 3 } \times  {2 \over 3} \times ({1 \over 3 } \times  {2 \over 3 } + {1 \over 3} \times {2 \over 3}) = {4 \over 9}  \times {4 \over 9} = {16 \over 81}.$

Hence the probability that the roots of the quadratic polynomial $x^2 - \alpha x + \beta$ is ${4 \over 81} + {16 \over 81} = {20 \over 81}$. Therefore the correct answer is B.

Rollback and Recovery, Write Ahead Logging - Database Systems - Part I

Introduction

In this article, I will discuss about transaction rollback and recovery component of database systems. Transaction defines a logical piece of work in database systems and adheres to  ACID semantics (Atomicity, Consistency, Isolation and Durability) inherent  of most relational database systems.

The key property of atomicity and durability is ensured by the logging component in the database. This component provides for transaction rollback and recovery. In discussion that follows, we shall first define a physical model and then on top of it we build an abstraction which ensures these properties. First and foremost, let me delve into problems which arises in data management systems and how the notion of transaction solves these problems.

To illustrate the idea of why  notion of transactions is needed, let's start with a typical real-life application scenario. The canonical example that we take is a  fund transfer application involving multiple user accounts. This is  a common application which falls under the category of OLTP (Online Transaction Processing Systems). Clearly many users would be wanting to transfer funds from one account to another and as such a centralised system which hosts the database should allow multiple users to do this operations concurrently. This is necessary because of increased throughput and reduced response time as well as to make effective usage of the system resources. In addition, the system hosting the database can fail due to power failure or the database process may be killed or the database process may crash while it's serving  requests. The database needs to recover from such failures and the data in it remains consistent. To address this problems, the logical notion of transaction is introduced. The transaction is a logical unit of requests/steps which ensures the following properties:

1. Atomicity: The multi-step operations either happens or doesn't happen at all.

2. Isolation:The effects of the other transaction that are running in parallel should not be visible to other transactions and each appear to run as if in isolation.

3. Consistency: The database preserves it's consistency in the face of multiple executions of the transactions. The data it holds is always consistent. This is usually enforced at high level by specification of  constraint conditions on logical data housed by the database by application developer.

4. Durability: Once a transaction is completed, it's effects are persisted. This property ensures the transactions to cope with failures.

In order to ensure the above properties are preserved under conditions of failure, the transaction subsystem of a database is made up of  lock manager & concurrency control component, logging & recovery component. The logging and recovery components masks  different kinds of failures. The various types of failures are:

• Transaction Failure: A transaction can be explicitly aborted by user or aborted as a result of exceptional conditions like resource not available. A transaction can also be aborted to break a deadlock either by user or by the deadlock prevention subsystem in a data management system. In these cases, the effects of the  transactions needs to be undone.
• Disk Failure: This type of failure include the  disk head crash or the disk blocks that make the storage device undergoes corruption. This shall result in the reads and writes from the disk failing and hence causing the transaction to fail.
• System Failure: Systems may fail either due to  power failure or software crash. We need to make sure that no committed transactions are lost (action needs to be redone) and the pending transactions needs to be undone.

Physical Model

Before we detail logging & recovery component, the section shall briefly introduce storage layer/ physical model of the database. All data transfers between  disk and  main memory happen in units of fixed size (usually 4K-16K) chunks called pages. Data records and other logical structures are abstracted and stored on pages. All high-level operations on data objects shall be mapped onto read & write operations on pages. The most recently or most frequently used pages are cached in memory to exploit locality in page access patterns thereby avoiding expensive disk i/o. The subsystem which manages in-memory cache of page is known as  buffer manager. The buffer frame consists of the page data along with the state info such as pageid, state (dirty or clean), latch (read-write lock to protect the page) and actual data contained on the page.   

 

The high-level interface to buffer manager consists of following two operations:

1. pin(pageNum): This requests the pageNum from the buffer manager. The page shall be brought into memory if required and it shall be marked clean. The reference to the buffer frame is returned.
2. unpin(pageNum, dirty): Release pageNum and mark dirty if dirty flag is true. The unpin makes the buffer frame eligible for eviction. Buffer frame marked with dirty bit shall have their pages written to disk. During unpin the dirty pages are not written back to disk instead marked dirty. This is known as write back instead of write through (or force). This helps in better transaction response time and less I/O cost. 

When buffer frame is not available on request by pin interface, a suitable candidate is chosen for eviction. The replacement strategy decides which buffer frame to replace. There are various strategies like LRU, MRU , 2Q etc.

Formal Definition of Transaction

As discussed in the previous section, all high-level operations can be modelled as sequence of read and write operations on pages. This abstraction helps in reasoning out properties/operations associated with transactions. 

Formally a transactions is a pair $(op, <)$ where op is a sequence of operations. These operations  are: 

1.  $r(x)$: Read the data item x.
2.  $w(x)$: Write the data item x
3.  $a$: Abort the operation.
4.  $c$: Commit
5.  $b$ : Begin of transaction (implicit).

The operation abort appears if and only if the commit doesn't appear in the sequence.

The partial order $\lt \subseteq op \times op$  on set $op$ such that:

If ${op1, op2} \subseteq op$ such that op1 and op2 access the same data item and at least one of them is a write operation , then op1 $\lt$ op2 $\lor$ op2 $\lt$ op1. This defines total order on operations involving read and write or two writes on the same data item.

Introducing the log

To support recovery and rollback, all updates to a page must be logged. The log updates are stored in a transaction log. The log records exists in  log buffer in memory as well on disk, the log storage. All updates are logged as log record on the log buffer (which in turn is flushed to log storage at time of commit). The log record store combinations of redo or undo required for  

Redo or undo are decided based on the replacement strategies adopted by the buffer manager and the write strategies adopted for committed transactions. The replacement strategies for replacing buffer pages involve two options:

• No Steal:- Pages that have been modified by active transactions shall not be replaced.
• Steal:-  Any unpinned page can be paged out if new pages need to be bought in. This allows for more buffer memory to be made available which shall allow for larger database updates. The modified pages shall be written to disk.

The write strategies for committed transactions involve:

• Force:- The changes are forced to disk when transaction commits (also called write-through).
• No Force:-  The changes are not committed to disk at time of transaction commit. They may be written back to disk at some later time.

In addition, another dimension is how page updated in in-memory cache is reflected on-disk. There are two approaches:

1. The page updated in cache shall be modified in-place with the same on-disk page in database. This is called the update-in place.
2. The new updates to page shall be installed to a separate copy of old page along with the updates. Then an indirection table is used to switch to the newer version atomically at time of commit. This  approach is called shadowing. 

The update in place requires the use of undo information to be available for recovery.  For no force, the redo information should always be able in the log. To ensure high throughput, less overhead and better response time, optimising disk i/o throughput during normal operation of database, the no force steal approach along with the update-in place is used in almost all on-disk database systems.  This complicates recovery of database at start time following a crash.  In  discussions that follow, we outline basic principles , data structures and algorithms required that recovery using the no force steal using the update-in place strategy.

Write Ahead Log Principle

Recovery in database systems which adopt No Force Steal paradigm is based on the Write Ahead Log principle. The "write ahead" indicates an ordering constraint imposed on writes made to the log and the database.  The Write Ahead Log  Write Ahead Log involves  following two principles:

• All log entries pertaining to the transaction shall be written to disk before transaction commit. 
• When a modified page is written to disk, all the log updates involving this page shall be written to disk. 

Log on disk is ordered by a monotonically increasing number known as log sequence number. Below is the diagram of the log.

Let flushed_lsn denote lsn of the last log record flushed so far. Each page has a page_lsn which is the lsn of the latest log update record which corresponds to the update on this page . Then as per WAL before a page can be flushed to disk, the following condition need to be met $$page_lsn $\le$ flushed_lsn$$.

Below is the format of the log record. 

It contain the common header (which is common to all types of log records).  The fields of the common header include

• lsn : It is the log sequence number. All log records are ordered by this identifier which is monotonically increasing.
• type: It indicates the type of log record and the various types of log records are:

1. Update Log Record:- This log record an update. The log record contains the additional fields page_id, page_offset, before_image and after_image. This info records helps in redoing the update during the crash recovery process.
2. Commit Log Record:-  A commit log record is written when the transaction is committed.
3. Abort Log Record :-  When a transaction aborts , an abort log record is written to the log.
4. Begin Checkpoint Log Record:-  A checkpoint is done in order to reduce recovery time as well as the amount of log which needs to be kept.  We use fuzzy checkpoint mechanism meaning during checkpoint the transactions processing  is not stopped and the state captured doesn't represent information at particular point in time. During start of the checkpoint, a begin checkpoint log record is written to the log.
5. End Checkpoint Log Record:-  In the end checkpoint log record, we write the necessary meta information required for redo and undo. For redo, we write the dirty page table maintained by the buffer pool. This contains information about dirty pages , the page  id and the oldest redo lsn which is the lsn of the update that is not yet reflected in the database. For undo, the active transaction table which consists of the transaction id and the lsn of the last update of this transaction. The end checkpoint log record contains  the active transaction table and the dirty page table. During checkpoint, the dirty pages can be flushed or page cleaner that runs in the background periodically shall flush the dirty pages to disk.
6. Compensation Log Record :- During recovery or abort or partial rollback, when an action is undone , as special type of log record known as Compensation Log Record (CLR) is written. This log record contains the before image (only the redo info) and the undo next lsn which is the previous lsn of the update record (for which undo is done). This avoids the need to undo what was already undone.

Recovery and ARIES

ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) is restart recovery algorithm based on on the Write Ahead Logging principle. It reconstructs state of database at time of crash and decides which transactions should commit and which needs to be rolled back/undone. It consists of three phases:

1. Analysis Phase :- This phase reconstructs active transaction table and dirty page table of database at time of crash. In the analysis phase, master record is read which has  checkpoint lsn. It is the lsn from which the log is scanned forward. Also the dirty page table and the active transaction table are  read. The log is scanned forward updating the active transaction table and dirty page table. During this phase , no I/O is done on the database and the log scans are purely sequential. Pseudo-code outline of this phase and a detailed algorithm (using C++) pseudo is given in the Algorithms section of this page.

2. REDO Phase :- The redo phase consists of  redoing the updates.  The minimum lsn among all the lsns in the dirty page table is found. The log scan starts from this lsn and the database pages are fetches and the updates are replayed. This phase is expensive in terms of I/O and involve random I/Os. Pseudo-code outline of the algorithm is presented below (with detailed algorithm in later section):

3. UNDO Phase :-  The undo phase consists of undoing the updates of  all the active transactions (transactions that have not been committed). This phase starts with maximum of last lsn found in the active transaction table.  It reverts the updates made to stable database based on before image information contained in the update record. The undo is logged by writing a compensation log record. As each update log record of a transaction is processed, the prev lsn of the transaction is added to the list of undo lsns (which is the last lsn of all active transactions) and the largest among them is picked and processed. Usually the undo pass is short and may not involve any database reads as data could be in the buffer pool bought by redo phase. However if there exists some long running transactions , the undo phase shall  involve quite amount of work increasing the recovery time thus  system comprising the system availability time. Brief outline of the algorithm is presented below (with detailed algorithm in later section):

Below is the diagrammatic illustration of the ARIES recovery:

Data Structures

We introduce the key data structures required to understand the WAL principle and algorithms required for recovery. (Note: Algorithm and data structures shall be in kind of pseudo C++ code). The data structures are:

Database:- Set of page indexed by page_id

std::vector<int> Database;

Buffer Cache/Page Cache: - Set of page indexed by page_id

std::vector<int> Cache

Page : A struct containing the following fields:

struct Page { 
      int page_id;
      int64_t page_lsn;
      Page_status status; // Signfies wheter page is CLEAN or DIRTY.
      std::string data;
   };

Log_record and their types: 

struct Log_record {
  int64_t lsn;
  int64_t trxn_id;
  int64_t prev_lsn;
  Log_type type; // Type can be BEGIN, UPDATE, COMMIT, ABORT, COMPENSATION_LOG_RECORD, BEGIN_CHECKPOINT, END_CHECKPOINT
};

struct Update_log_record : public Log_record {
	int page_no;
    int64_t offset;
    std::string before_image;
    std::string after_image;
};
struct Trxn_table_entry {
  int64_t last_lsn;   // Last LSN of the transaction
};

  

struct Checkpoint_record : public Log_record {
    std::map<int64_t, Trxn_table_entry> active_trxn_table;
    std::map<int64_t, int64_t> dirty_page_table; // Map of page_id to redo LSN - oldest lsn after last flush of this page.
};

Log Buffer:

vector<Log_record> Log_buffer; // Array of log records ordered by lsn

On-disk Log:

vector<Log_record> ondisk_log; // Array of log records ordered by lsn

Active Transaction Table:

std::map<int64_t, Trxn_table_entry> active_lsn_table; // Map of trxn id to transaction table entry.

Dirty Page Table:

std::map<int64_t, int64_t> dirty_page_table;

Algorithm Implementation

Detailed Implementation of various methods used in recovery/rollback:

Write:

void write(int page_id, int64_t trxn_id, int64_t offset,  const string &after_image, const string &before_content) {
     // Update page cache.
     int64_t cur_lsn = next_lsn(); // Atomically get a log sequence number.
     int64_t prev_lsn = active_lsn_table[trxn_id]; // UNDEFINED_LSN if no entry in table.
     
     // Create Update Log Record
     // We show explicit initialisation of the fields for clarity. In a C++ code, a constructor would do the job.
     Update_log_record update_lr;  // Log_type of the record is Log_type::UPDATE
     update_lr.lsn = cur_lsn;
     update_lr.prev_lsn = prev_lsn;
     update_lr.trxn_id = trxn_id;
     update_lr.page_id = page_id;
     update_lr.offset = offset;
     update_lr.after_image = after_image;
     update_lr.before_image = before_image;
         
     // Add log record to buffer
     log_buffer.push_back(update_lr);
     
     // Add it to txn table 
     active_trans_table[trxn_id].trxn_entry.last_lsn = cur_lsn;
     active_trans_table[trxn_id].trxn_entry.status = Trxn_status::TRXN_UPDATE;
    
     // Add page to dirty page table if not already present.
     dirty_page_table[page_id] = (dirty_page_table.count(page_id) == 0) ? UNDEFINED_LSN : cur_lsn;        
}    

Force:

void force() {
	add_log_buffer_to_on_disk_log(); // Append contents of the log buffer to log.
	log_buffer.clear();
}

void force(uint64_t lsn) {
  // add all log records up to lsn specified starting from the log record.  
  add_log_buffer_to_on_disk_log(lsn);
  erase_log_buffer(lsn); // Erase all log entries in the log buffer until lsn specified.
}

Flush:

void flush(int page_id) {
    // force log buffer up to the lsn identified by
    force(getLSN(page_id));
    database[page_id].data = page_cache[page_id].data;
    database[page_id].page_lsn = page_cache[page_id].page_lsn;
    page_cache[page_id].status = Page_status::CLEAN;
    dirty_page_table.erase(page_id);
}

Abort:

void abort(int64_t trxn_id) {
	int64_t log_lsn = active_trans_table[trxn_id].last_lsn;
    while (log_lsn != UNDEFINED_LSN) {
        Log_record lr = find_log_record(log_lsn);
        if (lr.type == Log_type::UPDATE) {
            // This is a update log record, will have additional fields.
        	Compensation_log_record compensation_lr;
            clr.lsn = nextLSN();
            clr.prev_lsn = active_trans_table[trxn_id].;
            clr.trxn_id = lr.trxn_id;
            clr.undonext_lsn = lr.prev_lsn;
            clr.after_image = lr.before_image;
            clr.page_id = lr.page_id;
            clr.offset = lr.offset;
            active_trans_table[trxn_id].last_lsn = clr.lsn; 
            // Add compensation log record.
            log_buffer.push_back(clr);
            write(lr.page_id); // Undo by doing page write based on before_image.
        }
        log_lsn = lr.prev_lsn;
    } // while 
    Log_record abort_lr;
    abort_lr.lsn  = next_lsn();
    abort_lr.prev_lsn = active_trans_table[trxn_id].last_lsn;
    abort_lr.type = Log_type::Abort;
    abort_lr.trxn_id = trxn_id;
    // Add abort log record to log buffer.
    log_buffer.push_back(abort_lr);
    // Remove trxn entry from active_trans_table.
    active_trans_table.erase(trxn_id);
    force(); // force log buffer to disk.
}

Commit:

void commit(int64_t trxn_id) {
    Log_record lr;
    lr.lsn = next_lsn();
    lr.log_type = Log_type::COMMIT;
    lr.trxn_id = trxn_id;
    lr.prev_lsn = active_trans_table[trxn_id].last_lsn;
    log_buffer.push_back(lr);
    active_trans_table.erase(trxn_id);
    force(); 
}

Checkpoint:

void checkpoint() {
    int64_t cur_lsn = next_lsn(); // Atomically get a sequence number.
    // Create a BEGIN_CKPT log record.
    LogRecord new_logr;
    new_logr.lsn = cur_lsn;
    new_logr.prev_lsn = UNDEFINED_LSN;
    new_logr.type = Log_type::BEGIN_CHECKPOINT;
    logbuffer.push_back(new_logr);
    
    // Write end checkpoint to stable storage
    int64_t prev_lsn = cur_lsn;
    cur_lsn = next_lsn();
    
    // Create a end checkpoint log record
    Checkpoint_log_record checkpoint_lr; // Type of this log record is END_CHECKPOINT
    checkpoint_lr.lsn = cur_lsn;
    checkpoint_lr.prev_lsn = prev_lsn;
    checkpoint_lr.active_trxn_table = active_trxn_table; 
    checkpoint_lr.dirty_page_table = dirty_page_table;
    store_master_record(cur_lsn);
    flushLogBuffer(cur_lsn);
}

Recovery:

void recover() {
  analysis() 
  redo();
  undo();
} 

Analysis:

  void analysis() {
    // Get most recent checkpoint via master record.
    int64_t checkpoint_lsn = master_record.checkpoint_lsn;
    // Get active transaction table & dirty page table from 
    int64_t log_index = find_checkpoint_ondisk_log_index(checkpoint_lsn);
    active_trans_table = ondisk_log[checkpoint_log_index].active_trans_table;
    dirty_page_table = ondisk_log[checkpoint_log_index].dirty_page_table;
    // Scan forward and build active transaction table and dirty page table at time of crash.
    while (log_index++ < ondisk_log.size()) {
       Log_record lr = on_disk_log[log_index];
       switch(lr.type) {
       	  case COMMIT:
            active_trxn_table.erase(trxn_id); 
            break;
          case UPDATE:
            active_trxn_table[lr.trxn_id].last_lsn = lr.lsn
            break;
       }
       if (lr.type == Log_type::COMPENSATION_LOG_RECORD || lr.type == UPDATE) { 
  	   	if (dirty_page_table.count(lr.page_id) == 0) 
        	dirty_page_table[page_id] = lr.lsn; 
       }
  }

Redo:

  void redo() {
      // Rebuild the system at point of crash
      // Get min of the oldest redo lsn in dirty page table.
      uint64_t min_oldest_redo_lsn = get_min_oldest_redo_lsn(dirty_page_table);
      // Scan this lsn until the end of log
      for(int i  = get_log_index(min_oldest_redo_lsn) ; i <= log.size(); i++) {
  		if (on_disk_log[i].type  == Log_type::UPDATE || 
                on_disk_log[i].type  == Log_type::COMPENSATION_LOG_RECORD) {
                int64_t cur_lsn  = on_disk_log[i].lsn;
                int page_id = on_disk_log[i].page_id;
                // Redo if page in dirty page table and
                // lsn in dirty less than or equal to this log record lsn (meaning page was not already flushed) and
                // page was not updated after this log record & flushed.
                if ( dirty_page_table[page_id] != dirty_page_table[end] &&
                    dirty_page_table[page_id].page_lsn <= cur_lsn  &&
                    get_page_lsn(page_id) < cur_lsn) 
                    page_write(page_id); // Redo the update
                    cache[page_id].page_lsn = cur_lsn;
      }
  }
 

undo:

  void undo() {
  	// Undo active transactions.
    priority_queue to_undo;  // Pick largest lsn among all lsns.
    
    for (auto it = active_trans_table.begin(); it != active_trans_table.end(); ++it) {
    	if (active_trans_table.last_lsn != UNDEFIND_LSN && active_trans_table.last_lsn == Txn_status::TXN_COMMIT)
        	to_undo.insert(active_trans_table.last_lsn);
    }
    
    while(!to_undo.empty()) {
       int64_t cur_lsn = to_undo.top()
       to_undo.pop();
       int64_t log_idx = find_log_idx(cur_lsn);
       if (on_disk_log[log_idx].type == Log_type::COMPENSATION_LOG_RECORD) {
       		Compensation_log_record compensation_lr = on_disk_log[log_idx];
            if (compensation_lr.undonext_lsn == UNDEFINED_LSN) {
            	active_trans_table.erase(compensation_lr.trxn_id);
                continue;
            }
            to_undo.push(compensation_lr.undonext_lsn);
       }
       
       if (on_disk_log[log_idx].type == Log_type::UPDATE) {
          Update_log_record update_lr = on_disk_log[log_idx];
          // write CLR record to log.
          Compensation_log_record compensation_lr;
          compensation_lr.lsn = next_lsn();
          compensation_lr.prev_lsn = active_trans_table[update_lr.trxn_id].last_lsn;
          compensation_lr.page_id = update_lr.page_id;
          compensation_lr.offset =  update_lr.offset;
          compensation_lr.after_image = update_lr.before_image
          compensation_lr.undonext_lsn = update_lr.prev_lsn;
          log_buffer.push_back(compensation_lr);
          active_trans_table[trxn_table].last_lsn = last_lsn;
          if (update_lr.prev_lsn == UNDEFINED_LSN) {
          	active_trans_table.erase(update_lr.trxn_id);
          } else to_undo.push(update_lr.prev_lsn);
          // Undo the page.
          page_write(update_lr.page_id, update_lr.before_image); // Undo based on before image
       }
    }
  }

Deciphering the Chandrayaan II (Vikram Lander) Landing on Moon - Part I (Successful Robotic Soft Landings On Lunar Surface And Lander Introduction)

Introduction

Robotic landing on planetary bodies  remains a key challenge. Moon landing is particularly difficult because of the following factors:

• Lack of atmosphere: Moon doesn't have an atmosphere. This means aerobraking can't be used for  slowing down the lander. One has to use the propulsion systems  for deceleration.  Liquid propellants are used in lunar lander. Because of appreciable moon's gravity, velocity at which lander starts it's descent, the amount of fuel required is huge land and this constitutes a significant mass of lander. The mass of  vehicle undergoes change as well as  fuel slosh ing happens when decelerating. This may result in unstable unless a careful design considering the mechanical design (placement of fuel tanks, baffles to damp sloshing) and precise thrust vector control taking into account the threshold slosh frequency.  
• Lunar dusts, Unknown terrain, Craters and Boulders: Moon is covered with lunar dusts. As lander approaches  moon's surface, lunar cloud dust formation happens.  This obscures the measurements from some sensors in particular the range sensors. Only data from IMU sensors needs to be used in this phase. Even though orbiters like LRO have mapped the moon surface at pretty high resolution and elevation models and terrains have been mapped, still there are complexities which needs to be assessed at the moment of landing. This calls for a robust and an autonomous Guidance & Navigation software capable of steering the lander to land on  moon with precise accuracy. This is particularly true of the south pole which is characterized by small plain regions interspersed with highlands and the terrain being uneven littered with craters, boulders and rocks.
• Harsh thermal environment, uneven and limited illumination at poles: The temperatures on the moon can vary between +120 to -180°C.  There are wide temperature swings during the course of day. In addition the illumination also depends on topographic and local conditions. At the poles, topography and local conditions vary.  On-board electronics can work under a particular range of temperature and so these needs to be factored in design. Hence landing  needs to be done at a favorable time and landing site selection plays a key role for successful lunar landing. From an operational perspective, lander may need to be powered off at particular times during lunar day and hence it's solar panel be controllable. In addition, the nights can become colder and hence radioisotope heating unit is required to keep both the lander and rover warm in order the mission's lifetime is more than a lunar day. 

The Chandrayaan II (Vikram lander) landing event on September 7 generated lot of enthusiasm among the youth and the common people in India.  However it could not do a soft landing and in the process communication with the lander was also lost. This aroused a lot of curiosity over the fate of lander among common people. People were glued to television sets and other media since then to get updates from ISRO and their Scientists. The article is broadly an attempt to  understand the technical details that underlay the lunar landing from a novice point of view.

In the past 50 years or so,  few nations and a private entity had attempted soft landing on the moon. Around one-third of the attempts had ended in failures. To start the article on a positive note, the next section shall give an overview of  successful robotic soft landings on moon till date.  The subsequent sections shall give an overview of  lander and it's requirements.

Successful Robotic Soft Landings on Lunar Surface

Luna Missions (by erstwhile Soviet Union aka. USSR): The 1960s saw a cold war between the erstwhile Soviet Union and the USA. This resulted in sending a number of robotic missions to the Moon. The first ever soft landing on Moon or for that matter the first man made object to touch a surface safely other than the earth was  Luna 9. It proved that an object can safely land on lunar surface without sinking. It returned images and some data from the moon. Below table lists the successful soft landings done on Moon done with some details:

Surveyor Mission (by USA): The first soft landing on Moon by United States was achieved by Surveyor 1. It probed the moons surface and provided data for manned Apollo Missions. Below tables lists out the successful lunar soft landings made by the United States:

Change series Mission (by China): The recent country to achieve soft landing on Moon was China. These soft landings come after a period of near about 25 years since the last Luna 25 lunar landing on 1976. The Change 3 and Change 4 possess sophisticated on-board Guidance & Navigation that actively adjust and optimize the trajectory based on several factors and local conditions existing at time of landing unlike the previous missions. This is mainly possible because of the growth of the information processing made possible by the advent  of computers. Below table lists the relevant details of lunar soft landings achieved by China.

Lander

Lander is a vehicle which needs to touchdown on the surface of the planet or natural satellite. It departs from  the orbiter with an initial orbital velocity and makes it's descent toward the surface and  it needs to come to a complete halt at the surface. The landing process needs to happen in a relatively short time and it needs to be decelerated and maneuvered accordingly to do a controlled landing on the surface. Landing safely is one of a critical requirement to ensure the success of a mission. For a safe lunar landing, several objectives and requirements factoring several aspects needs to be met. Below I have detailed the requirements of a lunar lander.

Requirements

• Accurate Landing: Based on mission requirements and lander engineering constraints, landing site selection is made and a location chosen. The goal of lander would then be to land safely within some accuracy around the landing site. Usually a site is chosen based on terrain not having much slope, free of huge rocks and boulders as well  keeping the scientific objectives in mind(like a place having likely presence of water so that rover has  scientific instruments relevant to detect and measure water).  If lander touches down  on an uneven terrain which has a greater slope than it's designed for, it may tip over and damage itself and the components and become non functional resulting in a complete mission failure. If lander happens to deviate from it's trajectory and land in a shadow region, the use of solar panels for power will be out of question and then the whole mission shall result in a failure. Hence lander accuracy is a key requirement for success of the mission. In addition, lander should stabilize itself and absorb the landing impact as it touches down  the surface.
• Autonomy, Hazard detection & Avoidance: The lander can't be piloted from  ground control owing to reasons such as time requirement for communication (in moon's caste it is almost 2 seconds for round trip) as well as there may be intermittent communication failure. So the landing process should be autonomous. At some distance (100 m) from the surface) , the lander should be able to  assess the local conditions out there and choose a safe reliable location to make the final landing. Hence a hazard detection & avoidance software should be part of the lander's Guidance and Navigation subsystem. This enables to hover over an area and do hazard detection and steer the lander around for a safe landing avoiding the hazards.
• Precise Thruster Control, Slosh Aware & Optimal Fuel Consumption: A lander shall  have several thrusters.  The On-board Guidance & Navigation Control (GNC) subsystem should be able to precisely control the different  thrusters to work cooperatively and achieve  necessary desired position, velocity and attitude at various stages of it's flight path. Liquid propellants are the main fuel and during acceleration/deceleration they slosh because of inertia and this shall causes instabilities in the thruster control. This needs to be factored in both by using baffles that damps and prevents slosh to some extent, placement of fuel tanks accordingly as well as the on-board GNC software does controlled acceleration and deceleration taking into account threshold slosh (which won' result in cutting off fuel supply, choking etc). The flight path of the trajectory as well as on-board GNC should also optimize the overall fuel consumption which is another key factor.
• Sensors accuracy: Sensors are subject to bias and measurement errors. All these needs to be factored in at time of design of lander and the  GNC subsystem be designed taking into account meeting the specified sensor accuracy. This ensures a safe reliable landing.

Conclusion

A very in-depth and detailed study spanning multiple domains is required to understand the lander and it's operational details. In this article I have just started with an introduction. My next series of articles shall  describe flight path of the lander, lander components and the different types of sensors and their purpose and how it aids in navigation and guidance. In further subsequent posts, I hope to uncover the Chandrayaan II Mission and it's Vikram Lander. I hope these series of articles shall provide the common people out there to decipher the updates provided by ISRO scientists as well as develop an interest in science & technology.

Geometry Problems

I was looking into school textbooks of various boards recently because of NEET, an entrance examination that determines students eligibility criteria to study medical courses, hogging  the limelight in media. This got me a bit interested in school geometry as well and below I shall post some set of geometry problems that I found on social media like Twitter and Facebook and  solutions to these problems. I believe these problems shall be useful for school students. Try solving the problems yourself before you have a look at the solutions.

Problem#1: Three circles of diameter  3 cm, 4 cm and 5 cm are inscribed in a rectangle and their circumferences touch each other as well the boundaries of the rectangle. (Note the diagrams are not drawn to scale). Find distance between point A and B.

Solution: We  make use of the following concepts: 

Since circle touch each other at exactly one  point, so there is common tangent to both circles at this common point. The radius is perpendicular to the tangent and hence a straight line can drawn connecting the centers of these circles through this common point.

Next is we make use of the Pythagoras theorem. The below diagram (along with necessary calculations) shows the solution.

I will post questions of the next 2 problems and may be if possible i will post the solutions later on, (I ran out of time today :-).)

Problem#2: Three 2x1 rectangles are laid out as in the below diagram below. What is the fraction of the shaded area ?

Problem#3: What is the area of the  shaded region in the below figure? (Note the diagram is not drawn to scale).

Probability Problems - The Monty Hall Problem and The Birthday Problem.

In this post, we consider the following classical probability problems and their solutions. The questions are:

1. There is a game show conducted on a television. In the game show, there are three doors. Behind two of these doors are goats and behind one there is a car. You as the contestant  is allowed to choose one door. Then the host of the game show opens a door revealing a goat. Then he asks you the question: Whether you would be interested to switch from your first choice to the other remaining door. What would be your answer? (Of course your intention is to maximize your chance of choosing the door that has car in it.)
2. Suppose your are in a hall where there are $n$ number of people present. What is the probability at least two people in the hall have the same birth days? (We assume the birth days are independent and uniformly distributed throughout the year. Well in reality that is not the case, humans do not mate in certain months and various other things.) 

Solution to Question#1:

The short answer is switching is better. Let's see why?. Let's name the three doors as $D_1$, $D_2$ and $D_3$.  There car can be in any one of the three doors. When you make the initial choice, you have a $1$ in $3$ chance of picking the correct door (i.e door with the car) and 2 in 3 chance of picking the door with the goat. Assume you have picked $D_1$. Let  $D_1$  has the  car behind it and the game show next opens a door (which could be either $D_2$ or $D_3$ but the door with the goat. After this if you made the switch, you lose. If the Car is in $D_2$ or $D_3$,   you pick $D_1$ in these two cases. Then if you make a switch, you win.  Thus your odds of winning has double by switching in contrast to the case if you have not switched. 

When this problem was asked in a magazine column in the 1990s, many readers of the magazine people, some of whom were Ph.D degree holders got it wrong. They felt switching doesn't matter. Hence the problem became famous and is known as the Monty Hall Problem named after the game show host Monty Hall.

Let's do this by using Bayes theorem. Let $H_i$ denote the hypothesis that car is behind the door $D_i$. So the prior probabilities are $P(H_1) = P(H_2) = P(H_3) = \frac {1} {3}$. After choose door $D_1$, the game show show can choose either $D_2$ or $D_3$.  Assume if car is behind door $D_1$, then the game show host can chose either $D_2$ or $D_3$ and he chooses either $D_2$ or $D_3$ randomly with probability  $\frac 1 2$. Else the host can choose one particular door (the one which has the goat) . Hence we can express this by the following:$$ P(D_2 | H_1) = \frac 1 2 \text { ,   }  P(D_3 | H_1) = \frac 1 2  \text {   , }  P(D_2 | H_2)= 0$$ $$P(D_3 | H_2) = 1 \text {  , }  P(D_2 | H_3) = 1 \text {  , } P(D_3 | H_3) = 1$$

Assume door $D_3$ (which has the goat) was shown by the host after our initial choice of $D_1$. Now our main aim is to find $P(H_1|D_3)$$ or P(H_2|D_3)$$ and see which one is better.

We calculate the posterior probabilities $$ P(H_i | D_3) = \frac {P(D_3 | H_i) \times P(H_i)} {PD_3}$$ $$ P(H_1 | D_3) = \frac {\frac 1 2 \times \frac 1 3} {P(D_3)} , P(H_2 | D_3 = \frac {1 \times \frac 1 3} {P(D_3)}, P(H_3 | D_3) = \frac {0 \times \frac 1 3} {P(D_3)}$$ $P(D_3)$ is used to normalize the probabilities. So it's value is $\frac 1 6 + \frac 1 3 + 0 = \frac 1 2$. Thus the posterior probabilities are:$$P(H_1 | D_3) = \frac 1 3,  P(H_2 | D_3) = \frac 2 3,  P(H_3 | D_3) = 0$$.

There switching to door 2 by the contestant increases his probability of winning and the probability is $\frac 2 3$.

  

Try yourself the following questions

1. Suppose instead of three doors, there are 1000 doors. 1 door has the car and the rest of the doors have goats in it. Initially you chose one door and the host shows 998 doors. If you switch to the other closed door from you initial choice of the closed, what is the probability that a car is behind this Door?
2. Consider the variant of the Monty hall problem. Somehow the contestant learns a trick so he always makes the first choice with a probability of $\frac 1 2$ instead of $\frac 1 3$ . With this change, what is the probability of winning the car prize by adopting an optimal strategy?

Solution to Question#2:

Let's ignore leap years and assume the year has $365$ days. If there were $366$ people, there would be at least a pair that would share the same birth date and hence the probability is 1. We solve for the case where there are less than $366$ days. The answer to this problem may appear a bit surprising. Hence this problem is also known by the name birthday paradox.

The problem is asking for probability that at least a pair of people share the same birth date. It is easier to solve this by  finding the probability that no people share the same birth day. Assume there are only two people. The first person birthday can fall on any of the $365$ days.  In order that the second person birth day be distinct from the first person birth day, it has to fall on any of the remaining $364$ days. So there are  $365 \times 364$ among a total of $365 \times 365$ such that the two doesn't share the same birthday.  Thus the probability is $\frac {364 \times 365} {365 \times 365} $. Now if there are three people what is this probability?. All three people need to have different birth dates. The first person birth day can fall on any of 365 days, there are remaining  $364$ days for the second person birth day  so that it doesn't clash with the first person birth day. After these,   the third person birth day can fall on remaining $363$ days. Thus there are $365 \times 364 \times 363$ choices among a total of $365 \times 365 \times 365$ possibilities. Thus the probability is $\frac {365 \times 364 \times 363} {365 \times 365 \times 365}$. Proceeding in the same way,  for n people there are $ 365 \times 364 \times 363 \times 362 \times ... \times (365 - (n-1)) $ choices out of $365^{n}$. Thus the probability that no share the same birth day among a group of $n$ people is $\frac {365 \times 364 \times 363 \times 362 \times ... \times (365 - (n-1))} {365^{n}}$. Let's generalize this a bit we just replace the 365 days in a year by D. Thus the probability that in a room of $n$ people atleast a pair have the same birthday is $$ 1 - \frac {D\times(D - 1) \times (D-2) \times (D-3) ... \times (D-n+1)} {D^(n)}$$. 

A very pertinent question to ask is for what value of n , is the probability 50%?. For this, let's rewrite the above equation and derive an approximate closed formula.$$ 1 - (1 \times {(1 - \frac 1 D)} \times {(1 - \frac 2 D)} \times .... \times {(1 -  \frac {n - 1} D)})$$. Let's make use of $e^x = 1 + x $(ignoring higher order terms) in the above. $$ \approx 1 - (e^0)\times(e^{\frac {-1} D})\times(e^{\frac {-2} D})\times ... \times(e^{\frac {-(n-1)} {D}})$$ $$ \approx 1 - e^{\frac {-1} {D} \sum_0^{n-1}} = 1 - e^{- {\frac {\frac {n\times(n-1)} 2} D}}$$ We want probability to be $.5$  we plugin this value and simplify to find the corresponding value of n. We get the formula $$n \approx 1.2\sqrt D$$.  For $D=365$, the value of n turns out to be  $23$. Thus in a group of $23$ people, we have 50 percent probability that at least a pair shall share the same birth date. Below plot shows number of people on X-axis and the probability that at least two people share the birth day on the Y-axis. 

From the plot we see that the probability value rapidly decreases below $23$ and it rapidly increases to 1 above this point.

The above result is important in computer science especially in the context of cryptography that which depends on the collision properties of hashing. Now try yourself the following questions:

1. Suppose we have  n-bit hash function, how much random message we need to sample in order to find a collision?
2. What should be the size of hash function should we chose so that the expected number of collision is 1 percent if we store N entries making use of the hash?
3. Develop an algorithm to find collisions in n-bit hash and what is the expected running time of this algorithm?

More Problems With Broken Sticks#1

Here are some more problems related to broken sticks and probability.

1. If a stick of unit length is broken at a point chosen uniformly at random, what is the expected length of the shorter piece?

Solution: The shorter piece can belong either to left half or right half of the broken stick. The length of shorter stick varies from 0 to $\frac {1}{2}$. Thus  the expected length is half of this length which is $\frac {1} {4}$. If the short piece belongs to right half, the lengths have the same distributions and are thus symmetric. Therefore the expected length is $\frac {1} {4}$. More formally the expectation here is $\frac {1} {2} \times \frac {1} {4} + \frac {1} {2} \times \frac {1} {4} = \frac {1} {4}$

Another way to solve is to use calculus and the notion of random variables. Let  X denote be the random variable that derives it's value uniformly at random  in the interval $(0,1)$. Let L(X) denote the random variable describing the lengths of the shorter pieces. Then the question asks for the expected value of the shorter piece which is $E(L(X))$.  If $x$ denote the location of the break , the shorter piece is $min(x,1-x)$ which is x if $0 < x < \frac {1} {2} $ else $1-x$. The probability density function for the interval (0,1)  is 1.Thus:$$E(L(X)) = \int_0^1 l(x) \times 1 dx = \int_0^{\frac {1} {2}} x dx + \int_{\frac {1} {2}}^1 (1-x) dx = \frac {1}{4}$$.Note: There is no need to evaluate integrals in the above (The integrals just correspond to area of a triangle with base as $1$ and height $\frac {1} {2}$ (just plot the functions $x$ and $1-x$ on a graph paper).

2. If a stick of unit length is broken at two points chosen uniformly at random, what are the expected lengths of shorter, mid sized and longer piece?

Solution: First I shall describe a solution which is based on geometry.  Let random variables (X,Y) denote the right and left locations of the unit length sick along which it is cut. Thus the lengths of the pieces are X, Y - X and 1 - Y. First let's assume X is the smallest piece. Then the following equations  are satisfied:
$$ X \lt Y  \\
     X \lt Y - X \rightarrow 2X \lt Y \\
     X \lt  1 - Y \rightarrow X + Y \lt 1 $$ The area of the shaded triangle in the below graph represents the inequalities above.

   

The expected length or the mean value is the centroid of the triangle. The centroid lies at a distance $\frac {1} {3}$ from the base and thus it is $\frac {1} {3} \times \frac {1} {3} = \frac {1} {9}$. Therefore the expected length of the shorter piece is $\frac {1} {9}$.

Now to find the expected length of the largest piece, let's assume X is the largest length piece. Then the following inequalities hold:
$$ X \lt Y \\
     X \gt Y - X \rightarrow 2X \gt Y \\
     X \gt 1 - Y   \rightarrow X + Y \gt 1 $$
This above conditions are  represented graphically by the shaded quadrilateral in the below figure:

Now we have to calculate the mean value of X in the quadrilateral above. The quadrilateral is divided into two right angled triangles by the dotted line in the figure. We find the mean value of these triangles and then find the mean value of X in quadrilateral  by weighting the two means by areas of the triangles. Mean of the right triangle in the figure is $\frac {1}{2} - \frac {1} {3} \times \frac {1} {6} = \frac 8 {18}$. Likewise the mean of the left triangle is $\frac 1 2 + \frac 1 3 \times \frac 1 2 = \frac 4 {6}$. Since both triangles have a common base, the areas are in proportion to their altitudes which is $\frac 1 6 : \frac 1 2$ which is $1:3$. Therefore the expected mean value of X is given by:$$ \frac {1 \times \frac 8 {18} + 3 \times \frac 4 6} {1 + 3} = \frac {4 \times \frac  {(9 + 2)} {18}} {4} = \frac {11} {18}$$
Therefore the expected length of the largest piece is $\frac {11} {18}$.
The expected length of the middle piece is $ 1 - \frac {1} {9} - \frac {11} {18} = \frac 5 {18}$

I will explain another solution which involves calculus and probability density functions in a separate post.

The Broken Stick problem

Here is another probability problem. (Probability is one of my favorite topics and I plan to post more probability problems in my subsequent posts. These problems shall be of use to school students who prepare for competitive exams and math enthusiasts.)

Two points are chosen randomly on a uniform stick. Find probability that three pieces formed by making two cuts across these two points, shall form a triangle? This problem for first time appeared  in a Cambridge University entrance examination paper conducted on 18th January , 1854. Below I present three solutions to the problem and the problem is usually called The Broken Stick Problem.

Solution#1:

Let 's for simplicity assume a stick of unit length. Let the randomly chosen two points be $x$ and $y$ on the stick.
Case#1: Assume $x \gt y$Then the leftmost edge has a length of x , the middle edge has length y - x and the right  edge has length 1 - y.

We know that for a triangle to be formed from three pieces, the length of the largest piece should be smaller than the sum of other two smaller pieces or for that matter, length of one side has to be smaller than the length of the other two sides. This is because the other two pieces should be able to touch or reach each other (when they are laid from the ends of a larger piece) for triangle to be formed. This fact is known as triangle inequality.

Let's write the condition for the above three pieces which satisfies triangle inequality.
$$  x  \lt (y - x) + (1-y)  \rightarrow 2x \lt 1 \rightarrow x \lt 0.5\\
     (y - x) \lt (1 - y) + x  \rightarrow 2(y - x) \lt 1 \rightarrow y - x \lt 0.5  \\
     (1 - y) \lt  x + (y - x) \rightarrow 2(1 - y) \lt 1 \rightarrow y \gt 0.5 \\
$$

Let's plot  graph with X-axis and Y-axis corresponding to x and y values. The above equations constitute correspond to  the upper left triangle. Similar by symmetry or we can derive set of equations as above for y \gt x which is case#2. This set of equations corresponds to the lower right triangle (shaded green) shown as in figure below:

Now the desired probability is the sum of the area of the triangles divided by the area of unit square which is $0.25$ or $\frac 1 4$.

Solution#2:

I will give another proof making use of the properties of equilateral triangle.

In the above figure, there is a larger equilateral triangle. Now connect the midpoints of the sides of the equilateral triangle. The result is four interior equilateral triangles as shown in the figure. The area of these four equilateral triangles sum up to the area of a larger equilateral triangle.

Consider any point P in the larger equilateral triangle. If we drop perpendiculars from the sides of the equilateral , then sum of the three perpendiculars from the sides of the equilateral triangle sum up to the altitude of the triangle.  If let the altitude of the equilateral triangle to be of unit length, then the 

three perpendicular bisectors represent the three pieces of a stick (broken at random by considering two points on the stick) and the number of different points within the  equilateral triangle form the possible sample space/event space for the problem in question.

Now for the three pieces (perpendicular bisectors) to from a triangle, the point P should lie anywhere inside the hatched triangle shown in the figure. This condition ensures the side of larger perpendicular bisector is less than the sum of the other two. This is a necessary condition (the triangle inequality) for a triangle to be formed.

Thus the probability is equal to the area of the hatched triangle divided by the area of the larger triangle and this ratio is clearly .25 or $\frac {1} {4}$.

Solution#3:

There is yet another solution. Connect the two ends of the stick (on which we have chosen two random points) into a circle. Now on this circle, let's choose three random points and then unroll the circle from one chosen point, then this transforms itself into a stick with remaining two random points. All that we need to prove that the none of the pieces doesn't have length greater than $\frac {1} {2}$. This means we need to find the probability that none of the three points lie on the semicircle. This we find by the probability of the complementary, that is, the probability of three points lying in a semicircle.

We consider one chosen point and proceed counterclockwise to chose two other points. In order to ensure that these points lie in a semicircle , it must be chosen such that it is within $180^{\circ}$ from the first chosen designated point. This happens with probability $ \frac {1} {2} \times \frac {1} {2} = \frac {1} {4}$. The designated first point can be chosen in three ways. So the probability is $\frac {3} {4}$. The complementary probability is $\frac {1} {4}$ which is the probability for the three pieces obtained from a  stick broken at two randomly chosen locations to form a triangle. 

There is yet another way to arrive at an answer here. Let's consider two points which are within $\le 180^{\circ}$ on the circle. From these two points, draw diameters to connect to their antipodes. Now for three points not to lie within a semicircle , the third point must lie on an arc formed by two antipodal points. Thus the probability is length of these antipodal arc divided by $2\pi$ (circle of unit radius).  Now the two diameters cut into 4 arcs which are equal in length. Thus the length is proportionate to $\frac {2\pi}{4}$. Thus the probability is $$\frac {\frac {2\pi}{4}} {2\pi} = \frac {1} {4}$$