Author: Stan Eisenstat
Subject: Re: [Cs223] Writing efficient algorithms
Date: Monday, 30 Mar 2020, 21:13:17

    > Message Posted By: Unknown
    >
    > I find myself struggling at times to write efficient code/come up with
    > efficient algorithms. For example, when I completed the sample midterm on
    > my own for the the first time, I was able to come up with a solution for
    > problem 5 that met the 2/3 credit requirement, but after that I hit a
    > brick wall. ...

That problem was one of the review problems for the
midterm; I gave several solutions at the review session.
=====

    >        ...  When you explained the algorithm that met the full credit
    > requirement in class, it made perfect sense to me and I could come up with
    > it now, but I don't know if I could have ever figured that out on my own
    > without some guidance. ...

The ability to devise new algorithms is something that
develops with practice.
=====

    >                   ...  On the current problem set, I found it pretty easy
    > to meet the 4*#compares + N requirement, but I have also hit a wall here
    > with finding a solution that meets the 2*#compares + N requirement.

The key idea is that in Note C.5 of the specification:

  5. Achieving C * #compares calls to addD()/pushD() by calling them at most
     C*M times at the level of recursion where there are M items to sort.

Your solution satisfies this with C = 4; to achieve C = 2
you have to reduce the amount of data movement.  The other
parts of Note C are also relevant.
=====

    > It's frustrating for me because I really want to get better at solving
    > problems like these on my own the first time without any guidance. I
    > realize that this is a pretty general question, but do you have any
    > suggested resources for getting better at this kind of thing (advice,
    > books, etc.)?

Read the textbook for CPSC 365.

--Stan-