# Algorithms

Learn To Think Like A Computer Scientist. Master the fundamentals of the design and analysis of algorithms.

SKILLS YOU WILL GAIN: Algorithms, Dynamic Programming, Greedy Algorithm, Divide And Conquer Algorithms

Algorithms are the heart of computer science, and the subject has countless practical applications as well as intellectual depth. This study program is an introduction to algorithms for learners with at least a little programming experience. The specialization is rigorous

but emphasizes the big picture and conceptual understanding over low-level implementation and mathematical details. After completing this specialization, you will be well-positioned to ace your technical interviews and speak fluently about algorithms with other programmers and computer scientists.

About the instructor: Tim Roughgarden has been a professor in the Computer Science Department at Stanford University since 2004. He has taught and published extensively on the subject of algorithms and their applications.

## COURSE 1 - Divide and Conquer, Sorting and Searching, and Randomized Algorithms

SKILLS YOU WILL GAIN: Algorithms, Randomized Algorithm, Sorting Algorithm, Divide And Conquer Algorithms

The primary topics in this part of the study program are: asymptotic (“Big-oh”) notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

Introduction; “big-oh” notation and asymptotic analysis.
Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.
The QuickSort algorithm and its analysis; probability review.
Linear-time selection; graphs, cuts, and the contraction algorithm.

## COURSE 2 - Graph Search, Shortest Paths, and Data Structures

SKILLS YOU WILL GAIN: Graphs, Data Structure, Algorithms, Hash Table

The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

Breadth-first and depth-first search; computing strong components; applications.
Dijkstra’s shortest-path algorithm.
Heaps; balanced binary search trees.
Hashing; bloom filters.

## COURSE 3 - Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

SKILLS YOU WILL GAIN: Spanning Tree, Algorithms, Dynamic Programming, Greedy Algorithm

The primary topics in this part of the study program are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim’s MST algorithm.
Kruskal’s MST algorithm and applications to clustering; advanced union-find (optional).
Huffman codes; introduction to dynamic programming.
Advanced dynamic programming: the knapsack problem, sequence alignment, and optimal binary search trees.

## COURSE 4 - Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

SKILLS YOU WILL GAIN: Data Structure, Algorithms. Np-Completeness, Dynamic Programming

The primary topics in this part of the study program are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

The Bellman-Ford algorithm; all-pairs shortest paths.
NP-complete problems and exact algorithms for them.
Approximation algorithms for NP-complete problems.
Local search algorithms for NP-complete problems; the wider world of algorithms.

# Algorithms for Battery Management Systems

Get Started in Algorithms for Battery Management. Learn how to model lithium-ion battery cells, and how to use those models to manage battery packs.

In this study program, you will learn the major functions that must be performed by a battery management system, how lithium-ion battery cells work and how to model their behaviors mathematically, and how to write algorithms (computer methods) to estimate state-of-charge, state-of-health, remaining energy, and available power, and how to balance cells in a battery pack.

## COURSE 1 - Introduction to battery-management systems

This course will provide you with a firm foundation in lithium-ion cell terminology and function and in battery-management-system requirements as needed by the remainder of the specialization. After completing this course, you will be able to:

– List the major functions provided by a battery-management system and state their purpose
– Match battery terminology to a list of definitions
– Identify the major components of a lithium-ion cell and their purpose
– Understand how a battery-management system “measures” current, temperature, and isolation, and how it controls contactors
– Identify electronic components that can provide protection and specify a minimum set of protections needed
– Compute stored energy in a battery pack
– List the manufacturing steps of different types of lithium-ion cells and possible failure modes

This topic, you will learn some important terminology used to describe battery cells, and will learn the principles of operation of standard electrochemical battery cells.

This topic, you will learn some of the principal advantages of lithium-ion cells versus standard electrochemical battery cells, what are their primary components, and how they work.

This topic, you will begin to learn about BMS requirements, and will study the requirements for sensing and high-voltage control in detail.

This topic, you will continue to learn about BMS requirements, studying requirements for protection, interface, performance management, and diagnostics in detail.
This topic, you will learn in more detail than before how lithium-ion cells are made and how they can fail.

## COURSE 2 - Equivalent Circuit Cell Model Simulation

