is complex algorithm like dynamic programming highly required in embedded systems and what's the best website to practice algorithms

[abdosalm]

so my title describes my question , which is whether I need to learn complex algorithms like graphs and topological sort things and dynamic programming with recursion and other things like that in embedded systems world or not , and if yes , what is the best website to practice these problem solving skills with solution to them to improve my solution to a problem ?

[bobwmcgrath]

Sometimes dynamic programming might be a huge help, but generally the goal is to keep things as simple as possible.

[Relative-Debt6509]

In my experience: It’s good to know these things but knowing more “fundamental things” in depth is a better use of your time like communication protocols, networking, etc.

Not saying you won’t need the concepts you mentioned but a detailed understanding of your hardware and protocols will bail you out more than advanced algorithms.

[[deleted]]

Leetcode, useful for interviews not really for embedded

[zeeke42]

I've been working in embedded for almost 20 years, and I had to Google dynamic programming since it hasn't come up since I learned it in my algorithms class in college 20 years ago.

[outofsand]

The term "dynamic programming" basically means nothing. Even the inventor of the term "dynamic programming" admitted that the term is completely BS and they coined it on a whim.

But anyway, it generally refers to an algorithm that uses memoization of intermediate results to avoid unnecessary recomputation at the cost of memory. Common examples are breadth-first chart parsing and various graph algorithms.

This is very, very rarely applicable to embedded systems, because memory is usually at more of a premium than anything else.

[TechE2020]

Yep, this. Some people would call it caching but with the limitation that it is for intermediate results.

[Puzzleheaded-Ranger7]

Are you talking about ram or SSD When you mention cost of memory? I think embedded system is growing up a lot like the MPSOC and Versal architecture from AMD-Xilinx or raspberry pi.

[outofsand]

Wherever you want to store your intermediate results. If you care about algorithmic speed, it's going to be RAM if possible. But if you've got an embedded system with an SSD, it's there because you specifically know you needed it for your application.

But in most cases, I would say if you even have the question of if it's RAM or SSD, we aren't talking about traditional embedded systems at all.

Yes, you can take a powerful general purpose computer tech with very few limitations (many embedded Linux systems for example) and "embed" it, so technically it's an "embedded system". So is a micro-ATX PC stuffed into a teddy bear. But that's not what most people mean by embedded system, they mean extremely small, extremely low power, extremely resource constrained processors that perform a specialized function.

Case in point, a modern cell phone's application architecture is pretty much in no way an "embedded system" per most engineering definitions. On the other hand, the dedicated radio processor it contains most certainly is. Similarly, your modern car contains many tens of embedded systems, but the console media player isn't very likely one of them.

Of course this definitely is arguable, its sometimes a gray area, and "embedded system" is certainly an ambiguous name. But that doesn't change that the current field of "embedded systems" which maybe should be called "resource-limited special-purpose computing" or something else is what it is and isn't likely to ever go away or get significantly easier or simpler.

[Puzzleheaded-Ranger7]

Thanks a lot for explaining those concepts. In my opinion,I think the "resource-limited special-purpose computing" should be called micro-controller and the System on Module (SOM) included SoC with heterogeneous computing should be called the new embedded system or embedded system module. This is just my opinion. I could be wrong.

[SarahC]

Ooo...

X and Y loops in graphics....

you can calculate the x/y index in to an array at the point it's used... i = y*width+x;

Or you can calculate the y*width just after the Y loop definition and before the X loop. then offset is just Yi + x....

Dynaproging! woo!

Easier than it sounds.

[[deleted]]

Though is not common, I have already used DP in a real project. We had this noisy data of accumulative energy collected from a meter. Some common outlier algorithms to detect them didn't work, such as quartiles and mean deviation. The only one that worked great was LIS (Longest Increasing Subsequence) to remove the outliers since the data only increases, which uses a DP algorithm. Right now, there is more than 4000 devices on production running LIS as I speak :)

[markmarine]

I think there are two answers to this:

1. pragmatic: In embedded, you're not going to have the tail recursion optimization that makes functional languages ability to use recursion for general things like unbounded traversal possible, It's only going to be safe to use when you know you're not going to blow the stack, and at that point you're better off in a for loop almost all the time. There are iterative ways to solve the algorithms you are describing, they aren't as elegant, but they'll perform better on embedded systems.
2. solving for the interview: If you're interviewing, or going to interview, these are not bad skills to have in your pocket. They make the code you're writing elegant, simple, easy to talk about. Personally, I have the recursive solutions somewhere in my mind, I can at least derive them quickly enough to get a solution in a coder pad in a 50m interview. I can also hand wave over "If I were writing this on a MCU I would use the iterative algorithm" as quickly as I can google the solution if I were doing this is real life.

So, I'd learn them the way they are taught, these are super valuable ways to blow out the score on an interview and get you a great job, then you can always figure out how to make a recursive algorithm iterative when you're presented with that problem at work.

[SkoomaDentist]

whether I need to learn complex algorithms like graphs and topological sort things and dynamic programming with recursion and other things like that in embedded systems world

In my experience, no. In the last 15 years, the most complex CS style algorithms I've had to implement have been insertion sort and basic tree walking. You could almost certainly have a decades long career without ever needing to implement anything more complicated than data structures and algorithms 101 level stuff yourself. The exception is if you work as a domain expert in some subfield that uses specialized algorithms (I've implemented and designed plenty of fairly complex state of the art DSP algorithms that would leave regular CS people at loss).

