diff options
125 files changed, 3793 insertions, 15 deletions
diff --git a/README.md b/README.md index 393c47a..4ebe2ae 100644 --- a/README.md +++ b/README.md @@ -2,21 +2,22 @@ Bài tập luyện tập thi Olympic, học sinh giỏi Tin học, trong đó: -| Thư mục | Nguồn đề bài | -| ---------------------- | ------------------------------------------------- | -| `09`, `10`, `11`, `12` | Đề thi, kiểm tra phân theo lớp | -| `COCI` | [Giải Tin học Croatia mở rộng][0] | -| `NTU` | [Đại học Nha Trang][1] | -| `THT` | Hội thi Tin học trẻ | -| `codechef` | [Codechef][2] | -| `codeforces` | [Codeforces][3] | -| `cpptour` | A Tour of C++ | -| `daily` | [/r/dailyprogrammer][4] | -| `others` | Các đề bài không rõ nguồn | -| `paip` | Paradigms of Artificial Intelligence Programming | -| `sicp` | Structure and Interpretation of Computer Programs | -| `thinkperl6` | Think Perl 6 | -| `toys` | Programs that don't deserve their own repo | +| Thư mục | Nguồn đề bài | +| ------------ | ------------------------------------------------------ | +| `\d{2}` | Đề thi, kiểm tra phân theo lớp | +| `COCI` | [Giải Tin học Croatia mở rộng][0] | +| `NTU` | [Đại học Nha Trang][1] | +| `THT` | Hội thi Tin học trẻ | +| `codechef` | [Codechef][2] | +| `codeforces` | [Codeforces][3] | +| `cpptour` | A Tour of C++ | +| `daily` | [/r/dailyprogrammer][4] | +| `others` | Các đề bài không rõ nguồn | +| `paip` | Paradigms of Artificial Intelligence Programming | +| `sicp` | Structure and Interpretation of Computer Programs | +| `thinkperl6` | Think Perl 6 | +| `toys` | Programs that don't deserve their own repo | +| `usth` | L'Université des Sciences et des Technologies de Hanoï | [0]: http://www.hsin.hr/coci/ [1]: http://laptrinh.ntu.edu.vn/ @@ -34,6 +35,7 @@ Phiên bản các trình dịch sử dụng test: | ----------- | ------------------ | | C | GNU GCC 4.9+ | | Common Lisp | SBCL 1.4.8+ | +| Java | OpenJDK 11+ | | Lua | Lua 5.1+ | | Pascal | Free Pascal 2.6.4+ | | Perl 6 | Rakudo 2018.12+ | diff --git a/usth/ICT2.2/final/Member.java b/usth/ICT2.2/final/Member.java new file mode 100644 index 0000000..a3e2092 --- /dev/null +++ b/usth/ICT2.2/final/Member.java @@ -0,0 +1,54 @@ +public class Member +{ + public static final String[] ROLES = {"leader", "club coordinator", + "keynote speaker of code sharing", + "product programmer"}; + + private String name; + private String time; + private int role; + + public String getName() + { + return name; + } + + public String getTime() + { + return time; + } + + public int getRole() + { + return role; + } + + public void setName(String name) + { + this.name = name; + } + + public void setTime(String time) + { + this.time = time; + } + + public void setRole(int role) throws IllegalArgumentException + { + if (role < 0 || role > 3) + throw new IllegalArgumentException("invalid role number: " + role); + this.role = role; + } + + public Member(String name, String time, int role) + { + setName(name); + setTime(time); + setRole(role); + } + + public String toString() + { + return String.format("%s (%s), from %s", name, ROLES[role], time); + } +} diff --git a/usth/ICT2.2/final/Point.java b/usth/ICT2.2/final/Point.java new file mode 100644 index 0000000..5e79428 --- /dev/null +++ b/usth/ICT2.2/final/Point.java @@ -0,0 +1,43 @@ +// Immutable Point +public class Point +{ + private double x; + private double y; + + public Point(double x, double y) + { + this.x = x; + this.y = y; + } + + public double getX() + { + return x; + } + + public double getY() + { + return y; + } + + public String toString() + { + return String.format("(%g, %g)", x, y); + } + + public static Point add(Point a, Point b) + { + return new Point(a.getX() + b.getX(), a.getY() + b.getY()); + } + + public static Point subtract(Point a, Point b) + { + return new Point(a.getX() - b.getX(), a.getY() - b.getY()); + } + + public static double calDisEuclid(Point a, Point b) + { + var trans = Point.subtract(a, b); + return Math.sqrt(trans.getX()*trans.getX() + trans.getY()*trans.getY()); + } +} diff --git a/usth/ICT2.2/final/Problem1.java b/usth/ICT2.2/final/Problem1.java new file mode 100644 index 0000000..a9c5e32 --- /dev/null +++ b/usth/ICT2.2/final/Problem1.java @@ -0,0 +1,15 @@ +import java.util.Scanner; + +class Problem1 +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + int n = scanner.nextInt(); + for (int i = 1; i <= n; i += 2) + System.out.println(i); + if (n % 2 == 0) + n--; + System.out.println((n + 1) * (n + 1) / 4); + } +} diff --git a/usth/ICT2.2/final/Problem2.java b/usth/ICT2.2/final/Problem2.java new file mode 100644 index 0000000..dcad796 --- /dev/null +++ b/usth/ICT2.2/final/Problem2.java @@ -0,0 +1,22 @@ +import java.util.Scanner; + +class Problem2 +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + System.out.println( + "Please enter two numbers which are the coordinate of one point:"); + var a = new Point(scanner.nextDouble(), scanner.nextDouble()); + System.out.println( + "Please enter two numbers which are the coordinate of another point:"); + var b = new Point(scanner.nextDouble(), scanner.nextDouble()); + + System.out.printf("First point: %s\nSecond point: %s\n", a, b); + // Vector would make a better name than Point + System.out.printf("Their sum: %s\nTheir difference: %s\n", + Point.add(a, b), Point.subtract(a, b)); + System.out.printf("The Euclidean distance between the two points: %s\n", + Point.calDisEuclid(a, b)); + } +} diff --git a/usth/ICT2.2/final/Problem3.java b/usth/ICT2.2/final/Problem3.java new file mode 100644 index 0000000..11be143 --- /dev/null +++ b/usth/ICT2.2/final/Problem3.java @@ -0,0 +1,40 @@ +import java.util.ArrayList; +import java.util.Scanner; + +class Problem3 +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + System.out.println("Number of members:"); + int n = scanner.nextInt(); + + var members = new ArrayList<Member>(); + for (int i = 0; i < n; ++i) + { + System.out.println("Member name: "); + String name = scanner.next(); + System.out.println("Member joining time: "); + String time = scanner.next(); + System.out.println("Member role number: "); + int role = scanner.nextInt(); + members.add(new Member(name, time, role)); + } + + var reports = new ArrayList<Report>(); + for (var m : members) + { + System.out.println(m); + System.out.println("Activity: "); + String act = scanner.next(); + System.out.println("Rate: "); + int rate = scanner.nextInt(); + reports.add(new Report(m.getName(), act, rate)); + } + + System.out.println("Members:"); + members.forEach(System.out::println); + System.out.println("Activity reports:"); + reports.forEach(System.out::println); + } +} diff --git a/usth/ICT2.2/final/Report.java b/usth/ICT2.2/final/Report.java new file mode 100644 index 0000000..ec4ee23 --- /dev/null +++ b/usth/ICT2.2/final/Report.java @@ -0,0 +1,18 @@ +public class Report +{ + String name; + String activity; + int rate; + + public Report(String name, String act, int rate) + { + this.name = name; + this.activity = act; + this.rate = rate; + } + + public String toString() + { + return String.format("%s: %s: %s", name, activity, rate); + } +} diff --git a/usth/ICT2.2/labwork/1/AllEqual.java b/usth/ICT2.2/labwork/1/AllEqual.java new file mode 100644 index 0000000..b1d6929 --- /dev/null +++ b/usth/ICT2.2/labwork/1/AllEqual.java @@ -0,0 +1,10 @@ +import java.util.Arrays; + +class AllEqual +{ + public static void main(String... args) + { + String first = args[0]; + System.out.println(Arrays.stream(args).allMatch(a -> (a.equals(first)))); + } +} diff --git a/usth/ICT2.2/labwork/1/Binary.java b/usth/ICT2.2/labwork/1/Binary.java new file mode 100644 index 0000000..3573a35 --- /dev/null +++ b/usth/ICT2.2/labwork/1/Binary.java @@ -0,0 +1,14 @@ +class Binary +{ + public static void main(String... args) + { + int n = Integer.parseInt(args[0]); + String s = ""; + while (n > 0) + { + s = (n % 2) + s; + n >>= 1; + } + System.out.println(s); + } +} diff --git a/usth/ICT2.2/labwork/1/Distance.java b/usth/ICT2.2/labwork/1/Distance.java new file mode 100644 index 0000000..16bcc2c --- /dev/null +++ b/usth/ICT2.2/labwork/1/Distance.java @@ -0,0 +1,10 @@ +class Distance +{ + public static void main(String... args) + { + double x = Double.parseDouble(args[0]); + double y = Double.parseDouble(args[1]); + System.out.printf("The distance from (%g, %g) to origin is %g\n", + x, y, Math.sqrt(x*x + y*y)); + } +} diff --git a/usth/ICT2.2/labwork/1/FivePerLine.java b/usth/ICT2.2/labwork/1/FivePerLine.java new file mode 100644 index 0000000..339e6cf --- /dev/null +++ b/usth/ICT2.2/labwork/1/FivePerLine.java @@ -0,0 +1,11 @@ +class FivePerLine +{ + public static void main(String... args) + { + for (int i = 1000; i < 2000; ++i) + if (i % 5 < 4) + System.out.print(i + " "); + else + System.out.println(i); + } +} diff --git a/usth/ICT2.2/labwork/1/FunctionGrowth.java b/usth/ICT2.2/labwork/1/FunctionGrowth.java new file mode 100644 index 0000000..e1bebfa --- /dev/null +++ b/usth/ICT2.2/labwork/1/FunctionGrowth.java @@ -0,0 +1,10 @@ +class FunctionGrowth +{ + public static void main(String... args) + { + System.out.println("ln n\tn\tn ln n\tn^2\tn^3\t2^n"); + for (long n = 16; n < 3005; n <<= 1) + System.out.printf("%g\t%d\t%g\t%d\t%d\t%g\n", Math.log(n), n, + n * Math.log(n), n*n, n*n*n, Math.pow(2, n)); + } +} diff --git a/usth/ICT2.2/labwork/1/HelloWorld.java b/usth/ICT2.2/labwork/1/HelloWorld.java new file mode 100644 index 0000000..cf7313a --- /dev/null +++ b/usth/ICT2.2/labwork/1/HelloWorld.java @@ -0,0 +1,7 @@ +class HelloWorld +{ + public static void main(String... args) + { + System.out.println("Hello, World!"); + } +} diff --git a/usth/ICT2.2/labwork/1/Hellos.java b/usth/ICT2.2/labwork/1/Hellos.java new file mode 100644 index 0000000..206ac58 --- /dev/null +++ b/usth/ICT2.2/labwork/1/Hellos.java @@ -0,0 +1,14 @@ +class Hellos +{ + private static final String[] TH = {"th", "st", "nd", "rd", "th", + "th", "th", "th", "th", "th"}; + + public static void main(String... args) + { + int n = Integer.parseInt(args[0]); + for (int i = 1; i <= n; ++i) + // Before one says this defeat the purpose of the section, + // the tertiary operator IS conditional. + System.out.println(i + TH[i % 100 / 10 == 1 ? 7 : i % 10] + " Hello"); + } +} diff --git a/usth/ICT2.2/labwork/1/Kary.java b/usth/ICT2.2/labwork/1/Kary.java new file mode 100644 index 0000000..51fd9af --- /dev/null +++ b/usth/ICT2.2/labwork/1/Kary.java @@ -0,0 +1,22 @@ +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +class Kary +{ + private static final char[] DIGITS = {'0', '1', '2', '3', '4', '5', '6', '7', + '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'}; + + public static void main(String... args) + { + int n = Integer.parseInt(args[0]); + List<Character> result = new ArrayList<Character>(); + for (int k = Integer.parseInt(args[1]); n > 0; n /= k) + result.add(DIGITS[n % k]); + + Collections.reverse(result); + for (char d : result) + System.out.print(d); + System.out.println(); + } +} diff --git a/usth/ICT2.2/labwork/1/RollLoadedDie.java b/usth/ICT2.2/labwork/1/RollLoadedDie.java new file mode 100644 index 0000000..161fd93 --- /dev/null +++ b/usth/ICT2.2/labwork/1/RollLoadedDie.java @@ -0,0 +1,10 @@ +import java.util.concurrent.ThreadLocalRandom; + +class RollLoadedDie +{ + public static void main(String... args) + { + int x = ThreadLocalRandom.current().nextInt(1, 9); + System.out.println((x < 6) ? x : 6); + } +} diff --git a/usth/ICT2.2/labwork/1/SpringSeason.java b/usth/ICT2.2/labwork/1/SpringSeason.java new file mode 100644 index 0000000..2fda09b --- /dev/null +++ b/usth/ICT2.2/labwork/1/SpringSeason.java @@ -0,0 +1,25 @@ +import java.time.LocalDate; +import java.time.DateTimeException; + +class SpringSeason +{ + private static final LocalDate start = LocalDate.of(42, 3, 19); + private static final LocalDate end = LocalDate.of(42, 6, 21); + + public static void main(String... args) + { + int m = Integer.parseInt(args[0]); + int d = Integer.parseInt(args[1]); + try + { + LocalDate query = LocalDate.of(42, m, d); + // Yes, I'm sorry for leaving it here. + // If only Java has the try-except-else like Python! + System.out.println(query.isAfter(start) && query.isBefore(end)); + } + catch (DateTimeException e) + { + System.out.println(false); + } + } +} diff --git a/usth/ICT2.2/labwork/1/SumOfSines.java b/usth/ICT2.2/labwork/1/SumOfSines.java new file mode 100644 index 0000000..2cf6e03 --- /dev/null +++ b/usth/ICT2.2/labwork/1/SumOfSines.java @@ -0,0 +1,8 @@ +class SumOfSines +{ + public static void main(String... args) + { + double t = Double.parseDouble(args[0]); + System.out.printf("sin2t + sin3t = %g", Math.sin(t * 2) + Math.sin (t * 3)); + } +} diff --git a/usth/ICT2.2/labwork/1/SumOfTwoDice.java b/usth/ICT2.2/labwork/1/SumOfTwoDice.java new file mode 100644 index 0000000..d955f28 --- /dev/null +++ b/usth/ICT2.2/labwork/1/SumOfTwoDice.java @@ -0,0 +1,13 @@ +import java.util.concurrent.ThreadLocalRandom; + +class SumOfTwoDice +{ + public static void main(String... args) + { + int x = ThreadLocalRandom.current().nextInt(1, 7); + System.out.println("First roll: " + x); + int y = ThreadLocalRandom.current().nextInt(1, 7); + System.out.println("Second roll: " + y); + System.out.println("Sum: " + (x + y)); + } +} diff --git a/usth/ICT2.2/labwork/1/TenHelloWorld.java b/usth/ICT2.2/labwork/1/TenHelloWorld.java new file mode 100644 index 0000000..d8a2cd9 --- /dev/null +++ b/usth/ICT2.2/labwork/1/TenHelloWorld.java @@ -0,0 +1,8 @@ +class TenHelloWorld +{ + public static void main(String... args) + { + for (int i = 0; i < 10; ++i) + System.out.println("Hello, World!"); + } +} diff --git a/usth/ICT2.2/labwork/1/UseArguments.java b/usth/ICT2.2/labwork/1/UseArguments.java new file mode 100644 index 0000000..d477f51 --- /dev/null +++ b/usth/ICT2.2/labwork/1/UseArguments.java @@ -0,0 +1,7 @@ +class UseArguments +{ + public static void main(String... args) + { + System.out.printf("Hi %s. How are you?\n", args[0]); + } +} diff --git a/usth/ICT2.2/labwork/1/UseThree.java b/usth/ICT2.2/labwork/1/UseThree.java new file mode 100644 index 0000000..9b5693b --- /dev/null +++ b/usth/ICT2.2/labwork/1/UseThree.java @@ -0,0 +1,8 @@ +class UseThree +{ + public static void main(String... args) + { + System.out.printf("Hi %s, %s and %s. How are you?\n", + args[2], args[1], args[0]); + } +} diff --git a/usth/ICT2.2/labwork/1/logic-xor-table.md b/usth/ICT2.2/labwork/1/logic-xor-table.md new file mode 100644 index 0000000..e955d5b --- /dev/null +++ b/usth/ICT2.2/labwork/1/logic-xor-table.md @@ -0,0 +1,8 @@ +# Logical Exclusive Or Table + +| a | b | a ^ b | +| ----- | ----- | ----- | +| false | false | false | +| false | true | true | +| true | false | true | +| true | true | false | diff --git a/usth/ICT2.2/labwork/1/string-concat.md b/usth/ICT2.2/labwork/1/string-concat.md new file mode 100644 index 0000000..624383f --- /dev/null +++ b/usth/ICT2.2/labwork/1/string-concat.md @@ -0,0 +1,15 @@ +# String Concatenation + +To quote the [official Java documentation](https://docs.oracle.com/javase/8/docs/api/java/lang/String.html): + +> The Java language provides special support for the string concatenation +> operator (`+`), and for conversion of other objects to strings. [...] +> String conversions are implemented through the method `toString`, defined +> by Object and inherited by all classes in Java. + +Thus the numbers (e.g. 2, 2 + 3 = 5) are converted to their strings +representations ("2", "5") and concatenated to the string. Since `+` is +operated from left to right, + + 2 + 3 + "bc" = 5 + "bc" = "5" + "bc" = "5bc" + "bc" + 2 + 3 = "bc" + "2" + 3 = "bc2" + 3 = "bc2" + "3" = "bc23" diff --git a/usth/ICT2.2/labwork/2/1_labwork1-extra.pdf b/usth/ICT2.2/labwork/2/1_labwork1-extra.pdf new file mode 100644 index 0000000..278400a --- /dev/null +++ b/usth/ICT2.2/labwork/2/1_labwork1-extra.pdf Binary files differdiff --git a/usth/ICT2.2/labwork/2/2_labwork2.pdf b/usth/ICT2.2/labwork/2/2_labwork2.pdf new file mode 100644 index 0000000..3cd1908 --- /dev/null +++ b/usth/ICT2.2/labwork/2/2_labwork2.pdf Binary files differdiff --git a/usth/ICT2.2/labwork/2/README.md b/usth/ICT2.2/labwork/2/README.md new file mode 100644 index 0000000..a81631e --- /dev/null +++ b/usth/ICT2.2/labwork/2/README.md @@ -0,0 +1,18 @@ +# Build with Maven + +Following the official guide [Maven in 5 Minutes](https://maven.apache.org/guides/getting-started/maven-in-five-minutes.html): + +1. Create a project named `my-app`: + + mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DarchetypeVersion=1.4 -DinteractiveMode=false + +2. Change into the project directory: `cd my-app` +3. Build the project: `mvn package` + +Extra exercises for labwork 1 are written in `src/main/java/com/mycompany/app/` +inside `my-app`. To launch a class named `App` for example, run + + java -cp my-app/target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App + +I find this build method to be overcomplicated for 5-minute throw-away programs +and decide not to use it in the upcoming labworks. diff --git a/usth/ICT2.2/labwork/2/my-app/pom.xml b/usth/ICT2.2/labwork/2/my-app/pom.xml new file mode 100644 index 0000000..07012c1 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/pom.xml @@ -0,0 +1,75 @@ +<?xml version="1.0" encoding="UTF-8"?> + +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <groupId>com.mycompany.app</groupId> + <artifactId>my-app</artifactId> + <version>1.0-SNAPSHOT</version> + + <name>my-app</name> + <!-- FIXME change it to the project's website --> + <url>http://www.example.com</url> + + <properties> + <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> + <maven.compiler.source>1.8</maven.compiler.source> + <maven.compiler.target>1.8</maven.compiler.target> + </properties> + + <dependencies> + <dependency> + <groupId>junit</groupId> + <artifactId>junit</artifactId> + <version>4.11</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <pluginManagement><!-- lock down plugins versions to avoid using Maven defaults (may be moved to parent pom) --> + <plugins> + <!-- clean lifecycle, see https://maven.apache.org/ref/current/maven-core/lifecycles.html#clean_Lifecycle --> + <plugin> + <artifactId>maven-clean-plugin</artifactId> + <version>3.1.0</version> + </plugin> + <!-- default lifecycle, jar packaging: see https://maven.apache.org/ref/current/maven-core/default-bindings.html#Plugin_bindings_for_jar_packaging --> + <plugin> + <artifactId>maven-resources-plugin</artifactId> + <version>3.0.2</version> + </plugin> + <plugin> + <artifactId>maven-compiler-plugin</artifactId> + <version>3.8.0</version> + </plugin> + <plugin> + <artifactId>maven-surefire-plugin</artifactId> + <version>2.22.1</version> + </plugin> + <plugin> + <artifactId>maven-jar-plugin</artifactId> + <version>3.0.2</version> + </plugin> + <plugin> + <artifactId>maven-install-plugin</artifactId> + <version>2.5.2</version> + </plugin> + <plugin> + <artifactId>maven-deploy-plugin</artifactId> + <version>2.8.2</version> + </plugin> + <!-- site lifecycle, see https://maven.apache.org/ref/current/maven-core/lifecycles.html#site_Lifecycle --> + <plugin> + <artifactId>maven-site-plugin</artifactId> + <version>3.7.1</version> + </plugin> + <plugin> + <artifactId>maven-project-info-reports-plugin</artifactId> + <version>3.0.0</version> + </plugin> + </plugins> + </pluginManagement> + </build> +</project> diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/App.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/App.java new file mode 100644 index 0000000..0f661cb --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/App.java @@ -0,0 +1,9 @@ +package com.mycompany.app; + +public class App +{ + public static void main(String... args) + { + System.out.println("Hello World!"); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Beers.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Beers.java new file mode 100644 index 0000000..b74a93b --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Beers.java @@ -0,0 +1,17 @@ +package com.mycompany.app; + +// Exercise 4 +public class Beers +{ + public static void main(String... args) + { + for (int i = 9; i > 1; --i) + System.out.printf( + "%d bottles of beer we are going to drink, %d bottles of beer.\n" + + "Now try to drink one, drink one,\n", i, i); + System.out.print( + "1 bottle of beer we are going to drink, 1 bottle of beer.\n" + + "Now try to drink one, drink one,\n" + + "Oh no, no bottles of beer to drink now.\n"); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/IsLeapYear.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/IsLeapYear.java new file mode 100644 index 0000000..f21b4b3 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/IsLeapYear.java @@ -0,0 +1,14 @@ +package com.mycompany.app; + +// Exercise 7 +public class IsLeapYear +{ + public static void main(String... args) + { + int n = Integer.parseInt(args[0]); + if (n % 4 == 0 && n % 100 != 0 || n % 400 == 0) + System.out.printf("%d is a leap year\n", n); + else + System.out.printf("%d is not a leap year\n", n); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Linear.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Linear.java new file mode 100644 index 0000000..e7a8413 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Linear.java @@ -0,0 +1,12 @@ +package com.mycompany.app; + +// Exercise 5 +public class Linear +{ + public static void main(String... args) + { + double a = Double.parseDouble(args[0]); + double b = Double.parseDouble(args[1]); + System.out.println(-b / a); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/MeanSTD.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/MeanSTD.java new file mode 100644 index 0000000..eb47914 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/MeanSTD.java @@ -0,0 +1,17 @@ +package com.mycompany.app; + +import java.util.Arrays; + +// Exercise 8 +public class MeanSTD +{ + public static void main(String... args) + { + double n = args.length; + double m = Arrays.stream(args).mapToDouble(Double::parseDouble).sum() / n; + double s = Math.sqrt( + Arrays.stream(args) + .mapToDouble(x -> Math.pow(Double.parseDouble(x) - m, 2)).sum() / n); + System.out.printf("Mean: %f\nStandard deviation: %f\n", m, s); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Quadratic.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Quadratic.java new file mode 100644 index 0000000..84d3ecd --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Quadratic.java @@ -0,0 +1,24 @@ +package com.mycompany.app; + +// Exercise 6 +public class Quadratic +{ + public static void main(String... args) + { + double a = Double.parseDouble(args[0]); + double b = Double.parseDouble(args[1]); + double c = Double.parseDouble(args[2]); + // assume ax^2 + bx + c = 0 is a valid quadratic equation + double d = b*b - a*c*4; + if (d < 0) + { + System.out.printf("%f + %fj\n", -b/a/2, Math.sqrt(-d)/a/2); + System.out.printf("%f + %fj\n", -b/a/2, -Math.sqrt(-d)/a/2); + } + else + { + System.out.println(-b/a/2 + Math.sqrt(d)/a/2); + System.out.println(-b/a/2 - Math.sqrt(d)/a/2); + } + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/RandRange.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/RandRange.java new file mode 100644 index 0000000..f5c5ffd --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/RandRange.java @@ -0,0 +1,13 @@ +package com.mycompany.app; + +import java.util.concurrent.ThreadLocalRandom; + +// Exercise 3 +class RandRange +{ + public static void main(String... args) + { + System.out.println( + ThreadLocalRandom.current().nextInt(0, Integer.parseInt(args[0]))); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/TenHellos.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/TenHellos.java new file mode 100644 index 0000000..a517d39 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/TenHellos.java @@ -0,0 +1,10 @@ +package com.mycompany.app; + +public class TenHellos +{ + public static void main(String... args) + { + for (int i = 0; i < 10; ++i) + System.out.println("Hello, World!"); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/UseThree.java b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/UseThree.java new file mode 100644 index 0000000..a139fc8 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/UseThree.java @@ -0,0 +1,11 @@ +package com.mycompany.app; + +// Exercise 2 +class UseThree +{ + public static void main(String... args) + { + System.out.printf("Hi %s, %s and %s. How are you?\n", + args[2], args[1], args[0]); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/src/test/java/com/mycompany/app/AppTest.java b/usth/ICT2.2/labwork/2/my-app/src/test/java/com/mycompany/app/AppTest.java new file mode 100644 index 0000000..4291826 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/src/test/java/com/mycompany/app/AppTest.java @@ -0,0 +1,16 @@ +package com.mycompany.app; + +import static org.junit.Assert.assertTrue; + +import org.junit.Test; + +// Unit test for simple App. +public class AppTest +{ + // Rigorous Test :-) + @Test + public void shouldAnswerWithTrue() + { + assertTrue( true ); + } +} diff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/App.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/App.class new file mode 100644 index 0000000..740d561 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/App.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Beers.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Beers.class new file mode 100644 index 0000000..ff4573d --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Beers.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/IsLeapYear.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/IsLeapYear.class new file mode 100644 index 0000000..f8464c6 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/IsLeapYear.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Linear.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Linear.class new file mode 100644 index 0000000..6797c5e --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Linear.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/MeanSTD.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/MeanSTD.class new file mode 100644 index 0000000..8da82c5 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/MeanSTD.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Quadratic.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Quadratic.class new file mode 100644 index 0000000..15b1c7b --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/Quadratic.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/RandRange.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/RandRange.class new file mode 100644 index 0000000..9fe4ac3 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/RandRange.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/TenHellos.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/TenHellos.class new file mode 100644 index 0000000..ce0b894 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/TenHellos.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/UseThree.class b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/UseThree.class new file mode 100644 index 0000000..b66069e --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/classes/com/mycompany/app/UseThree.class Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/maven-archiver/pom.properties b/usth/ICT2.2/labwork/2/my-app/target/maven-archiver/pom.properties new file mode 100644 index 0000000..248310d --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/maven-archiver/pom.properties @@ -0,0 +1,4 @@ +#Created by Apache Maven 3.6.2 +groupId=com.mycompany.app +artifactId=my-app +version=1.0-SNAPSHOT diff --git a/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/compile/default-compile/createdFiles.lst b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/compile/default-compile/createdFiles.lst new file mode 100644 index 0000000..5a3a47c --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/compile/default-compile/createdFiles.lst @@ -0,0 +1,9 @@ +com/mycompany/app/App.class +com/mycompany/app/UseThree.class +com/mycompany/app/Linear.class +com/mycompany/app/TenHellos.class +com/mycompany/app/MeanSTD.class +com/mycompany/app/RandRange.class +com/mycompany/app/Beers.class +com/mycompany/app/IsLeapYear.class +com/mycompany/app/Quadratic.class diff --git a/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/compile/default-compile/inputFiles.lst b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/compile/default-compile/inputFiles.lst new file mode 100644 index 0000000..7c51ee3 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/compile/default-compile/inputFiles.lst @@ -0,0 +1,9 @@ +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Quadratic.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/IsLeapYear.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/App.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/RandRange.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Beers.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/Linear.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/TenHellos.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/MeanSTD.java +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/main/java/com/mycompany/app/UseThree.java diff --git a/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/testCompile/default-testCompile/createdFiles.lst b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/testCompile/default-testCompile/createdFiles.lst new file mode 100644 index 0000000..6348184 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/testCompile/default-testCompile/createdFiles.lst @@ -0,0 +1 @@ +com/mycompany/app/AppTest.class diff --git a/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/testCompile/default-testCompile/inputFiles.lst b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/testCompile/default-testCompile/inputFiles.lst new file mode 100644 index 0000000..543454e --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/maven-status/maven-compiler-plugin/testCompile/default-testCompile/inputFiles.lst @@ -0,0 +1 @@ +/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/src/test/java/com/mycompany/app/AppTest.java diff --git a/usth/ICT2.2/labwork/2/my-app/target/my-app-1.0-SNAPSHOT.jar b/usth/ICT2.2/labwork/2/my-app/target/my-app-1.0-SNAPSHOT.jar new file mode 100644 index 0000000..30b9fdc --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/my-app-1.0-SNAPSHOT.jar Binary files differdiff --git a/usth/ICT2.2/labwork/2/my-app/target/surefire-reports/TEST-com.mycompany.app.AppTest.xml b/usth/ICT2.2/labwork/2/my-app/target/surefire-reports/TEST-com.mycompany.app.AppTest.xml new file mode 100644 index 0000000..4041d13 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/surefire-reports/TEST-com.mycompany.app.AppTest.xml @@ -0,0 +1,60 @@ +<?xml version="1.0" encoding="UTF-8"?> +<testsuite xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="https://maven.apache.org/surefire/maven-surefire-plugin/xsd/surefire-test-report.xsd" name="com.mycompany.app.AppTest" time="0.019" tests="1" errors="0" skipped="0" failures="0"> + <properties> + <property name="awt.toolkit" value="sun.awt.X11.XToolkit"/> + <property name="java.specification.version" value="11"/> + <property name="sun.cpu.isalist" value=""/> + <property name="sun.jnu.encoding" value="UTF-8"/> + <property name="java.class.path" value="/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/test-classes:/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/classes:/home/cnx/.m2/repository/junit/junit/4.11/junit-4.11.jar:/home/cnx/.m2/repository/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar:"/> + <property name="java.vm.vendor" value="Debian"/> + <property name="sun.arch.data.model" value="64"/> + <property name="java.vendor.url" value="https://tracker.debian.org/openjdk-11"/> + <property name="user.timezone" value=""/> + <property name="java.vm.specification.version" value="11"/> + <property name="os.name" value="Linux"/> + <property name="sun.java.launcher" value="SUN_STANDARD"/> + <property name="user.country" value="US"/> + <property name="sun.boot.library.path" value="/usr/lib/jvm/java-11-openjdk-amd64/lib"/> + <property name="sun.java.command" value="/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/surefire/surefirebooter4171187558944627507.jar /home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/surefire 2019-10-09T17-47-23_851-jvmRun1 surefire1053437032396327338tmp surefire_014762799941833427558tmp"/> + <property name="jdk.debug" value="release"/> + <property name="surefire.test.class.path" value="/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/test-classes:/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/classes:/home/cnx/.m2/repository/junit/junit/4.11/junit-4.11.jar:/home/cnx/.m2/repository/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar:"/> + <property name="sun.cpu.endian" value="little"/> + <property name="user.home" value="/home/cnx"/> + <property name="user.language" value="en"/> + <property name="java.specification.vendor" value="Oracle Corporation"/> + <property name="java.version.date" value="2019-10-15"/> + <property name="java.home" value="/usr/lib/jvm/java-11-openjdk-amd64"/> + <property name="file.separator" value="/"/> + <property name="basedir" value="/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app"/> + <property name="java.vm.compressedOopsMode" value="32-bit"/> + <property name="line.separator" value=" "/> + <property name="java.specification.name" value="Java Platform API Specification"/> + <property name="java.vm.specification.vendor" value="Oracle Corporation"/> + <property name="java.awt.graphicsenv" value="sun.awt.X11GraphicsEnvironment"/> + <property name="surefire.real.class.path" value="/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app/target/surefire/surefirebooter4171187558944627507.jar"/> + <property name="sun.management.compiler" value="HotSpot 64-Bit Tiered Compilers"/> + <property name="java.runtime.version" value="11.0.5-ea+6-post-Debian-2"/> + <property name="user.name" value="cnx"/> + <property name="path.separator" value=":"/> + <property name="os.version" value="4.19.0-5-amd64"/> + <property name="java.runtime.name" value="OpenJDK Runtime Environment"/> + <property name="file.encoding" value="UTF-8"/> + <property name="java.vm.name" value="OpenJDK 64-Bit Server VM"/> + <property name="localRepository" value="/home/cnx/.m2/repository"/> + <property name="java.vendor.url.bug" value="https://bugs.debian.org/openjdk-11"/> + <property name="java.io.tmpdir" value="/tmp"/> + <property name="java.version" value="11.0.5-ea"/> + <property name="user.dir" value="/home/cnx/Documents/B2/ICT2.2/labwork/2/my-app"/> + <property name="os.arch" value="amd64"/> + <property name="java.vm.specification.name" value="Java Virtual Machine Specification"/> + <property name="java.awt.printerjob" value="sun.print.PSPrinterJob"/> + <property name="sun.os.patch.level" value="unknown"/> + <property name="java.library.path" value="/usr/java/packages/lib:/usr/lib/x86_64-linux-gnu/jni:/lib/x86_64-linux-gnu:/usr/lib/x86_64-linux-gnu:/usr/lib/jni:/lib:/usr/lib"/> + <property name="java.vendor" value="Debian"/> + <property name="java.vm.info" value="mixed mode, sharing"/> + <property name="java.vm.version" value="11.0.5-ea+6-post-Debian-2"/> + <property name="sun.io.unicode.encoding" value="UnicodeLittle"/> + <property name="java.class.version" value="55.0"/> + </properties> + <testcase name="shouldAnswerWithTrue" classname="com.mycompany.app.AppTest" time="0.001"/> +</testsuite> \ No newline at end of file diff --git a/usth/ICT2.2/labwork/2/my-app/target/surefire-reports/com.mycompany.app.AppTest.txt b/usth/ICT2.2/labwork/2/my-app/target/surefire-reports/com.mycompany.app.AppTest.txt new file mode 100644 index 0000000..1c0c529 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/surefire-reports/com.mycompany.app.AppTest.txt @@ -0,0 +1,4 @@ +------------------------------------------------------------------------------- +Test set: com.mycompany.app.AppTest +------------------------------------------------------------------------------- +Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.019 s - in com.mycompany.app.AppTest diff --git a/usth/ICT2.2/labwork/2/my-app/target/test-classes/com/mycompany/app/AppTest.class b/usth/ICT2.2/labwork/2/my-app/target/test-classes/com/mycompany/app/AppTest.class new file mode 100644 index 0000000..88a6c58 --- /dev/null +++ b/usth/ICT2.2/labwork/2/my-app/target/test-classes/com/mycompany/app/AppTest.class Binary files differdiff --git a/usth/ICT2.2/labwork/3/3_labwork3.pdf b/usth/ICT2.2/labwork/3/3_labwork3.pdf new file mode 100644 index 0000000..0c9c533 --- /dev/null +++ b/usth/ICT2.2/labwork/3/3_labwork3.pdf Binary files differdiff --git a/usth/ICT2.2/labwork/3/C++/README.md b/usth/ICT2.2/labwork/3/C++/README.md new file mode 100644 index 0000000..8cd208f --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/README.md @@ -0,0 +1,10 @@ +# Labwork 3: Implementations in C++ + +At this point I've come to realized that like Thanos, C++ is inevitable. +Despite my disgust toward the language (TBH I don't like Java any better), +I need to know it enough, at least at the read-only level. + +Compilation of tests could be done as follows (on Unix-like system of course, +since poor Windows users don't even have a standard C/C++ compiler): + + c++ <classname>*.cc diff --git a/usth/ICT2.2/labwork/3/C++/automobile.cc b/usth/ICT2.2/labwork/3/C++/automobile.cc new file mode 100644 index 0000000..d274a60 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/automobile.cc @@ -0,0 +1,56 @@ +#include <regex> +#include <stdexcept> +#include <string> + +#include "automobile.h" + +using namespace std; + +const regex license_pattern ("[0-9A-Z]+"); + +void +Automobile::set_license (string s) +{ + smatch m; + if (!regex_match (s, m, license_pattern)) + throw invalid_argument{"invalid license plate"}; + license = s; +} + +void +Automobile::set_fuel (double x) +{ + if (x < 0) + throw invalid_argument{"negative fuel"}; + fuel = x; +} + +void +Automobile::set_speed (double x) +{ + speed = (x < 0) ? 0 : x; +} + +Automobile::Automobile (string l, double f, double s) +{ + set_license (l); + set_fuel (f); + set_speed (s); +} + +void +Automobile::accelerate (double v) +{ + if (v < 0) + throw invalid_argument{"negative acceleration"}; + if (fuel) + set_speed (speed + v); +} + +void +Automobile::decelerate (double v) +{ + if (v < 0) + throw invalid_argument{"negative deceleration"}; + set_speed (speed - v); +} diff --git a/usth/ICT2.2/labwork/3/C++/automobile.h b/usth/ICT2.2/labwork/3/C++/automobile.h new file mode 100644 index 0000000..0e65865 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/automobile.h @@ -0,0 +1,20 @@ +#include <string> + +using namespace std; + +class Automobile +{ + double fuel; + double speed; + string license; +public: + Automobile (string, double, double); + string get_license () { return license; } + double get_fuel () { return fuel; } + double get_speed () { return speed; } + void set_license (string); + void set_fuel (double); + void set_speed (double); + void accelerate (double); + void decelerate (double); +}; diff --git a/usth/ICT2.2/labwork/3/C++/button-test.cc b/usth/ICT2.2/labwork/3/C++/button-test.cc new file mode 100644 index 0000000..7164b2f --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/button-test.cc @@ -0,0 +1,14 @@ +#include <iostream> + +#include "button.h" + +using namespace std; + +int +main () +{ + Button butt ("foo", "bar"); + butt.depress (); + butt.undepress (); + cout << "button " << butt.label << " color " << butt.color << endl; +} diff --git a/usth/ICT2.2/labwork/3/C++/button.h b/usth/ICT2.2/labwork/3/C++/button.h new file mode 100644 index 0000000..92fa685 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/button.h @@ -0,0 +1,14 @@ +#include <string> + +using namespace std; + +class Button +{ + bool state; +public: + string label; + string color; + Button (string l, string c) : label {l}, color {c}, state {false} {} + void depress () { state = true; } + void undepress () { state = false; } +}; diff --git a/usth/ICT2.2/labwork/3/C++/cow-test.cc b/usth/ICT2.2/labwork/3/C++/cow-test.cc new file mode 100644 index 0000000..ea7b86d --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/cow-test.cc @@ -0,0 +1,9 @@ +#include "cow.h" + +int +main () +{ + Cow cow ("foo", "bar", 7); + cow.age = -4; // some casting happens here + cow.moo (); +} diff --git a/usth/ICT2.2/labwork/3/C++/cow.cc b/usth/ICT2.2/labwork/3/C++/cow.cc new file mode 100644 index 0000000..84fabc8 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/cow.cc @@ -0,0 +1,11 @@ +#include <iostream> + +#include "cow.h" + +using namespace std; + +void +Cow::moo () +{ + cout << "Moo...!" << endl; +} diff --git a/usth/ICT2.2/labwork/3/C++/cow.h b/usth/ICT2.2/labwork/3/C++/cow.h new file mode 100644 index 0000000..df7ffd9 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/cow.h @@ -0,0 +1,17 @@ +#include <string> + +using namespace std; + +class Cow +{ + // The reason these have private access + // is that their no way a cow's name and breed can be changed. + string name; + string breed; +public: + unsigned age; + + Cow (string n, string b, unsigned a) : name {n}, breed {b}, age {a} {} + Cow (string n, string b) : name {n}, breed {b}, age {0} {} + void moo (); +}; diff --git a/usth/ICT2.2/labwork/3/C++/name-card-test.cc b/usth/ICT2.2/labwork/3/C++/name-card-test.cc new file mode 100644 index 0000000..b459d0d --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/name-card-test.cc @@ -0,0 +1,14 @@ +#include <iostream> + +#include "name-card.h" + +using namespace std; + +int +main () +{ + NameCard card ("Foobar Baz", "420-69", "foo@bar.baz"); + cout << "Name: " << card.get_name () << endl + << "Phone: " << card.get_phone () << endl + << "Email: " << card.get_email () << endl; +} diff --git a/usth/ICT2.2/labwork/3/C++/name-card.cc b/usth/ICT2.2/labwork/3/C++/name-card.cc new file mode 100644 index 0000000..b6c0751 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/name-card.cc @@ -0,0 +1,47 @@ +#include <regex> +#include <stdexcept> +#include <string> + +#include "name-card.h" + +using namespace std; + +const regex name_pattern ("[ A-Za-z]+"); +const regex phone_pattern ("[-0-9]+"); +// This should be good enough I guess? +const regex email_pattern ("(\\w+)(\\.|_)?(\\w*)@(\\w+)(\\.(\\w+))+"); + +void +NameCard::set_name (string s) +{ + // I miss Raku so much + smatch m; + if (!regex_match (s, m, name_pattern)) + throw invalid_argument{"invalid name"}; + name = s; +} + +void +NameCard::set_phone (string s) +{ + smatch m; + if (!regex_match (s, m, phone_pattern)) + throw invalid_argument{"invalid number"}; + phone = s; +} + +void +NameCard::set_email (string s) +{ + smatch m; + if (!regex_match (s, m, email_pattern)) + throw invalid_argument{"invalid name"}; + email = s; +} + +NameCard::NameCard (string n, string p, string e) +{ + set_name (n); + set_phone (p); + set_email (e); +} diff --git a/usth/ICT2.2/labwork/3/C++/name-card.h b/usth/ICT2.2/labwork/3/C++/name-card.h new file mode 100644 index 0000000..08e76a7 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/name-card.h @@ -0,0 +1,18 @@ +#include <string> + +using namespace std; + +class NameCard +{ + string name; + string phone; + string email; +public: + string get_name () { return name; } + string get_phone () { return phone; } + string get_email () { return email; } + void set_name (string); + void set_phone (string); + void set_email (string); + NameCard (string, string, string); +}; diff --git a/usth/ICT2.2/labwork/3/C++/shopping-cart-test.cc b/usth/ICT2.2/labwork/3/C++/shopping-cart-test.cc new file mode 100644 index 0000000..4833e70 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/shopping-cart-test.cc @@ -0,0 +1,19 @@ +#include <iostream> + +#include "shopping-cart.h" + +using namespace std; + +int +main () +{ + ShoppingCart cart; + cart.add_to_cart ("foo"); + cart.add_to_cart ("foo"); + cart.add_to_cart ("bar"); + cart.remove_from_cart ("baz"); + cout << cart.count ("foo") << ' ' + << cart.count ("bar") << ' ' + << cart.count ("baz") << endl; + cart.check_out (); +} diff --git a/usth/ICT2.2/labwork/3/C++/shopping-cart.h b/usth/ICT2.2/labwork/3/C++/shopping-cart.h new file mode 100644 index 0000000..c1450e7 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/shopping-cart.h @@ -0,0 +1,16 @@ +#include <string> +#include <unordered_map> + +using namespace std; + +class ShoppingCart +{ + // quite of an improvement over the Java version + unordered_map<string, int> contents; +public: + void add_to_cart (string item) { contents[item]++; } + void remove_from_cart (string item) { contents[item] = 0; } + // to make this class useful anyhow + int count (string item) { return contents[item]; } + void check_out () { contents.clear (); } +}; diff --git a/usth/ICT2.2/labwork/3/C++/vector-test.cc b/usth/ICT2.2/labwork/3/C++/vector-test.cc new file mode 100644 index 0000000..647c8a6 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/vector-test.cc @@ -0,0 +1,20 @@ +#include <iostream> + +#include "vector.h" + +using namespace std; + +int +main () +{ + Vector u (4, 20); + Vector v (6, 9); + cout << "u = (" << u.x << ", " << u.y << ")" << endl; + cout << "v = (" << v.x << ", " << v.y << ")" << endl; + Vector w {u + v}; + cout << "u + v = (" << w.x << ", " << w.y << ")" << endl; + w = u - v; + cout << "u - v = (" << w.x << ", " << w.y << ")" << endl; + w = u * v; + cout << "u * v = (" << w.x << ", " << w.y << ")" << endl; +} diff --git a/usth/ICT2.2/labwork/3/C++/vector.cc b/usth/ICT2.2/labwork/3/C++/vector.cc new file mode 100644 index 0000000..5ac56de --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/vector.cc @@ -0,0 +1,19 @@ +#include "vector.h" + +Vector +operator+ (Vector u, Vector v) +{ + return u += v; +} + +Vector +operator- (Vector u, Vector v) +{ + return u -= v; +} + +Vector +operator* (Vector u, Vector v) +{ + return u *= v; +} diff --git a/usth/ICT2.2/labwork/3/C++/vector.h b/usth/ICT2.2/labwork/3/C++/vector.h new file mode 100644 index 0000000..8433e79 --- /dev/null +++ b/usth/ICT2.2/labwork/3/C++/vector.h @@ -0,0 +1,17 @@ +class Vector +{ +public: + int x; + int y; + + Vector (int ex, int why) : x {ex}, y {why} {} + Vector () : x {0}, y{0} {} + + Vector& operator+= (Vector v) { x += v.x, y += v.y; return *this; } + Vector& operator-= (Vector v) { x -= v.x, y -= v.y; return *this; } + Vector& operator*= (Vector v) { x *= v.x, y *= v.y; return *this; } +}; + +Vector operator+ (Vector, Vector); +Vector operator- (Vector, Vector); +Vector operator* (Vector, Vector); diff --git a/usth/ICT2.2/labwork/3/Java/Automobile.java b/usth/ICT2.2/labwork/3/Java/Automobile.java new file mode 100644 index 0000000..14a82ef --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/Automobile.java @@ -0,0 +1,68 @@ +import java.util.regex.Pattern; + +class Automobile +{ + private static final Pattern licensePattern = Pattern.compile("[0-9A-Z]+"); + private double fuel; + private double speed; + private String license; + + public double getFuel() + { + return fuel; + } + + public double getSpeed() + { + return speed; + } + + public String getLicense() + { + return license; + } + + public void setFuel(double fuel) + { + if (fuel < 0) + throw new IllegalArgumentException( + "fuel must be nonnegative, instead got " + fuel); + this.fuel = fuel; + } + + public void setSpeed(double speed) + { + this.speed = Math.max(0, speed); + } + + public void setLicense(String license) + { + if (!licensePattern.matcher(license).matches()) + throw new IllegalArgumentException("invalid license: " + license); + this.license = license; + } + + public Automobile(double f, double s, String l) + { + setFuel(f); + setSpeed(s); + setLicense(l); + } + + public void accelerate(double v) + { + if (v < 0) + throw new IllegalArgumentException( + "acceleration must be nonnegative, instead got " + v); + if (fuel > 0) + setSpeed(speed + v); + } + + public void decelerate(double v) + { + if (v < 0) + throw new IllegalArgumentException( + "deceleration must be nonnegative, instead got " + v); + setSpeed(speed - v); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/Button.java b/usth/ICT2.2/labwork/3/Java/Button.java new file mode 100644 index 0000000..8a26b3f --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/Button.java @@ -0,0 +1,50 @@ +public class Button +{ + private String label; + private String color; + private boolean state; + + public Button(String label, String color) + { + this.label = label; + this.color = color; + this.state = false; + } + + public String toString() + { + return String.format("<button %s with color %s and state %s>", + label, color, state); + } + + // To be honest these getters and setters are really redundant in this case + public String getLabel() + { + return label; + } + + public String getColor() + { + return color; + } + + public void setLabel(String label) + { + this.label = label; + } + + public void setColor(String color) + { + this.color = color; + } + + public void dePress() + { + this.state = true; + } + + public void unDepress() + { + this.state = false; + } +} diff --git a/usth/ICT2.2/labwork/3/Java/ButtonTest.java b/usth/ICT2.2/labwork/3/Java/ButtonTest.java new file mode 100644 index 0000000..51dd4d2 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/ButtonTest.java @@ -0,0 +1,12 @@ +class ButtonTest +{ + public static void main(String... args) + { + Button button = new Button("foo", "bar"); + System.out.println(button); + button.setLabel("fu"); + button.setColor("baz"); + button.dePress(); + System.out.println(button); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/Cow.java b/usth/ICT2.2/labwork/3/Java/Cow.java new file mode 100644 index 0000000..36a1051 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/Cow.java @@ -0,0 +1,36 @@ +public class Cow +{ + private String name; + private String breed; + private int age; + + public Cow(String name, String breed) + { + this(name, breed, 0); + } + + public Cow(String name, String breed, int age) + { + this.name = name; + this.breed = breed; + setAge(age); + } + + public static void moo() + { + System.out.println("Moo...!"); + } + + public int getAge() + { + return age; + } + + public void setAge(int age) + { + if (age < 0) + throw new IllegalArgumentException( + "age must be nonnegative, instead got " + age); + this.age = age; + } +} diff --git a/usth/ICT2.2/labwork/3/Java/CowTest.java b/usth/ICT2.2/labwork/3/Java/CowTest.java new file mode 100644 index 0000000..1a13f67 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/CowTest.java @@ -0,0 +1,9 @@ +class CowTest // there's no reason to import a test what-so-ever +{ + public static void main(String... args) + { + Cow cow = new Cow("foo", "bar", 7); + cow.setAge(-4); + cow.moo(); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/NameCard.java b/usth/ICT2.2/labwork/3/Java/NameCard.java new file mode 100644 index 0000000..165d5f9 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/NameCard.java @@ -0,0 +1,67 @@ +import java.util.regex.Pattern; + +public class NameCard +{ + private static final Pattern namePattern = Pattern.compile("[ A-Za-z]+"); + private static final Pattern phonePattern = Pattern.compile("[-0-9]*"); + // I have not learnt regex properly + private static final Pattern emailPattern = Pattern.compile( + "(\\w+)(\\.|_)?(\\w*)@(\\w+)(\\.(\\w+))+"); + + private String name; + private String phone; + private String email; + + public String getName() + { + return name; + } + + public String getPhone() + { + return phone; + } + + public String getEmail() + { + return email; + } + + public void setName(String name) + { + if (!namePattern.matcher(name).matches()) + throw new IllegalArgumentException("invalid name: " + name); + this.name = name; + } + + public void setPhone(String phone) + { + if (!phonePattern.matcher(phone).matches()) + throw new IllegalArgumentException("invalid phone number: " + phone); + this.phone = phone; + } + + public void setEmail(String email) + { + if (!emailPattern.matcher(email).matches()) + throw new IllegalArgumentException("invalid email: " + email); + this.email = email; + } + + public NameCard(String name) + { + this(name, "", ""); + } + + public NameCard(String name, String phone) + { + this(name, phone, ""); + } + + public NameCard(String name, String phone, String email) + { + setName(name); + setPhone(phone); + setEmail(email); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/NameCardTest.java b/usth/ICT2.2/labwork/3/Java/NameCardTest.java new file mode 100644 index 0000000..ed66343 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/NameCardTest.java @@ -0,0 +1,9 @@ +class NameCardTest +{ + public static void main(String... args) + { + NameCard card = new NameCard("Foobar Baz", "420-69", "foo@bar.baz"); + System.out.printf("Name: %s\nPhone: %s\nEmail: %s\n", + card.getName(), card.getPhone(), card.getEmail()); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/README.md b/usth/ICT2.2/labwork/3/Java/README.md new file mode 100644 index 0000000..f0c494a --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/README.md @@ -0,0 +1,10 @@ +# Labwork 3: Implementations in Java + +For the ease of typing, the test files are named `<classname>Test.java` +instead of `<classname>TestDrive.java`. +To rename them to the original requirement, use Perl `rename` and GNU `sed` + +```sh +rename s/Test/TestDrive/ *Test.java +sed -i s/Test/TestDrive/ *TestDrive.java +``` diff --git a/usth/ICT2.2/labwork/3/Java/ShoppingCart.java b/usth/ICT2.2/labwork/3/Java/ShoppingCart.java new file mode 100644 index 0000000..f5e23ad --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/ShoppingCart.java @@ -0,0 +1,27 @@ +import java.util.ArrayList; +import java.util.List; + +public class ShoppingCart +{ + private List<String> cartContents = new ArrayList<String>(); + + public boolean addToCart(String content) + { + return cartContents.add(content); + } + + public boolean removeFromCart(String content) + { + return cartContents.remove(content); + } + + public void checkOut() + { + cartContents.clear(); + } + + public String toString() + { + return "Cart content(s): " + String.join(", ", cartContents); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/ShoppingCartTest.java b/usth/ICT2.2/labwork/3/Java/ShoppingCartTest.java new file mode 100644 index 0000000..315f9f4 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/ShoppingCartTest.java @@ -0,0 +1,16 @@ +class ShoppingCartTest +{ + public static void main(String... args) + { + ShoppingCart cart = new ShoppingCart(); + System.out.println(cart); + cart.addToCart("foo"); + cart.addToCart("bar"); + cart.addToCart("baz"); + System.out.println(cart); + cart.removeFromCart("bar"); + System.out.println(cart); + cart.checkOut(); + System.out.println(cart); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/Vector.java b/usth/ICT2.2/labwork/3/Java/Vector.java new file mode 100644 index 0000000..3fc9137 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/Vector.java @@ -0,0 +1,39 @@ +public class Vector +{ + // There's nothing to validate + public int x; + public int y; + + public Vector() + { + this(0, 0); + } + + public Vector(int x, int y) + { + this.x = x; + this.y = y; + } + + public String toString() + { + // I feel bad writing this + return "(" + x + ", " + y + ")"; + } + + public Vector add(Vector other) + { + return new Vector(this.x + other.x, this.y + other.y); + } + + public Vector subtract(Vector other) + { + return new Vector(this.x - other.x, this.y - other.y); + } + + public Vector multiply(Vector other) + { + // instruction unclear, applying element-wise multiplication + return new Vector(this.x * other.x, this.y * other.y); + } +} diff --git a/usth/ICT2.2/labwork/3/Java/VectorTest.java b/usth/ICT2.2/labwork/3/Java/VectorTest.java new file mode 100644 index 0000000..4f0a4a3 --- /dev/null +++ b/usth/ICT2.2/labwork/3/Java/VectorTest.java @@ -0,0 +1,10 @@ +class VectorTest +{ + public static void main(String... args) + { + Vector u = new Vector(4, 20); + Vector v = new Vector(6, 9); + System.out.printf("u = %s\nv = %s\nu + v = %s\nu - v = %s\nu * v = %s\n", + u, v, u.add(v), u.subtract(v), u.multiply(v)); + } +} diff --git a/usth/ICT2.2/labwork/4/4_labwork4.pdf b/usth/ICT2.2/labwork/4/4_labwork4.pdf new file mode 100644 index 0000000..4a4de56 --- /dev/null +++ b/usth/ICT2.2/labwork/4/4_labwork4.pdf Binary files differdiff --git a/usth/ICT2.2/labwork/4/BubbleSort.java b/usth/ICT2.2/labwork/4/BubbleSort.java new file mode 100644 index 0000000..8557c64 --- /dev/null +++ b/usth/ICT2.2/labwork/4/BubbleSort.java @@ -0,0 +1,21 @@ +import java.util.ArrayList; +import java.util.Scanner; + +import static java.util.Collections.swap; + +class Stats +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + int n = scanner.nextInt(); + var numbers = new ArrayList<Double>(); + for (int i = 0; i < n; ++i) + numbers.add(scanner.nextDouble()); + for (int m = 0; n > 1; n = m, m = 0) + for (int i = 1; i < n; ++i) + if (numbers.get(i).compareTo(numbers.get(i - 1)) < 0) + swap(numbers, m = i, i - 1); + System.out.println(numbers); + } +} diff --git a/usth/ICT2.2/labwork/4/Centroid.java b/usth/ICT2.2/labwork/4/Centroid.java new file mode 100644 index 0000000..7862cbb --- /dev/null +++ b/usth/ICT2.2/labwork/4/Centroid.java @@ -0,0 +1,26 @@ +import java.util.Scanner; + +class Centriod +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + double m = 0.0, x = 0.0, y = 0.0; + + while (scanner.hasNextDouble()) + { + double n = scanner.nextDouble(); + if (!scanner.hasNextDouble()) + break; + double s = scanner.nextDouble(); + if (!scanner.hasNextDouble()) + break; + double i = scanner.nextDouble(); + + m += n; + x += n * s; + y += n * i; + } + System.out.println(m + " " + x/m + " " + y/m); + } +} diff --git a/usth/ICT2.2/labwork/4/Closest.java b/usth/ICT2.2/labwork/4/Closest.java new file mode 100644 index 0000000..2f1e45d --- /dev/null +++ b/usth/ICT2.2/labwork/4/Closest.java @@ -0,0 +1,45 @@ +import java.util.Scanner; + +class Closest +{ + private static double x, y, z; + + private static double dist(double a, double b, double c) + { + double g = x - a; + double h = y - b; + double i = z - c; + return g*g + h*h + i*i; + } + + public static void main(String... args) + { + var scanner = new Scanner(System.in); + Double length = null; + double a = 0.0, b = 0.0, c = 0.0; + + x = Double.parseDouble(args[0]); + y = Double.parseDouble(args[1]); + z = Double.parseDouble(args[2]); + while (scanner.hasNextDouble()) + { + double d = scanner.nextDouble(); + if (!scanner.hasNextDouble()) + break; + double e = scanner.nextDouble(); + if (!scanner.hasNextDouble()) + break; + double f = scanner.nextDouble(); + double len = dist(d, e, f); + + if (length == null || len < length) + { + length = len; + a = d; + b = e; + c = f; + } + } + System.out.println(a + " " + b + " " + c); + } +} diff --git a/usth/ICT2.2/labwork/4/Deal.java b/usth/ICT2.2/labwork/4/Deal.java new file mode 100644 index 0000000..b2d9ba9 --- /dev/null +++ b/usth/ICT2.2/labwork/4/Deal.java @@ -0,0 +1,27 @@ +import static java.util.Collections.shuffle; +import static java.util.stream.Collectors.toList; +import static java.util.stream.IntStream.range; + +class Deal +{ + static final String[] suits = {"clubs", "diamonds", "hearts", "spades"}; + static final String[] ranks = {"Ace", "Two", "Three", "Four", "Five", + "Six", "Seven", "Eight", "Nine", "Ten", + "Jack", "Queen", "King"}; + + public static void main(String... args) + { + var deck = range(0, 52).boxed().collect(toList()); + shuffle(deck); + + // I have no time handling exceptions. + int n = Integer.parseInt(args[0]) % 52; + while (n-- > 0) + { + int card = deck.get(n); + int suit = card / 13; + int rank = card % 13; + System.out.printf("%s of %s\n", ranks[rank], suits[suit]); + } + } +} diff --git a/usth/ICT2.2/labwork/4/DiscreteDistro.java b/usth/ICT2.2/labwork/4/DiscreteDistro.java new file mode 100644 index 0000000..b603ed7 --- /dev/null +++ b/usth/ICT2.2/labwork/4/DiscreteDistro.java @@ -0,0 +1,23 @@ +import java.util.concurrent.ThreadLocalRandom; +import java.util.stream.Stream; + +import static java.util.Collections.binarySearch; +import static java.util.stream.Collectors.toList; + +class DiscreteDistro +{ + public static void main(String... args) + { + var numbers = Stream.of(args).mapToInt(Integer::parseInt) + .boxed().collect(toList()); + int n = numbers.size(); + for (int i = 1; i < n; ++i) + numbers.set(i, numbers.get(i) + numbers.get(i - 1)); + + int x = ThreadLocalRandom.current().nextInt(0, numbers.get(n - 1)); + int i = binarySearch(numbers, x) + 1; + System.out.println(numbers); + System.out.println(x); + System.out.println((i < 0) ? -i : i); + } +} diff --git a/usth/ICT2.2/labwork/4/Employ.java b/usth/ICT2.2/labwork/4/Employ.java new file mode 100644 index 0000000..924e1d3 --- /dev/null +++ b/usth/ICT2.2/labwork/4/Employ.java @@ -0,0 +1,30 @@ +import java.io.File; +import java.io.FileNotFoundException; +import java.util.ArrayList; +import java.util.Scanner; + +class Employ +{ + private static Employee scan(Scanner s) + { + int ID = s.nextInt(); + s.nextLine(); + return new Employee(ID, s.nextLine(), s.nextLine(), + s.nextDouble(), s.nextDouble()); + } + + public static void main(String... args) throws FileNotFoundException + { + var stdin = new Scanner(System.in); + var f = new File("employees.txt"); + var file = new Scanner(f); + var employees = new ArrayList<Employee>(); + int n = stdin.nextInt(); + for (int i = 0; i < n; ++i) + { + employees.add(scan(stdin)); + employees.add(scan(file)); + } + employees.forEach(System.out::println); + } +} diff --git a/usth/ICT2.2/labwork/4/Employee.class b/usth/ICT2.2/labwork/4/Employee.class new file mode 100644 index 0000000..3176b0c --- /dev/null +++ b/usth/ICT2.2/labwork/4/Employee.class Binary files differdiff --git a/usth/ICT2.2/labwork/4/Employee.java b/usth/ICT2.2/labwork/4/Employee.java new file mode 100644 index 0000000..51647b5 --- /dev/null +++ b/usth/ICT2.2/labwork/4/Employee.java @@ -0,0 +1,27 @@ +public class Employee +{ + private int ID; + private String name; + private String dep; + private double basic; + private double extra; + + public Employee(int ID, String name, String dep, double basic, double extra) + { + this.ID = ID; + this.name = name; + this.dep = dep; + this.basic = basic; + this.extra = extra; + } + + public int getID() { return ID; } + public String getName() { return name; } + public String getDep() { return dep; } + public double getIncome() { return basic + extra*2.5; } + + public String toString() + { + return String.format("#%d %s [%s]: %g", ID, name, dep, getIncome()); + } +} diff --git a/usth/ICT2.2/labwork/4/HowMany.java b/usth/ICT2.2/labwork/4/HowMany.java new file mode 100644 index 0000000..16c07bd --- /dev/null +++ b/usth/ICT2.2/labwork/4/HowMany.java @@ -0,0 +1,7 @@ +class HowMany +{ + public static void main(String... args) + { + System.out.println(args.length); + } +} diff --git a/usth/ICT2.2/labwork/4/LongestRun.java b/usth/ICT2.2/labwork/4/LongestRun.java new file mode 100644 index 0000000..74c18c7 --- /dev/null +++ b/usth/ICT2.2/labwork/4/LongestRun.java @@ -0,0 +1,30 @@ +import java.util.Scanner; + +class LongestRun +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + Integer number = null; + Integer length = null; + Integer n = null, len = null; + + while (scanner.hasNextInt()) + { + Integer i = scanner.nextInt(); + if (i == n) + { + len++; + continue; + } + if (length == null || len > length) + { + number = n; + length = len; + } + n = i; + len = 1; + } + System.out.printf("Longest run: %d consecutive %d\n", number, length); + } +} diff --git a/usth/ICT2.2/labwork/4/MaxMin.java b/usth/ICT2.2/labwork/4/MaxMin.java new file mode 100644 index 0000000..d34c01f --- /dev/null +++ b/usth/ICT2.2/labwork/4/MaxMin.java @@ -0,0 +1,18 @@ +import java.util.ArrayList; +import java.util.Scanner; + +import static java.util.Collections.min; +import static java.util.Collections.max; +import static java.util.stream.Collectors.toList; + +class MaxMin +{ + public static void main(String... args) + { + var numbers = new ArrayList<Integer>(); + var scanner = new Scanner(System.in); + while (scanner.hasNextInt()) + numbers.add(scanner.nextInt()); + System.out.printf("Min: %d\nMax: %d\n", min(numbers), max(numbers)); + } +} diff --git a/usth/ICT2.2/labwork/4/Stats.java b/usth/ICT2.2/labwork/4/Stats.java new file mode 100644 index 0000000..88d6832 --- /dev/null +++ b/usth/ICT2.2/labwork/4/Stats.java @@ -0,0 +1,19 @@ +import java.util.ArrayList; +import java.util.Scanner; + +class Stats +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + int n = scanner.nextInt(); + var numbers = new ArrayList<Double>(); + for (int i = 0; i < n; ++i) + numbers.add(scanner.nextDouble()); + + double m = numbers.stream().mapToDouble(Double::doubleValue).sum() / n; + double s = Math.sqrt(numbers.stream() + .mapToDouble(x -> Math.pow(x - m, 2)).sum() / n); + System.out.printf("Mean: %f\nStandard deviation: %f\n", m, s); + } +} diff --git a/usth/ICT2.2/labwork/4/Transpose.java b/usth/ICT2.2/labwork/4/Transpose.java new file mode 100644 index 0000000..597a783 --- /dev/null +++ b/usth/ICT2.2/labwork/4/Transpose.java @@ -0,0 +1,24 @@ +class Transpose +{ + public static void main(String... args) + { + int[][] m = {{7, 8, 9}, + {4, 5, 6}, + {1, 2, 3}}; + int n = 3; // some sort of abstraction + System.out.println("Original matrix:"); + for (int i = 0; i < n; ++i) + System.out.printf("%d %d %d\n", m[i][0], m[i][1], m[i][2]); + + for (int i = 1; i < n; ++i) + for (int j = 0; j < i; ++j) + { + m[i][j] ^= m[j][i]; + m[j][i] ^= m[i][j]; + m[i][j] ^= m[j][i]; + } + System.out.println("Transposed matrix:"); + for (int i = 0; i < n; ++i) + System.out.printf("%d %d %d\n", m[i][0], m[i][1], m[i][2]); + } +} diff --git a/usth/ICT2.2/labwork/4/WordCount.java b/usth/ICT2.2/labwork/4/WordCount.java new file mode 100644 index 0000000..4d0bfc6 --- /dev/null +++ b/usth/ICT2.2/labwork/4/WordCount.java @@ -0,0 +1,16 @@ +import java.util.Scanner; + +class WordCount +{ + public static void main(String... args) + { + var scanner = new Scanner(System.in); + int count = 0; + while (scanner.hasNext()) + { + scanner.next(); + count++; + } + System.out.println(count); + } +} diff --git a/usth/ICT2.2/labwork/4/employees.txt b/usth/ICT2.2/labwork/4/employees.txt new file mode 100644 index 0000000..7dc4e8f --- /dev/null +++ b/usth/ICT2.2/labwork/4/employees.txt @@ -0,0 +1,8 @@ +7 +Foo Bar +lmao +420 69 +3 +Baz Bac +lol +1 4 diff --git a/usth/ICT2.2/labwork/5/Java/abstract/Circle.java b/usth/ICT2.2/labwork/5/Java/abstract/Circle.java new file mode 100644 index 0000000..3ee8c84 --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/abstract/Circle.java @@ -0,0 +1,13 @@ +public class Circle extends Point +{ + public double r; + + public Circle(double x, double y, double r) + { + super(x, y); + this.r = r; + } + + public double calArea() { return r * r * Math.PI; } + public String getName() { return "Circle"; } +} diff --git a/usth/ICT2.2/labwork/5/Java/abstract/Cylinder.java b/usth/ICT2.2/labwork/5/Java/abstract/Cylinder.java new file mode 100644 index 0000000..8fa9e0c --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/abstract/Cylinder.java @@ -0,0 +1,14 @@ +public class Cylinder extends Circle +{ + public double h; + + public Cylinder(double x, double y, double r, double h) + { + super(x, y, r); + this.h = h; + } + + public double calArea() { return super.calArea()*2.0 + r*h*Math.PI*2.0; } + public double calVolume() { return super.calArea() * h; } + public String getName() { return "Circle"; } +} diff --git a/usth/ICT2.2/labwork/5/Java/abstract/Point.java b/usth/ICT2.2/labwork/5/Java/abstract/Point.java new file mode 100644 index 0000000..f6daf22 --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/abstract/Point.java @@ -0,0 +1,13 @@ +public class Point extends Shape +{ + public double x; + public double y; + + public Point(double x, double y) + { + this.x = x; + this.y = y; + } + + public String getName() { return "Point"; } +} diff --git a/usth/ICT2.2/labwork/5/Java/abstract/Shape.java b/usth/ICT2.2/labwork/5/Java/abstract/Shape.java new file mode 100644 index 0000000..dd4124c --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/abstract/Shape.java @@ -0,0 +1,12 @@ +public abstract class Shape +{ + public double calArea() { return 0.0; } + public double calVolume() { return 0.0; } + public abstract String getName(); + + public String toString() + { + return String.format("%s of area %g and volume %g", + getName(), calArea(), calVolume()); + } +} diff --git a/usth/ICT2.2/labwork/5/Java/abstract/Test.java b/usth/ICT2.2/labwork/5/Java/abstract/Test.java new file mode 100644 index 0000000..b0502f0 --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/abstract/Test.java @@ -0,0 +1,11 @@ +import static java.util.Arrays.asList; + +class Test +{ + public static void main(String... args) + { + var array = asList(new Point(1.0, 2.0), new Circle(3.0, 4.0, 5.0), + new Cylinder(6.0, 7.0, 8.0, 9.0)); + array.forEach(System.out::println); + } +} diff --git a/usth/ICT2.2/labwork/5/Java/interface/Circle.java b/usth/ICT2.2/labwork/5/Java/interface/Circle.java new file mode 100644 index 0000000..3ee8c84 --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/interface/Circle.java @@ -0,0 +1,13 @@ +public class Circle extends Point +{ + public double r; + + public Circle(double x, double y, double r) + { + super(x, y); + this.r = r; + } + + public double calArea() { return r * r * Math.PI; } + public String getName() { return "Circle"; } +} diff --git a/usth/ICT2.2/labwork/5/Java/interface/Cylinder.java b/usth/ICT2.2/labwork/5/Java/interface/Cylinder.java new file mode 100644 index 0000000..8fa9e0c --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/interface/Cylinder.java @@ -0,0 +1,14 @@ +public class Cylinder extends Circle +{ + public double h; + + public Cylinder(double x, double y, double r, double h) + { + super(x, y, r); + this.h = h; + } + + public double calArea() { return super.calArea()*2.0 + r*h*Math.PI*2.0; } + public double calVolume() { return super.calArea() * h; } + public String getName() { return "Circle"; } +} diff --git a/usth/ICT2.2/labwork/5/Java/interface/Point.java b/usth/ICT2.2/labwork/5/Java/interface/Point.java new file mode 100644 index 0000000..90b2569 --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/interface/Point.java @@ -0,0 +1,21 @@ +public class Point implements Shape +{ + public double x; + public double y; + + public Point(double x, double y) + { + this.x = x; + this.y = y; + } + + public double calArea() { return 0.0; } + public double calVolume() { return 0.0; } + public String getName() { return "Point"; } + + public String toString() + { + return String.format("%s of area %g and volume %g", + getName(), calArea(), calVolume()); + } +} diff --git a/usth/ICT2.2/labwork/5/Java/interface/Shape.java b/usth/ICT2.2/labwork/5/Java/interface/Shape.java new file mode 100644 index 0000000..1eb33fa --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/interface/Shape.java @@ -0,0 +1,6 @@ +interface Shape +{ + public double calArea(); + public double calVolume(); + public String getName(); +} diff --git a/usth/ICT2.2/labwork/5/Java/interface/Test.java b/usth/ICT2.2/labwork/5/Java/interface/Test.java new file mode 100644 index 0000000..b0502f0 --- /dev/null +++ b/usth/ICT2.2/labwork/5/Java/interface/Test.java @@ -0,0 +1,11 @@ +import static java.util.Arrays.asList; + +class Test +{ + public static void main(String... args) + { + var array = asList(new Point(1.0, 2.0), new Circle(3.0, 4.0, 5.0), + new Cylinder(6.0, 7.0, 8.0, 9.0)); + array.forEach(System.out::println); + } +} diff --git a/usth/ICT2.2/labwork/5/virtual.cc b/usth/ICT2.2/labwork/5/virtual.cc new file mode 100644 index 0000000..23ae78a --- /dev/null +++ b/usth/ICT2.2/labwork/5/virtual.cc @@ -0,0 +1,61 @@ +#include <cmath> +#include <iostream> +#include <memory> +#include <string> +#include <vector> + +using namespace std; + +static constexpr double PI = acos (-1.0); + +class Shape +{ +public: + virtual string get_name () const = 0; + + virtual double cal_area () const { return 0.0; } + virtual double cal_vol () const { return 0.0; } +}; + +class Point : public Shape +{ +public: + double x, y; + Point (double a, double b) : x {a}, y {b} {} + + string get_name () const override { return "Point"; } +}; + +class Circle : public Shape +{ +public: + double x, y, r; + Circle (double a, double b, double c) : x {a}, y {b}, r {c} {} + + string get_name () const override { return "Circle"; } + double cal_area () const override { return r * r * PI; } +}; + +class Cylinder : public Shape +{ +public: + double x, y, r, h; + Cylinder (double a, double b, double c, double d) + : x {a}, y {b}, r {c}, h {d} {} + + string get_name () const override { return "Cylinder"; } + double cal_area () const override { return (r + h) * r * PI * 2.0; } + double cal_vol () const override { return r * r * h * PI; } +}; + +int +main () +{ + vector<unique_ptr<Shape>> v; + v.push_back (make_unique<Point> (1.0, 2.0)); + v.push_back (make_unique<Circle> (3.0, 4.0, 5.0)); + v.push_back (make_unique<Cylinder> (6.0, 7.0, 8.0, 9.0)); + for (auto& p : v) + cout << p->get_name () << " of area " << p->cal_area () + << " and volume " << p->cal_vol () << endl; +} diff --git a/usth/ICT2.2/midterm/report/bubbleplot.jpg b/usth/ICT2.2/midterm/report/bubbleplot.jpg new file mode 100644 index 0000000..13ea13d --- /dev/null +++ b/usth/ICT2.2/midterm/report/bubbleplot.jpg Binary files differdiff --git a/usth/ICT2.2/midterm/report/report.pdf b/usth/ICT2.2/midterm/report/report.pdf new file mode 100644 index 0000000..4b4ad3c --- /dev/null +++ b/usth/ICT2.2/midterm/report/report.pdf Binary files differdiff --git a/usth/ICT2.2/midterm/report/report.tex b/usth/ICT2.2/midterm/report/report.tex new file mode 100644 index 0000000..627530a --- /dev/null +++ b/usth/ICT2.2/midterm/report/report.tex @@ -0,0 +1,928 @@ +\documentclass[a4paper,12pt]{article} +\usepackage[english,vietnamese]{babel} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{booktabs} +\usepackage{lmodern} +\usepackage{graphicx} +\usepackage{hyperref} +\usepackage{lmodern} +\usepackage{forest} +\usepackage{textcomp} +\usepackage[nottoc,numbib]{tocbibind} + +\renewcommand{\thefootnote}{\fnsymbol{footnote}} + +\begin{document} +\setcounter{page}{0} +\thispagestyle{empty} +\vspace*{\stretch{1}} +\begin{flushright} + \setlength{\baselineskip}{1.4\baselineskip} +\textbf{\Huge Midterm Report\\Sorting and Searching} + \noindent\rule{\textwidth}{5pt} + \emph{\Large Object Oriented Programming} + \vspace{\stretch{1}} + + \textbf{by Nguyễn Công Thành, Nguyễn Gia Phong\\ + Nguyễn Văn Tùng, Trần Minh Vương and Trần Hồng Minh\\} + \selectlanguage{english} + \today +\end{flushright} +\vspace*{\stretch{2}} +\pagebreak + +\selectlanguage{english} +\tableofcontents +\pagebreak + +\section{Introduction} +\subsection{Brief Description} +Since the dawn of computer science, sorting and searching algorithms +have drawn a significant amount of attention from researchers, +due to their broad applications in solving a huge number of problems +and sub-problems in many fields. In spite of their straightforward, familiar +statements, these algorithm link with a variety of important programming +concepts, namely data structures, divide and conquer technique and of course +complexity analysis and time–space tradeoffs. + +In this report, we only discuss some of the most basic searching +and sorting algorithms. While trying to implement them, we also analyze +their strengths and weaknesses, as well as the ease and difficulties +we encounter using the language Java and object-oriented programming in general. + +Whilst overall, we follow~\cite{wu}, we also try to make use of newer Java +features to write more generic and concise code. + +This report is licensed under a +\href{http://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons +Attribution-ShareAlike 4.0 International License.} + +\selectlanguage{vietnamese} +\subsection{Authors and Credits} + +The work has been undertaken by group number 11, whose members are listed +in the following table, with Nguyễn Công Thành being our leader. +\begin{center} + \begin{tabular}{c c} + \toprule + Full name & Student ID\\ + \midrule + Nguyễn Công Thành & BI9-210\\ + Nguyễn Gia Phong & BI9-184\\ + Nguyễn Văn Tùng & BI9-229\\ + Trần Minh Vương & BI9-239\\ + Trần Hồng Minh & BI8-114\\ + \bottomrule + \end{tabular} +\end{center} + +We would like to express our special thanks to Dr. Nghiêm Thị Phương, +whose lectures gave us basic understanding on the key principles of +object-oriented programming. Without her guidance, we might never +have a chance to take an in-depth exploration on this topic. +\pagebreak + +\selectlanguage{english} +\section{Searching} +For the sake of simplicity, we only consider searching operating on array-like +data structures with constant-time random access and without duplicated entries. +This affects a few implementation design decision we will be making later on. +The searching problem is then stated in ~\cite[p.~634]{wu} accordingly: +\begin{quote} + Given a value $x$, return the [zero-based] index of $x$ in the array, + if such $x$ exists. Otherwise, return \verb|NOT_FOUND| (-1). +\end{quote} + +In this section, we will discover two searching algorithms: linear search +and binary search. Both of these, albeit being simple, are being used in +many different programming tasks. + +\subsection{Linear Search} +Linear search, by definition, sequentially checks each element of a list +until a match is found or the whole list has been searched. This matches +the algorithm implemented in \verb|java.util.List.indexOf|~\cite[indexOf]{list}. +Given +\begin{verbatim} +var list = java.util.Arrays.asList(4, 20, 6, 9); +\end{verbatim} +where \verb|var| is a Java SE 10 feature for eliding ``the often-unnecessary +manifest declaration of local variable types''~\cite{var}, which, in this case, +is \verb|List<Integer>|. + +\verb|list.indexOf(6)| would then give 2 and \verb|list.indexOf(7)| returns -1. + +For the matter of completeness, we also try to implement the description +provided by the documentation~\cite[indexOf]{list} +\begin{verbatim} +import java.util.List; + +public class Search +{ + public static final int NOT_FOUND = -1; + + public static linear(List l, Object o) + { + for (int i = 0; i < l.size(); ++i) + if (o == null ? l.get(i) == null : o.equals(l.get(i))) + return i; + return NOT_FOUND; + } +} +\end{verbatim} + +From this dummy implementation, it is trivial that linear search has, +as it name suggests, \emph{linear time} complexity. The nullity check +every iteration adds a bit of overhead, but if performance is ever concerned, +the better tested and optimized standard library should be used instead. +Moving \verb|o == null| to the upper level would require duplicating +the \verb|for| loop, creating redundancy and making the code less readable +and less maintainable. + +Unsurprisingly, 2 and -1 are returned from +\verb|Search.linear(list, 6)| and \verb|Search.linear(list, 7)|, +respectively. + +\subsection{Binary Search} +Binary search find the position of a target value within a sorted array by +``testing the middle of an interval, eliminating the half of the [array] in +which the key cannot lie, and then repeating the procedure iteratively'' +\cite{bsearch}. This could be intuitively implemented using recursion: +\begin{verbatim} +// ... +public class Search +{ + // ... + private static <T> + int binary(List<? extends Comparable<? super T>> list, T key, + int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = list.get(mid).compareTo(key); + if (cmp < 0) + return binary(list, key, mid + 1, high); + if (cmp > 0) + return binary(list, key, low, mid - 1); + return mid; + } +} +\end{verbatim} + +\verb|Search.binary| is declared as a \emph{generic method} to allow +more implicit calls, where the compiler will \emph{infer} the type of \verb|key| +as well as that of each element of \verb|list|~\cite{infer}. This makes +the method work on any type of argument that is a subclass of \verb|Comparable|, +which is required for \verb|Comparable.compareTo|. In fact, +\verb|java.util.Collections.binarySearch|'s declaration follows +the same strategy~\cite[binarySearch]{collections}. + +Instead of directly exposing this method where users need to provide +the lower and higher bound of the indices, we overload it with a wrapper +to ensure encapsulation: +\begin{verbatim} +// ... +public class Search +{ + // ... + public static <T> + int binary(List<? extends Comparable<? super T>> list, T key) + { + return binary(list, key, 0, list.size()); + } +} +\end{verbatim} + +To test our implementation, we first need \verb|list| to be sorted. +By providing \verb|null| to its \verb|sort| method, we can sort it +in the elements' natural (ascending) order~\cite[sort]{list}. +As \verb|list| is now [4, 6, 9, 20], \verb|Search.binary(list, 6)| +and \verb|Search.binary(list, 7)| return 1 and -1 respectively. + +\verb|java.util.Collections.binarySearch(list, 7)| gives -3, however, +due to its slightly different behavior: +\begin{quote} + [If \verb|key| is not in the list, returns] \verb|(-(insertion point) - 1)|. + The insertion point is defined as the point at which the key would be + inserted into the list: the index of the first element greater than the key, + or \verb|list.size()| if all elements in the list are less than + the specified key.~\cite[binarySearch]{collections} +\end{quote} + +Since the algorithm only give up the search until the array is bisected to +a nonpositive length (\verb|high < low|), the time-complexity of binary search +is asymptotic to $\log_2 n$, where $n$ is the size of the array. +In other words, on modern 64-bit computers with support for at most 18EB +of address space, the running time is still negligible (64 comparisons). +Despite the use of \verb|List| interface in the implementation, +\verb|Search.binary| is not $\Theta(\lg n)$\footnote{The notation +$f = \Theta(g)$ indicates that $f$ grows at the same rate as $g$.} +on \verb|LinkedList|, which has $\Theta(n)$ random access. + +Since the algorithm only works on ordered lists, it is not +suitable for iteratively inserting to a sorted list, as for linear +data structures, either random access or middle insertion has to be +$\Omega(n)$\footnote{The notation $f = \Omega(g)$ indicates that $f$ grows at +least as as fast as $g$.}. In that case, self-balancing binary search tree +should be used instead. +\pagebreak + +\section{Sorting} +The sorting problem is stated in~\cite[p. 638]{wu} as +\begin{quote} + Given an array of $n$ values, arrange the values into ascending order. +\end{quote} + +This section discusses only three sorting algorithms, +namely selection sort, bubble sort and heapsort. + +\subsection{Selection Sort} +Selection sort could be performed by iterating through every position and select +the minimum element from the current one to the end of the array. The in-place +algorithm could be implemented in Java as follows: +\begin{verbatim} +import java.util.List; + +import static java.util.Collections.swap; + +public class Sort +{ + public static <T extends Comparable<? super T>> + void selection(List<T> list) + { + int i, j, m, n = list.size(); + for (i = 0; i < n; ++i) + { + for (m = j = i; j < n; ++j) + if (list.get(j).compareTo(list.get(m)) < 0) + m = j; + swap(list, i, m); + } + } +} +\end{verbatim} + +Since only atomic \verb|int|'s are introduced, the space complexity is +$\Theta(1)$. The time complexity is, in term of swaps, $\Theta(n)$ +and, in term of comparisons, +\[T(n) = \sum_{i=0}^{n-1}\sum_{j=i}^{n-1}1 + = \sum_{i=0}^{n-1}(n - i) + = \sum_{i=1}^{n}i + = \frac{n^2 + n}{2} + = \Theta(n^2)\] + +One could micro-optimize by tweaking \verb|i|'s and \verb|j|'s +bounds by an unit but that does not make the algorithm +any faster asymptotically. + +Just to make sure everything works correctly, we do a simple check +\begin{verbatim} +var list = java.util.Arrays.asList("foo", "bar", "baz"); +Sort.selection(list); +System.out.println(list); +\end{verbatim} +and get \verb|[bar, baz, foo]| printed to \verb|stdout| as expected. + +\subsection{Bubble Sort} +In~\cite[p. 646]{wu}, the author praised bubble sort to finish sooner than +selection sort on average and best cases. Whilst the latter is true, +we will try to explain why the former is generally incorrect. + +To do this, we first need to understand what bubble sort is. +As defined in~\cite[p. 40]{clrs}, the code below operating on +an array \verb|a| of size \verb|n| qualifies as bubble sort. +\begin{verbatim} +for (int i = n - 1; i > 0; --i) + for (int j = 1; j < i; ++j) + if (a[j] < a[j - 1]) + swap(a, j, j - 1); +\end{verbatim} + +This naïve version, like selection sort, has the time complexity $\Theta(n^2)$ +in term of comparisons (it underperform selection sort in term of swaps +however--this will be discussed right after the implementation is completed). +Though, as pointed out in~\cite{bubblebad}, +\begin{quote} + Nearly every description of bubble sort describes + how to terminate the sort early if the vector becomes sorted. +\end{quote} + +Hence, we \emph{upgrade} the pseudocode to +\begin{verbatim} +boolean swapped; +do + { + swapped = false; + for (int j = 1; j < n; ++j) + if (a[j] < a[j - 1]) + { + swap(a, j, j - 1); + swapped = true; + } + } +while (swapped); +\end{verbatim} + +We can do further optimization avoiding comparing the last $t - 1$ items +when running for the $t$-th time of the outer loop, as after iteration $t - 1$, +these have already \emph{bubbled up} to its final place~\cite{wikibubble}. +With this in mind, we write our final implementation: +\begin{verbatim} +// ... +public class Sort +{ + // ... + public static <T extends Comparable<? super T>> + void bubble(List<T> list) + { + for (int n = list.size(), m = 0; n > 1; n = m, m = 0) + for (int i = 1; i < n; ++i) + if (list.get(i).compareTo(list.get(i - 1)) < 0) + swap(list, m = i, i - 1); + } +} +\end{verbatim} + +In the best case where the list is already sorted, during the first iteration +of the outer loop, \verb|m| remains zero, which is then assigned to \verb|n| +to break the loop, hence the time complexity is that of the inner loop +or $n - 1 = \Omega(n)$. Otherwise, denote $S$ as a subset of all +positive integers not greater than \verb|list.size()|. The time complexity +would then be +\[T(n) = \sum_{n\in S}\Theta(n)\] +On random data, $\#S = \Theta(n)$ and thus $T(n) = \Theta(n^2)$. + +As demonstrated in~\cite{bubblebad}, selection sort outperforms bubble sort +on average cage, despite their asymptotically equivalent time complexity: +\begin{center} + \includegraphics[width=0.57\textwidth]{bubbleplot.jpg} +\end{center} + +Looking back at~\cite[p. 646]{wu}, we are now able to spot Wu's misconception: +\begin{quote} + On average, we expect the bubble sort to finish sorting sooner than + the selection sort, \emph{because there will be more data movements for + the same number of comparisons}, and there is a test to exit the method + when the array gets sorted. +\end{quote} + +While bubble sort may take advantage of the pre-sorted parts of the array +to do fewer comparisons, the number of swaps is $\Theta(n^2)$, which grows +strictly faster than selection sort's $\Theta(n)$. Consequently, instead of +swapping more to finish faster, the bubble variant does more unnecessary +data movements. Furthermore, write operations on memory are usually slower +than reading, which makes swaps much costlier than comparisons. Finally, +it could be summarized by a quote from Donald Knuth~\cite{peculiar}, +\begin{quote} + In fact, one of Demuth's main results was that in a certain sense + `bubble sorting' is the optimum way to sort. [...] It turns out that + [all other sorting methods studied] are always better in practice, + in spite of the fact that Demuth has proved the optimality of bubble sorting + on a certain peculiar type of machine. +\end{quote} + +\subsection{Heapsort} +Heapsort could be viewed as an improved version of selection sort, where +the selection is done on the right data structure: the heap~\cite{heapselect}. +To sort an array ascendingly in place, we use a binary max-heap to keep track +of the largest element in the unsorted region and move it to the beginning +of the sorted one, iteratively. + +The binary heap is an array object $A$ which resembles a nearly completely +filled binary tree, except possibly the lowest level. This kind of heap has +two attributes: $length$ of the array and $size$ of the heap, +where $0 \le size \le length$ and valid elements of the heap only reside +within the $[0, size)$ index interval of the array~\cite[p. 151]{clrs}. + +We choose \verb|java.util.List| as the interface for the inner representation +of heap and come up with the following declaration: +\begin{verbatim} +import java.util.List; + +public class Heap<T extends Comparable<? super T>> +{ + private List<T> list; + private int size; + public int getSize() + { + return size; + } + + public int getLength() + { + return list.size(); + } + + public T get(int i) + { + return list.get(i); + } +} +\end{verbatim} + +Since the elements are of the type \verb|Comparable|, \verb|Heap| is a max-heap +in a purely conceptual sense. That is, the order totally depends on +\verb|T.compareTo|, which could be defined or overridden by the users. +The max-heap property is then defined as that for every node $i$ other than +the root $A_0$, $A_{\mathrm{parent}(i)} \ge A_i$, where the indices of a node's +parent, left child and right child are given by +\[\begin{array}{ll} + \mathrm{parent}(i) &= \left\lfloor\dfrac{i - 1}{2}\right\rfloor\\ + \mathrm{left}(i) &= 2i + 1\\ + \mathrm{right}(i) &= 2i + 2 +\end{array}\] + +To maintain this property at node $i$, with the assumption that +the binary trees rooted at left($i$) and right($i$) are already max-heaps, +we use \verb|heapify|, which sift the value at $A_i$ down the heap if it is +smaller than its children: +\begin{verbatim} +// ... +import static java.util.Collections.swap; + +public class Heap<T extends Comparable<? super T>> +{ + // ... + public void heapify(int i) + { + int right = i + 1 << 1; + int left = right - 1; + int largest = i; + if (left < size && get(left).compareTo(get(largest)) > 0) + largest = left; + if (right < size && get(right).compareTo(get(largest)) > 0) + largest = right; + if (largest != i) + { + swap(list, i, largest); + heapify(largest); + } + } +} +\end{verbatim} + +At each call, the index of the greatest element among $A_i$, +$A_{\mathrm{left}(i)}$ and $A_{\mathrm{right}(i)}$ is assigned +to \verb|largest|. In case $A_i$ is greatest, the subtree rooted at $A_i$ +is already a max-heap and the method terminates. Otherwise, $A_i$ is swapped +with $A_{\mathtt{largest}}$, which makes node $i$ and its children to satisfy +the max-heap property. The subtree rooted at \verb|largest|, though, +\emph{might} violate the property so \verb|heapify| needs to be called on it. +For instance, given $i$ points to the subtree on the left, then \verb|heapify| +would step-by-step turn it to the one on the right: +\begin{center} + \begin{forest} + for tree={circle,draw} + [,phantom [4,fill=yellow [9 [0] [6]] [8 [3] [,phantom]]] + [9 [4,fill=yellow [0] [6]] [8 [3] [,phantom]]] + [9 [6 [0] [4,fill=yellow]] [8 [3] [,phantom]]]] + \end{forest} +\end{center} + +The running time of \verb|heapify| on a subtree of height (number of edges +between the root and the furthest leaf) $h$ is the time $\Theta(1)$) to make +$A_i$, $A_{\mathrm{left}(i)}$ and $A_{\mathrm{right}(i)}$ a max-heap, plus +the time to run \verb|heapify| on one of its children if necessary: +\[T(h) \le T(h - 1) + \Theta(1) + \le T(0) + \sum_{i=1}^{h}\Theta(1) = T(0) + \Theta(h)\] +Since $T(0)$ is obviously $\Theta(1)$, +\[T(h) \leq \Theta(h) \Longrightarrow T(h) = O(h)\footnotemark\] +A binary tree of size $n$ may have at maximum height of +$h = \lfloor\log_2 n\rfloor$, thus the time complexity with respect to +the size of the subtree is $O(\log_2 n)$. +\footnotetext{The notation $f = O(g)$ indicates that $f$ grows +at most as as fast as $g$.} + +Noticeably, $\forall i \ge \lfloor n/2\rfloor,\; 2i + 2 > 2i + 1 \ge n +\iff \mathrm{right}(i) > \mathrm{left}(i) \ge n$. In other words, +only nodes of indices less than $\lfloor n/2\rfloor$ have children. +Therefore, a heap could be constructed as follows +\begin{verbatim} +// ... +public class Heap<T extends Comparable<? super T>> +{ + // ... + public Heap(List<T> a) + { + list = a; + size = a.size(); + for (int i = size >> 1; i-- > 0;) + heapify(i); + } +} +\end{verbatim} + +Before the construction, each node from $\lfloor n/2\rfloor$ (\verb|size >> 2|) +to $n - 1$ is a leaf and a trivial heap on its own. Consider the iteration +where \verb|heapify| is called on node $i$ and assume every node after $i$ +is the root of a heap beforehand, then after the iteration, all nodes from $i$ +to $n - 1$ are foots of max-heaps. Consequently, by mathematical induction, +after the construction, the whole array becomes a heap. According +to~\cite[p. 159]{clrs}, this constructor runs in linear time ($O(n)$). + +Heapsort uses the max-heap to select the next largest element to move it +to the start of the sorted region. This in-place movement could be implemented +as the method \verb|pop|, which also return the largest element to make +the method make sense on its own. +\begin{verbatim} +// ... +public class Heap<T extends Comparable<? super T>> +{ + // ... + public T pop() throws RuntimeException + { + if (size < 1) + throw new RuntimeException("heap underflow"); + swap(list, 0, --size); + heapify(0); + return get(size); + } +} +\end{verbatim} + +Choosing the $n - 1$ largest element, we are left with the minimum value at +the beginning of the list and the rest of the list are all greater or equal to +the first element. +\begin{verbatim} +// ... +public class Sort +{ + // ... + public static <T extends Comparable<? super T>> + void heap(List<T> list) + { + var heap = new Heap<T>(list); + for (int i = 1; i < list.size(); ++i) + heap.pop(); + } +} +\end{verbatim} + +The step-by-step selection from the example heap is shown below as +an illustration. One may notice that the result qualifies as a min-heap. +\begin{center} + \begin{forest} + for tree={circle,draw} + [,phantom [9 [6 [0] [4]] [8 [3] [,phantom]]] + [8 [6 [0] [4]] [3 [9,edge=dotted] [,phantom]]] + [6 [4 [0] [8,edge=dotted]] [3 [9,edge=dotted] [,phantom]]]] + \end{forest} +\end{center} +\begin{center} + \begin{forest} + for tree={circle,draw} + [,phantom [4 [0 [6,edge=dotted] [8,edge=dotted]] + [3 [9,edge=dotted] [,phantom]]] + [3 [0 [6,edge=dotted] [8,edge=dotted]] + [4,edge=dotted [9,edge=dotted] [,phantom]]] + [0 [3,edge=dotted [6,edge=dotted] [8,edge=dotted]] + [4,edge=dotted [9,edge=dotted] [,phantom]]]] + \end{forest} +\end{center} + +The running time of \verb|Sort.heap| is that of \verb|Heap| constructor, +plus $n - 1$ times that of \verb|Heap.pop|, which is +\begin{align*} + T(n) &= O(n) + (n - 1)(\Theta(1) + O(\log_2 n))\\ + &= O(n) + \Theta(n)O(\log_2 n)\\ + &= O(n) + O(n\log_2 n)\\ + &= O(n\log_2 n) +\end{align*} +This is a huge improvement from selection sort's and bubble sort's $O(n^2)$. +\pagebreak + +\section{Comparing}\label{sec:cmp} +Our implementations of searching and sorting algorithms in Java work on +any collection of data whose \emph{natural} order is specified, that is, +where elements implement \verb|Comparable|. However, they does not cover +the case \emph{another} order is required, there is not any option to use +our current library other than subclassing every item with a different +\verb|compareTo| method, which, in every sense, is counter-intuitive. + +In~\cite{wu}, Wu dedicated a whole ``Sample Development'' section to address +this issue and came up with the final solution of using the standard interface +\verb|java.util.Comparator|~\cite{cmp} which declare the method \verb|compare|. +We start with refactoring \verb|Sort.selection| to comply with this facility: +\begin{verbatim} +// ... +import java.util.Comparator; + +public class Sort +{ + public static <T> + void selection(List<T> list, Comparator<T> comparator) + { + int i, j, m, n = list.size(); + for (i = 0; i < n; ++i) + { + for (m = j = i; j < n; ++j) + if (comparator.compare(list.get(j), list.get(m)) < 0) + m = j; + swap(list, i, m); + } + } +} +\end{verbatim} + +To sort in reversed order, we can subclass \verb|Comparator| +anonymously~\cite{anon} +\begin{verbatim} +var list = java.util.Arrays.asList(4, 2, 0, 6, 9); +Sort.selection(list, new java.util.Comparator<Integer>() +{ + public int compare(Integer a, Integer b) + { + return -a.compareTo(b); + } +}); +System.out.println(list); +\end{verbatim} + +As expected, the snippet above prints \verb|[9, 6, 4, 2, 0]| to \verb|stdout|. + +In order to maintain backward-comparability, we write a helper class extracting +the natural order from any \verb|Comparable| to a \verb|Comparator|: +\begin{verbatim} +import java.util.Comparator; + +public class Compare<T extends Comparable<? super T>> +implements Comparator<T> +{ + public int compare(T a, T b) + { + return a.compareTo(b); + } +} +\end{verbatim} +and wrap the current \verb|Sort.selection| with +\begin{verbatim} +// ... +public class Sort +{ + // ... + public static <T extends Comparable<? super T>> + void selection(List<T> list) + { + selection(list, new Compare<T>()); + } +} +\end{verbatim} + +\verb|Sort.bubble| can be refactored similarly, but since \verb|Sort.heap| +does all the comparisons in \verb|Heap|, we are required to make \verb|Heap| +work with \verb|Comparator|'s +\begin{verbatim} +// ... +import java.util.Comparator; + +public class Heap<T> +{ + // ... + private Comparator<T> cmp; + + public void heapify(int i) + { + int right = i + 1 << 1; + int left = right - 1; + int largest = i; + if (left < size && cmp.compare(get(left), get(largest)) > 0) + largest = left; + if (right < size && cmp.compare(get(right), get(largest)) > 0) + largest = right; + if (largest != i) + { + swap(list, i, largest); + heapify(largest); + } + } + + public Heap(List<T> a, Comparator<T> c) + { + list = a; + size = a.size(); + cmp = c; + for (int i = size >> 1; i-- > 0;) + heapify(i); + } +} +\end{verbatim} +and re-write \verb|Sort.heap| to use the new \verb|Heap| +\begin{verbatim} +// ... +public class Sort +{ + // ... + public static <T> + void heap(List<T> list, Comparator<T> comparator) + { + var heap = new Heap<T>(list, comparator); + for (int i = 1; i < list.size(); ++i) + heap.pop(); + } + + public static <T extends Comparable<? super T>> + void heap(List<T> list) + { + heap(list, new Compare<T>()); + } +} +\end{verbatim} + +For the next example, we use a minimal, read-only version of the \verb|Person| +class from~\cite[p. 666]{wu}, which is ordered by \verb|name| by default: +\begin{verbatim} +public class Person implements Comparable<Person> +{ + private String name; + private Integer age; + private Character gender; + + public Person(String name, Integer age, Character gender) + { + this.name = name; + this.age = age; + this.gender = gender; + } + + public int compareTo(Person other) + { + return this.name.compareTo(other.name); + } + + public String toString() + { + return String.format("%s (%d%c)", name, age, gender); + } + + public String getName() + { + return name; + } + + public Integer getAge() + { + return age; + } + + public Character getGender() + { + return gender; + } +} +\end{verbatim} + +We use a list of the oldest current state leaders~\cite{old} for this test +\begin{verbatim} +var list = java.util.Arrays.asList( + new Person("Mahathir Mohamad", 94, 'M'), + new Person("Elizabeth II", 93, 'F'), + new Person("Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah", 90, 'M'), + new Person("Paul Biya", 86, 'M'), + new Person("Michel Aoun", 84, 'M'), + new Person("Mahmoud Abbas", 83, 'M'), + new Person("Francis", 82, 'M')); +Sort.heap(list); +list.forEach(System.out::println); +\end{verbatim} +and get +\begin{verbatim} +Elizabeth II (93F) +Francis (82M) +Mahathir Mohamad (94M) +Mahmoud Abbas (83M) +Michel Aoun (84M) +Paul Biya (86M) +Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah (90M) +\end{verbatim} + +It would neither be challenging to re-sort this list by their ages: +\begin{verbatim} +var ageComparator = new java.util.Comparator<Person>() +{ + public int compare(Person a, Person b) + { + return a.getAge().compareTo(b.getAge()); + } +}; +Sort.heap(list, ageComparator); +list.forEach(System.out::println); +\end{verbatim} +which gives us +\begin{verbatim} +Francis (82M) +Mahmoud Abbas (83M) +Michel Aoun (84M) +Paul Biya (86M) +Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah (90M) +Elizabeth II (93F) +Mahathir Mohamad (94M) +\end{verbatim} + +Linear search is able to run without any modification: we would still receive +4 from \verb|Search.linear(list, list.get(4))|. Binary search, however, +would not work correctly if the order of the list is not \emph{natural}. +One with \verb|Comparator| support may be implemented as follows. +\begin{verbatim} +import java.util.List; +import java.util.Comparator; + +public class Search +{ + // ... + private static <T> + int binary(List<? extends T> list, T key, + Comparator<? super T> c, int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = c.compare(list.get(mid), key); + if (cmp < 0) + return binary(list, key, c, mid + 1, high); + if (cmp > 0) + return binary(list, key, c, low, mid - 1); + return mid; + } + + public static <T> + int binary(List<? extends T> list, T key, + Comparator<? super T> c) + { + return binary(list, key, c, 0, list.size()); + } +} +\end{verbatim} + +Now \verb|Search.binary(list, list.get(5), ageComparator)| would return +the right index 5 instead of -1 like \verb|Search.binary(list, list.get(5))|. +\pagebreak + +\section{Conclusion} +Albeit searching and sorting belong to the category of algorithms, +by implementing them, we were still able to recognize a variety of +object-oriented concepts, namely: +\begin{enumerate} + \item Through encapsulation of the inner representations + and behaviors, we can create intuitive programming interfaces, + whilst keeping the code clear and concise. Notable examples are + the implementation of binary search and the heap data structure. + \item Through polymorphism, generic and convenient libraries can be written, + which allow more \emph{code reuse} and thus facilitate more effective + development. We wrote all of the classes and methods with this principle + in mind. + \item Through inheritance, it is possible to extend the functionalities of + each object. Together with polymorphism (which defines the behavioral + interfaces), it enable us to generalize our codebase one step further, + as shown in section~\ref{sec:cmp}, without spending too much energy + on refactoring. +\end{enumerate} + +Generally, though, we find shoving every self-contained function into a class +as a static method rather redundant. +\pagebreak + +\begin{thebibliography}{99} + \bibitem{wu} C. Thomas Wu. + ``Chapter 11: Sorting and Searching''. + \emph{An Introduction to Object-Oriented Programming with Java}, 5 ed. + McGraw-Hill, 2010. ISBN 978–0–07–352330–9. + \bibitem{list} \href{https://docs.oracle.com/javase/8/docs/api/java/util/List.html}{List (Java Platform SE 8)}. + \emph{Oracle}. + \bibitem{var} \href{http://openjdk.java.net/jeps/286}{JEP 286: Local-Variable Type Inference}. + \emph{OpenJDK}. + \bibitem{bsearch} \href{http://mathworld.wolfram.com/BinarySearch.html}{Binary Search}. + \emph{Wolfram WathWorld}. + \bibitem{infer} \href{https://docs.oracle.com/javase/tutorial/java/generics/methods.html}{Generic Methods}. + \emph{Oracle}. + \bibitem{collections} \href{https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html}{Collections (Java Platform SE 8)}. + \emph{Oracle}. + \bibitem{clrs} Thomas H. Cormen, Charles E. Leiserson, + Ronald L. Rivest and Clifford Stein. + \emph{Introduction to Algorithms}, 3 ed. + MIT Press, 2009. ISBN 978-0-262-03384-8. + \bibitem{bubblebad} Owen Astrachan. + \emph{\href{https://users.cs.duke.edu/~ola/bubble/bubble.html}{Bubble Sort: An Archaeological Algorithmic Analysis}}. + Duke University. + \bibitem{wikibubble} \href{https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort}{Bubble sort}. + \emph{Wikipedia}. + Section 2.2: \emph{Optimizing bubble sort}. + \bibitem{peculiar} Donald E. Knuth. The Dangers of Computer-Science Theory. + \emph{Studies in Logic and the Foundations of Mathematics}, vol. 74. + Elsevier, 1973. + doi:\href{https://doi.org/10.1016/S0049-237X(09)70357-X}{10.1016/S0049-237X(09)70357-X}. + \bibitem{heapselect} Steven Skiena. + ``Searching and Sorting''. + \emph{The Algorithm Design Manual}, p. 109. + Springer, 2008. + doi:\href{https://doi.org/10.1007/978-1-84800-070-4_4}{10.1007/978-1-84800-070-4{\_}4}. + ISBN 978-1-84800-069-8. + \bibitem{cmp} \href{https://docs.oracle.com/javase/8/docs/api/java/util/mparator.html}{Comparator (Java Platform SE 8)}. + \emph{Oracle}. + \bibitem{anon} \href{https://docs.oracle.com/javase/tutorial/java/javaOO/anonymousclasses.html}{Anonymous Classes}. + \emph{Oracle}. + \bibitem{old} \href{https://en.wikipedia.org/wiki/Lists_of_state_leaders_by_age#10_oldest_currently_serving_state_leaders}{Lists of state leaders by age}. + \emph{Wikipedia}. + Section 1: \emph{10 oldest currently serving state leaders}. +\end{thebibliography} +\end{document} diff --git a/usth/ICT2.2/midterm/slides/USTH.jpg b/usth/ICT2.2/midterm/slides/USTH.jpg new file mode 100644 index 0000000..d2190eb --- /dev/null +++ b/usth/ICT2.2/midterm/slides/USTH.jpg Binary files differdiff --git a/usth/ICT2.2/midterm/slides/bubbleplot.jpg b/usth/ICT2.2/midterm/slides/bubbleplot.jpg new file mode 100644 index 0000000..13ea13d --- /dev/null +++ b/usth/ICT2.2/midterm/slides/bubbleplot.jpg Binary files differdiff --git a/usth/ICT2.2/midterm/slides/slides.pdf b/usth/ICT2.2/midterm/slides/slides.pdf new file mode 100644 index 0000000..37fca3f --- /dev/null +++ b/usth/ICT2.2/midterm/slides/slides.pdf Binary files differdiff --git a/usth/ICT2.2/midterm/slides/slides.tex b/usth/ICT2.2/midterm/slides/slides.tex new file mode 100644 index 0000000..b69cdff --- /dev/null +++ b/usth/ICT2.2/midterm/slides/slides.tex @@ -0,0 +1,734 @@ +\documentclass[pdf]{beamer} +\usepackage[english,vietnamese]{babel} +\usepackage{amsmath} +\usepackage{booktabs} +\usepackage{colortbl} +\usepackage{graphicx} +\usepackage{hyperref} +\usepackage{lmodern} +\usepackage{forest} + +\mode<presentation>{} +\usetheme[hideothersubsections]{Hannover} +\usefonttheme[onlymath]{serif} +\usebackgroundtemplate{ + \includegraphics[width=\paperwidth,height=\paperheight]{USTH.jpg}} +\beamerdefaultoverlayspecification{<+->} + +\title[Sort \& Search]{Sorting and Searching} +\author[Group 11]{Nguyễn Công Thành---BI9-210\\ + Nguyễn Gia Phong---BI9-184\\ + Nguyễn Văn Tùng---BI9-229\\ + Trần Minh Vương---BI9-239\\ + Trần Hồng Minh---BI8-114} +\institute{University of Science and Technology of Hà Nội} +\date{\selectlanguage{english}\today} + +\begin{document} +\frame{\titlepage} +\begin{frame}{Contents} + \tableofcontents +\end{frame} + +\section{Introduction} +\begin{frame}{Introduction}\Large + \begin{itemize} + \item Sorting \& Searching are \emph{important} + \item Object-Oriented Programming + \item Implementation in Java + \item Generic Programming + \end{itemize} +\end{frame} + +\section{Searching} +\begin{frame}[fragile]{Searching}\Large + Given a value $x$, return the [zero-based] index of $x$ in the array, + if such $x$ exists. Otherwise, return \verb|NOT_FOUND| (-1). +\end{frame} + +\subsection{Linear Search} +\begin{frame}[fragile]{Linear Search}\Large + \begin{itemize} + \item Checks sequentially till + \begin{itemize}\Large + \item match found + \item whole list searched + \end{itemize} + \item Linear time complexity + \item \verb|java.util.List.indexOf| + \item Example: Search for number 7 + \begin{center} + \only<1-5>{\begin{tabular}{|c|c|c|c|c|} + \hline 4 & 20 & 6 & 9\\\hline + \end{tabular}}% + \only<6>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{yellow}4 & 20 & 6 & 9\\\hline + \end{tabular}}% + \only<7>{\begin{tabular}{|c|c|c|c|c|} + \hline 4 & \cellcolor{yellow}20 & 6 & 9\\\hline + \end{tabular}}% + \only<8>{\begin{tabular}{|c|c|c|c|c|} + \hline 4 & 20 & \cellcolor{yellow}6 & 9\\\hline + \end{tabular}}% + \only<9>{\begin{tabular}{|c|c|c|c|c|} + \hline 4 & 20 & 6 & \cellcolor{yellow}9\\\hline + \end{tabular}} + \end{center} + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Implementation} +\begin{verbatim} +import java.util.List; + +public class Search +{ + public static final int NOT_FOUND = -1; + + public static linear(List l, Object o) + { + for (int i = 0; i < l.size(); ++i) + if (o == null ? l.get(i) == null + : o.equals(l.get(i))) + return i; + return NOT_FOUND; + } +} +\end{verbatim} +\end{frame} + +\subsection{Binary Search} +\begin{frame}[fragile]{Binary Search}\Large + \begin{itemize} + \item For sorted arrays only + \item Repeat halving interval cannot have $x$ till + \begin{itemize}\Large + \item match found + \item invalid interval + \end{itemize} + \item Logarithmic time complexity + \item \verb|java.util.Collections.binarySearch| + \item Example: Search for number 7 + \begin{center} + \only<1-6>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} + \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & $\emptyset$\\\hline + \end{tabular}}% + \only<7>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} + \hline \cellcolor{red}0 & 1 & 2 & 3 & 4 & \cellcolor{green}5 + & 6 & 7 & 8 & 9 & \cellcolor{blue}$\emptyset$\\\hline + \end{tabular}}% + \only<8>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} + \hline 0 & 1 & 2 & 3 & 4 & 5 & \cellcolor{red}6 & 7 + & \cellcolor{green}8 & 9 & \cellcolor{blue}$\emptyset$\\\hline + \end{tabular}}% + \only<9>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} + \hline 0 & 1 & 2 & 3 & 4 & 5 & \cellcolor{yellow}6 & \cellcolor{blue}7 + & 8 & 9 & $\emptyset$\\\hline + \end{tabular}}% + \only<10>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} + \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cellcolor{gray}7 + & 8 & 9 & $\emptyset$\\\hline + \end{tabular}} + \end{center} + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Implementation} +\begin{verbatim} +public class Search +{ + private static <T> int binary( + List<? extends Comparable<? super T>> list, + T key, int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = list.get(mid).compareTo(key); + if (cmp < 0) + return binary(list, key, mid + 1, high); + if (cmp > 0) + return binary(list, key, low, mid - 1); + return mid; + } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Wrapper} +\begin{verbatim} +public class Search +{ + public static <T> int binary( + List<? extends Comparable<? super T>> list, + T key) + { + return binary(list, key, 0, list.size()); + } +} +\end{verbatim} +\end{frame} + +\section{Sorting} +\begin{frame}{Sorting}\Large + Given an array of $n$ values, arrange the values into ascending order. +\end{frame} + +\subsection{Selection Sort} +\begin{frame}{Selection Sort}\Large + \begin{itemize} + \item Iterate through every position,\\ + select the minimum from there to array's end + \item Quadratic time complexity + \item Example: + \only<1-2>{\begin{tabular}{|c|c|c|c|c|} + \hline 6 & 9 & 4 & 2 & 0\\\hline + \end{tabular}}% + \only<3>{\begin{tabular}{|c|c|c|c|c|} + \hline 6 & 9 & 4 & 2 & \cellcolor{yellow}0\\\hline + \end{tabular}}% + \only<4>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{gray}0 & 9 & 4 & \cellcolor{yellow}2 & 6\\\hline + \end{tabular}}% + \only<5>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{gray}0 & \cellcolor{gray}2 & + \cellcolor{yellow}4 & 9 & 6\\\hline + \end{tabular}}% + \only<6>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{gray}0 & \cellcolor{gray}2 & + \cellcolor{gray}4 & 9 & \cellcolor{yellow}6\\\hline + \end{tabular}}% + \only<7>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{gray}0 & \cellcolor{gray}2 & + \cellcolor{gray}4 & \cellcolor{gray}6 & \cellcolor{yellow}9\\\hline + \end{tabular}}% + \only<8>{\begin{tabular}{|c|c|c|c|c|} + \hline\rowcolor{gray} 0 & 2 & 4 & 6 & 9\\\hline + \end{tabular}} + \end{itemize} +\end{frame} + +\begin{frame}[fragile,label=selimpl]{Implementation} +\begin{verbatim} +import static java.util.Collections.swap; + +public class Sort +{ + public static <T extends Comparable<? super T>> + void selection(List<T> list) + { + int i, j, m, n = list.size(); + for (i = 0; i < n; ++i) + { + for (m = j = i; j < n; ++j) + if (list.get(j).compareTo(list.get(m)) < 0) + m = j; + swap(list, i, m); + } + } +} +\end{verbatim} +\end{frame} + +\subsection{Bubble Sort} +\begin{frame}{Bubble Sort}\Large + \begin{itemize} + \item Repeatedly iterate through the array,\\ + swap adjacent elements in wrong order + \item Quadratic time complexity + \item Example: + \only<1-2>{\begin{tabular}{|c|c|c|c|c|} + \hline 6 & 9 & 4 & 2 & 0\\\hline + \end{tabular}}% + \only<3>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{magenta}6 & \cellcolor{yellow}9 & 4 & 2 & 0\\\hline + \end{tabular}}% + \only<4>{\begin{tabular}{|c|c|c|c|c|} + \hline 6 & \cellcolor{magenta}9 & \cellcolor{yellow}4 & 2 & 0\\\hline + \end{tabular}}% + \only<5>{\begin{tabular}{|c|c|c|c|c|} + \hline 6 & 4 & \cellcolor{magenta}9 & \cellcolor{yellow}2 & 0\\\hline + \end{tabular}}% + \only<6>{\begin{tabular}{|c|c|c|c|c|} + \hline 6 & 4 & 2 & \cellcolor{magenta}9 & \cellcolor{yellow}0\\\hline + \end{tabular}}% + \only<7>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{magenta}6 & \cellcolor{yellow}4 + & 2 & 0 & \cellcolor{gray}9\\\hline + \end{tabular}}% + \only<8>{\begin{tabular}{|c|c|c|c|c|} + \hline 4 & \cellcolor{magenta}6 & \cellcolor{yellow}2 + & 0 & \cellcolor{gray}9\\\hline + \end{tabular}}% + \only<9>{\begin{tabular}{|c|c|c|c|c|} + \hline 4 & 2 & \cellcolor{magenta}6 & \cellcolor{yellow}0 + & \cellcolor{gray}9\\\hline + \end{tabular}}% + \only<10>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{magenta}4 & \cellcolor{yellow}2 & 0 + & \cellcolor{gray}6 & \cellcolor{gray}9\\\hline + \end{tabular}}% + \only<11>{\begin{tabular}{|c|c|c|c|c|} + \hline 2 & \cellcolor{magenta}4 & \cellcolor{yellow}0 + & \cellcolor{gray}6 & \cellcolor{gray}9\\\hline + \end{tabular}}% + \only<12>{\begin{tabular}{|c|c|c|c|c|} + \hline \cellcolor{magenta}2 & \cellcolor{yellow}0 + & \cellcolor{gray}4 & \cellcolor{gray}6 & \cellcolor{gray}9\\\hline + \end{tabular}}% + \only<13>{\begin{tabular}{|c|c|c|c|c|} + \hline\rowcolor{gray} 0 & 2 & 4 & 6 & 9\\\hline + \end{tabular}} + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Implementation} +\begin{verbatim} +public class Sort +{ + public static <T extends Comparable<? super T>> + void bubble(List<T> list) + { + for (int n = list.size(), m = 0; + n > 1; n = m, m = 0) + for (int i = 1; i < n; ++i) + if (list.get(i).compareTo(list.get(i-1)) < 0) + swap(list, m = i, i - 1); + } +} +\end{verbatim} +\end{frame} + +\begin{frame}{Bubble v Selection: Dawn of Sort}\Large + \only<1>{ + C. Thomas Wu (2010) claimed that + \begin{quote} + On average, we expect the bubble sort to finish sorting sooner than + the selection sort, \emph{because there will be more data movements for + the same number of comparisons}, and there is a test to exit the method + when the array gets sorted. + \end{quote}} + \only<2>{\includegraphics[width=\textwidth]{squint.jpg}} +\end{frame} + +\begin{frame}{BvS: Time Complexity} + \begin{center} + \begin{tabular}{c c c c c} + \toprule + Case & \multicolumn{2}{c}{Selection Sort} + & \multicolumn{2}{c}{Bubble Sort}\\ + \midrule + & Comparisons & Swaps & Comparisons & Swaps\\ + Best & $\Omega(n^2)$ & $\Omega(n)$ & $\Omega(n)$ & $\Omega(n)$\\ + Average & $\Theta(n^2)$ & $\Theta(n)$ & $\Theta(n^2)$ & $\Theta(n^2)$\\ + Worst & $O(n^2)$ & $O(n)$ & $O(n^2)$ & $O(n^2)$\\ + \bottomrule + \end{tabular} + \end{center} +\end{frame} + +\begin{frame}{BvS: Average Case in Practice} + \begin{center} + \includegraphics[width=0.85\textwidth]{bubbleplot.jpg} + \end{center} +\end{frame} + +\subsection{Heapsort} +\begin{frame}{Heapsort}\Large + \begin{itemize} + \item Selection sort, but use heap for selection + \item Linearithmic time complexity + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Using PriorityQueue (Min-Heap)} +\begin{verbatim} +import java.util.PriorityQueue; + +public class Sort +{ + public static <T extends Comparable<? super T>> + void pq(List<T> list) + { + var q = new PriorityQueue<T>(list); + for (int i = 0; i < list.size(); ++i) + list.set(i, q.poll()); + } +} +\end{verbatim}\pause + +But hey, there is also \verb|List.sort|! +\end{frame} + +\begin{frame}{Binary Max-Heap}\Large + \begin{itemize} + \item Nearly complete binary tree + \item Parent $\ge$ Children $\Longrightarrow$ Root is max! + \item Example: + \begin{center} + \begin{forest} + for tree={circle,draw} + [9 [4 [0] [6]] [8 [3] [,phantom]]] + \end{forest} + \end{center} + \end{itemize} +\end{frame} + +\begin{frame}{Linear Binary Max-Heap}\Large + \begin{itemize} + \item $length$ of inner representation + \item $size$ of heap ($0 \le size \le length$) + \item Index within $[0\,..\, size)$ + \[\begin{array}{ll} + \mathrm{parent}(i) &= \left\lfloor\dfrac{i - 1}{2}\right\rfloor\\ + \mathrm{left}(i) &= 2i + 1\\ + \mathrm{right}(i) &= 2i + 2 + \end{array}\] + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Heap Declaration} +\begin{verbatim} +public class Heap<T extends Comparable<? super T>> +{ + private List<T> list; + private int size; + + public int getSize() { return size; } + public int getLength() { return list.size(); } + public T get(int i) { return list.get(i); } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{void Heap::heapify(int i)} +\begin{verbatim} +int right = i + 1 << 1; +int left = right - 1; +int largest = i; +if (left < size + && get(left).compareTo(get(largest)) > 0) + largest = left; +if (right < size + && get(right).compareTo(get(largest)) > 0) + largest = right; +if (largest != i) + { + swap(list, i, largest); + heapify(largest); + } +\end{verbatim} +\end{frame} + +\begin{frame}{Heapification}\huge + \begin{center} + \only<1>{\begin{forest} + for tree={circle,draw} + [4,fill=yellow [9 [0] [6]] [8 [3] [,phantom]]] + \end{forest}}% + \only<2>{\begin{forest} + for tree={circle,draw} + [9 [4,fill=yellow [0] [6]] [8 [3] [,phantom]]] + \end{forest}}% + \only<3>{\begin{forest} + for tree={circle,draw} + [9 [6 [0] [4,fill=yellow]] [8 [3] [,phantom]]] + \end{forest}} + \end{center} +\end{frame} + +\begin{frame}[fragile]{The Loop Invariant}\Large + For $i$ =$\lfloor n/2\rfloor - 1$ downto $0$, \verb|heapify(i)|: + \begin{itemize} + \item \textbf{Initialization}: For every array, + each node $\lfloor n/2\rfloor\,..\,n-1$ is trival max-heap (leaf). + \item \textbf{Maintenance}: If nodes $i+1\,..\,n-1$ are max-heaps, + after \verb|heapify(i)|, all nodes $i\,..\,n-1$ are max-heaps. + \item \textbf{Terminination}: After \verb|heapify(0)|, + the whole array is a max-heap. + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Heap Constructor} +\begin{verbatim} +public class Heap<T extends Comparable<? super T>> +{ + public Heap(List<T> a) + { + list = a; + size = a.size(); + for (int i = size >> 1; i-- > 0;) + heapify(i); + } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Maximum Selection} +\begin{verbatim} +public class Heap<T extends Comparable<? super T>> +{ + public T pop() throws RuntimeException + { + if (size < 1) + throw new RuntimeException("heap underflow"); + swap(list, 0, --size); + heapify(0); + return get(size); + } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Heapsort Implementation} +\begin{verbatim} +public class Sort +{ + public static <T extends Comparable<? super T>> + void heap(List<T> list) + { + var heap = new Heap<T>(list); + for (int i = 1; i < list.size(); ++i) + heap.pop(); + } +} +\end{verbatim} +\end{frame} + +\begin{frame}{Sorting a Heap}\huge + \begin{center} + \only<1>{\begin{forest} + for tree={circle,draw} + [9 [6 [0] [4]] [8 [3] [,phantom]]]\ + \end{forest}}% + \only<2>{\begin{forest} + for tree={circle,draw} + [8 [6 [0] [4]] [3 [9,edge=dashed] [,phantom]]] + \end{forest}}% + \only<3>{\begin{forest} + for tree={circle,draw} + [6 [4 [0] [8,edge=dashed]] [3 [9,edge=dashed] [,phantom]]] + \end{forest}}% + \only<4>{\begin{forest} + for tree={circle,draw} + [4 [0 [6,edge=dashed] [8,edge=dashed]] + [3 [9,edge=dashed] [,phantom]]] + \end{forest}}% + \only<5>{\begin{forest} + for tree={circle,draw} + [3 [0 [6,edge=dashed] [8,edge=dashed]] + [4,edge=dashed [9,edge=dashed] [,phantom]]] + \end{forest}}% + \only<6>{\begin{forest} + for tree={circle,draw} + [0 [3,edge=dashed [6,edge=dashed] [8,edge=dashed]] + [4,edge=dashed [9,edge=dashed] [,phantom]]] + \end{forest}}% + \end{center} +\end{frame} + +\section{Comparing} +\begin{frame}[fragile]{Comparing}\Large + \begin{itemize} + \item $<$, $\le$, $=$, $\ge$, $>$ or $\ne$? + \item e.g. \verb|420 > 69| + \item But \verb|"420" < "69"|! + \item How do we sort any collection of data? + \end{itemize} +\end{frame} + +\subsection{Comparable} +\begin{frame}[fragile]{Comparable}\Large + \begin{itemize} + \item \emph{Natural} increasing order + \item Define \verb|int compareTo(T other)| + \item Negative: less than; Zero: equal;\\ + Positve: greater than. + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Example Element} +\begin{verbatim} +public class Person implements Comparable<Person> +{ + private String name; + private Integer age; + private Character gender; + + public int compareTo(Person other) + { + return this.name.compareTo(other.name); + } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Example Element (misc.)} +\begin{verbatim} +public class Person implements Comparable<Person> +{ + public Person(String name, Integer age, + Character gender) + { + this.name = name; + this.age = age; + this.gender = gender; + } + + public String toString() + { + return String.format("%s (%d%c)", + name, age, gender); + } +} +\end{verbatim} +\end{frame} + +\againframe{selimpl} + +\begin{frame}[fragile]{Sorting People} +\begin{verbatim} +var list = java.util.Arrays.asList( + new Person("Mahathir Mohamad", 94, 'M'), + new Person("Elizabeth II", 93, 'F'), + new Person("Paul Biya", 86, 'M'), + new Person("Michel Aoun", 84, 'M'), + new Person("Mahmoud Abbas", 83, 'M'), + new Person("Francis", 82, 'M')); +Sort.selection(list); +list.forEach(System.out::println); +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Sort by Name Output}\Large + \begin{quote} + Elizabeth II (93F)\\ + Francis (82M)\\ + Mahathir Mohamad (94M)\\ + Mahmoud Abbas (83M)\\ + Michel Aoun (84M)\\ + Paul Biya (86M) + \end{quote} +\end{frame} + +\subsection{Comparator} +\begin{frame}[fragile]{Comparator}\Large + \begin{itemize} + \item How about reverse order? + \item Sort by another \emph{key}? + \item \verb|compareTo| (or any other) method\\ + cannot be overriden without subclassing. + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{java.util.Comparator}\Large + \begin{itemize} + \item Define \verb|int compare(T one, T another)| + \item Negative: less than; Zero: equal;\\ + Positve: greater than. + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Refactored Selection Sort} +\begin{verbatim} +public class Sort +{ + public static <T> + void selection(List<T> list, + Comparator<T> comparator) + { + int i, j, m, n = list.size(); + for (i = 0; i < n; ++i) + { + for (m = j = i; j < n; ++j) + if (comparator.compare(list.get(j), + list.get(m)) < 0) + m = j; + swap(list, i, m); + } + } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Exposing Attributes} +\begin{verbatim} +public class Person implements Comparable<Person> +{ + public String getName() { return name; } + public Integer getAge() { return age; } + public Character getGender() { return gender; } +} +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Sorting by Age} +\begin{verbatim} +Sort.heap(list, new Comparator<Person>() +{ + public int compare(Person a, Person b) + { + return a.getAge().compareTo(b.getAge()); + } +}); +list.forEach(System.out::println); +\end{verbatim} +\end{frame} + +\begin{frame}{Sorting by Age Output}\Large + \begin{quote} + Francis (82M)\\ + Mahmoud Abbas (83M)\\ + Michel Aoun (84M)\\ + Paul Biya (86M)\\ + Elizabeth II (93F)\\ + Mahathir Mohamad (94M) + \end{quote} +\end{frame} + +\begin{frame}[fragile]{Backward Compatibility} +\begin{verbatim} +public class Compare<T extends Comparable<? super T>> +implements Comparator<T> +{ + public int compare(T a, T b) + { + return a.compareTo(b); + } +} + +public class Sort +{ + public static <T extends Comparable<? super T>> + void selection(List<T> list) + { + selection(list, new Compare<T>()); + } +} +\end{verbatim} +\end{frame} + +\section{Conclusion} +\begin{frame}{Conclusion}\Large + Though the topic is more algorithmic than OOP: + \begin{itemize} + \item \textbf{Encapsulation}: Intuitive interface and concise code, + e.g. binary search, heap. + \item \textbf{Polymorphism}: Generic, convenient libraries, + thus more \emph{code reuse} and more effective development. + \item \textbf{Inheritance}: Extend objects' functionalities, + hence even more generalization. + \item However, shoving every self-contained function into a class + is rather redundant. + \end{itemize} +\end{frame} + +\begin{frame}{Copying}\Large + \begin{itemize} + \item For the list of references, see our report. + \item The report also contains more explainations and examples. + \item The documents as well as Java source files are licensed under + \href{https://creativecommons.org/licenses/by-sa/4.0/}{CC BY-SA 4.0}. + \end{itemize} +\end{frame} +\end{document} diff --git a/usth/ICT2.2/midterm/slides/squint.jpg b/usth/ICT2.2/midterm/slides/squint.jpg new file mode 100644 index 0000000..1e86257 --- /dev/null +++ b/usth/ICT2.2/midterm/slides/squint.jpg Binary files differdiff --git a/usth/ICT2.2/midterm/src/Compare.java b/usth/ICT2.2/midterm/src/Compare.java new file mode 100644 index 0000000..e6bda90 --- /dev/null +++ b/usth/ICT2.2/midterm/src/Compare.java @@ -0,0 +1,9 @@ +import java.util.Comparator; + +public class Compare<T extends Comparable<? super T>> implements Comparator<T> +{ + public int compare(T a, T b) + { + return a.compareTo(b); + } +} diff --git a/usth/ICT2.2/midterm/src/Heap.java b/usth/ICT2.2/midterm/src/Heap.java new file mode 100644 index 0000000..3803924 --- /dev/null +++ b/usth/ICT2.2/midterm/src/Heap.java @@ -0,0 +1,61 @@ +import java.util.List; +import java.util.Comparator; + +import static java.util.Collections.swap; + +public class Heap<T> +{ + private List<T> list; + private Comparator<T> cmp; + private int size; + + public int getSize() + { + return size; + } + + public int getLength() + { + return list.size(); + } + + public T get(int i) + { + return list.get(i); + } + + public void heapify(int i) + { + int right = i + 1 << 1; + int left = right - 1; + int largest = i; + + if (left < size && cmp.compare(get(left), get(largest)) > 0) + largest = left; + if (right < size && cmp.compare(get(right), get(largest)) > 0) + largest = right; + if (largest != i) + { + swap(list, i, largest); + heapify(largest); + } + } + + public Heap(List<T> a, Comparator<T> c) + { + list = a; + size = a.size(); + cmp = c; + for (int i = size >> 1; i-- > 0;) + heapify(i); + } + + public T pop() throws RuntimeException + { + if (size < 1) + throw new RuntimeException("heap underflow"); + swap(list, 0, --size); + heapify(0); + return get(size); + } +} diff --git a/usth/ICT2.2/midterm/src/Person.java b/usth/ICT2.2/midterm/src/Person.java new file mode 100644 index 0000000..045c3f4 --- /dev/null +++ b/usth/ICT2.2/midterm/src/Person.java @@ -0,0 +1,38 @@ +public class Person implements Comparable<Person> +{ + private String name; + private Integer age; + private Character gender; + + public Person(String name, Integer age, Character gender) + { + this.name = name; + this.age = age; + this.gender = gender; + } + + public int compareTo(Person other) + { + return this.name.compareTo(other.name); + } + + public String toString() + { + return String.format("%s (%d%c)", name, age, gender); + } + + public String getName() + { + return name; + } + + public Integer getAge() + { + return age; + } + + public Character getGender() + { + return gender; + } +} diff --git a/usth/ICT2.2/midterm/src/Search.java b/usth/ICT2.2/midterm/src/Search.java new file mode 100644 index 0000000..efb9e45 --- /dev/null +++ b/usth/ICT2.2/midterm/src/Search.java @@ -0,0 +1,57 @@ +import java.util.List; +import java.util.Comparator; + +public class Search +{ + public static final int NOT_FOUND = -1; + + public static int linear(List list, Object key) + { + for (int i = 0; i < list.size(); ++i) + if (key == null ? list.get(i) == null : key.equals(list.get(i))) + return i; + return NOT_FOUND; + } + + private static <T> + int binary(List<? extends Comparable<? super T>> list, T key, + int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = list.get(mid).compareTo(key); + if (cmp < 0) + return binary(list, key, mid + 1, high); + if (cmp > 0) + return binary(list, key, low, mid - 1); + return mid; + } + + public static <T> + int binary(List<? extends Comparable<? super T>> list, T key) + { + return binary(list, key, 0, list.size()); + } + + private static <T> + int binary(List<? extends T> list, T key, Comparator<? super T> c, + int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = c.compare(list.get(mid), key); + if (cmp < 0) + return binary(list, key, c, mid + 1, high); + if (cmp > 0) + return binary(list, key, c, low, mid - 1); + return mid; + } + + public static <T> + int binary(List<? extends T> list, T key, Comparator<? super T> c) + { + return binary(list, key, c, 0, list.size()); + } +} diff --git a/usth/ICT2.2/midterm/src/Sort.java b/usth/ICT2.2/midterm/src/Sort.java new file mode 100644 index 0000000..3f146af --- /dev/null +++ b/usth/ICT2.2/midterm/src/Sort.java @@ -0,0 +1,49 @@ +import java.util.List; +import java.util.Comparator; + +import static java.util.Collections.swap; + +public class Sort +{ + public static <T> void selection(List<T> list, Comparator<T> comparator) + { + int i, j, m, n = list.size(); + for (i = 0; i < n; ++i) + { + for (m = j = i; j < n; ++j) + if (comparator.compare(list.get(j), list.get(m)) < 0) + m = j; + swap(list, i, m); + } + } + + public static <T extends Comparable<? super T>> void selection(List<T> list) + { + selection(list, new Compare<T>()); + } + + public static <T> void bubble(List<T> list, Comparator<T> comparator) + { + for (int n = list.size(), m = 0; n > 1; n = m, m = 0) + for (int i = 1; i < n; ++i) + if (comparator.compare(list.get(i), list.get(i - 1)) < 0) + swap(list, m = i, i - 1); + } + + public static <T extends Comparable<? super T>> void bubble(List<T> list) + { + bubble(list, new Compare<T>()); + } + + public static <T> void heap(List<T> list, Comparator<T> comparator) + { + var heap = new Heap<T>(list, comparator); + for (int i = 1; i < list.size(); ++i) + heap.pop(); + } + + public static <T extends Comparable<? super T>> void heap(List<T> list) + { + heap(list, new Compare<T>()); + } +} |