In this course, you will learn the purpose of each component in an equivalent-circuit model of a lithium-ion battery cell, how to determine their parameter values from lab-test data, and how to use them to simulate cell behaviors under different load profiles. By the end of the course, you will be able to:

– State the purpose for each component in an equivalent-circuit model – Compute approximate parameter values for a circuit model using data from a simple lab test – Determine coulombic efficiency of a cell from lab-test data – Use provided Octave/MATLAB script to compute open-circuit-voltage relationship for a cell from lab-test data – Use provided Octave/MATLAB script to compute optimized values for dynamic parameters in model – Simulate an electric vehicle to yield estimates of range and to specify drivetrain components – Simulate battery packs to understand and predict behaviors when there is cell-to-cell variation in parameter values
In this module, you will learn how to derive the equations of an equivalent-circuit model of a lithium-ion battery cell.
In this module, you will learn how to determine the parameter values of the static part of an equivalent-circuit model.
In this module, you will learn how to determine the parameter values of the dynamic part of an equivalent-circuit model.
In this module, you will learn how to generalize the capability of simulating the voltage response of a single battery cell to a profile of input current versus time to being able to simulate constant-voltage and constant-power control of a battery cell, as well as different configurations of cells built into battery packs.
In this honors module, you will learn how to co-simulate a battery pack and an electric-vehicle load. This ability aids in sizing vehicle components and the battery-pack.
In this final module for the course, you will modify three sample Octave programs to create functions that can simulate temperature-dependent cells, battery packs built from PCMs, and battery packs built from SCMs.

## COURSE 3 - Battery State-of-Charge (SOC) Estimation

In this course, you will learn how to implement different state-of-charge estimation methods and to evaluate their relative merits. By the end of the course, you will be able to:

– Implement simple voltage-based and current-based state-of-charge estimators and understand their limitations – Explain the purpose of each step in the sequential-probabilistic-inference solution – Execute provided Octave/MATLAB script for a linear Kalman filter and evaluate results – Execute provided Octave/MATLAB script for state-of-charge estimation using an extended Kalman filter on lab-test data and evaluate results – Execute provided Octave/MATLAB script for state-of-charge estimation using an sigma-point Kalman filter on lab-test data and evaluate results – Implement method to detect and discard faulty voltage-sensor measurements
This week, you will learn some rigorous definitions needed when discussing SOC estimation and some simple but poor methods to estimate SOC. As background to learning some better methods, we will review concepts from probability theory that are needed to be able to deal with the impact of uncertain noises on a system’s internal state and measurements made by a BMS.
This week, you will learn how to derive the steps of the Gaussian sequential probabilistic inference solution, which is the basis for all Kalman-filtering style state estimators. While this content is highly theoretical, it is important to have a solid foundational understanding of these topics in practice, since real applications often violate some of the assumptions that are made in the derivation, and we must understand the implication this has on the process. By the end of the week, you will know how to derive the linear Kalman filter.
The steps of a Kalman filter may appear abstract and mysterious. This week, you will learn different ways to think about and visualize the operation of the linear Kalman filter to give better intuition regarding how it operates. You will also learn how to implement a linear Kalman filter in Octave code, and how to evaluate outputs from the Kalman filter.
A linear Kalman filter can be used to estimate the internal state of a linear system. But, battery cells are nonlinear systems. This week, you will learn how to approximate the steps of the Gaussian sequential probabilistic inference solution for nonlinear systems, resulting in the “extended Kalman filter” (EKF). You will learn how to implement the EKF in Octave code, and how to use the EKF to estimate battery-cell SOC.
The EKF is the best known and most widely used nonlinear Kalman filter. But, it has some fundamental limitations that limit its performance for “very nonlinear” systems. This week, you will learn how to derive the sigma-point Kalman filter (sometimes called an “unscented Kalman filter”) from the Gaussian sequential probabilistic inference steps. You will also learn how to implement this filter in Octave code and how to use it to estimate battery cell SOC.
Kalman filtering requires that noises have zero mean. What do we do if the current-sensor has a dc bias error, as is often the case? How can we implement Kalman-filter type SOC estimators in a computationally efficient way for a battery pack comprising many cells? This week you will learn how to compensate for current-sensor bias error and how to implement the bar-delta method for computational efficiency. You will also learn about desktop validation as an approach for initial testing and tuning of BMS algorithms.
You have already learned that Kalman filters must be “tuned” by adjusting their process-noise, sensor-noise, and initial state-estimate covariance matrices in order to give acceptable performance over a wide range of operating scenarios. This final course module will give you some experience hand-tuning both an EKF and SPKF for SOC estimation.

