Clean Energy Landscape

With the Cop21 talks in Paris ending earlier this month… and the outcome being a global agreement to limit temperature increase to 2 degrees celcius, I wanted to capitalize on this momentum and ask myself what I, as a technologist, can do.

The agreement made speaks to limiting temperature, supporting developing countries to maintain growth, and keeping visibility into actions and compliance by all memebers. While there is vagueness about how this will be implemented, there is worldwide agreement that technology needs to be advanced in clean energy and related areas.

As a concerned citizen of the world and one that wants to leave it as beautiful as I’ve found it, I want to know what I, as a software engineer/technologist do to help? How can I contribute my largest asset, my tech skills, to help bring about this change?

Why 2 Degrees

In fact scientists actually believe we should not raise temperatures more than 1.5 degrees above pre-industrial averages. The graph below shows our potential CO2 emissions pathways for this century and their long-term impact on temperature.

What Needs to Change?

To achieve the aim of limiting temperature increase to 2 degrees celcius, we need to move away from getting most of our energy from fossil fuels. We need change to occur across governments, private investment, and societal comprehension/awareness of the problem and more. While I care about all of these, and technology can play a role in bringing these changes about, the largest technological changes need to happen in the energy system itself. So, what needs to change here?

Our current energy system is made up of the sourcing/production, movement, storage, and consumption of energy.

There’s space in all of these areas for major improvement. Let’s look at the current situation for each of these, where things need to get to.

Energy Production

The bottom line is that we need energy and we’re going to need more and more of it. We do have alternative, clean sources of energy available: solar, wind, geothermal, hydroelectric, biomass, and nuclear. But, today we largely rely on coal, oil and natural gas.

US energy usage breakdown 2014

Note that clean, renewable energy sources represent < 10%, with the bulk of that in nuclear (which is debatable in terms of cleanliness and long-term liability). These percentages need to shift.

What needs to change to bring these shifts about?

Energy Networks

Today, our energy grids are a relic of a 100+ year old system. The limitations of these networks represent where much innovation need to happen. Let’s look at each limitation and the changes needed.

Efficiency

In the Lawrence Livermore National Laboratory graph above, note that ‘rejected energy’ or energy produced, but lost and never consumed represents 59% of all the energy produced in the US. This is a huge area for improvement.

Timing/Storage

Our current electricity grids work on a realtime system. As in, when you pull electritiy off the grid and into your home to power your TV.. that electricity is a result of energy recently created at a power plant (probably by burning coal or natural gas). The idea is that the power plant predicts how much electricity will be demanded by consumers during any given hour of the day and they burn the appropriate level of coal or natural gas to provide that and put it out on the grid.

Currently wind and solar energy don’t integrate well. Solar energy is produced during the day (and sunny days at that) and wind is even more unpredictable.. although can provide energy at night. But, the issue is that they cannot currently be efficiently stored for later conversion and distribution onto the existing energy grid.

Whats needed here are better ways of storing renewable, clean energy for future use. There are a lot of interesting things happening here, but I’m going to dive into that in a future post.

Energy Location/Movement

Similar to the idea above, currently energy needs to be produced somewhat nearby to where it’s distributed and consumed. Wind farms in North Dakota cannot, now, efficiently have their energy transported for realtime consumption in Chicago.

Innovation needs to happen in both enabling energy production in many different environments and in new energy transportation networks that can efficiently move energy around where it’s needed.

Consumption

It may come as no suprise, but the US and many other first world countries consume the most energy per person globally.

Part of the solution needs to be figuring out ways to use less dirty energy in our high consumption areas without a decrease in standard of living. If we look back at that Estimated U.S. Energy Use graph above, it shows that transportation is 27% of our annual energy usage. This is definitely an area to seek improvement and but it needs to move beyond this to more consumer areas and to the industrial sector as well.

These are definitely areas to seek improvement and watch as a technologist.

Takeaway

This blog post was an examination of the current clean energy landscape and the areas where we need to innovate to answer our energy dillema. If we truly need to ratchet down our CO2 to reach a temperature rise of under 2 degrees, we will need innovation across all these areas. And these are areas where a technologist can bring their skills. If not in the specific answers to say battery efficiency or energy grid waste, definitely in the consumer products and infrastructure that will be needed to adopt these advances across the US and around the world.

This is the fifth post in a series of posts dedicated to algorithmic problem solving. The focus of this series is on organizing the approach taken to solving such problems and laying out the stages that one should move through.

The posts prior to this one cover:

This post will be more of a move into the algorithm design phase itself. The focus will be on understanding and idetifying the runtime of given algorithm, why it’s important, and a review of the vocabulary and concepts used to convey and dicusss this information with others.

