Lesson 1 - Binary Search, Linked Lists and Complexity


Please visit the Lesson Page for more detailed info :point_up:

:play_or_pause_button: Live Session Links:
English: https://youtu.be/clTW4lydwOU
Hindi: https://youtu.be/Jh4t9o2y_pw

:date: Lecture Date and Time:
English: Add to Calendar (Google)
Hindi: Add to Calendar (Google)

:zap: In this lesson, we learn and implement, binary search, one of the fundamental algorithms in computer science. Along the way, we also discuss a universal strategy for solving programming problems and gain an intuitive understanding of the complexity analysis.

Notebooks used in this lesson:

:question: Asking/Answering Questions :
Reply on this thread to ask questions during and after the lecture. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. During the lecture, we’ll answer 8-10 questions with the most likes. The rest will be answered on the forum. If you see a question you know the answer to, please post your answer as a reply to that question. Let’s help each other learn!

8 Likes

a data science enthusiast always got stuck during college placement time like a pendulum between the DS-ALGO and Data Science concept also he/she might get diverted between C++ and Python. So what can be the solution for this?

4 Likes

Thank you so much @aakashns for this course. Data Science job opportunities are scarce enough as is, and these basic principles are too boring to self-study. But you have a way of making the most mundane of subjects interesting :slight_smile:

5 Likes

Can someone please explain how this line works in Line 8 of the notebook:

locate_card(**test['input']) == test['output']

How is the comparison performed and what does the “**” actually do?
Thanks,

2 Likes

this statement resembles as same as locate_card(test[‘input’][‘cards’],test[‘input’][‘query’]) == test[‘output’]
as its access the elements from the dictionary so to use short hand we can also write the above statement as locate_card(**test[‘input’]) == test[‘output’]
hope this helps.

2 Likes

Sounds good thanks…

I also have same question. I was about to write but seen you asking the same. Eagerly waiting for someone to help us out!

this statement resembles as same as locate_card(test[‘input’][‘cards’],test[‘input’][‘query’]) == test[‘output’]
as its access the elements from the dictionary so to use short hand we can also write the above statement as locate_card(**test[‘input’]) == test[‘output’]
hope this helps.

def reverse(l):
    if l.head is None:
        return
    
    current_node = l.head
    prev_node = None
    
    while current_node is not None:
        # Track the next node
        next_node = current_node.next
        
        # Modify the current node
        current_node.next = prev_node
        
        # Update prev and current
        prev_node = current_node
        current_node = next_node
        
    l.head = prev_node

In the notebook python-classes-and-linked-lists](https://jovian.ai/aakashns/python-classes-and-linked-lists) please explain the above given code. It seems to me like the current node is not changing/updating and the same three nodes are updating(1, 2, 3). There should be something like
current_node = current_node.next
at the end of the loop.

1 Like

i also have same question.

Can we add another test case in the 1st problem in the lesson 1 notebook that
The ‘query’ occurs at multiple positions and it’s the only number in the cards.

Is this a valid test case @aakashns

Why is it that the notebook used in live streamed lecture is somewhat different from the one I am executing in Colab ?

1 Like

Can you please explain how is it different ?

I think the notebook used in lecture for Data Structure and algorithm course is run on binder not on colab. If that you are asking. Otherwise, please explain how is it different as @birajde said.

Not much difference. Like evaluate_test_cases was not explained in the beginning of the notebook. My point of view was that the same notebook is executed, then why such variations. That’s all, not much to bother about. :slightly_smiling_face:

1 Like

Hi, so I added this test case and failed the evaluation.

image

So for a simple solution, I added a single line of code where it will check if the query can be found on the ‘left’ part of the list other than the middle.

image

It works fine but the average running time has become about 5 times slower. Is this solution a good thing or redundant at all?

For Binary Search the input array cards needs to be in sorted order, otherwise, the binary search will not work properly, The test case you added does not have a sorted list that is why your evaluation failed.
And the code you added will cause in increasing the execution time because of the query in cards[:mid-1] part.

1 Like

Thank you!! I appreciate the response. I think I should’ve researched first before asking.

1 Like

I have found 2 typos in the https://jovian.ai/aakashns/python-binary-search Lessons notebook.

Typo 1. In cell block “In [11]:” Where it mentions the test case with " query occurs in the middle". This is an invalid description because the query is for 1, which is the 2nd to last element in the cards List. It’s not in the middle of the list.

Typo 2. For the header “3. Come up with a correct solution to the problem. State it in plain English”. The first sentence misses the word “NOT” in " which may necessarily be the most efficient solution.". There should be a NOT before “necessarily”.

Just some small things I noticed when reading through the notebook.

Hello guys and girls,

I wrote a Medium post about the lesson. Since it is only one day left due for the assignment, I think it is opportune to share the information as everyone has had time to think about the problem. If you are still wrapping your head around the assignment, maybe give it a read. It might help you.

Feedback is appreciated.

I am kinda still waiting on the Jovian team and @aakashns to accept it as a Jovian publication on Medium.

Thanks!

1 Like