## COURSE 4 - Battery State-of-Health (SOH) Estimation

In this course, you will learn how to implement different state-of-health estimation methods and to evaluate their relative merits. By the end of the course, you will be able to:

– Identify the primary degradation mechanisms that occur in lithium-ion cells and understand how they work – Execute provided Octave/MATLAB script to estimate total capacity using WLS, WTLS, and AWTLS methods and lab-test data, and to evaluate results – Compute confidence intervals on total-capacity estimates – Compute estimates of a cell’s equivalent-series resistance using lab-test data – Specify the tradeoffs between joint and dual estimation of state and parameters, and steps that must be taken to ensure robust estimates (honors)
As battery cells age, their total capacities generally decrease and their resistances generally increase. This week, you will learn WHY this happens. You will learn about the specific physical and chemical mechanisms that cause degradation to lithium-ion battery cells. You will also learn why it is relatively simple to estimate and track changes to resistance, but why it is difficult to track changes to total capacity accurately.
Total capacity is often estimated using ordinary-least-squares (OLS) methods. This week, you will learn that this is a fundamentally incorrect approach, and will learn that a total-least-squares (TLS) method should be used instead. You will learn how to derive a weighted OLS solution, to use as a benchmark, and how to derive a weighted TLS solution also.
Unfortunately, the weighted TLS solution you learned in week 2 is not well suited for efficient computation on an embedded system like a BMS. As an intermediate step toward finding an efficient weighted TLS method, you will first learn a proportionally weighted TLS method this week. You will then learn how to generalize this to an “approximate weighted TLS” (AWTLS) method, which gives good estimates, and is feasible to implement on a BMS.
So far this course, you have learned a number of methods for estimating total capacity. This week, you will learn how to implement those methods in Octave code. You will also explore different simulation scenarios to benchmark how well each method works, in comparison with the others. The scenarios are representative of hybrid-electric-vehicle (HEV) and battery-electric-vehicle (BEV) applications, but the principles learned can be extrapolated to other similar application domains.
In the third course of the specialization, you learned how to use extended Kalman filters (EKFs) and sigma-point Kalman filters (SPKFs) to estimate the state of a battery cell. In this honors week, you will learn how to extend those concepts to apply EKF and SPKF to estimating the parameters of a battery-cell model if the state is known, and also how to simultaneously estimate both the state and parameters of a cell model.
You have learned several different total-capacity estimation methods. Some of these methods work better than others in general, but any method is only as good as the data you give it. In this project, you will explore a different way to determine the “x” and “y” data you use as input to the total-capacity estimation methods.

## COURSE 5 - Battery Pack Balancing and Power Estimation

In this course, you will learn how to design balancing systems and to compute remaining energy and available power for a battery pack. By the end of the course, you will be able to: – Evaluate different design choices for cell balancing and articulate their relative merits – Design…

In this course, you will learn how to design balancing systems and to compute remaining energy and available power for a battery pack. By the end of the course, you will be able to:

– Evaluate different design choices for cell balancing and articulate their relative merits
– Design component values for a simple passive balancing circuit
– Use provided Octave/MATLAB simulation tools to evaluate how quickly a battery pack must be balanced
– Compute remaining energy and available power using a simple cell model
– Use provided Octave/MATLAB script to compute available power using a comprehensive equivalent-circuit cell model

The Bellman-Ford algorithm; all-pairs shortest paths.
NP-complete problems and exact algorithms for them.
Approximation algorithms for NP-complete problems.
Local search algorithms for NP-complete problems; the wider world of algorithms.
Present-day BMS algorithms primarily use equivalent-circuit models as a basis for estimating state-of-charge, state-of-health, power limits, and so forth. These models are not able to describe directly the physical processes internal to the cell. But, it is exactly these processes that are precursors to cell degradation and failure. This week quickly introduces some concepts that might motivate future BMS algorithms that use physics-based models instead.

This capstone project explores the design of resistor value for a switched-resistor passive balancing system as well as enhancing a power-limits method based on the HPPC approach.