Michael의 작업실

 Week 6: Linear Lists - Simulated Pointer Representation
6주차 선형 목록 : 포인터 시뮬레이트 표현법.
Since we have midterm exams next week, I will give you an extremely easy assignment. I belive that this takes only a couple of hours.
다음주에 시험이니까 매우쉬운 과제를 줄께, 난 이 과제가 2시간 정도 걸릴거라고 생각해.

Section 7.7 introduces the concepts of the equivalent relationship and union set.
7.7장에서 동등관계와 공용체의 컨셉을 소개했다.

Just type in the example code to find the union set, and write a program that test the example code.
책에서 공용체를 찾는 코드를 그대로 쳐라, 그리고 그것을 테스트하는 예제 코드를 만들어 보아라.

What you will turn in is a PDF file that contains the test code, screen shots of the test program in execution, and brief explanation of your understanding on the concepts of the equivalent relationship and union set.
니가 할일은 테스트 코드와, 실행 스크린샷, 그리고 니가 이 컨셉을 이해했다는것을 증명하는 설명을 PDF에 담아 제출하는것이다.

Week 6: Linear Lists - Simulated Pointer Representation

Week 5: Linear Lists - Linked Representation

1. Write code for the class ChainWithSortMethods.

ChainWithSortMethods 클래스를 만들어라

This class is a subclass of Chain and it includes the number method insertionSort, which uses insertion sort to reorder the chain elements into nondecreasing order.
이 클래스는 Chain을 상속받는다. 그리고 인자의 크기를 오름차순 정렬하는 insertionSort 메소드를 갖고있다.
Do not create new nodes or delete old ones.

노드를 새로 생성하거나 삭제하지 마라.

a) What is the worst-case time complexity of your method? How much time does your method need if the elements are already in sorted order?

최악의 경우 에 시간복잡도는 얼마인가?

이미 정리되어 있는 경우에는 시간이 얼마나 걸리는가?

b) Test the correctness of your method by compiling and then executing the code. Use your own test data (any programs with any data are allowed).

측정의 정확성을 위해 컴파일링을 하고 실행해봐라.

너만의 테스트 데이터를 만들어라

Week 5: Linear Lists - Linked Representation

1. Write code for the class ChainWithSortMethods. This class is a subclass of Chain and it includes the number method insertionSort, which uses insertion sort to reorder the chain elements into nondecreasing order. Do not create new nodes or delete old ones.

a) What is the worst-case time complexity of your method? How much time does your method need if the elements are already in sorted order?

b) Test the correctness of your method by compiling and then executing the code. Use your own test data (any programs with any data are allowed).

1. Make an interface “StudentLinearList” as shown in Program 5.1.
프로그램 5.1 에 있는것과 같이 StucentLinearList 인터페이스를 만들어라.

Implement the “StudentArrayLinearList” class, which is an implementation of the interface “StudentLinearList”.
StudentLinearList를 인터페이스로 갖는, StucentArrayLinearList클래스를 구현하여라.

Modify the time measuring program, which was used in the last homework, by replacing the “Student” object array with the “StudentArrayList” class.
지난번 과제에서 만들어 놓은 시간측정프로그램을 Student배열을 사용하던것에서 StudentArrayList클래스를 사용하는것으로 수정해라.

2. Extend “StudentArrayLinearList” to include the method “removeRange”, which removes all elements in the specified index range.
StudentArrayLinearList를 특정 인덱스 범위를 제거하는 removeRange메소드를 갖도록 확장해라.

What is the complexity of your method?
이 메소드의 복잡도는 얼마인가?

3. Extend “StudentArrayLinearList” to include the method “concateList”, which concatenates a parameter “StudentArrayLinearList” to the list of the method-owner object.
StudentArrayLinearList를 StudentArrayLinearList를 인자로 하여, 원래 배열에 인자로 받은 배열을 이어 붙이는 concateList메소드를 갖도록 확장해라.

