Prof Luiz Araujo

Please find attached some practice questions. This document is under construction. DSA Practice Test Questions (updated on 13/02/2020)

This topic is typically addressed during the courses of Discreet Mathematics or Mathematics for Computer Science. I've added here a very generical road map for solving recurrences. First things first. You have a problem to be algorithmically solved. After writing your algorithm, you analyse its complexity. For divide and conquer, for example, we typically have recurrence functions - you express the runtime in terms of the runtime of the subproblems. For brute force, on the other hand, the running time is directly affected by the size search space or the number of all possible solutions. For solving recurrences you can use one (or more than one) of the following approaches: substitution, iteration, iteration with visual trees and master method (this one for the order of growth only). Let's see an example and try to obtain the closed form of a recurrence: A very strict proof would require an informed guess using Iteration, followed by the proof of the obtained cl...

Binomial trees and binomial heaps Binomial trees are used for implementing priority queues, but I've just learned that they are also used for predicting stock prices . It means that there are niches where this topic is extremely relevant, although we don't fully understand how. Notes from the board: Someone asked if it was a coincidence that the number of child nodes of the root was equal to the degree of the binomial tree. No, it's not a coincidence. Remember from the slides that there is a property stating the number of nodes in each level of the tree. A good question is how to prove this particular property not only for the level 1 (child nodes of the root) but for every level. Hint: Try a proof by induction. If you like this topic, you can dig deeper and read about its application into economics for predicting optimal stock prices. Research into this topic looks like this . Finally, I will try to post weekly some questions on the topics seen in lec...

Questions about the master theorem. Here is a copy from Cormen's book (Cormen et al.; Introduction to Algorithms; MIT Press): As you can see, there is no statement limiting f(x) to polynomial functions. Another thing is about the comparison between f(x) and n^log_b a. See the text below from the same book: Finally, some students googled about the cases and found subcases 2b, 2c, etc. We are using in this course Cormen's book since it is a trustful source used by top universities and has been revised several times. If these "subcases" are not in there, there is a reason for such. Let's stick to the book. Questions about dynamic programming. There are several ways of solving the problem in the given assignment. Probably most of the doubts are about how to describe each step. So here is a summary: For the algorithm, either top-down with memoization or bottom-up method are acceptable. For proving the correctness of the algorithm, a small paragraph wit...

The content of the tutorial: INORDER-TREE-WALK is Big-Theta(n) Randomly built BST Screens: The rest of the proof is in my notes, but I don't have a scanner. Another thing is that several students asked me to explain the expected value of a random variable. To them, I strongly recommend the following material: Mathematics for Computer Science - MIT Course notes of Mathematics for Computer Science - MIT