php.ini에서 short_open_tag = Off 로 설정.

블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

댓글을 달아 주세요

This is my result of the individual project from Algorithm class CSCI 3101 Hawaii Pacific University.

알고리듬 수업에서 수행한 개인 프로젝트의 결과물입니다.


Freckles Skiena and Revilla Programming Challenges book.

알고리즘 트레이닝 북에 실린 주근깨 문제입니다.


I implemented Prim and Kruskal algorithms for this project with Python. See attached files on the bottom of this post if you need.

You are allowed to edit attached source codes, but please do not remove my name as an author on the top.

참고로, 한국에서 판매하는 책에 해답(C로 작성된 소스코드)이 실려있지만, 실제로 작성해서 컴파일/실행해본 결과 제대로 작동이 되질 않았습니다. 따라서, 이것을 필자가 파이썬으로 재작성했고, 프로젝트의 조건은 Prim과 Kruskal 두 개의 알고리즘으로 구현해야하는 것이었습니다. 소스코드는 첨부된 하단에 파일을 참고해주세요. 내용은 수정해도 되지만, 제 이름은 삭제하지 말아주세요.


The below is the problem from the book.

아래는 알고리즘 트레이닝 북에 실린 문제의 원문입니다.



In an episode of the Dick Van Dyke television show, Dick’s son Richie connects the freckles on his father’s back to form a picture of the Liberty Bell. Consider Dick's back to be a plane with freckles at various (x, y) locations. Your job is to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.


Input

The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.

The first line of each test case contains 0 < n <= 100, giving the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x, y) coordinates of the freckle.

Put a blank line between each two consecutive test cases.


Output

For each test case, your program must print a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. The output of each two consecutive cases must be separated by a blank line.


Sample Input

1

3
1.0 1.0
2.0 2.0
2.0 4.0

Sample Output

3.41 


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

My source codes


Prim:






Kruskal:






HowItWorks.pdf


SeowonJung_Kruskal_Comment.py


SeowonJung_Prim_Comment.py


블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

댓글을 달아 주세요

파이썬으로 작성한 Max-Heapify의 코드다. 의사코드는 Introduction to Algorithms라는 MIT Press에서 나온 교재에서 참조했다.

MinHeapify.py

Source code: MinHeapify.py

블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

Tag Heap, heapify

댓글을 달아 주세요

파이썬으로 작성한 Max-Heapify의 코드다. 의사코드는 Introduction to Algorithms라는 MIT Press에서 나온 교재에서 참조했다.

MaxHeapify.py

Source: MaxHeapify.py

블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

Tag Heap, heapify

댓글을 달아 주세요

RecursiveInsertionSort.py

소스코드: recursiveInsertoinSort.py

블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

댓글을 달아 주세요

참고로, 맥에서만 가능하다.

 

from AppKit import NSPasteboard, NSArray

 

pb = NSPasteboard.generalPasteboard()

pb.clearContents()

strClipboard = NSArray.arrayWithObject_('Message Here')

pb.writeObjects_(strClipboard)

블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

댓글을 달아 주세요

자바로 만든 UDP Ping 프로그램이다.
서버를 실행할 때 포트번호를 임의로 적어주면 된다.
예) javac PingServer.java && java PingServer localhost 1024

클라이언트의 실행법은 서버의 IP와 포트번호를 적으면 된다.
예) javac PingClient.java && java PingClient localhost 1024

서버의 코드는 Computer Networking, Kurose and Ross, 5th edition에서 작성된 그대로다.

Programming Assignment 3: UDP Pinger Lab

In this lab, you will study a simple Internet ping server written in the Java language, and implement a corresponding client. The functionality provided by these programs are similar to the standard ping programs available in modern operating systems, except that they use UDP rather than Internet Control Message Protocol (ICMP) to communicate with each other. (Java does not provide a straightforward means to interact with ICMP.) 

The ping protocol allows a client machine to send a packet of data to a remote machine, and have the remote machine return the data back to the client unchanged (an action referred to as echoing). Among other uses, the ping protocol allows hosts to determine round-trip times to other machines.

You are given the complete code for the Ping server below. Your job is to write the Ping client.
 

Server:
// File name: PingClient.java
import java.io.*;
import java.net.*;
import java.util.*;

public class PingServer
{
   private static final double LOSS_RATE = 0.3;
   private static final int AVERAGE_DELAY = 100;  // milliseconds

