Algorithms and Data Structures 2024/2025 (L.EIC011) - DCC/FCUP & DEI/FEUP

Practical Class #03 - Sequential Search, Binary Search and Variants
(07/10 to 11/10)

Exercises for submission

In what concerns the continuous evaluation solving exercises during the semester, the exercises you can submit in this class are:

Submission Deadline: October 26th (submit to AED's Mooshak)

You are encouraged to talk to the professor and to your colleagues if you have difficulties. However, any more direct help you have received from other colleagues should be acknowledged in the comments of the code you submit.
After the deadline the problems will still be available on Mooshak, but the submissions will not count towards your grade.
Each class is worth 10 per cent of the grade for this component. As there will be 11 classes with submissions, you can get full marks even if you haven't done everything.
For a problem to count, you have to get all the tests right (i.e. accepted). Even if you solve all the problems, the maximum in a single class is 100 per cent.
it is guaranted that the main exercises on each class will sum to at least 100% of the class grade.

Lectures Content

This class is about searching. It is therefore convenient that you know what was discussed on the lectures:

1. Foundations of searching
(the goal of this exercise is for you to test a base implementation of sequential and binary search and check its execution time)

In this exercise you will be testing a int search(const vector<int> & v, int key) function that, given a vector v of distinct integers sorted in increasing order, should return the position index of key in vector v if key exists or -1 if it does not exist.

For instance:

Start by downloading the class03_ex1.zip file. Uncompress in your computer, compile and run it. If everything is correct you should be able to see something like the following: 

. Case with n = 10 and 10 queries [INCORRECT]
  Time: 0.000004 s

. Case with n = 100 and 100 queries [INCORRECT]
  Time: 0.000004 s

. Case with n = 1000 and 1000 queries [INCORRECT]
  Time: 0.000009 s

. Case with n = 10000 and 10000 queries [INCORRECT]
  Time: 0.000083 s

. Case with n = 100000 and 100000 queries [INCORRECT]
  Time: 0.000574 s

This indicates all examples were executed but the answers were incorrect. This is because search it is not implemented yet and is always returning -1. Notice how even just a simple function takes some time to be called 100 000 times in the last input.

  1. A first solution in linear time \(O(n)\)

    Start by implementing a simple sequential search (see slides 5 to 9 of Chapter 3 - Searching) that goes through all the numbers of the vector trying to find the key in linear time (and because here we are searching for an int, the cost of the operation == is \(O(1)\)). Copy the following code to function search, compile it, execute it and see if it is correct and how much time it takes for each test. 

    for (int i=0; i<v.size(); i++)
  if (v[i] == key)
    return i; // found key
return -1;    // not found

  2. Improving the solution to logarithmic time \(O(\log n)\)

    Intuitively you should be able to improve this solution by taking advantage of the fact that the vector is sorted. And for that we will use... binary search (see slides 10 to 16 of Chapter 3 - Searching). 

    int low = 0, high = (int)v.size() - 1;
while (low <= high) {
  int middle = low + (high - low) / 2;
  if (key < v[middle])      high = middle - 1;
  else if (key > v[middle]) low = middle + 1;
  else return middle; // found key
}
return -1; // not found

    Implement this new solution, compile, execute it and see how much time it took now.

  3. Testing binary search in Mooshak


    For this exercise you will be solving the problem [AED005] Number Searching.

    With what you now know, it should be really easy to solve this problem, right? You can even reuse the function you just implemented before. 😉

    Code the solution, test it with the examples given, submit to Mooshak and go get your Accepted.

2. Your first variant of binary search


For this exercise you will be solving the problem [AED006] Lower Bound.
Desired time complexity: \(O(N + Q \times \log N)\)

Read the problem statement and understand what it is asking. The lower bound is a very useful primitive that can be used in many problems. Our suggestion is that you create a function int lowerBound(const vector<int> & v, int key)

A brute force approach that goes does a sequential search in linear time is not enough (if you want you can check by implementing and submitting to Mooshak, where you should get a Time Limit Exceeded).

To solve in the desired time complexity you need to be able to answer each query in logarithmic time. But you know you can use binary search to do this, right? Don't forget you are expected to code, test and submit in Mooshak until you get an accepted solution.

(note: for these and the following problems we will give hints that are initially hidden in case you want to do the problems by yourself without any spoilers; nevertheless, you should always check the hints even if you got an Accepted without seeing them)

Hints

- This exercise is explained directly in the lecture slides (see slide 32 and of Chapter 3 - Searching)

- Try to implement manually the lower bound so that you can understand it; after having Accepted you can try to solve again but this time using the lower_bound available in <algorithm> (note that this function return an iterator, but since it is of RandomAccess you easily compute the position - see for instance slide 47).


3. Solving a problem with binary search


For this exercise you will be solving the problem [AED007] Interval Count.
Desired time complexity: \(O(N + Q \times \log N)\)

Read the problem statement and understand what it is asking. Can you think on how you could use the lowerBound function you created for the previous exercise? Try to think about the problem by yourself before seeing the hints. 😉

Hints

- Assuming the numbers are stored in vector v and you trying to count the elements in [a,b], what would you obtain if you call lowerBound(v, a)?

- A cal to lowerBound(v, b) would obtain the first occurrence of b, if it occurs. How can you use this function to obtain the element exactly after all occurrences of elements ≤b?

- If you have the first position inside the interval and the first position immediately after the last position of the interval, how could you obtain the result?

- With two binary searches, each one taking \(O(\log N)\), what is the total complexity of each query? And what about the entire program?


4. Binary search the answer on a partition problem


For this exercise you will be solving the problem [AED008] Backpacking Trip.
Desired time complexity: \(O(N + Q \times \log S)\), where \(S\) is the sum of all \(N\) distances

This problem was explained in detail in the lectures (see slides 35 to 40 of Chapter 3 - Searching).

  1. isPossible

    Let's start by implementing an auxiliary function that will be very useful: bool isPossible(const vector & v, int x, int k). This function should have time \(O(n)\) where \(n\) is the size of the vector.

    This function should return true if it is possible to divide the vector v into k partitions (sequences of contiguous numbers) such that the sum of the largest partition is ≤x or false otherwise. Here are some examples of possible calls and the expected results:

    Implement and test the function before going to the next part of the exercise.

    Hints

    This function can be made with a greedy algorithm that extends the current partition while its sum is ≤ x; if it surpasses x, then a new partition is started; at the end we simply need to check the minimum number of partitions to see if k partitions would suffice (slide 37)


  2. Solving the problem

    We can now use binary search the answer using the previous primitive 😉

    Hints

    - We can use binary search of the space of possible answers \([1,S]\) (see slide 38), where S is the sum of all distances

    - The search space is of the type no no .. yes yes .. yes for the function isPossible and so we can at its essence a lowerBound type of binary search

    - Each of these \(Q\) queries takes therefore time \(O(\log S)\)


Extra Exercises for Consolidating your knowledge [extra]

5. Closest Sums


For this exercise you will be solving the problem [AED009] Closest Sums.
Desired time complexity: \(O(N^2 \times \log N + Q \times \log N)\) - note that \(\log(N^2) = 2 \times \log(N) \in O(\log(N))\)

Read the problem statement and understand what it is asking. Implement, test and submit on Mooshak. Can you think on how you could use binary search or a variant? Try to think about the problem by yourself before seeing the hints. 😉

Hints

- Let's start by computing all possible sums \(S_i + S_j\) such that \(0 \leq i < j < N\)
   . How many pairs exist? What is its asymptotic order of magnitude?
   . Implement two cycles to generate all these sums and store them on a new vector sums and verify that its size is what you expected

- For each of the \(Q\) queries we will now search on sums for the closest number
   . A sequential search is slow and would not pass on Mooshak
   . The vector of sums is the same for all queries, so we can pre-process it to then improve the search. So, we could... sort it, so that we can use binary search! Use C++ sort available in <algorithm>.    . Since the query number might not exist, how could we use lowerBound?

- In the end the overall time complexity is:
   . Read the numbers in \(O(N)\) time
   . Compute the sum of all pairs in \(O(N^2)\)
   . Order the sums in \(O(N^2 \log N^2) \in O(N^2 \log N) \)
   . Answer each of the \(Q\) queries in time \(O(\log N^2) \in O(\log N) \)



6. Word game


For this exercise you will be solving the problem [AED010] Word Game.
Desired time complexity: \(O(|A| \times \log |A|)\)

Read the problem statement and understand what it is asking. Implement, test and submit on Mooshak. Can you think on how you could use binary search or a variant? Try to think about the problem by yourself before seeing the hints. 😉

Hints

-Can you think of a function to tell if it is possible for Susan to remove \(k\) letters? This can be done in time \(O(n)\) on a single passage "at the same time" on \(A\) and \(B\)

- With the previous function, your search space on \(k\) is now of type no no .. yes yes .. yes, so you can binary search the answer. What are the possible values of \(k\)?


Challenge Exercise [challenge]

As on the previous class, this exercise can be harder than the previous ones and does not need to simply tackle the topics of this class.

The main idea is to give you the opportunity of improving your problem solving abilities.


For this exercise you will be solving the problem [AED011] Cool Numbers.

Since this is a challenge, I will not give you any hints, but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.

Happy coding! 😊

Pedro Ribeiro & Ana Paula Tomás (DCC/FCUP) / Última actualização: