DEV Community: phoebehala

To collaborate on GitHub by fork

phoebehala — Wed, 20 Apr 2022 06:56:17 +0000

How we worked on the group project:

Came up with ideas
Talked about the structure and library we could use
Set our goal: Leaning how to collaborate with Git by fork
Learned and Practiced the workflow of GitHub fork
Set a timeline and Used "Trello" to trace the progress
Assigned tasks to each one
Had several meeting to make sure everyone worked well and were on the same page
Wrapped up

Noted down the workflow of GitHub fork:

Step 1. Fork the repo
Step 2. Clone the forked Repository

cd folderName
git clone https://github.com/Your-GitHub-Username/github-practice

step 3. Create my feature branch

git checkout -b myOwnBranchName

step 3.1 Work on my part and push to my remote repository

git add . 
git commit -m “......”
git push origin myOwnBranchName(feature)

Step 4.1 Check if the develop branch has ever changed
(Do it every time I resume my work)

git fetch upstream 
git checkout main
git merge upstream/develop

Step 4.2. Push to my own remote repository

git push origin main

Step 5 Merge synchronized main to my local feature branch which I am currently working on

git switch(or checkout) yourOwnBranchName(feature)
git merge main

if merge conflict happens, go step6.

Step 6. Manage the conflict

step 6.1. Send a pull request

step 7. Push to my own remote repository after merge

git push origin myOwnBranchName(feature)

Stacks and Queues

phoebehala — Wed, 23 Feb 2022 07:26:05 +0000

Stack

LIFO = "last in first out"
Examine the item most recently added.
push()
pop()

implementation -How it works in linked-list

inner class
private class Node
{
 String item;
 Node next;
}

/* === pop() === */
String item = first.item;
first = first.next;   //delete first node
return item;

/* === push() === */
Node oldfirst = first;
first = new Node();
first.item = "not";
first.next = oldfirst;

Queue

FIFO = "first in first out"
Examine the item least recently added.
enqueue()
dequeue()

implementation -How it works in linked-list

inner class
private class Node
{
 String item;
 Node next;
}

/* === dequeue() === */
String item = first.item;
first = first.next;   //delete first node
return item;

/* === enqueue() === */
Node oldlast = last;
//create a new node for the end
last = new Node();
last.item = "not";
//link the new node to the end of the list
oldlast.next = last;

UNION-FIND

phoebehala — Wed, 09 Feb 2022 16:31:17 +0000

Dynamic connectivity

Connected components

Maximal set of objects that are mutually connected.

connected(x,y)

Find/connected query: is there a path connecting the two objects?

union(x,y)

Union command: connect two objects.

Quick-find

is too slow for big problem

initialize: N
union: N
find: 1

find: Check if p and q have the same id.
Number of array accesses (for read or write):

Union: To merge components containing p and q, change all entries whose id equals id[p] to id[q].
It takes N^2 array accesses to process a sequence of N union commands on N objects.

The maximum number of #id[] array entries that can change (from one value to a different value) during one call to union when using the quick-find data structure on n elements is n

Quick-Union

is also slow

initialize: N
union: N (includes cost of finding roots)
find: N

find: Check if p and q have the same root
Number of array accesses (for read or write):

Union: To merge components containing p and q,
set the id of p's root to the id of q's root.

Weighted quick-union: (Improvement 1)

find:_Check if p and q have the same root (Identical to quick-union)
_Union: Modify quick-union to:
・Link root of smaller tree to root of larger tree.
・Update the sz[] array.

KEY POINT:
Increases by 1 when tree T1 containing x is merged into another tree T2.

The size of the tree containing x at least doubles since | T 2 | ≥ | T 1 |.

Size of tree containing x can double at most lg N times.

initialize: N
union: N (includes cost of finding roots)
find: lgN (lg = base-2 logarithm)