Week 1 - Linear Sorts + Command Line

Linux

https://towardsdatascience.com/basics-of-bash-for-beginners-92e53a4c117a
Bash Command:

• pwd
• echo
  • echo “Hello $X”

• if

  X=World
  if[[$X = "World"]]
  >then
  >  echo T
  >else
  >  echo F
  >fi

• for ```bash for x in a b c

  do echo “Hello $X” done

output:

hello a

hello b

hello c

for X in $(seq 10); do echo “hello $X”; done

快速创建多个文件夹

for i in $(seq 13)

do mkdir Week$i done ```

• mkdir
• ls, ls -a(ll)
• touch
• nano
• cat
• rm -r
• rmdir
• mv

  Linear Sort

  

Week 2 - Editors and Build Systems

Vim toturial

SSH

scp sampleFile.txt yingwei@best-linux.wisc.edu:sampleFile.txt  
scp yingwei@best-linux.wisc.edu:sampleFile.txt fromCSFile.txt

Build System - Make

https://www.gnu.org/software/make/
https://www.gnu.org/software/make/manual/make.html#Rule-Introduction
Makefile - example_1

test:runTest
TestPrintMessage.class: TestPrintMessage.java
        javac TestPrintMessage.java
runTest: TestPrintMessage.class PrintMessage.class
        java TestPrintMessage

Makefile - example_2

run:compile
        java Main
compile:Main.class
Main.class: Main.java
        javac Main.java

Java Generics

泛型类
https://www.cnblogs.com/coprince/p/8603492.html

class LinkedNode<T>{
    protected T data;
    protected LinkedNode<T> next;
}
class DoublyLinkedNode<S> extends LinkedNode<S>{
    protected DoublyLinkedNode<S> prev;
}
class LinkedListOfStrings extends LinkedNode<String>{
    //add, remove, get...
}

Homework Ans.

//限定为两个都为Double类型
class MetricBox implements Parcel<Double, Double>{  //set Double as param. both
    public Double Volume;
    public Double Weight;
    //constructor
    public MetricBox(Double Volume, Double Weight){
        this.Volume = Volume;
        this.Weight = Weight;
    }
}
//限定为String 和 任意类型
class EnglishBox<T> implements Parcel<String,T>{    //set String as the 1st param.
    public String Volume;
    public T Weight;
    //constructor
    public EnglishBox(String Volume, T Weight){
        this.Volume = Volume;
        this.Weight = Weight;
    }
}
//限定为两个为相同类型
class UniformBox<T> implements Parcel<T, T>{    //both generic type
    public T Volume;
    public T Weight;
    //constructor
    public UniformBox(T Volume, T Weight){
        this.Volume = Volume;
        this.Weight = Weight;
    }
}

Week 3 - HashTables + Source Control

HashTables

Source Control

https://git-scm.com/book/en/v2/Git-Basics-Recording-Changes-to-the-Repository

git config --global user.email "you@example.com"
git config --global user.name "Your name"

git add    README.md//put into stage
git commit -m "New update"    #commit the new new version
#git commit -am "-a means update all"


git status
git log

#rename master -> main
git brach -m master main    #-m means mv

#add .gitignore
vim .gitignore
git add .gitignore
git commit -m "add git ignore"

Week 4 - Review BSTs + Testing

Testing - Jar

javac Other.java 

#-c means creat, -f means the filename of the jar
jar -cf Other.jar Other.class

#cp: class path; Linux use : as /
java -cp .:Other.jar Main

#e: entry point
jar -cfe Both.jar Main Main.class Other.class

#run Main in jar
java -jar Both.jar

Testing - JUnit

javac -cp .:junit5.jar *.java
java -jar junit5.jar -cp . --scan-classpath

HashTable

Week 5 - RedBlack Tree Insert + Advanced Git

Advanced Git

git checkout branch_name    #change branch
git checkout -b branch_name    #create and check new branch
git branch    #check current branch and list all branches
git push --set-upstream origin branch_name    //push

RedBlack Tree