Before we begin, much of the information here I got from following the Khan Academy lecture series on this topic. It’s execellent and I fully encourage people trying to understand Asymptotic Analysis to check it out!

What is Asymptotic Notation?

In as few words as possible, it is a way of categorizing the runtimes of various functions as input size increases.

Where does the name come from? In mathematics, the term asymptotic refers to a line that approaches a curve but never touches. Unless your math skills are fresh, this may not immediately ring bells for you.

Check out the following graph showing input vs. time plotted on a graph, this is for a given set of some pretty typical function runtimes. You can see that the different ones show different curves on the graph.

bigocheatsheet.com

Asymptotic notation refers to dropping the constant coefficient and less significant terms of a given function to identify the component where input size really grows.

Ex. a given function, f = 6n​^2​​+100n+300

  • The 6n​^2 becomes larger than the remaining terms once n becomes very large.
  • The 6 also becomes insignificant as n becomes large
  • We can say the n^​2 is the portion of this function that really impacts it’s growth as n increases.

Three forms

Different input can incur significantly different runtimes for a given algorithm. These can logically be discussed as best, average and worst case scenarios. three forms of asymptotic notation are available to describe these.

Big-Θ (Theta)

  • A way of saying the growth of a runtime is constant across best and worst case inputs
  • Ex. Merge Sort:
    • runtime is always n log(n)
  • So, you can say it has a runtime of Θ(n log(n))

Big-O (Oh)

  • A way of describing the worst case input
  • Ex. Insertion sort:
    • best case, when input is nearly sorted, has runtime of n
    • worst case, when input is really unsorted, has runtime of n^2
  • So, you can say it has a runtime of O(n^2)

Big-Ω (Omega)

  • A way of describing the best case input.. and that an algorithm takes at least a certain runtime
  • Ex. Insertion sort:
    • Best case here is again a runtim of n
  • So, you can also say it has a runtime of Ω(n)

Generally, people use Big-O. This may be because our keyboards don’t have easy accessible Θ or Ω keys. It may also be that describing the worst case runtime is sufficient for their needs. Either way, it’s good to always consider best, average and worst case runtimes when analyzing your algorithms runtime.

One other useful thing I found for this topic was this table of example runtimes on the wikipedia page for Big O notation.

This is the fourth post in a series of posts dedicated to algorithmic problem solving. The focus of this series is on organizing the approach taken to solving such problems and laying out the stages that one should move through. The posts prior to this one covers understanding the problem and deciding on a data structure. This post continues with the data structure discussion and functions more as a cheatsheet for the various data structures you might choose from and what considerations might lead you to that choice. It also highlights implementation notes for each.

Data Structures

Linked List

Often linked list problems are given with the caveat that you’re operating with a linked list. i.e. ‘Given a linked list’… etc.. You’re not often given a problem where the means of structuring your data is open-ended and you decide to go with a linked list.

Example problems:

  • Given a linked list, determine it’s midpoint with only one traversal through the list
  • Write an algorithm to remove duplicates from a linked list.
  • Find the kth element from the end of a linked list

Implementation Reminders

  • If not specified, check whether the list is singly or double linked
  • You can use multiple pointers
  • Often, if you need to operate on a linked list given it’s length, recursive approaches can be used to find the end and then operate on the return from each recursive call.
    • Example: Find the kth element from the end of a linked list
def findKthFromEnd currentNode, targetDistance, currDistance
	if currentNode.next == nil
		currDistance = 0
		return currentNode
	end

	node = [self findKthNodeFromEnd:currentNode.next dist:targetDistance currCalc:currDistance];
	calc += 1;

	#pass back the currentNode as the matched distance from the end through 
	#the recursive method returns
	return currentNode if (targetDistance == currDistance)	
	node 
end

Collections

Set

Sets are unordered, unique collections of data.

When to Use:

  • You need a unique collection of items
  • You’re not worried about the order items are stored
  • You need to sort the contents to extract what you need. (i.e All entries where name starts with A-D)

Example problems:

  • Juke box admin: implement a function that allows juke box users to add new tracks to the juke box.
    • Duplicate tracks may confuse users, so if a user tries to add a song that already is in the juke box, don’t add it again.

Implementation Reminders

  • As sets unordered.. if you want a specific item within it, you need to already have a pointer to it or iterate through/sort the set to find the item(s) you want.
  • Depending on specific languages, be mindful of mutability constraints.

Array

Arrays make the most sense when you need to order the items within and you know you want to access items relative to their position in the collection. Unlike sets arrays allow duplicates as all contents are keyed by their index in the collection. i.e. Given an obj1, this ojbect can exist at multiple indexes within the array.

