Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
29

Similar to @Vince, I think it's a good practice to do both. I don't really agree with the cooking recipe analogy, though. Pseudocode describes that the algorithm does, without going into detail how you do it. I think perhaps a better analogy: Pseudocode: you need to put an egg into the flour mixture Actual code: pick up an egg, crack it open on the side of ...


20

Actually I am of the opinion that you should not present your own code, but rather get the students to implement the algorithms you teach them, which you give in pseudocode, and give them the freedom to choose any one of a fixed set of languages that you are familiar with, such as C++/Java/Python. Really, the only way students can truly understand an ...


13

Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $\log_a n = \Theta(\log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.


10

It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant. If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.


6

I understand your dilemma, but from a general pov it's better to present content through pseudocode. This actually gives students the freedom to explore multiple languages. When you present your code in a particular language you are making them comfortable with that language alone and they might find it hard to shift to other languages later on. The main ...


5

As $\log_xy = \frac{1}{\log_y{x}}$ and $\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$, so $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. As $\log_a{b}$ is positive constant (for all $a,b > 1$), so $\log_a{n} = \Theta(\log_b{n})$.


4

One of the key points here is that you are teaching to future engineers, even if at academic level. The very nature of engineering is solving problems by implementing a solution. Therefore I think that presenting the pseudocode is useful to give your student the correct theoretical POV to frame the problem, BUT showing them an actual, working ...


4

When I took algorithms, my first professor used a pseudo-code of his choosing. It may have been clear in his mind, but in was pretty opaque in they eyes of his students. It was a much dreaded class, and hard to get useful knowledge from. Then he had a heart attack. New professor (let's call him "Finkle"), discarded the previous class notes and textbook. ...


3

Let $P$ be the distribution of $i^*$, which you can calculate explicitly: $$ \begin{align*} p_i := \Pr[P=i] &= \left(1-\frac{i-1}{n}\right)^k - \left(1-\frac{i}{n}\right)^k. \end{align*} $$ This is the probability that all samples are at least $i$ minus the probability that they are all at least $i+1$. The counter $C(i)$ has binomial distribution $\...


3

The formula is wrong. The notation $f = O(g)$ is asymmetric, and has the meaning $f \in O(g)$. For more, check our reference question on Landau notation. Other relevant reference questions are this one and this one.


3

Forget the even-length requirement for a moment and consider how something like Dijkstra's algorithm works. As the algorithm progresses, you have essentially two types of vertex: the ones for which you've already figured out the shortest path, and the ones for which you only have an upper bound (i.e., the shortest path you've seen to that vertex so far). ...


3

Pseudocode helps a lot by removing anything unnecessary, and focusing entirely on the algorithm, which can already be hard to understand as is. It's also faster to express ideas : if a student wants to write a different algorithm than the one you taught them, it can be really cumbersome if they have to deal with every details of Java. As others said, it's ...


2

These two cases are already counted in the recursive calls g(n-1). A**** A**** BB*** g(n-1) g(n-1) counts all possibilities to fill the empty space in this ^ form. One way would be to fill it out like the following image, so this case already gets counted and you don't need to add another recursive call. AC*** AC*** BB***


2

Based on insights in the other answers, one simple and quite efficient algorithm is: Set $r = 0$. Choose the top $k$ values of $x_i - ry_i$ (using, e.g., quickselect in $O(n)$ time). Sum the chosen $x_i$ into $X$ and the $y_i$ into $Y$. If $X - rY > 0$: Set $r = X / Y$. (This will strictly increase $r$.) Go to step 2. The idea is to determine a set of ...


2

A quantity $a$ is bounded above by a quantity $b$ if $a \leq b$. A quantity $a$ is bounded above (up to constant factor) by a quantity $b$ if there exists a constant $C>0$ such that $a \leq Cb$. (This makes sense when $a,b$ depend on some other variable). A quantity $a(n)$ is bounded above (up to constant factor) asymptotically by a quantity $b(n)$ if ...


2

For a node $i$ with children $j_1,\ldots,j_d$, let us denote the best solution for the subtree rooted at $i$ by $\tau(i)$; you're interested in $\tau(r)$, where $r$ is the root. The function $\tau$ satisfies the recurrence $$ \tau(i) = \min(0, \sigma(i) + \tau(j_1) + \cdots + \tau(j_d)). $$ Indeed, there are two cases to consider. Either we take no vertex, ...


2

Writing from a students point of view: I had a course regarding algorithms and data structures two years ago. The first exercise consisted of implementing a program with a certain behavior (Search in a sorted array, etc.). In the next lecture we would discuss an algorithm in pseudocode which fulfills the requirement of the previous exercise, only in a ...


2

Neither alone is enough for a good dish. I'd go with pseudo code in the lecture, and use homework to give students practice in turning pseudo code into real code. Using pseudo code in the lecture has the pragmatic reason that pseudo code is, by nature, somehow vague. You want to use it as a tool to be able to concisely state ideas that still contain all ...


2

Let's prove a more general result: Any sorting algorithm which only swaps adjacent elements makes $\Omega(n^2)$ swaps on average. Let us assume that the elements being sorted are $1,\ldots,n$, and their positions are $i_1,\ldots,i_n$. We need to move element $j$ from position $i_j$ to position $j$. Each swap changes the position of two elements by 1. It ...


2

The running time of both BFS and DFS are $\Theta(V+E)$ since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study). It is not surprising that the ...


2

Your problem is NP-hard, by reduction from clique. Given a graph $G=(V,E)$ and a number $k$, we construct a graph with $k$ internal layers, each containing $|V|$ vertices. All vertices in a layer are connected to all vertices in the following layer. The weight of an edge is $0$ if the corresponding edge is not in $G$, and $-1$ otherwise. We also add shortcut ...


1

Here are some more hints: The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle. When $n=4$, the ...


1

There is an ambiguity in the specification of the bubble sort algorithm given in the start of the post. In fact, there are multiple versions of the bubble sort algorithm. Variations of bubble sort. One simple version is presented in exercise 2.2. of CLRS, version 2 which does $n-1$ iterations, where each iteration performs one less comparison than the ...


1

Answer: the low-link value is not the identifier. I eventually found this while researching during the writing of this question. Question posted because I wrote it and hey, maybe this will help someone else. Everything up to the current node is popped off the stack when identifying an SCC. My misunderstanding was trying to pop only what has the same low-...


1

Let me show you how to solve these without using the master theorem. For the first item: $$ T(n) = n\log n + \frac{n}{2} \log \frac{n}{2} + \frac{n}{4} \log \frac{n}{4} + \cdots \leq \left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) \log n \leq 2n\log n. $$ This shows that $T(n) = O(n\log n)$. Since clearly $T(n) = \Omega(n\log n)$, we can conclude that $...


1

The count of any rectangle $C(U, L, D, R)$ can be obtained combining the counts of 4 fixed "upper-left" retangles: $C(U, L, D, R) = C(0, 0, D, R) - C(0, 0, U, R) - C(U, 0, D, L) + C(0, 0, U, L)$, noting $C(up, left, down, right)$ the count in the rectangle delimited by $(up, left, down, right)$. Thus, you cannot expect more than a factor 4 runtime ...


1

I think the best is to do a comparison. The algorithm may be a cooking recipe that may be written in many languages but produce always the same cake. Pseudo-code is like describing the recipe with pictures. There is not a unique grammar or way to "talk" in pseudo-code but anyone should be able to interpret it. By reading the pseudo-code written by someone, ...


1

For an optimal selection, one possible sequencing is always the one respecting the order of arrival time $S_0$. Another may be possible, but you can check that you always can do the switches to obtain $S_0$. This is due to the fact that all jobs have the same $d$. Thus, your problem is equivalent to select the subset of jobs which do not overlap if they are ...


1

Ok as you have a working solution but seem concerned by optimization, I will detail here how to do it very efficiently. I assume that your rectangle has to follow the discretized grid (I now have a doubt on it reading your question). Let's build 2 $n \times m$ count arrays $NB$ and $NW$ which are the number of respectively black and white points in each ...


1

First, we have some basic observations: The minimum number of steps to convert $N$ to $0$ equals to the minimum number of steps to convert $0$ to $N$. To convert $0$ to $N$, the optimal way would be to apply Operation 1 and 2 alternatively. Now consider the bit sequence $b_1\ldots b_m0$. After performing Operation 1 and 2 alternatively, we get $$b_1\ldots ...


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