Red black Tree Properties:

1. Every node is either Red or Black
2. Red nodes can only have 0 or 2 black node children(red nodes cnnot have red node children)
3. All paths from a given node to its descendent leaves must contain the same number of black nodes

Rotation:

https://vlambda.com/wz_x0gVUSBDx5.html

Insert:

CASE 1: parent’s sibling is black, and is on the opposite side from violating node
rotate and color swap parent with grandparent
CASE 2: parent’s sibling is black, and is on the same side from violating node
rotate two red violating nodes
(case 1) rotate and color swap parent with grandparent
CASE 3: parent’s sibling is red
swap colors of parent, parent’s sibling, and grandparent;
then check for and handle new violations between grandparent and its parent

Week 6 - RedBlack Tree Delete + lambda expression

RedBlack Tree Delete

Remove:

0 remove node with zero children if node is read, then we’re done
if node is red, then we’re done
else node is black, replace with double black node with value null
1 remove node with single child
if node and it’s only child are different colors, then the child must end up black(if red, change to black), then done
if node and it’s only child are both black, make the child double black
2 remove node with two child:
change value of node being removed, but leave color when removing pred. or succ. = case 0 or case 1

Double Black:

CASE 1:

CASE 2:


CASE 3:

lambda expression

1. 在接口中定义好方法
2. 直接(a,b) -> a + b

Homework:

import java.util.ArrayList;

interface MathOperation {
    public int compute(int a, int b);
}

class Addition implements MathOperation {
    public int compute(int a, int b) {
        return a + b;
    }
}

public class LambdaExpressionActivity {

    public void performAllOperations(int a, int b) {

        ArrayList<MathOperation> ops = new ArrayList<>();

        // TODO: use named class Addition for addition:
        // ops.add( ??? ); // addition 10+6=16
        Addition add = new Addition();
        ops.add(add);

        // TODO: use anonymous class for multiplication:
        // ops.add( ??? ); // multiplication 10*6=60
        ops.add(new MathOperation() {
            @Override
            public int compute(int a, int b) {
                return a * b;
            }
        });

        // TODO: use lambda expression for subtraction:
        // ops.add( ??? ); // subtraction 10-6=4
        ops.add((a1, b1) -> a1 - b1);


        // TODO: use lambda expressions for division:
        // ops.add( ??? ); // division 10/6 = 1 (integer arithmetic)
        ops.add((a1, b1) -> a1 / b1);


        for (MathOperation op : ops) {
            System.out.println(op.compute(a, b) + " // computed by " + op.getClass().toString());
        }
    }

    public static void main(String args[]) {
        LambdaExpressionActivity lambdaActivity = new LambdaExpressionActivity();
        lambdaActivity.performAllOperations(10, 6);
    }
}

Week 7 - Set, Graphs + Stream

Stream

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/stream/Stream.html
What are Streams?

• a pipeline for data: process one data item per step
• intuitive
• works on large data sets well (even though that don’t fit into memory)
• easily optimize

+——————————+ +———+ +———-+ +——-+ +———+
| stream of elements +——-> | filter +-> |sorted+-> |map+-> |collect|
+——————————+ +———+ +———-+ +——-+ +———+
这种风格将要处理的元素集合看作一种流， 流在管道中传输， 并且可以在管道的节点上进行处理， 比如筛选， 排序，聚合等。
元素流在管道中经过中间操作（intermediate operation）的处理，最后由最终操作(terminal operation)得到前面处理的结果。

Stream<Pet> s = Stream.of( pets );
Optional<String> allNames = s
    .filter(x -> x.getType() == AnimalType.Bird;)    //筛选
    .filter(x -> x.getAge() >= 2)
    .map(pet -> "a pet named " + pet.getName()) //映射
    .reduce((a,b) -> a + ", " + b);  //合并
    if( allNames.isPresent())
        System.out.println(allNames.get())

Stream<String> wordStream = Files.lines(Path.get(filepath))
                                    .map( x -> x.trim)
                                    .filter( x -> x != null && x != "")
                                    .map( x -> x.toUpperCase());

Bash Steam

https://www.digitalocean.com/community/tutorials/an-introduction-to-linux-i-o-redirection

ls -l > test.txt #将ls -l 结果写入 test.txt
ls -l | grep Week | wc -l    #筛选Week关键字，查行
ls */*.java | sort | uniq -c     # -c means count

Week 8 - Regex + Graph

Graph

Prims Algorithm

![]R447AYG13CN]G]GV9B}RV.png
核心思想：贪心算法，Greedy. 总是选择当前最优的情况（当前步骤下的最短路径）

KruskalsAlgorithm

先排序，后链接（确保不成环）

Regex

https://regexone.com/
https://regex101.com/

Week 9 - Shortest Paths + HTML

Shortest Paths

![LCB7G~_ZA{ILNORJODJ1@R.png

![6}CH7~B(RH6N2H@R4%9SEY.png

HTML

<head>
  <title>Simple title</title>
  <meta name="author" content="Yingwei">
  <meta name="keywords" content="HTML,HEAD,BODY,BASIC TAGS">
</head>
<body>
  <ul>
    <li>o1</li>
    <li>ul</li>
  </ul>
</body>

Week 10 - B Trees + CSS and JavaScript

B Trees

Insert:

CSS and JavaScript

CSS

<style>
    h1{
    color:green;
    font-weight:bold;
  }
  <!--ID>
  #favorite{    
      color:black;
    font-weight:bold;
  }
  <!--Class>
  .odd{
      color:green;
    font-weight:bold;
  }


</style>

<li style="color:green;font-weight:bold;">Example</li>
<li id="favorite">Example favorite</li>
<li class="odd">Example class</li>

<link rel="stylesheet" href="magic.css">

JS

<html>
  <head>
    <title>First JavaScript Webpage</title>
    <script>
      function handleButtonClick() {
        //console.log('hello world from a function');
        document.querySelectorAll("input").forEach( input => {
              input.style.color = 'green';
              input.style.backgroundColor = 'yellow';
        });
      }
    </script>
   </head>
   <body>
     <h1>My Simple Dynamic Page!</h1>
     <input type="button" value="Lable" onclick="handleButtonClick();"> 
   </body>
</html>

<html>
  <head>
    <title>First JavaScript Webpage</title>
    <script>
      function handleButtonClick() {
        //console.log('hello world from a function');
        document.querySelectorAll("input").forEach( input => {
              input.style.color = 'green';
              input.style.backgroundColor = 'yellow';
        });
        var out = document.querySelectorAll('#output')[0];
        var input = document.querySelectorAll('#input')[0];
        //out.innerHTML += "here is a line of text <br\>"
        out.innerHTML += input.value + " x 2 = " + (parseInt(input.value) * 2) + "<br/>";
      }
    </script>
   </head>

   <body>
     <h1>My Simple Dynamic Page!</h1>
     <input id="input" type="text">
     <input type="button" value="x2" onclick="handleButtonClick();">
     <p id="output"></p>
   </body>

</html>

Week 11 - Skip Lists + CGI

Skip Lists

Reading: https://igoro.com/archive/skip-lists-are-fascinating/

Search
从height最高的开始找

    /// <summary>
    /// Returns whether a particular value already exists in the skip list
    /// </summary>
    public bool Contains(int value)
    {
        Node cur = _head;
        for (int i = _levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = cur.Next[i])
            {
                if (cur.Next[i].Value > value) break;
                if (cur.Next[i].Value == value) return true;
            }
        }
        return false;
    }

Remove
必须保证跳表可以正常运行

Week 12 - Tries + JavaFx

Tries 字典树

Reading: https://www.toptal.com/java/the-trie-a-neglected-data-structure
What is the maximum height of a trie that contains n strings when the maximum length of those strings is m characters each?
ANS: m

Intro to JavaFX

import javafx.application.Application;
import javafx.scene.Group;
import javafx.scene.Scene;
import javafx.stage.Stage;
// these imports are used for the First JavaFX Activity
import javafx.scene.control.Label;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Polygon;


public class JavaFXActivity extends Application {
    @Override
    public void start(final Stage stage) {
        // update this method definition to complete the First JavaFX Activity
        Label label = new Label("    The key to making programs fast\n" +
                "    is to make them do practically nothing.\n" +
                "    -- Mike Haertel");
        Circle circle = new Circle(160, 120, 30);
        Polygon polygon = new Polygon(160, 120, 200, 220, 120, 220);

        Group group = new Group(label,circle,polygon);
        Scene scene = new Scene(group,320,240);

        stage.setScene(scene);
        stage.setTitle("CS400: The Key");
        stage.show();
    }

    public static void main(String[] args) {
        Application.launch();
    }
}

Week 13 - AVL Trees + JavaFX

AVL Trees

Balance factor is : 0, -1 or 1
Reading: https://medium.com/basecs/the-little-avl-tree-that-could-86a3cae410c7
各项操作都是O(log n)级别的，高度最高位log n

JavaFX

Homework code:

import javafx.application.Application;
import javafx.scene.Scene;
import javafx.stage.Stage;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.Pane;
import javafx.application.Platform;
import javafx.geometry.Pos;
import java.util.Random;

public class DessertGame extends Application {
    private int score = 0;

    @Override
    public void start(final Stage stage) {
        // Step 1 & 2
        BorderPane borderPane = new BorderPane();
        Scene scene = new Scene(borderPane, 640, 480);
        stage.setTitle("Dessert in the Desert JavaFX Game");

        // Step 3
        Label scoreLabel = new Label("Score: 0");
        borderPane.setTop(scoreLabel);
        BorderPane.setAlignment(scoreLabel, Pos.TOP_LEFT);

        Button exitButton = new Button("Exit");
        exitButton.setOnAction(event -> {
            Platform.exit();
        });
        borderPane.setBottom(exitButton);
        BorderPane.setAlignment(exitButton, Pos.BOTTOM_RIGHT);

        // Step 4
        Pane pane = new Pane();
        borderPane.setCenter(pane);
        BorderPane.setAlignment(pane, Pos.CENTER);

//      TODO: Step 5-8

        Button Dessert = new Button("Dessert");
        Button Desert1 = new Button("Desert");
        Button Desert2 = new Button("Desert");
        Button Desert3 = new Button("Desert");
        Button Desert4 = new Button("Desert");
        Button Desert5 = new Button("Desert");
        Button Desert6 = new Button("Desert");
        Button Desert7 = new Button("Desert");

        pane.getChildren().add(Dessert);
        pane.getChildren().add(Desert1);
        pane.getChildren().add(Desert2);
        pane.getChildren().add(Desert3);
        pane.getChildren().add(Desert4);
        pane.getChildren().add(Desert5);
        pane.getChildren().add(Desert6);
        pane.getChildren().add(Desert7);

        Button[] buttons = {Dessert,Desert1,Desert2,Desert3,Desert4,Desert5,Desert6,Desert7};   //button array

        Random rd = new Random();
        randomizeButtonPositions(rd,buttons);   //randomize position before game start
        exitButton.requestFocus();  //focus before game start

        Dessert.setOnAction(e -> {score = score + 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert1.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert2.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert3.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert4.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert5.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert6.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});
        Desert7.setOnAction(e -> {score = score - 1; randomizeButtonPositions(rd,buttons); exitButton.requestFocus(); scoreLabel.setText("Score: " + score);});



        stage.setScene(scene);
        stage.show();
    }

    /**
     * This method will generate random button's position
     * @param generator random generator
     * @param buttons buttons array
     */
    private void randomizeButtonPositions(Random generator,Button[] buttons ){
        for (Button button:buttons) {
            button.setLayoutX(generator.nextInt(600));
            button.setLayoutY(generator.nextInt(400));
        }
    }

    public static void main(String[] args) {
        Application.launch();
    }
}