Example problems:

  • Given a collection of numbers, find the equilibrium index where the sum for items behind that index equals the sum of the numbers ahead

Implementation Reminders

  • Use when you need to allow for duplicates

Stack

A stack expands on the an array.. as it keeps the items ordered. However, insertion and removal only happen from one end or the ‘top’. Stacks allow you implement problems that require that sort of insertion or removal.

Stacks are a more nuanced structure like linked lists and many times you are given a problem where it’s specified that you use a stack. i.e. ‘Given a stack…’

Example problems:

  • The Tower of Hanoi
@implementation HanoiTower

- (void)transferDisks:(int)numberOfDisks from:(Tower *)origin to:(Tower *)destination buffer:(Tower *)buffer {
    if (numberOfDisks > 1) {
        int nextDisks = numberOfDisks - 1;

        [self transferDisks:nextDisks from:origin to:buffer buffer:destination];
        [self transferDisks:1 from:origin to:destination buffer:buffer];
        [self transferDisks:nextDisks from:buffer to:destination buffer:origin];
    } else if (numberOfDisks == 1) {
        NSNumber *number = [origin pop];
        [destination push:number];
    }
}
@end

Queue

In terms of insertions and removals, queues generally operate under FIFO (first-in, first-out) mechanism. More can be read here.

Queue visualization

Example problems:

  • Employees for a given company submit vacation requests. Only a certain number of employees can take vacation on a given day, so sometimes the request needs to be declined. Each day of each month allows a varied number of employees to be off, this number is set at the beginning of each month, so requests must wait to be approved or declined until this is known. Implement a function that accepts requests from employees and at the beginning of each month determines who can have their requested days off.

Implementation Reminders

  • Some interesting implementation can exist around prioritized queues.
  • Queue frequently come in handy in system operation problems.

Graphs

Graphs make the most sense when items or nodes connect to one or more other nodes. Think about a social network of friends. Or a network of train lines. One way you know you’ll probably be working with graph is if the problem domain talks about connections between nodes.

Example problems:

  • Traveling Salesman Problem: Is a well known problem in the graph algorithm domain. Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
  • Given a family heirarchy, and two members of this family, find the next common ancestor between them.
  • Given a list of university courses for a given major, where a student must take certain courses before others, determine a suitable order that a student can take their course load.

(All of these problems speak to nodes have direct relationships or dependencies on other nodes!)

Implementation Reminders

  • Decide or consider whether you graph is directed or undirected
  • Make use of sub structures like trees if you know that each node can have no more than 2 children.
  • During traversal or building of graph, can use concepts such as “weight” to give certain nodes priorities over others.
  • During traversal, if appropriate, use a visited flag to not visit the same node more than once.
  • Always consider a breadth-first traversal vs. a depth-first traversal. More on this in a future post!
  • If sorting a tree, consider a binary search tree. More on this later.

This is the third post in a series of posts around problem solving at the algorithmic level. This series outlines the steps to approaching such problems: questions that need to be to asked, architectural decisions, consideration of tradeoffs, etc..

The post prior to this discussed the first stage of the process which was around analyzing and understanding the problem thoroughly.

This post is around choosing how to represent your data. For me, this means both of the following:

  • Deciding on the appropriate data structure to represent your data
  • Organizing an object model that helps in representing this data

I don’t want to dive too deeply into what the different data structures are. But to name a few, they are: array, set, linked list, stack, queue, and graph. What this post will focus is on what you need to think about while deciding which to use. Check out the next post for more on specific data structures.

I think the best way to do this is to walk through an example and discuss.

Example

Representing a maze.

Suppose we have the problem of finding the solution for a given maze. Before figuring out how we’d go about that, let’s get a picture of what a maze looks like and what information we need.

Step 1 - Visualize the data

Simple maze with start, finish and interior.

After visualizing and thinking about a maze, we can say that it consists of:

  • a start and finish position
  • a number of interior positions
  • every position is connected to neighbor positions that can be traveled to (Left, Right, Up and Down)
  • there should be a path between the start and finish positions

Step 2 - Generate Data Representation Options

With each option, we need to figure out if it assists in representing the data we need to represent.

1) Array of arrays:

That maze visualization up there looks an awful lot like an array of arrays.

In psuedocode, would look something like:

maze = 	[[start, p2, p3, p4],
	[p5, p6, p7, p8],
	[p9, p10, p11, p12],
	[p13, p14, p15, finish]]

What this structure allows us:

  • the ability to show that start, p5, p9 and p13 all exist on the maze’s left boundary.