   public static void main(String[] args) throws Exception
   {
      // Get command line argument.
      if (args.length != 1) {
         System.out.println("Required arguments: port");
         return;
      }
      int port = Integer.parseInt(args[0]);

      // Create random number generator for use in simulating
      // packet loss and network delay.
      Random random = new Random();

      // Create a datagram socket for receiving and sending UDP packets
      // through the port specified on the command line.
      DatagramSocket socket = new DatagramSocket(port);

      // Processing loop.
      while (true) {
         // Create a datagram packet to hold incomming UDP packet.
         DatagramPacket request = new DatagramPacket(new byte[1024], 1024);

         // Block until the host receives a UDP packet.
         socket.receive(request);

         // Print the recieved data.
         printData(request);

         // Decide whether to reply, or simulate packet loss.
         if (random.nextDouble() < LOSS_RATE) {
            System.out.println("   Reply not sent.");
            continue;
         }

         // Simulate network delay.
         Thread.sleep((int) (random.nextDouble() * 2 * AVERAGE_DELAY));

         // Send reply.
         InetAddress clientHost = request.getAddress();
         int clientPort = request.getPort();
         byte[] buf = request.getData();
         DatagramPacket reply = new DatagramPacket(buf, buf.length, clientHost, clientPort);
         socket.send(reply);

         System.out.println("   Reply sent.");
      }
   }

   /*
    * Print ping data to the standard output stream.
    */
   private static void printData(DatagramPacket request) throws Exception
   {
      // Obtain references to the packet's array of bytes.
      byte[] buf = request.getData();

      // Wrap the bytes in a byte array input stream,
      // so that you can read the data as a stream of bytes.
      ByteArrayInputStream bais = new ByteArrayInputStream(buf);

      // Wrap the byte array output stream in an input stream reader,
      // so you can read the data as a stream of characters.
      InputStreamReader isr = new InputStreamReader(bais);

      // Wrap the input stream reader in a bufferred reader,
      // so you can read the character data a line at a time.
      // (A line is a sequence of chars terminated by any combination of \r and \n.)
      BufferedReader br = new BufferedReader(isr);

      // The message data is contained in a single line, so read this line.
      String line = br.readLine();

      // Print host address and data received from it.
      System.out.println(
         "Received from " +
         request.getAddress().getHostAddress() +
         ": " +
         new String(line) );
   }
}



Client:
// File name: PingClient.java
import java.util.*;
import java.net.*;
import java.text.*;

public class PingClient
{
    private static final int PING_MESSAGES = 10;
    private static final int TOKEN_TIMESTAMP = 2;
    private static final int MAX_WAIT_TIME = 1000;
    private static final String CRLF = "\r\n";

    public static void main(String[] args) throws Exception
    {
        // If user doesn't input both port number and ip address, the program will display an error message.
        if (args.length != 2)
        {
            System.out.println("usage: java PingClient <Host> <Port>");
            //return;
        }
        
        try
        {
            if(!args[0].isEmpty())
                System.out.println("\nHost: "+args[1]+"\nIP address: "+args[0]+"\n");
        }
        catch(ArrayIndexOutOfBoundsException e)
        {
            System.out.println("Host name and ip address please");
            System.exit(1);
        }
        InetAddress host = InetAddress.getByName(args[0]);
        
        int portNumber = Integer.parseInt(args[1]);
        
        //Create a datagram socket used for sending and recieving UDP packets
        DatagramSocket socket = new DatagramSocket();

        //Set up the maximum time the socket waits for responses
        socket.setSoTimeout(MAX_WAIT_TIME);

        //Construct a ping message to be sent to the Server
        for (int sequence_num = 0; sequence_num < PING_MESSAGES; sequence_num++)
        {
                String message = generatePing(sequence_num);
                DatagramPacket ping_request =
                    new DatagramPacket(message.getBytes(), message.length(), host, portNumber);

                //Send a ping request
                socket.send(ping_request);

                //Datagram packet to hold server response
                DatagramPacket ping_response =
                    new DatagramPacket(new byte[message.length()], message.length());

                //Wait for ping response from server
                try
                {
                        socket.receive(ping_response);
                        printData(ping_response);
                }
                catch (SocketTimeoutException e)
                {
                        System.out.println("No response was received from the server");
                }
                catch (Exception e)
                {
                        //Another unknown error may have occured that can't be handled
                        e.printStackTrace();
                        return;
                }
        }
    }

    private static String generatePing(int sequence_num)
    {
        // For getting current date and time 
        SimpleDateFormat sdfNow = new SimpleDateFormat("MM/dd/yyyy HH:mm:ss");
        String strNow = sdfNow.format(new Date(System.currentTimeMillis()));
        return "PING #" + sequence_num + " " + System.currentTimeMillis() + " ("+strNow+")";
    }

    //Print ping page to standard output stream
    private static void printData(DatagramPacket request) throws Exception
    {
        String response = new String(request.getData());
        String[] tokens = response.split(" ");
        
        //Create sent and received timestamps for RTT
        long sent_timestamp = new Long(tokens[TOKEN_TIMESTAMP]);
        long received_timestamp = System.currentTimeMillis();

        //RTT
        long rtt = received_timestamp - sent_timestamp;

        //Display results
        System.out.print(response+" Received from "+
                request.getAddress().getHostAddress() + " "+"(RTT=" + rtt + "ms)"+CRLF);
    }
}
블로그 이미지

Seowon Jung jswlinux

Seowon Jung의 잡동사니 보관소

댓글을 달아 주세요