What is the complexity of your method? Test your code with a simple example code.

1. Now we have four sorting algorithm implementations, which were originated from the 2nd week homework.
이제 우리는 2번째 과제의 4개의 정렬 알고리즘을 갖고있다.
This is the time for asymptotically analyze each program. Of course, you have to analyze them under best, worst and average cases.
이번엔 점근적인(asymptotically) 분석을 해보자. 물논, 최악, 최적, 평균적인 사건에 대해 분석해야 된다.

2. Since we have the actual implementations, we can measure the execution time of them.
실제로 구현을 해놓았기 때문에 우리는 각 알고리즘의 실행시간을 측정할수 있다.

As we learned in the class, insert profiling (time measuring) code into your programs, and measure the time to sort randomly generated data sets (Yes, you have to make random student object generating code, too!).
우리가 수업에서 배운 시간 측정용 코드를 너의 프로그램에 넣어라, 그리고 임의로 생성된 데이터셋을 정렬하는 시간을 측정하여라(우리는 랜덤한 학생 오브젝트를 만드는것도 수업시간에 해 보았다.)

The number of students to be sorted must vary from 10 to 1,000,000 by log-scale increment (10, 100, 1,000, 10,000, … on and on).
학생의 숫자는 10에서 1,000,000 까지 큼직큼직하게 변해야 한다(10, 100, 1,000, 10,000, 이런식으로,,)

Draw graphs illustrating the tendency of the execution time changes depending on the changes of the data set size.
데이터 셋의 사이즈에 따라 실행 시간이 변하는 추세를 나타내는 그래프를 그려라.

The source codes, analysis results and graphs have to be prepared in a PDF file.
소스코드와, 분석결과, 그리고 그래프는 반드시 PDF파일로 보내세요.

1. Now we have four sorting algorithm implementations, which were originated from the 2nd week homework. This is the time for asymptotically analyze each program. Of course, you have to analyze them under best, worst and average cases.

2. Since we have the actual implementations, we can measure the execution time of them. As we learned in the class, insert profiling (time measuring) code into your programs, and measure the time to sort randomly generated data sets (Yes, you have to make random student object generating code, too!). The number of students to be sorted must vary from 10 to 1,000,000 by log-scale increment (10, 100, 1,000, 10,000, … on and on). Draw graphs illustrating the tendency of the execution time changes depending on the changes of the data set size.

The source codes, analysis results and graphs have to be prepared in a PDF file.

음,, 일단 랭크소트가 무엇인지를 파악해야겠군,,,
최형이라면 알지도 모르지만, 혼자 해보는것도 재미있을것 같다,,
문제는 시간.

시간 복잡도의 경우도 “counting the comparison operations(비교 연산자 갯수 세기)”는 쉬운데 “counting the steps with the s/e and frequency table(스텝을 세어서 빈도분석)”법은,,,,, 서의성 교수님 시간이었지만, 전날 무리하는 바람에 못들었다..

공부할게 많네,,,

공간 사용에 대해서는 보통 정렬의 경우에 공간은 거의 차지하지 않지, 임시공간 1개 정도? (merge의 경우를 제외하면,, 저번에 보니까 merge도 새로 안만들고 어떻게 하는 모양이던데,, 나는 같은 크기의 배열을 2개 만들고 옮겨 다녔으니,,,,)

 뭐,,, 오늘부터 해봐야지..

1. Our textbook introduces another sorting algorithm called rank sort at page 80.
1. 우리의 교제에서는 또다른 정령 알고리즘인 rank정렬을 80페이지에서 소개하고 있다.
Make a rank sort program that sorts students by their name and print their scores along side the names in the sorted order.
Rank정렬을 이용하여 학생들을 그들의 이름으로 정렬하고, 그들의 점수를 정렬된 이름옆에 표시하는 프로그램을 작성하여라.
Student names and scores must be included in a Student object.
학생의 이름과 점수는 반드시 Student 오브젝트에 포함되도록 만들어져야 한다.
The data are input through keyboard and the number of students is flexible (use a sentinel).
입력받는 데이터는 키보드로 입력받도록 하고, 학생의 수는 자유롭게 입력 받을수 있도록 한다(sentinel은 보초라는 뜻인데,,,,).
Analyze the best case, worst case and average case space and time complexity of the program you made.
당신이 만든 프로그램에서 시,공간 복잡도를 최적, 최악, 평균적인 경우을 놓고 분석하여라.
For time complexity, use both “counting the comparison operations” and “counting the steps with the s/e and frequency table” approaches.
시간 복잡도의 경우 “counting the comparison operations(비교 연산자 갯수 세기)”와 “counting the steps with the s/e and frequency table(스텝을 세어서 빈도분석)”법을 모두 사용하여라.

2. Modify the program for problem 1 by replacing the sorting algorithm with bubble sort, insert sort and selection sort.
2. 1에서 만들었던 프로그램을 Bubble정렬과 Insert정렬, Selection정렬로 고쳐보아라.
Also, you have to analyze the best, worst and average case space and time complexity of each version.
또한 최적, 최악, 평균적인 경우의 시, 공간 복잡도를 각각 분석하여라.

* The source codes, analysis results and screen shots of your programs in working have to be prepared in a PDF file.
* 소스코드와 분석결과, 그리고 프로그램 작동의 스샷은 PDF파일로 작성하여라.

이제 C++패스했다고, 점점 귀찮아 집니다....ㄷㄷ

1. Julian dates. Suppose you would like to know how many days ago Columbus was born. It is tedious to figure this out by hand, because months have different lengths and because you have to worry about leap years. Many people, such as astronomers, who deal with dates a lot have become tired of dealing with the craziness of the calendar and instead represent days in a completely different way: the so-called Julian day number. That value is defined as the number of days that have elapsed since Jan. 1, 4713 B.C. A convenient reference point is that October 9, 1995, is Julian day 2,450,000.

Here is an algorithm to compute the Julian day number: Set jd, jm, jy to the day, month, and year. If the year is negative, add 1 to jy. (There was no year 0. Year 1 B.C. was immediately followed by year A.D. 1) If the month is larger than February, add 1 to jm. Otherwise, add 13 to jm and subtract 1 from jy. Then compute

long jul = floor(365.25 * jy) + floor(30.6001 * jm) + d + 1720995.0

We store the result in a variable of type long; simple integers may not have enough digits to hold the value. If the date was before October 15, 1582, return this value. Otherwise, perform the following correction:

int ja = 0.01 * jy;

jul = jul + 2 - ja + 0.25 * ja;

Now write a function

long julian(int year, int month, int day)

that converts a date into a Julian day number. Use that function in a program that prompts the user for a date in the past, then prints out how many days that is away from today's date.

이게 1번문제 이고

 

2. Write a procedure void sort2(int& a, int& b) that swaps the values of a and b if a is greater than b and otherwise leaves a and b unchanged. For example,

int u = 2;

int v = 3;

int w = 4;

int x = 1;

sort2(u, v);

/* u is still 2, v is still 3 */

sort2(w, x);

/* w is now 1, x is now 4 */
이게 2번인데,,,
1번은 무슨 juliandate라는 만년력을 구하라는 문제 같고,,
2번은 간단히 크기가 작은것을 앞으로 큰것을 뒤로 보내는 문제 같네여,, C++은 BB를 보시면 교수님의 ppt도 있고, wiley에 보시면 교재도 있으니,, 참조변수에 관한것을 좀 보시는것이 도움이 되겠네요,,

요즘 정신없이 사느라 티스토리도 못들어 오네요,,,ㄷㄷ
일단 이번숙제는

1. Write a unit conversion program that asks users to identify the unit from which they want to convert and the unit to which they want to convert. Available units should be mm, cm, m, ft, and in. Define two objects of a class UnitConverter that convert between meters and a given unit.

Convert from:
in
Convert to:
mm
Value:
10
10 in = 254 mm

Use the following class as your main class:

import java.util.Scanner;

/**
   This class converts between two units.
*/
public class ConversionCalculator
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);

      System.out.println("Convert from:");
      String fromUnit = in.nextLine();

      System.out.println("Convert to:");
      String toUnit = in.nextLine();

      UnitConverter from = new UnitConverter(fromUnit);
      UnitConverter to = new UnitConverter(toUnit);

      System.out.println("Value:") ;
      double val = in.nextDouble();

      double meters = from.toMeters(val);
      double converted = to.fromMeters(meters);

      System.out.println(val+ " "+ fromUnit+ " = "+ converted
            + " "+ toUnit);
   }
}

이거입니다.
mm, cm, m, ft, in중 2개를 선택받아 서로 단위를 변환하는 계산기 문제인데요,,
UnitConverter 란 클래스를 만들어서
생성자에서는 처음 들어간 string을 갖고 처음의 단위를 계산하고, toMeter라는 함수를 이용해서 공통단위인 Meter로 고침니다. 그다음 그Meter단위 숫자를 받아서 다시 원하는 단위로 고치는,,,


순서는 이렇습니다.

1. 먼저 2개의 단위를 입력받습니다.
2.  이것을 각각 from, to라는 UnitConverter클래스에 생성자의 인자로 주어 from, to의 단위를 정합니다.
3. 그다음 from을 meter로 바꾸는 함수를 이용해 meter값을 임시변수에 넣습니다.
4. meter단위인 임시변수를 to 에 집어넣어 to 단위로 바꿈니다.
5. 이것을 출력합니다.,,,

말은 쉽지만, 이걸 하려면 if노가다나 단위변환상수를 정해놔야겠군요,,,

늦었지만 공지 합니다.
제가 C++을 패스하고 좀 게을러 졌네요,,,

1번.
"Do you want to continue?"라는 문구를 출력한뒤 사용자게  "Y", "Yes", "OK", "Sure", or "Why not?"을 입력하면 "OK"를 출력하고, "N", "No"를 입력하면 "Terminating"을 출력,
둘다 아니면 "Bad input"을 출력하도록 하고, 대소문자는 구분하지 않는대요,,

2번.
계속 사용하던 Employee 클래스형 변수를 이용해서 이름과 시급을 읽어 냅니다.
그후 일주일에 몇시간을 일했는지를 물어보고, 1주일의 급여를 계산하는데,
주당 40시간 이상 일한부분은 1.5배의 봉금을 주래요,,, (맞나, 오역이 있으면 댓글이나 쪽지로,,)

문제는 이 두가지 인데,
1번은 입력을 받은뒤 if문을 쓸줄 아느냐? 라는 문제이고,
2번은,, 글쎄,, 값을 갖고,,,, 이것도 if문이네요,,
열심히 해 보세요(참 쉽죠?)

그리고 제가 모든것을 다 설명드릴수는 없지만(검열때문에), dcmichael@nate.com <<네이트온
으로 쪽지주시면 모르는 부분은 좀더 자세히 설명해 드리겠습니다

너무 늦었지만, 공지합니다.
이번 숙제는 두개의 수를 입력받을수 있고
합, 차, 곱, 평균, 차이의 절대값, 둘중 큰수, 둘중 작은수
들을 출력할수 있는 클래스 Pair을 설계하는것 이 첫번째 숙제고요,

두번째는 DataSet 라는 클래스를 설계해서 값을 입력받고, 입력받은값중
제일 큰 수와 제일 작은수를 출력하는 클래스를 설계하랍니다.

우선 첫번째 Pair클래스는
 public class Pair
{
   /**
      Constructs a pair.
      @param aFirst the first value of the pair
      @param aSecond the second value of the pair
   */
   public Pair(double aFirst, double aSecond) { . . . }

