Given an undirected graph G, made up of a set of node V, and a set of edges E, we would like to determine if G contains a cycle in time relatives to the number of nodes.

Understanding depth first search

First to understand our solution we must understand depth first search (DFS).

DFS is a greedy algorithm which recursively traverses a tree left-to-right, exploring each deepest path. The algorithm runs first on a given root node, in this case [1]. We then check if the node v is our target node. If not, we recursively call DFS on each child node of v. If we have explored every node in the graph and haven’t found our target, the target does not exist in the graph G.

Applying DFS to Finding Graph Cycles

One given property of undirected graphs is that they have a cycle if and only if depth first search visits an already visited edge (aka a back edge). We can utilize this property, making a slight modification to DFS, to detect any cycles.

In our defined version of DFS we simply ignore already visited nodes. Instead, we’re going to intialize all nodes to the color white before we run the algorithm, and change the node color to black once it has been visited. This algorithm returns “cycle exists” if at any moment we find a node that is colored black already on what should be a new exploration.

Linked Lists are an implementation of the AbstractList class in which we have an linear ordering of objects where each node has 32 components: the object, and a pointer to the next object in the list. The Linked List Object itself generally references a “head” node, or the first node in the linked list.

Use Cases

Linked Lists are extremely useful for constant time addition and deletion of elements. To add an element, all we have to do is change the pointer of the last object in the List to the new object. We can also treat the list as a first in — first out data structure, aka a “queue”.

Linked Lists may not be as useful when we need to grab a specific element of the index, as we don’t know where it is located at. When we want to grab a specific index, we have to iterate through the array up to that index which is a O(n) time operation compared to the constant time getIndex operation of a normal array.

LinkedLists can either be singular or doubly linked. A single linked list is one where each object only points to the next one in the List, not allowing us the ability to iterate backwards. Doubly linked lists have pointers to the previous and next node, allowing us to move freely in either direction till we hit the head or the tail.

Class Methods

The class holds various methods for both construction and utilizing the data structure

• add(E e) — adds an element e to the end of the List
• clear() — removes all elements
• contains(Object o) — returns true if the list contains o
• get(int index) — gets the object at the index
• indexOf(Object o) — returns index of object
• peek() — Returns the object at the end of the list
• pop() — removes the object at the end
• remove(Object O) — removes specified object

Resource(s)

LinkedList (Java Platform SE 7 ) (oracle.com)

Long call options, or more simply “calls” are a defined risk derivative strategy used on a number of various equities.

Options are known for their hedging capabilities, i.e. their ability to guard against the risk of another play, much like insurace. While options are great for hedging, we can also utilize them as a leveraged gamble, either long or short, against a given stock.

What is an option?

In simple terms, a stock option is a contract that gives us the right, but not the obligation, to buy or sell shares of a certain equity at a certain price before a certain date. With long calls, these contracts give us the right to purchase a stock at a certain price before expiration. This means that if we purchase a long call with a strike price of $30 for a premium p1, and the stock increases in values to $50 per share, we are still able to purchase the stock at a price of $30 to whoever sold us the contract.

Since long call options are “defined risk” we can only lose the premium we paid for the contract, and theoretically have unlimited upside. While this may sound great, it gives no guarantee that the contract will be profitable before it expires.

Premium

Premium is what the seller of the contracts receives for their risk, much like insurance contracts. The total premium collected for a contract is determined by taking the premium * 100, as options contracts are written in bundles of 100 stock units.

Collecting premium for owning stock shares (aka selling covered calls) can be a valuable method of profiting during generally sideways markets, as we expect the long calls to expire worthless a majority of the time.

Profits

Profits for a long call are determined by the strike price and the premium the contract was purchased for. We can determine the profit for an “in the money” stock option by taking the current stock price minus the strike price of the option and minus any premium paid for the contract.

HTTP strict transport security (commonly written as HSTS) is a browser response header allowing a website to specify that it should only be used through the hyper text transport secure protocol (HTTPS).

This security functionality ideally prevents visitors from accidentally requested the non secure version of the website, and being subjected to stolen information, or a man-in-the-middle attack. This is especially important when using an unsecured wifi-access point (AP), as we may not have verification that the AP is who they say they are.

The Request

When we first reach out to a website we don’t have stored in a cache, the browser returns the header Strict-Transport-Security. Your browser then records this information, and knows to access the site over HTTPS for any further requests while the header is still active.

Strict-Transport-Security: max-age=300000000;

Usually these headers have some time to expiration, and upon such we simply approach the website as we would have the first time around, upon which we receive a new header.

If we try to connect to an example website over HTTP now, the website will terminate our connection. This also may occur if the website no longer has a valid or signed SSL certificate.

Reference(s)

Strict-Transport-Security — HTTP | MDN (mozilla.org)

HashMaps in Java 8 are an implementation of the AbstractMap class, allowing us to store a key value pair inside a non-ordered structure.

Each element in the structure consists of a Key, Value pair in which every key in the data structure is unique. We can use different types such as Integers, Strings, or Chars as a key value, but we must be able to tell them apart. For our Value, we can store any primitive or object, even a null object!

Usage

We define a HashMap in java with the definition

HashMap<KEY,VALUE> map=new HashMap<KEY,VALUE>();

This allows us to utilize any defined HashMap function such as put(), getKey(), and many more for that specific obect.

We unfortunately cannot use duplicate keys in Java HashMaps, and anytime we add a key that already exists, it will overwrite the current value stored in the map.

Runtime

A Java HashMap allows for constant time (O(1)) operations for the two basic operations, get() and put(). This however falls under the assumption that the hash function for the data type occurs in constant time as well. You can read more about hashing here.

Once we hash the key value, we take the hashValue modulus the # of buckets in the array, to find which bucket we place our object in. Each bucket consists of essentialy a LinkedList which we place our object for storage.

To retrieve an object by key, we simply hash the key value and check that “bucket” for any object containing the key. So if a single bucket contains every item in the hashmap, we aren’t actually gaining any efficiency, as every element is just stored in a single LinkedList.

Reference(s)

HashMap in Java — javatpoint

HashMap (Java Platform SE 7 ) (oracle.com)