6

Buffy is provably correct (no risk needed!) that it is impossible to do it with automated code analysis, as this is an attempt to figure out when a program will finish (i.e. the halting problem.) You can get a very good guess, however, by using a few (very) differently sized input data sets, run the program on each one multiple times, and observe the ...


4

I'll accept a bit of risk here, but claim that this isn't possible in general unless the student writes very naive code. But in the courses for which you want to use it, that doesn't seem likely. Imagine a linear algorithm implemented as two nested loops. The outer loop depends on the "n" that you are interested in, say the length of an array. The inner ...


3

How about Huffman encodings? Given a text that uses an alphabet of $n$ unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits? More formally for Huffman encodings (as formulated by Tardos & Kleinberg in their book Algorithm Design): Given an alphabet and a set of frequencies for letters, we ...


2

One nice problem that I found is: Given n segments in 2D Euclidean space, find two segments that intersect. Seek for $O(n \cdot log(n))$ solution. https://cp-algorithms.com/geometry/intersecting_segments.html


2

The key to learning this, or much of anything, is reinforcement and feedback. Reinforcement comes from doing exercises and solving problems in a course like this and the book has plenty of mid chapter and end chapter exercises and problems. You can do a lot of these. All of them may be asking too much, but you want to be able to answer any of them. Getting ...


1

For anyone with a similar question who reads this in the future, I found this very helpful series of YouTube videos concerning algorithms. I liked it because the series covers topics in a similar order to the book. There is no assumption of what you do or don't know, material is covered from the ground up. Each video provides multiple examples of problems.


1

Another one is the following job scheduling problem: N jobs are arriving with priorities: priority_1 arrival_time_1 execution_time_1 priority_2 arrival_time_2 execution_time_2 ... priority_N arrival_time_N execution_time_N The arriving jobs are queued. When the CPU can process the next job, he will pick the one that has already arrived and has the ...


1

MergeSort is fairly easy to implement in Python and it's a straightforward divide-and-conquer algorithm. You keep splitting the collection in half until it is in trivial-to-sort pieces. This splitting reduces sorting from O(n^2) to O(nlog(n)). Second example: computing integer powers. if the power is even, square base and integer divide exponent by 2. ...


Only top voted, non community-wiki answers of a minimum length are eligible