[Basic Linux Command]

Moving Around the Filesystem

1. pwd - print working directory
2. cd - change directories

Manipulating Files and Folders

copy, move, remove, list, create, permission, owner

1. cp - copy

e.g., cp file foo : an new copy of file whose name is foo

2. mv- moves

e.g., mv file foo : rename original file to foo

e.g., mv foo ~/Desktop: move file foo to your desktop

e.g., sudo mv foo /user/.../Desktop : sudo need full path name instead of ! in place of home directory

3. rm - remove file not directory containing files
4. ls - list files in your current directory

e.g., ls ~: show files in your home directory

5. mkdir - making directory

mkdir music: create a music dirctory

6. chmod: change permission/mode

user/group/world

e.g., a file allow everybody to read but only user could write => rwx r-- r--

e.g.,add a permission -> chmod g+x file

7. chown: change the user and group ownership of a file

e.g., chown jim file : change the ownership of file to jim

System Information Commands

hardware, network, operating system disk space, process

1. df : display filesystem disk space usage for all partitions

e.g., df -h (human readable, MB, GB)

Filesystem      Size   Used  Avail Capacity  iused   ifree %iused  Mounted on /dev/disk0s2   184Gi  175Gi  9.6Gi    95% 45826245 2513597   95%   / devfs          191Ki  191Ki    0Bi   100%      662       0  100%   /dev map -hosts       0Bi    0Bi    0Bi   100%        0       0  100%   /net map auto_home    0Bi    0Bi    0Bi   100%        0       0  100%   /home /dev/disk0s4   281Gi  274Gi  6.1Gi    98%  1049759 6366153   14%   /Volumes/BOOTCAMP

2. free: free and used memory in the system

e.g., free -m : gives the information using megabytes, which is probably useful for current computers

3. top: running processes and system resources, including CPU, RAM, swap usage, and total number of tasks being run

e.g., top

e.g., to exit , press Q

4. uname -a: CHECKING WHICH KERNEL you are using

print all system information, including machine name, kernel name, verison , and a few other details

5. lsb_release -a: print version information for the linux release you’re running

user@computer:~$ lsb_release -a

LSB Version: n/a

Distributor ID: Ubuntu

Description: Ubuntu (The Breezy Badger Release)

Release:

Codename: breezy

6. ifconfig: reports on your network interfaces
7. iwconfig: wireless network adapters and the wireless-specific information from them, such as speed and network connected
8. ps: view all proceess running on the mahcine

The following commands list the hardware on your computer, either of a specific type or with a specific method. They are most useful for debugging when a piece of hardware does not function correctly.

9. lspci :  all PCI buses and devices conneced to them, including nerwork cards and sound cards

10.lsusb: list all USB buses and any connected USB devices, such as printers and thumb drives

11.lshal: lsit all deveices the hardware abstraction layer(HAL) knows about, hwich shouldb e most hardware on your system

12.lshw: lists hardware on your system, including marker, type, and where it is connected

Searching and Editing Text Files

search, search and replace, concatenate, open to edit/view

1. grep-search inside a number of files for a particular search pattern and print matching lines

e.g,. grep blah file : will search for the text “blah” in the file and then print any matching lines

2. sed- stream editor- allows searhc and replace of a particular string in a file

e.g., sed s/cat/dog/g pets : search the string “cat” and replace it with “dog” in a file named pets

Both grep and sed are extremely powerful programs. There are many excellent tutorials available on using them, but here are a few good Web sites to get you started:

• www.panix.com/~elflord/unix/grep.html
• www.itworld.com/Comp/2378/swol-1199-unix101/

3. cat : concatenate

e.g., cat filename : display the contents of the file

e.g., cat filename file: adds the contents of the first file to the second

4. nano: simple text editor

e.g., nano filename

commands listed at the bottom of the screen are accessed via pressing Ctrl followed by the letter

5. less: viewing text files as well as standard output [TEXT MODE]

ls | less : pipe another command through less to be able to see all the output

Dealing with Users and Groups

add, delete,

1. adduser:

e.g., sudo adduser $loginname : this creates user’s home directory and default group. It promprs for a user passowrd and the nfurther details about the user

2. passwd:

e.g., sudo passwd joe : change Joe’s password

3. who:

e.g., who : tell you who is currently logged into the machine

4. addgroup:

e.g., sudo addgroup $groupname

5. deluser:

e.g., deluser -remove-home : to remove user’s file and home directory

6. delgroup:

you cannot remove a group that is the primary group of any users

