Data Structures, Design Patterns & Algorithms in Java

Operating Systems Concepts for IoT (Internet of Things)

2019-01-19T10:17:00.000-08:00

Fundamentals

A task is a program, program unit, process, or thread (lightweight process). It could be a sequential function with an infinite loop. Usually can be of two types user or kernel.

Why do we need an operating system (OS)?

Manage hardware and software resources
Power Management
Task schedulers
Task management
supports multitasking
Inter-process communications
Memory allocation and management
Managing I/O devices and peripherals

Analog

motors
valves

Digital
Hardware Interrupts

ISR (Interrupt Service Routines)

Task Scheduling Algorithms

Time-sharing task scheduling

Pre-emptive
Non-preemptive

Priority-based Round Robin Scheduling

Timers

Internal core timers
Software timers

One shot timers
Auto-reloaded timers

Task Management

Managing the Task States

Running
Not Running

Ready
Suspended
Blocked

Context Switching

Race Condition

Undesirable condition when multiple tasks (or threads) try to access and change the shared data simultaneously.

Thread Safety

Locking shared resources/data using a critical section
Intertask communication

Deadlock

Two tasks are waiting for the same resource held by the other

Deadlock Prevention

- planning resource allocation

Interprocess Communications

- Message Queues

- Interrupts

- Mutex - provides mutual exclusion when concurrent tasks access a shared resource

- semaphore

Dynamic Memory Allocation

- Heap

- First Fit Memory Allocation

Static Memory Allocation

- Stack

Characteristics

Small Footprint
Modularity
Extensibility
Flexible
Easy to use API
Portability
Tools Support

Should we use an OS in IoT?

to build an ecosystem for device drivers.
support for extensibility
Security

Why ecosystem

vendor
open source community
user support
community

IoT System

managing processor

Types of Operating Systems

General Purpose

rich functionality
complex functionality

Embedded OS for resource constraint device

e.g. coffee machines, smart sensors, wireless routers
small footprint
high reliability
for optimized performance
e.g. FreeRTOS (real-time OS), Android Things
limited file system support

Definition of Data Structures

2019-01-19T06:57:00.002-08:00

Definition

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Understanding data structures is a must for every programmer as it clarifies the working of inner data for a program.

Below are the examples of data structures from real life

shopping list
bank statement - intentional list of transactions where each transaction is an intentional arrangement of data fields like information, date, amount, involved parties etc. with a chronological order to
telephone directory
dictionary
thesaurus
encyclopedia
movie ticket availability
railway time table
flight schedule
mobile phone plans (showing various monthly packages)

Facebook Edgerank Algorithm Explained

2012-11-16T18:10:00.001-08:00

the Edgerank algorithm is used in Facebook to determine the order of posts that should be shown on a user's Top News feed.

Flyweight Design Pattern

2012-11-04T19:16:00.001-08:00

The flyweight design pattern is used to dramatically increase the speed of code when using many similar objects.

To reduce memory usage the flyweight design pattern shares Objects that are the same rather than creating new ones.

Bridge Design Pattern

2012-11-04T19:05:00.001-08:00

This pattern is used to build a group of classes that slowly adds functionality from one class to the next.

Facade Design Pattern

2012-11-04T18:53:00.001-08:00

English: Author: Alcides Carlos de Moraes Neto (wikipedia.10.alcides@spamgourmet.com) (Photo credit: Wikipedia)

The Facade pattern simplify methods so that most of the processing is done in the background. In technical terms it decouples the client from the sub components needed to perform an operation.

Iterator Design Pattern

2012-11-04T18:38:00.001-08:00

The Iterator design pattern illustration, UML diagram. (Photo credit: Wikipedia)

The iterator pattern is used to access objects that are stored in many different types of collection.
This is done by creating a common interface that all the different collection classes share. Then an iterator is provided to traverse the objects they contain.

Because all different Collection classes share a common interface they can be treated polymorphically and it eliminate duplicate code.

Below is the video tutorial for the Iterator pattern

State Design Pattern

2012-11-04T17:00:00.001-08:00

English: UML Class Diagram of the State Design Pattern (Photo credit: Wikipedia)

Below is the video tutorial on State Design Pattern

Command Design Pattern