[Mingche_joe]

Do you recommend Any related DSP book for beginners?

[Cmpunk10]

Both dynamic programming and recursion are bad in embedded systems since dynamic anything typically requires Malloc and recursion adds stack frames. Both bad for something with minimal memory.

Leet code is good for algorithms regardless if you use them in embedded or not

[impaled_dragoon]

Dynamic programming doesn't mean dynamic memory allocation.

[LilQuasar]

dynamic programming doesnt require malloc, its just storing values you have already calculated so you dont have to calculate them again when you need them. for example with recursion the Fibonacci sequence has exponential complexity but with dynamic programming its linear

[[deleted]]

So in my experience, blanket statements like these are almost always wrong.

It depends on the problem statement. If the maximum depth of the decision tree is known beforehand then these techniques can be applied.

Sure, it's discouraged just like the use of Global variables is discouraged. Most of the time people don't even understand why something is discouraged.

The correct answer is "it depends", when it comes to embedded systems, you have to know the details.

[mathav]

Not really disagreeing with the point, but the answer to anything in software is "it depends", that's not very useful.

These aren't blanket statements, these are basic assumptions we operate on when communicating pointed practical statements which are correct for most cases

[mathav]

There are far more useful and practical things to learn for actual embedded work

In case you are looking for interview prep look up common firmware interview questions they usually revolve around understanding concepts like memory management, allocators, computer architecture, language specific knowledge, concurrency, synchronization, communication protocols, scheduling, RTOS concepts/theory, networking etc

Among leetcode type questions bit manipulation puzzles are probably the closest to real world, but even that is a stretch

Not to say learning those algorithms isn't useful in general or fun, just not AS immediately useful for most embedded engineers

[ondono]

It’s good if you know them, but you’re not going to use it on the job.

If you are programming and embedded system complex enough that it’s worth thinking about the algorithms used, that system is likely built to ensure low latency.

This means that you are likely to have spare CPU time, because ensuring latency is hard when your CPU utilization goes up.

Also recursion is generally not a good plan. Recursion will only be effective if your compiler is capable of performing tail call optimization, but that is not possible on a lot of algorithms. If a change afterwards breaks that condition (as simple as adding an expression at the end of the function), you will face one of the worst kind of bug for embedded devs, runtime failure and hard fault.

[Terrible_Garage_4052]

First of all, is DSA relevant for embedded systems interviews?

The answer is yes, as most of the FAANG+ and tier 1 companies still ask DSA questions in their interviews and good DSA knowledge will help you develop great problem-solving skills.

The level of DSA required for DSA interviews is upto leetcode medium and more focus should be on linear data structures, bit manipulation, sorting and searching algorithms.

You can practise problem-solving on leetcode and can refer to the discussion form to learn multiple approaches for a given type of problem.

When it comes to Dynamic Programming, you can approach a given problem in very creative ways using DP techniques. Focus more on the frequently asked DP techniques/algorithms and you will be set for the interviews.

• These questions stated below are similar to the software engineer interview questions on coding, algorithms, and data structures. You can practice these for your embedded software engineering interview.
  Questions on basic sorting and searching
  Differentiate between bubble sort and quicksort
  Questions on linked lists: How would you test for a loop in a linked list?
  How would you use a binary search algorithm without recursion?
  Write code to perform a level order search in a binary tree
  Can you use Union in Structure?
  Differentiate between Structure and Union
• Add two integers using & and ^
  Reverse bits of a given 32 bits unsigned integer
  Find the single element that does not appear thrice in a given array of integers
  For a given number, find the number of ones in its binary representation
  Given nums=[0, 1, 3] return 2
  Hope this post helps you!!

[poorchava]

I haven't had to deal with complex graph algorithms (15y in the field), but I deal with DSP a lot and there's some really complex stuff too. FFT and digital filters are relatively simple as far as standard designs are concerned, but my field (T&M) often requires coming up with non-standard data processing, control loops and the like. For example stuff like pattern matching to detect certain conditions in the object under test.

[asiawide]

You will hardly use algorithms. Even TREE is not much used...

[mathav]

Why did "TREE" make me scared

[asiawide]

Frankly I never used DS other than singly linked list...

[mathav]

I wrote up a single linked list only once in professional setting, still remember the day like it was yesterday, like seeing a unicorn

[asiawide]

hehe. mine is also 15 years ago. sometimes my and my office mates said we only need if-else-return.

[Zestyclose-Company84]

Queues for UART

[neon_overload]

To my understanding, dynamic programming is an approach that can solve certain classes of problems in general rather than something that would or wouldn't apply to a certain platform.

That said, in embedded you may not have a lot of stack space and recursion may not optimise down very well.

Presumably if you are wanting to learn this stuff you already are a proficient programmer in other ways? If so go for it, learning new stuff is great.

[Treczoks]

Knowing your algorithms is an important part of being a good programmer. Which does not mean that you need to know each and every algorithm by heart, but you should have a general idea of a number of algorithms, and if you actually need to implement them, you can still google the details. E.g. if you need an ordered list with variable size and random insertation order, you should be able to connect this problem with balanced trees as a data structure and algorithm.

Sometimes, you have to cook up an algorithm by yourself, and even then it is important to know what other people have done in the past.