Getting Help on the Command Line

1. --help
2. man (manual)
3. -h or -help
4. man -h
5. man --help

e.g., man mv - bring up the mv(move) manual

6. Arrow keys: move up and down the man file by using the arrow keys
7. q - quit back to the command prompt by typing q
8. man man: bring up the manual entry for the man command, which is a good place to start
9. man intro: display the introduction to User Commands, which is a well-written, firly brief instrocution to the linux command line
10. info info

Searching for Man Files

1. man -k foo: serach the main files for “foo”

e.g., man -k nautilus

2. man -f foo: serch only the titles of your system’s man files

e.g., man -f gnome

man -f foo is the same as the whatis command

Using Wildcards *(multiple), ?(Single),[](Specify)

look at or use multiple files at the same time, e.g., delete all .rar files or move all .odt files to another directory

1. * matches any number of characters.

For example, *.rar matches any file with ending .rar

2. ? mathces any single character

For example, ?.rar mathces a.rar but not ab.rar

3. [characters] matches any of the characters within brackets.

For example, [ab].rar matches a.rar and b.rar but not c.rar

4. [!characters] matches any characters that are not listed.

For example, [!ab].rar matches c.rar but not a.rar or b.rar.

Executing Multiple Commands

Often you want to execute several commands together,

either by running one after another or

by passing output from one to another

Running Sequentially

e.g., run regardless of whether or not preceding commands succeed

lspci ; lsusb

e.g., ./confiure && make && make install

Passing output

pipe

e.g., ls | less: allow you to view the contents of the ls more easily

Moving to More Advanced Uses of the Command Line

• A Practical Guide to Linux Commands, Editors and Shell Programming by Mark G. Sobell (Prentice Hall, 2005) is a good book for any user of the shell in Linux to have on his or her bookshelf.
• LinuxCommand.org is an excellent Web site designed to help people new to using the command line.
• The Linux Documentation Project is an excellent and free resource for many things Linux.

Reference:
http://www.computerworld.com/article/2598082/linux/linux-linux-command-line-cheat-sheet.html

[Singleton]

6. Singleton