2012-11-04T16:39:00.001-08:00

The UML diagram describing relations between objects of the Command design pattern. (Photo credit: Wikipedia)

The UML diagram which describes the structure of the Command design pattern. (Photo credit: Wikipedia)

public interface Computer {
void start();
void shutdown();
}

public class Laptop implements Computer {
public void start() {
System.out.print("Laptop is started");
}

public void shutdown() {
System.out.print("Laptop is shutdown");
}

}

public interface Command {
void execute();
void undo();
}

public class StartLaptop implements Command {
Computer theComputer;

public StartLaptop (Computer newComputer ) {
theComputer = newComputer;
}

public void execute() {
theComputer.start();
}

public void undo() {
theComputer.shutdown();
}
}

Below is the video tutorial about the Command pattern.

Singleton Design Pattern Tutorial

2012-11-04T00:08:00.001-07:00

Singleton Pattern is used to prevent instantiation of an object more than once.

Abstract Factory Design Pattern

2012-11-03T23:57:00.001-07:00

Factory Design Pattern

2012-11-03T23:52:00.001-07:00

Factory design pattern is used to define the class of an object at runtime. It allows encapsulating object creation to keep all object creation code in one place. (separation of concerns)

You cannot instantiate an abstract class. It is just there to facilitate polymorphism.

Basic Principles of Object Oriented Technology

2012-11-03T22:53:00.001-07:00

Algorithm Types

2010-06-29T01:41:00.001-07:00

Below are the list of categories into which various algorithm can be categorized:

Simple recursive algorithms
Backtracking algorithms
Divide and conquer algorithms
Dynamic programming algorithms
Greedy algorithms
Branch and Bound algorithms
Randomized algorithms

ArrayList or LinkedList ...??

2010-06-28T07:08:00.000-07:00

ArrayList or LinkedList ...?? compares ArrayList and LinkedList

Lecture Series on Design & Analysis of Algorithms

2010-06-28T01:06:00.000-07:00

Computer Sc - Design & Analysis of Algorithms
Lecture Series on Design & Analysis of Algorithms by Prof.Abhiram Ranade, Department of Computer Science Engineering,IIT Bombay.

2010-06-24T04:06:00.001-07:00

Refcardz #08: Design Patterns

List of Algorithms

2010-06-24T03:53:00.000-07:00

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.

Algorithms are a sequence of steps for accomplishing a task. We use complex algorithms in our day to day tasks for eg. searching in Google, sending emails, booking air tickets etc.

an example on insertion sort (Photo credit: Wikipedia)

Characteristics of algorithms
Performance (memory & CPU)
Simplicity

List of Algorithms

Finding Maximum
Order Statistics
Matrix Multiplication
Comparison
Linear Search
String searching algorithm (Photo credit: Wikipedia)
Binary Search
Selection Sort
Insertion Sort
Bubble Sort
English: an example on bubble sort. (Photo credit: Wikipedia)

English: Sorting a random list using bubble sort (Photo credit: Wikipedia)
Heap Sort
Merge Sort
English: Sorting a random list using merge sort. (Photo credit: Wikipedia)

English: an example on merge sort. (Photo credit: Wikipedia)
Radix or Bucket Sort
Random algorithms - improves the worst case performance

Quick Sort
Finding Median

Hashing
Fibonacci sequence
Spanning Tree
Shortest Path - finding the shortest path from one point to another.

Djikstra's algorithm

String Searching
String Matching

NP-complete or NP-hard problem has no known good optimal solution. If someone finds an efficient algorithm for one NP-hard problem, then that algorithm would be applicable to all NP-hard problems.

List of Design Patterns

2010-06-24T03:48:00.000-07:00

LazyList-Iterator (Photo credit: propella)

singleton
iterator / enumerator
decorator
facade
listener
publisher-subscriber
factory
Factory Method pattern in LePUS3 (Photo credit: Wikipedia)
abstract factory - A tutorial about abstract factory design pattern
The Abstract Factory pattern illustration, UML diagram. (Photo credit: Wikipedia)

Abstract Factory (Photo credit: Wikipedia)
Model View Controller (MVC)
English: This diagram depicts how the Model View Controller Architecture works. (Photo credit: Wikipedia)