   /**
      Computes the sum of the values of this pair.
      @return the sum of the first and second values
   */
   public double getSum() { . . . }
   . . .
}
이런식이 되야겠구요,
두번째 DataSet 클래스문제는 초기화땐 Integer.MIN_VALUE, Integer.MAX_VALUE 라는 함수를 사용하고, 대소를 구분할땐 Math.max, Math.min함수를 사용하라는 힌트가 주어졌군요,,, if 같은거 쓰지 말래요,,,
그리고 각각 Pair클래스를 테스트하는 PairTester클래스와
DataSet클래스를 테스트하는 DataSetTest클래스도 만들어야 겠네요,,

제가 모든것을 다 설명드릴수는 없지만(검열때문에), dcmichael@nate.com <<네이트온
으로 쪽지주시면 모르는 부분은 좀더 자세히 설명해 드리겠습니다

내용은

내용은 아래와 같아요~~

1. Your boss, Juliet Jones, is getting married and decides to change her name. Complete the following program so that you can type in the new name for the boss:

	int main()
	{
	   Employee boss("Jones, Juliet", 45000.00);
	   /* your code goes here; leave the code above and below unchanged */
	
	   cout << "Name: " << boss.get_name() << "\n";
	   cout << "Salary: " << boss.get_salary() << "\n";
	
	   return 0;
	}

The problem is that there is no set_name member function for the Employee class. Hint: Make a new object of type Employee with the new name and the same salary. Then assign the new object to boss.

2. Write a program that reads in three-floating point numbers and print the largest of the three inputs. For example:
Please enter three numbers: 4 9 2.5The largest number is 9.

1번 문제는 지난번의 Employee클래스 또 써먹는 거구요,
2번 문제는 숫자 3개의 크기비교하는 문제네요,,,

우리 교수님 항상 클래스문제와 프로그램 구현능력문제를 골고루 내주시는군요,,,
여러분 수고하세요^^

You are supposed to make two simple programs in this week.

1. Based on the rectangle class example in our text book, add "intersection method" to the rectangle class. The intersection method returns the intersection of two rectangles, that is the rectangle formed by two overlapping rectangles.

You call this method as follows:

Rectangle r3 = r1.intersection(r2);

r3 is the intersection rectangle formed by r1 and r2.

Write a program IntersectionPrinter that constructs two rectangle objects, prints them, and then prints the rectangle object that describes the intersection. Then the program should print the result of the intersection method when the rectangles do not overlap. Add a comment to your program that explains how you can tell whether the resulting rectangle is empty.

2. Write a program HollePrinter that switches the letters "e" and "o" in a string. Use the replace method repeatedly. You don't need to get inputs from console or GUI. Place the input in your code (For example String input = "Hello, World"). Demonstrate that the string "Hello, World!" turns into "Holle, Werld!".

내용은 요렇게,,,

역시 파일은 여기(였는데,,, due가 넘어가는바람에 검열당한,,,)

You need to set up a C++ compiler in your computer. I recommend Microsoft Vistual C++ Express. It is free. Another option is using Cygwin G++ compiler, which is also free.

In this week, you will make three simple programs.

1. Write a program that asks the user for the lengths of the sides of a rectangle. Then print

The area and perimeter of the rectangle
 
The length of the diagonal (use the Pythagorean theorem)
 

2. Write a program that prompts the user for the names and salaries of three employees. Then print out the average salaries of the employees. Information about each employee must be stored in an employee object.

3. Write a program that reads a number greater than or equal to 1,000 from the user and prints it out with a comma separating the thousands. Here is a sample dialog; the user input is in color:

    Please enter an integer >= 1000:  23456    23,456

내용은 대략 요거,,,

내 풀이는,,,, 이거참조(였는데,,, due가 길어져서 검열당한,,,)