What this structure doesn’t allow us:

  • A means of indicating a node’s open neighbors.. the fact that p2 follows start can represent that it is it’s right neighbor, however, how can we represent if that move is not available?
    • The node itself could hold this information, but we must acknowledge that the data structure is not providing this.

2) Graph of postion nodes

start = Position.new
p5 = Position.new
p6 = Position.new

start.right = p2
start.left = p5

p5.up = start
p5.right = p6

What this structure allows us:

  • In a way, this expands on the above acknowlegement that the nodes would need to know which neighbors were available to move to.
  • This also gives the option of not necessarily representing the maze as a grid. In a grid, every position has an up, down, left and right, with a graph representation, a given position could potentially have 4+ open neighbors. They could all be represented as just neighbors on the Postion object.
start = Position.new
p5 = Position.new
p6 = Position.new

start.neighbors = [p2, p5]
p5.neighbors = [start, p6]

What this structure doesn’t allow us:

  • we aren’t able to easily identify the positions that exist on the boundaries of the maze (as in option 1).. but that may not actually be required or useful information.

Step 3 - Circle back to Problem

Ok, so we have a few options. Which one is best? Let’s revisit the problem we were presented with.

‘Given a maze with a start and finish, find a solution path.’

So, we need to explore the maze (given the start position) tracking potential paths until we find one that leads to the finish. This sounds an awful lot like a graph traversal where we’re looking for the path to a target node.

However, lets examine our other options again. In the array of arrays option, we could have each node know if it’s Left, Right, Top, Bottom neighbors were open.

maze = 	[[start, p2, p3, p4],
	[p5, p6, p7, p8],
	[p9, p10, p11, p12],
	[p13, p14, p15, finish]]

start.top = false
start.bottom = true
start.left = false
start.right = true

But, then we’d have to calculate the position of the next node to visit. Whereas in the graph option, those nodes are directly associated as neighbors.

Step 4 - Decision

It’s fairly clear that graph data structure feels like the cleaner, more representative, less restrictive data struction for this problem. That’s not to say that upon getting further into the solution and turning up new information that this can’t be changed!

One thing that’s fairly important here is that you know and understand the capabilities of your optional data structures. Here, recognizing that rewording the problem made it sound an awful lot like graph traversal was key. The next post in this series is going to be a review of problem to data structure mapping.. with example problems and clues about indicative data structures.

Before diving into how to solve a problem, we’ve got to make sure we completely understand all aspects of the problem itself.

Understand the Problem

  • What data do we have to serve as our input? This can come from different sources/places. Identify all information that could serve as useful. Don’t worry yet about how to organize it.
  • How can that input data vary? Will certain aspects of it get very big? Can things be empty or nil?
  • What format is our expected result? How does that result differ under the varied input?
  • Do we have any constraints to worry about? Memory? Processor? Network speed?

Example

Let’s take an example problem and walk through these steps.

Problem Statement

You are writing a scheduling application for a large concert hall. Requests to book the venue come in and must either be approved or the application should suggest the next nearest date that could accommodate the event.

Step 1 - Ask Questions

This problem is a little open-ended. When things are open ended.. Best to start asking questions.

  • What information does a request contain?
  • What allows us to approve a request?
  • How do we determine the next nearest date to suggest?
  • Are there any special cases where the answers to the above don’t hold?

Let’s assume we’ve talked to the organizers of this venue and we’ve gotten the following set of rules:

  1. Assume a request contains: a date, a performer’s name and other miscellanious data
  2. Due to setup and teardown, no event can be scheduled within 5 days of another event.
  3. When suggesting an alternative date, should suggest either an earlier or later date whichever is closest (and >= 5 days away). If both are available, suggest the earlier.
  4. As a convienence offering, they want to allow people booking to identify one or more potential dates to request. Only make suggestions off the first choice date.

Step 2 - Examine and Understand Input/Output data

Data we need (Input Data)

Calendar

  • Information about existing bookings and allow us to determine if a requested date is available.

Booking Request

  • Containing a collection of dates the requester is interested in. (Let’s assume the collection is ordered in terms of preference.)

Data we need to return (Output data)

We can have two separate results.

  1. That the booking was successful for one of the requested dates. We’d want to return the date that the booking was made on so the user knows if it was their 1st choice, 2nd choice, etc..
  2. None of the requested dates are available.. We’d want to return a suggested date relative to their top choice requested date.

Next

This represents a pretty good example of exploring a given problem, it’s input and expected results, and some of it’s related edgecases. Next in the problem solving process is thinking about how to represent the data we have in an appropriate data structure.