English: The model, view, and controller (MVC) pattern relative to the user. (Photo credit: Wikipedia)

Deutsch: Model View Controller (Photo credit: Wikipedia)
Inversion of Control (IoC)

List of Data Structures

2010-06-24T03:46:00.000-07:00

Below is the list of important data structures

Simple Data Structures

Primitive Data Types

Boolean
Numbers
String

Structures (structs)

Points (x & y coordinates), Color (red, green, blue, alpha)

Objects (Custom Data Types)
Collections

Arrays

single -dimensional arrays
multi-dimensional arrays

two-dimensional arrays (rectangular),
three-dimensional arrays,
and so on...

Jagged arrays (ex. daily sales per month )

Lists

ArrayList (resizable, dynamic or mutable arrays)
Vector

Operations

Appending (Push) - adding an element at the end
Insertion / Add - adding in the middle at a specified index
Removing (Pop) - deleting an element at the end
Deletion - removing an element at a specified index
Splice - (adding and removing)
Search / Find / Contains - searching for an item and returning location
Sort - ordering the data

Linked List

Singly Linked List

Definition: A data structure consisting of a group of nodes where each node is composed of data and a reference (or a link) to the next node in the sequence.
Operations

Insertion
Deletion
Find / Search
Traversal

Iterative
Recursive

Reversal

Iterative
Recursive

Doubly Linked List

Definition: A data structure consisting of a group of nodes where each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
Operations

Insertion
Deletion
Traversal
Reverse Traversal

Circular Linked List

Abstract Data Type

Queue - First In, First Out

Examples - Job Queue
Operations

Enqueue - adding an element at Last
Dequeue - removing an element from Front

Stack - Last In, First Out

Operations

Push
Pop
Peek

Priority Queue
Double-ended Queue (Deque) - supports adding deletion from both ends
Hash-Based Data Structures

hash table illustration, with three keys, funcbox, sparse range, no collisions, only the values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 3 -funcbox 1 -sparse 1 -keys 0 -values 1 -collisions 0 -links 0 -overflow SP (Photo credit: Wikipedia)

hash table illustration, with three keys, sparse range, buckets are links, collisions resolved by separate chaining, keys and values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 5 -funcbox 0 -sparse 1 -keys 1 -values 1 -collisions 1 -links 1 -overflow LL (Photo credit: Wikipedia)

Associative Arrays

Invariants

Unique Keys

Operations

Add
Remove

Hash Tables / Hash Map / Dictionaries

create with an initial capacity
Hash Collision

separate chaining

Set / HashSet

unordered collection of objects
No sequence
No duplicates
Fast lookup - for checking membership, not retrieval
Operations

add
remove
contains

Tree

Binary Tree

A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. (Photo credit: Wikipedia)

Binary Search Tree

invariants

no duplicates

operations

add
delete
find
traverse

pre-order
in-order
post-order

Self Balancing Trees

AVL Tree
Red-Black Tree - (implementation of TreeMap in Java uses this)
Scapegoat Trees
Splay Trees

Segment Tree (for min/max/sum range queries)
Fenwick Tree (Binary Indexed Tree)
Heap (Min Heap or Max Heap)

A method for implementing Double ended priority queue(DEPQ) (Photo credit: Wikipedia)

Graph

Directed Graph
Undirected Graph
Weighted Graph

Trie
Disjoint Set
Bloom Filter
Consistent Hash Ring
Maps
Ternary Search Trees
B-Trees
Graph

Data Structures, Design Patterns & Algorithms in Java

Operating Systems Concepts for IoT (Internet of Things)

Definition of Data Structures

Definition

Facebook Edgerank Algorithm Explained

Flyweight Design Pattern

Bridge Design Pattern

Facade Design Pattern

Iterator Design Pattern

Related articles

State Design Pattern

Related articles

Command Design Pattern

Related articles

Singleton Design Pattern Tutorial

Abstract Factory Design Pattern

Factory Design Pattern

Basic Principles of Object Oriented Technology

Algorithm Types

ArrayList or LinkedList ...??

Lecture Series on Design & Analysis of Algorithms

List of Algorithms

Related articles

List of Design Patterns

Related articles

List of Data Structures

Related articles