Method1 - Early initialization: we create the object when the class is getting loaded into the JVM. Method1 - Early initialization public class JavaHungrySingleton {      private static JavaHungrySingleton uniqueInstance  = new JavahungrySingleton();       private JavaHungrySingleton(){}      // cannot be accessed by object      public static JavaHungrySingleton getInstance()      {            return uniqueInstance;      } } Method2 - Lazy initialization: Last moment to have an object. We create the object of the class only when it is about to use in the program code. deferred initialization Advantage: 1. faster startup times, at the cost of delay caused by initialization the first time the instance is accessed 2. If never accessed, then never initialized, save initialization time and resources it would otherwise require if it were initialized by the classloader <== Method 1. 3. allow selection of the class of the singleton object to be deferred until run time rather than being specified at compile time. Disadvantage:  1. in a resource-limited environment, deferred initialization could fail due to inadequate resources. 2. increase the complecity of the singleton class, especially in a multi-threaded system. 3. If getInstance is called frequently, busy waiting due to synchronized ==> Method 3 Method2-   Lazy initialization + Synchronized(for thread-safe) public class JavaHungrySingleton {        private static JavaHungrySingleton uniqueInstance = null ;      private JavaHungrySingleton(){}      public static synchronized JavaHungrySignleton getInstance ()      {            if (uniqueInstance == null)            {                   uniqueInstance = new JavaHungrySignleton();            }            return uniqueInstance;      } } Method3 - Inner Class initialization : Thread-safe + Avoid overhead of synchronization Method3 - Inner Class initialization : Advantage: Thread-safe: because calssloader is guaranteed to be serialized, so the inner class is laoded and initialized only once, no matter how many threads call getInstance simutaneously. Avoid overhead of synchronization, because serialization is provided by classloader - after the class has been loaded, the classloader is no longer involved, so there’s no residual overhead. public class JavaHungrySingleton {     private static JavaHungrySingleton uniqueInstance  = null;         private JavaHungrySingleton(){}     // Inner class initializea instacne on laod, won;t be loaded     // until referenced by getInstance()     private static class JavaHungrySingletonHolder()     {                 public static final JavaHungrySingleton uniqueInstance = new JavaHungrySingleton();     }     // cannot be accessed by object     public static JavaHungrySingleton getInstance()     {           return JavaHungrySingletonHolder.uniqueInstance;     } } Method 3 - double checked locking: first we check if the object is created, if not then we create one using synchronized block. Advantage: 1. reduce the overhead of acquiring a lock Method 3 - double checked locking : Volatile(write before any read, invalidate all the read and flush)  + Double checked lock + Synchonized public class JavaHungrySingleton {      private static volatile JavaHungrySingleton uniqueInstance;      private JavaHungrySingleton(){}      public static JavaHungrySingleton getInstance()      {             if (uniqueInstance == null)             {                     synchronized(JavaHungrySingleton.class)                     {                           if (uniqueInstance == null)                           {                                    uniqueInstance = new JavaHungrySingleton();                            }                      }             }             return uniqueInstance;       } } volatile establishes happens-before relation between reads and writes, and fixes the broken pattern volatile is here because without it by the time second thread passes instance == null, first thread might not construct new Singleton() yet: no one promises that assignment to instance happens-before creation of the object for any thread but the one actually creating the object. reduce the overhead of acquiring a lock by first testing the locking criterion (the "lock hint") without actually acquiring the lock Reference:http://stackoverflow.com/questions/7855700/why-is-volatile-used-in-this-example-of-double-checked-locking  1.What only one instance of whole application It is the most used design pattern in web applications. Singleton in Java is a class with just one instance in whole data java application and provides a getInstance() method to access the singleton instance . For example, java.lang.Runtime is a singleton class. Creating Singleton was tricky prior Java 4 but once java 5 introduced Enum its very easy. 2. How write Java singleton using double checked locking. Remember to use volatile variable to make Singleton thread-safe. -create a static variable private stati JavaHungrySingleton uniqueInstance; -declare the constructor private private JavaHungrySingleton() {} -getInstance() -public static synchronized JavaHungrySingleton getInstance(){} -if (uniqueInstance == null ) uniqueInstance = new JavaHungrySingleton(); return uniqueInstance; Reference: http://javahungry.blogspot.com/2013/06/top-25-most-frequently-asked-core-java.html http://javarevisited.blogspot.com/2011/03/10-interview-questions-on-singleton.html

[Multithreading]

           synchronized( this ){

                    .... // do the task

                       this.notify();

            }

synchronized( task )

{

         task.start();

         try {

              task.wait();

          }

          catch( InterruptedException e ){

                ... // do something if interrupted

          }

}

Producer and Consumer Problem :

public void add( int num ){                           ==> Prob.1 Busy Waiting , Prob.2 No Access Control

         while( true ){

           ....

         }

}

public synchronized void add( int num ){     ==> Prob.1 Busy Waiting

        while( true ){

               if( index < buffer.length ){

                  buffer[index++] = num;

                  return;

               }

       }

}

public synchronized void add( int num ){    

        while( index == buffer.length -1  ){

                try

                {

                      wait();

                }

                catch (InterrruptedException e)

               {

                }

       }

        buffer[index++] = num;

       notifyAll();

}

Busy Waiting:

Thread task = new TheTask();     // Prob1. Busy Waiting

task.start();

      while( task.isAlive() ){

            ; // do nothing

      }

Thread task = new TheTask();    // Prob. None

synchronized( task )

{

         task.start();

         try {

              task.wait();

          }

          catch( InterruptedException e ){

                ... // do something if interrupted

          }

}

.....

class TheTask extends Thread {

    public void run(){

           synchronized( this ){

                    .... // do the task

                       this.notify();

            }

     }

}

Concurrerncy or Multithreading

1.  Graphical user interface that perform lengthy I/O operations, caches
2. AJAX - web server response are processed asynchronously, and hence the JavaScript that runs to process the response possibly accesses data used by other parts of the application.


Thread

1. A fundamental unit of execution within an application
2. An application has at lease one thread.
3. Each thread has its own stack and runs independently from the application's other threads.
4. share resources such as file handles or memory
5. native or kernel-level thread: OS manages the thread
6. Preemptive threading: OS can suspend a thread's execution at any point in order to let another thread run.
7. Context switch: swapping one thread out and another
https://docs.google.com/document/d/1znFkZsnuWj0CI5yjNsiZGjQkReMBAKBg5566J4G3H-s/edit

Thread VS Process
1. thread: inside a process,  within a program where CPU is fetching and executing instructions, make the progress of a process(program), a flow of control or line of execution
2. process: a program

System Threads versus User Threads

1. System threads: created and managed by the system
2. User threads: created and managed by the application to do the tasks that cannot or hsould not be done by the main thread
2. Event Thread: waits for and delivers events (such as mouse clicks and key presses) . to avoid blocking, applications creating threads to handle time-consuming operations, especially those involving network access.

Monitors(simpler) and Semaphores

Monitors
1. Thread synchronization: monitors and semaphores
2. Monitors: a set of routines that are protected by a Mutual Exclusion  Lock.
3. Only one thread at a time acquiring the lock can execute within the monitor
4. Suspended thread : waiting thread
5. Wake up thread
Semaphores
1.A lock
2. Other is blocked until the owning thread releases the lock
3. mutual exclusion or mutex semaphore
4. Counting semaphores: let maximum of n threads access a resource at any given time
5. Event semaphores: notify one or all waiting threads that a even has occurred, but they all owrk in much the same way.
6. Cost: extra time is required to acquire the necessary lock


DeadLocks

1. shared resource
2. circular wait
3. No preemption
4.

1. Solution:forcefully terminate one of the thread
2. Best solution is deadlock avoidance

synchronized void someMethod(){

.... // the code to protect

}

is exactly equivalent to:

void someMethod(){

synchronized( this ){

.... // the code to protect

}

}

// A single central computer that controls multiple automated teller mahcines (ATMs) in different locations.

public class Account
{
      int userNubmer;
      String userLastNAMe;
      String userFirstName;
      double userBalance;



      public   Synchronized   boolean deposit( double amount )
      {
            double newBalance;
            if ( amount < 0.0)
                 return false;
            else
            {
                 newBalance = userBalance + amount;
                 userBalance = newBlaance;
                 return true;
            }
      }

      
      public    Synchronized    boolean withdraw( double amount )
      {
            double newBalance;
            if ( amount < 0.0)
                 return false;
            else
            {
                 newBalance = userBalance - amount;
                 userBalance = newBlaance;
                 return true;
            }
      }

}

public class Account {
int userNumber;
String userLastName;
String userFirstName;
double userBalance;
public boolean deposit( double amount ){
double newBalance;
if( amount < 0.0 ){
return false; /* Can’t add negative amt */
} else {
synchronized( this ){
newBalance = userBalance + amount;
userBalance = newBalance;
}
return true;
}
}
public boolean withdraw( double amount ){
double newBalance;
synchronized( this ){
if( amount < userBalance ){
return false; /* Insufficient funds */
} else {
newBalance = userBalance – amount;
userBalance = newBalance;
return true;
}
}
}
}

// Busy Waiting
// Consider a thread that spawns another thread to complete a task
// First thread cannot be a event thread (GUI thread)
// Queue pseudo-events for processing by the event thread, which is what second thread would do when it finished its task


// Solution: Busy waiting is avoided using a monitor or a semaphore
// Lock object can do wait and notify


Thread task = new TheTask();
task.start();

while (  task.isAlive() )
{
      // do nothing 
}

// Solution: Busy waiting is avoided using a monitor or a semaphore

// Lock object can do wait and notify
// wait in the main function and notify in each task object's run mehtod


// ===   simplified
Thread task = new TheTask();
synchronized ( task )
{
     task.start();
     try{
          task.wait()
     }
     catch(){
          // so somehting if interrupted
     }
}
......
class TheTask extedns Thread
{
     public void run()
     {
         synchronized(this)
         {
                // do the task

                this.notify();
         }
     }

}






// ===   Not simplified

Object theLock = new Object();
Synchronized (  theLock ) 
{
Thread task = new TheTask( theLock );
task.start(); // Call task's run()

try{
   theLock.wait();
}
catch ( InterruptedException e )
{
     // do something if interrupted
}
}

......

class TheTask extends Thread
{
     private Object theLock;
     public TheTask( Object theLock )
          this.theLock = theLock;
     public void run()
     {
          synchronized( theLock )
          {
             // do the task
             theLock.notify()
          }
     }
}

// Producer and consumer
// Fixed-size buffer and an index to access the buffer


public class IntBuffer
{
     private int index;// current available
     private int[] buffer = new int[8];

     public     synchronized    void add(int num)
     {
          while (true)
          {
                if (index < buffer.length)
                {
                       buffer[index++] = num;
                       return; // only happen once
                }
          }
     }

     public    synchronized    int remove()
     {
           while(true)
           {
                if (index > 0 )
                {
                      return buffer[--index];
                }
           } 
     }
}


public class Producer extends Thread
{
     private IntBuffer buffer;
     public Producer(IntBuffer buffer){
         this.buffer = buffer
     }
     public void run(){
            Random r = new Random();
            while(true){
                 int num = r.nextInt();
                 buffer.add(  num  );
                 System.out.println( "Produced" + num );
            }
    }
} 


public class Consumer extends Thread
{
     private IntBuffer buffer;
     public Consumer(IntBuffer buffer)
     {
        this.buffer = buffer;
     }
     public void run(){
          while(true){
               int num = buffer.remove();
               System.out.println("Consumed" + num);
          }            
     }
}

public static void main (String[] )
{
      IntBuffer b=  new IntBuffer();
      Producer p = new Producer(b);
      Consumer c = new Consumer(b);
      p.start();
      c.start();
}


// Problem 1:  busy waiting, while(true)
// Problem 2:  no access control to share resource
// Solution : add Synchronized keyword to the add() and remove()


// Problem :the producer suspends itself when the buffer is full and waits for a slot to open up, 
// While the consumer suspends itseft if the buffer is empty and waits for a new vlaue ot arive


public class IntBuffer
{
      ..index
      .. buffer
  
      .. synchonized void add..
      {
// Do the task           
            while (index == buffer.length-1)
            {
                   try{
                           wait();
                   }
                   catch ( InterruptedException e){
                        
                   } 
            }
            buffer[index +1] = num;
// Notify
            notifyAll();
      }


       .... synchonized int remove....
       {
            while (index == 0)
            {
                   try{
                           wait();
                   }
                   catch ( InterruptedException e){
                        
                   } 
            }
            int ret = buffer[--index];
            notifyAll();
            return ret;
       }
}
 

// The dining Pholosophers
// Only one fork to eat

Problem 1: This application deadlocks when all philosophers have simultaneously picked up their left fork: Because no right fork is available to any philosopher, no philosopher can eat

Solution1: One solution is to add a timeout to the waiting: If a philosopher is not able to eat within a predetermined amount of time after acquiring the first fork, then the philosopher drops the fork and tries again.

Problem2: The flaw with this solution is that it’s possible for one or more philosophers to starve because they never acquire both forks. This is referred to as livelock.


Solution2:The best solution requires a very simple change to the application. Instead of having all the philosophers pick up the left fork first, have one of the philosophers pick up the right fork first:

public class DiningPholisphers
{
        // Field
       // Each “fork” is just an object we synchronize on
       private Object[] forks;
       private Philosophers[] philosophers;
       

       // Constructor
       // prepare the forks and philosophers
      private DiningPholosophers( int num )
      {
              forks = new Object[num];
             philosophers = new Philosopher[ num];
              for (int i = 0 ; i < num ; i ++ )
              {
                          forks[i] = new Object();
                          int fork1 = i;
                         int fork2 = (i+1)%num;
                         philosophers[i] = new Philosopher(fork1, fork2, (i+1)%num ); // 
                           //   ‘A’ B’ C’ D’ E’ (5+1)%5 = 1 ⇒ E’s right fork == fork1 = A’s left fork


// This one change to the fork pickup order is enough to break the deadlock and ensure that forks are always available to enable hungry philosophers to eat.

// Ori   : 0,1 ; 1,2 ; 2,3; 3,4 ; 4,0; 
// New : 1,0; 1,2 ; 2, 3; 3,4 ;4, 0
 
int fork1 = i;
int fork2 = (i+1)%num;
if (i == 0)
       philosophers[0] = new Philosophers(0, fork2, fork1);
else 
       philosophers[i] = nwe Philosopher(i, fork1, fork2);



              }
      }


      // Main funtion
      public void startEating() throws InterrupedException
      {
                      for (int i = 0; i < philosophers.length;i++)
                             philosophers[i].start();


                      // suspend the main thread until the first philosopher stops eating, which will never happen -- this keeps the simulation running indefinitely
                     philosophers[0].join();
       }
          public static void main (Stirng[] args)
         {
                 try
                 {
                          DiningPhilosophers d = new DiningPhilosohers(5);
                          d.startEating();
                 }
                 catch (InterruptedException e)
                 {
                 }
          }
}

// Each philosophers run in its own thread
private class Philosophers extends Thread
{
          // Field 
          private itn id; 
          private int fork1;
          private int fork2;

         // Constructor
          Philosopoher(int id , int fork1, int fork2)
           { 
                    this.id = id; 
                    this.fork1 = fork1;
                   this.fork2 = fork2;
          } 
 
          public void run() 
          {
                      status (“Ready to eat using forks” + fork1 + “ and “+ fork2);
                      pause(); // pause to let others get ready
                      while (true)
                      {
                                   status(“Picking up fork ” + fork1);
                                   Synchronized (   forks[fork1] )
                                   {
                                                status (“ Picking up fork” + fork2);
                                              synchronized ( fork[fork2])
                                               {
                                                           status(“Eating”);
                                               }  
                                   }
                        }
          }

          private void pause()
           {
                    try{
                          sleep(200);
                    }
                     catch (InterruptedException e)
                   {
                          // do nothing
                    }
           }
           
          private void status (String msg)
         {
                   System.out.println(“Pholisopher ” +id + “;” + msg);
          }
}

[Snapchat]Company Party Dynamic programming

1. Example

              A
      /        |        \
     B       C -F      D-E
      |
     G

Case 1:
              A go
      /         |        \
     BNgoC -F      D-E
      |         Ngo     Ngo
     G go

Case2:
              A  nogo
      /        |        \
     B go  C -F   D-E
      |         go     go
     G nogo

Every node can go or nogo
go     => vlaue = node.rating;
nogo => value = 0;
     
2. Implementation

// time :O(2^n)

// ArrayList listOfStrings = new ArrayList<>(list.size());
// listOfStrings.addAll(list);
public List guestList(Node[] nodes)
{
      
      List maxlist = new ArrayList();
      int maxSum = 0;
      for (int i =0 ; i < nodes.length; i++)
      {
             List list = new ArrayList();
             int sum = FindMaxRating(nodes[i], list);
             if (  sum > maxSum )
             {
                  maxSum = sum;
                  maxList = new ArrayList(list);
                  list = null;
             }  
      }

}

private int FindMaxRating(Node node, List list)
{
      if ( node.children == null)
          return Math.max(0, node.rating);
      else      
      {
           
          int childrenSum = 0;
          for ( Node c: node.children)
          {
              childrenSum += FindMaxRating(c, list);
          }
          int grandChildrenSum  = node.rating;
          
          for (Node c: node.grandchildren)
          {
              grandChildrenSum += FindMaxRating(c, list);

          }
          return Math.max( childrenSum, grandChildrenSum  );
      }
}       

// Time:O(n)

public  List guestList(Node[] nodes)
{
     

      int[] MC = new int[nodes.length];
      for (i = nodes.length-1 ; i>=0; i++)
      {
          if (nodes[i].children == null || nodes[i].grandChildren == null)
               MC[i]  = Math.max(0+ node.rating, 0);
          else
               MC[i] = Math.max(   node.rating+ sumOfAll(node.children), 0 + sumOfAll(node.grandChildren) );
      }

     
      return MC[0];
}

private int sumOfAll(Node[] children)
{
      int sum = 0; 
      for (Node c: children)
      {
         sum+= c.rating;
      }
      return sum;
}

// Time:O(2n), n is the number of nodes

typredef struct Node
{
   int rating;
   int *parent, *leftChild, *rightSibling;
   int sel, unsel;
   int go; 
} Node;
typedef struct stack
{
   int *top, *base;
   int stackSize;
} Stack;
void traverse (Node *T)
{
      Stack s;
      s.top =1;
      Node *r;
      r = T;
      while(top != -1 || r != null )
      {
          s.top++;
          *s.top = r;
          while(   r.leftChild != null ) // add
          {
              s.top++;
              *s.top = r.leftchild;
              r = r.leftChild;
          }

          r = *s.top; // pop
          s.top--;

   
          // 
          if (r.leftChild == null) // check if leave
          {
              r.sel = r.rating;
              r.unsel = 0;
          }
          else // not a leaf
          {
              r.sel = r.rating + sum( j.unsel );
              r.unsel = sum ( max{ j.unselect, j.sel} );
          }
          
          r = r.rightSibling;
      }
}
void find_the_list(Node *T)
{

   Node *r, *s;
   r = T;
   if (  r == null ) return ;
   else if ( r.parent == NULL ) 
   {
        if ( r.select > r.unselct )
              r.go = 1;
         else
              r.go =0;
   }
   else 
   {
        if (r.parent.go ==1)
              r.go = 0;
         else
         {
            if ( r.unselect < r.select)
              r.go = 0;
            else
              r.go = 1;
         }
   }
   
   r = r.leftChild;
   s= r.rightSibling;
   find_the_list(r);
   find_the_list(s);
    
   // Print out those go ==1       
}

3. Similar Ones
http://mypathtothe4.blogspot.com/2013/03/dynamic-programming-company-party.html
http://blog.csdn.net/edonlii/article/details/8623058