0
$\begingroup$

I'm in the first year of computer engineering and I feel completely lost when it comes to solving hard programming exercises. I think it's due to a bad modus operandi. And that is why I'm asking this question. My question is that: what do you do when you have to do a difficult task? In other words, what do you do when you have to deal with algorithms that are not so obvious. How do you deal with those tasks?

$\endgroup$
2
2
$\begingroup$

Here are some tips for reading algorithms, but also for coming up with new ones. Almost all algorithms are composed of multiple conceptual steps. What counts as a conceptual step depends on context and your personal background, but usually it is more than a mere increment like $i \leftarrow i + 1$.

  • make conceptual steps explicitly: sometimes the way algorithms are written down do not show the steps explicitly or show them already intermingled (e.g., for efficiency of execution). Try breaking down (or reformulating) the algorithm in a way that shows all steps explicitly in a granularity that suits you.
  • understand which granularity of steps suits you: e.g., avoid unfolding loops, avoid unfolding recursion. Almost always, doing so is counterproductive to understanding an algorithm. Instead, formulate invariants for loops or use induction hypotheses for your conceptual understanding (see next point).
  • state invariants, pre-, and post-conditions for every step to improve your understanding of what every step expects, computes, and returns.
  • execute the algorithm with a toy example as input that is neither too trivial nor too complicated. Follow the input and output data between each step.

Example 1: Wikipedia shows a recursive algorithm to solve Tower of Hanoi. It looks deceptively simple, being only five lines of Python code.

def move(n, source, target, auxiliary):
    if n > 0:
        move(n - 1, source, auxiliary, target)
        target.append(source.pop())
        move(n - 1, auxiliary, target, source)

As a freshperson back then, I had a hard time understaind this algorithm in my first semester of CS. I had always tried unfolding the recursion to understand its inner workings -- but that's massively counterproductive. Instead, key to understanding was:

  1. formulate pre-condition and post-condition for move
  2. use the technique of induction to understand the code's correctness/functionality:
    • for $n = 0$, we understand that move is correct
    • for $n > 0$, in lines 3 and 6 we take for granted that the calls to move(n - 1, ...) work correctly for valid input. Thus, we only have to verify whether inputs supplied in these function calls is valid in the sense of pre-conditions formulated in Step 1.
$\endgroup$
1
$\begingroup$

With practice, many things that are hard for you today won’t be hard in the future.

To solve problems that stay hard, number one advice: Talk to someone else. Explain the problem and why it is difficult. That step alone often solves the problem! Or you get advice, or at least ideas how to tackle the problem. And sometimes, the problem just is hard.

And in many cases, the advice will tell you that you don’t actually need to solve the hard problem. Many people start with a problem x, figure out that they can solve x by solving y, and then y turns out to be hard - and ignore other ways to solve x.

$\endgroup$
1
  • 1
    $\begingroup$ Good answer! Also important is to first understand the problem, and then try to break it up into pieces that are more manageable. $\endgroup$
    – Pål GD
    Nov 19 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.