Welcome to our 1st short course: Introduction To Logic Building ! of our “Programming Fundamentals with Python” master course series.

As we are about to learn a computer science course, let’s begin with the fundamental question: What is a computer? The standard definition characterizes a computer as “an electronic device that takes input, processes it, and converts it into output” or “an electronic device which manipulates data by processing it.” However, these definitions pose a challenge.

Many other machines fulfill these criteria but are not considered computers. For example, a washing machine takes input in the form of clothes and detergent, processes it(washes it), and produces output (returns clean clothes), since a washing machine performs all the operations that are required from the standard definition of computer, does it mean that we are about to learn how to build a washing machine or how a washing machine works? Of course not, computer science is not about that.

Another famous definition of a computer says “A computer is a machine which performs arithmetic operations like {+, -, x, /}”. If we consider this definition to define a computer then a calculator is also a computer, isn’t it? But we know there is a huge difference between a calculator and a computer. Even though there’s a part in a computer called ALU that performs arithmetic(+, -, x, /), a computer does much more than calculations. It engages in multiple operations, and the automatic calculation it performs is called computation.

This leads to several fascinating questions: How does the computer work? What is computation in its entirety? How is it related to computers? What is the essence of computer science? We will explore these questions in the upcoming video. Stay tuned for more insights.

In the last video, the discussion centered on what a computer is. Now, let’s focus on how the computer works. To understand this, we need to know about computation.

Computation refers to various operations performed by a computer, including arithmetic operations such as addition and multiplication, as well as non-arithmetic operations like moving, copying, etc. In simple words, computation is what computers do.

How does a computer perform computations?

In our daily lives, we encounter various problems and execute numerous tasks. Whether it’s problem-solving or completing a daily task, we follow a series of steps to accomplish it. This series of steps is known as an algorithm. An algorithm serves as a recipe to solve a specific problem. Likewise, when a computer solves a problem i.e. performs computation, it uses algorithms to work on that.

An algorithm is just a plan or mental strategy to perform a task. When an algorithm is implemented, it becomes a program. A computer “works” using an algorithm given in the form of sets of instructions and these sets of instructions are called programs. Every program is an algorithm but every algorithm is not always a program.

In the next video, we will dig deep and learn to build effective algorithms. We will see how every program, in essence, is an algorithm, and why computer scientists need to be good at coming up with algorithms. Stay tuned for an interactive learning experience as we’ll explore these concepts through a game!

In the last video, we discussed computation, algorithms, and programs. Now, we are gonna play a game and try different algorithms to accomplish the task. Let’s start!

Many of us have played the guessing game in our childhood, where we try to guess a number within a range, say 1-1000.

We have multiple ways to guess the number.

Using the simplest technique of guessing the number one by one can be quite naive. Why?

By following this technique, we might end up guessing 999 wrong answers before reaching the correct one. Is it efficient? Not at all.

Can we do better? Absolutely.

Let’s try to think of a better algorithm to solve this problem. In the last approach, we asked 999 questions to eliminate wrong answers and narrowed down the range. But, can we ask smarter questions to shrink our range more effectively?

Yes, we can. Let’s ask yes/no questions. For example, we could start by asking if the number is even. The answer to this question will reduce our range to 500 numbers. If the number is even, it will be from the set {2,4,6,8,…}, otherwise, it will be from the set {1,3,5,7,…}. With just one question, we’ve significantly improved our approach. What should the next question be?

One question that can be asked is whether the required number has 2 or 3 decimal places. For a better understanding we can say, is the number greater than or less than 100? The answer to this question will further shrink the range.

That’s it for this video. We’ll leave you with a question: Can we think of a better algorithm in which the questions are more effective, allowing us to find the required number with the fewest questions possible?

In the previous video, we were playing a number guessing game, trying to figure out a way to guess the number using as few questions as possible.

Let’s look at a better approach. The problem space could be divided into intervals of 100s. For example, we ask if the number is less than 100. If yes, then we can guess the number in only a hundred tries (asking about each number from 1-99). If no, then we ask if the number is in the next interval, i.e. less than 200 but greater than 100. If yes, then we will be able to guess the number in 101 tries. Ultimately, if the number is between 900 to 1000, this approach will take 109 tries to guess the number which is much better than the previous ways which took 500 or 999 tries.

Can we make an even better algorithm?

HINT: Divide the space in such a way that the ranges are almost equal to each other.

What should be the first question?

We should ask if the number is greater or less than 500. If yes, then the number could be from 1 to 500. If not, then the range would be from 501 to 1000. This question halves the range. Can we apply the same strategy again?

Let’s say, the number is between 1 and 500. The next question should be if the number is greater than 250 or not. The answer to this question will once again shrink the range to half(one-fourth of the total numbers). This strategy can be repeated till we find the required number.

In the worst case, how many questions are needed to guess the number using this technique? Only 10 questions would be enough to guess the number in the range between 1 to 1000.

This strategy is known as the halving technique. At each step, the range is divided into half until we get the required answer. The halving technique is one of the most important techniques for computer scientists.

We will leave you with a question: We have guessed a number from 1 to 1000 in 10 questions. How many questions are needed if the range is from 1 to 2000? Think about it!

In the next lecture, we’ll explore how fast the halving technique is. We’ll also discover how the tech giants and famous computer science companies rely on this halving technique. Stay tuned!

In the previous video, we discovered the halving technique. In this session, we’ll explore how fast and useful this technique can be.

Before that, let’s understand a basic mathematical concept called logarithm (log), which is crucial in computer science.

Imagine we have a number, let’s call it N. We will get N/2 by dividing the number by 2, repeating this step will give us N/4, then N/8, and so on until the number will finally become equal to 1. This creates a series like N, N/2, N/4, N/8, …, 4, 2, 1. The number of steps it takes a number N to become 1 is called the log of N with base 2(log₂ N).

Now, if we think about it differently, suppose we start with 1 and keep multiplying the number by 2 until it reaches N. The number of steps needed to get from 1 to N by multiplying 2 each time is also log₂ N.

Similarly, if we replace 2 with another number, say 3, the steps it takes to reach N by multiplying 3 at each step is a log of N with base 3.

In general terms, Logb N is the number of steps needed to make N equal to 1 by dividing it by b at each step.

N, N/b , N/b^2 , N/b^3,…,1.

So, what’s the connection between log and halving technique?

When we apply the halving technique, we start with a range from 1 to N. With each question, the range halves. The total steps needed to reach 1 using this technique is log base 2 N.

log₂ 1000 is approximately 10. So, it would take about 10 questions to guess a number in the range from 1 to 1000.

Let’s take a look at an example to understand the power of the halving technique. The total number of atoms in the universe is around 10^82(10 raised to the power 82) atoms. Imagine labeling every atom in the universe, numbering them from 1 to 10^82, so N is equal to 10^82. If we want to find a specific atom, it’s like playing a guessing game with a range of 10^82. Using the halving technique, we could find the required atom in log₂ (10^82) steps. There is a property of log that the exponent of N could be multiplied with logb N which makes log2(10^82) equal to 82 * log₂ 10. The halving technique requires 272 steps to find the particular atom in the universe.

Let’s compare it to the approach of guessing the atoms one by one. It would take 10^82 steps and the halving technique takes only 272 steps. How large is this number 10^82?

Let’s say we have a computer that has a processor of 10 GHz(GigaHertz) which means that it performs 10^10 computations in one second. How much time would this computer need to perform 10^82 computations? It would take 10^82/10^10 seconds to find the atom. If we had to guess one by one, it would take 10^69 years to find the atom.

In simpler words, if we had a computer that could perform 10 billion computations per second, it would still take billions of billions of years to find the atoms one by one. But with the halving technique, it’s just 272 steps!

Amazing, isn’t it?

This efficient algorithm is also used by search engines like Google to swiftly extract data. The data is stored in the form of numbers and the halving technique is applied to provide the required data at a lightning-fast speed. It’s truly remarkable how a good algorithm can minimize effort and maximize productivity. In the next video, we are going to play another game to explore more about algorithms and techniques. Stay Tuned!

In our previous discussion, we explored the efficiency of the halving technique. In this video, we’ll play another game and try to think of the best strategy to crack a puzzle.

The puzzle is to find the heaviest ball among 8 balls using a balance. All the balls are of the same design and size. Except for one, all the balls have the same weight too. The challenge is to do it in minimum tries. ”Minimum tries” means using the balance a minimum number of times.

What can be the most naive approach? we could pick any two balls and place them on the balance. If one side weighs down, we’ve found the heaviest ball. If not, then the heaviest must be among the remaining 6 balls. We repeat this process, taking 2 balls at a time. How many tries does it take with this technique? At least 4.

Can we do better?

The question arises: Can we use the halving technique we’ve previously learned to solve this problem? Let’s apply the halving technique. Divide the balls into two groups. Weigh each group on the balance and take the 4 balls of the group that weigh down on the balance. Now divide the 4 balls into 2 pairs and place each pair on either side of the balance. The pair that weighs down has the heaviest ball. Take that pair and weigh each ball separately. The heaviest ball will weigh down and it took us 3 tries to find the heaviest ball.

Using the halving technique, it took us the log of N with base 2 tries to find the heaviest ball among N balls.

While it is an improvement, can we still do better than this?

To find a better algorithm, let’s consider that we only have 3 balls. How can we find the heaviest ball among three balls? Place any two balls on either side of the balance. The side that will weigh down has the heaviest ball, if no side weighs down then the third ball placed aside is the heaviest. It took one try to find the heaviest ball among 3 balls.

Similarly, if we divide the 8 balls into 3 groups. The first group has 3 balls, the second group also has 3 balls and the third group has 2 balls. Take the first two groups and weigh them on balance, if they weigh the same then the ball is among the third group and you can easily find the ball in one more try. If any of the first two groups weigh down, then the heaviest ball is in that group and we have already seen how to find the heaviest ball among 3 balls. So in each case, we can find the heaviest ball in just 2 tries. We highly encourage you to try solving this problem in 2 tries on your own for a better understanding.

In the upcoming video, we’ll explain the significance of playing these games. You’ll discover why this brainstorming is important for computer scientists.

In the last video, we played games to sharpen our thinking skills. But you might wonder, how do these games connect to logic and computation?

All the great ideas in computer science are based on logic building and algorithms. Logic building is all about designing strategies and finding the best algorithms possible. ‘Best possible’ algorithm means one that is efficient. Because if the algorithm is not efficient, it is of no use. Remember our first idea in the guessing game? It wasn’t the best. Though it was an algorithm, it was inefficient as compared to the halving technique.

When computer scientists discuss algorithms, the most powerful one is referred to as ‘The Algorithm’ and they always work to come up with an even better one. We have seen the example of Google, Google strives to continually improve its algorithms to deliver the most accurate information in the most efficient way possible.

In the upcoming videos, we will explore more interesting algorithms to solve different challenging issues.

We have seen various problems to learn logic-building and today we will have a look at another problem that will help us understand a beautiful algorithm.

Let’s hear an interesting story to understand the problem.

The story starts with a boy named ’Sarim’ who is standing on one side of a river and a girl ‘Katrina’ who is standing on the other side of the river. Both sarim and katrina have a lot of boxes and locks. Each one of them has the keys to their locks. In the river, some pirates steal everything they find in the river if it has no lock on it. The pirates have a strange policy that if they find a box with a lock on it, they do not open it and let it pass the river. Sarim wants to propose katrina and the only way he can give her a ring is to put the ring in the box and let it pass the river. But to protect the box from the pirates, the box must have a lock on it. Now Sarim needs your help to devise a strategy to pass the ring to katrina.

What are the challenges of the problem?

The ring can only be passed across the river if it’s inside a box with a lock. The challenge here is it if sarim puts a lock on the box and passes it to katrina then katrina cannot open that box because she does not have the keys to the lock that sarim has put on the box.

How can you solve this problem? Think about it for some time before looking at the answer below.

Here’s a possible solution. Sarim places the ring in the box and puts a lock on it. Since the box has a lock on it, pirates do not take it. Katrina now has the box but she cannot open it. What can she do then?

Think about it yourself for a second.

Yes, she can put another lock on the box to which she has the key herself and pass the box across the river back to sarim. Sarim now removes the lock he has put on the box and sends the box back to katrina. Each time the box had a lock on it so the pirates could not take the ring inside the box and let it pass. Now finally katrina has the box with only one lock on it that she has put on it, she opens it with the key and takes the ring.

This was the strategy behind sarim and katrina proposal story. But there is more to this story than a happy ending, there is an elegant algorithm in it that was used to solve the overall problem. You probably have seen links on different social media sites with “https” as initials in which the ‘s’ represents that the website is secure. All these secure websites use a similar kind of protocol as used in this problem to maintain the client-server connection.

There are different kinds of algorithms such as RSA and ElGamal that work on similar kinds of protocols and are built on the idea of the algorithm discussed in the above example story. There is a whole branch of computer science known as cryptography that made all the e-commerce possible. Today we learnt how the ideas hidden in these simple stories are fundamental to the modern world and in the upcoming video we will see another example of such ideas. Stay tuned!

In our final video of this short course, we will look into another fascinating problem: Population Count. Imagine being in a large hall and the task is to count the total number of people in there. Asking one person to count everyone would be inefficient and time-consuming.

A more efficient method for counting people in a rectangular hall could involve determining the total number of rows (R) and the total number of people in each row (C). Multiplying the total number of people in each row by the total number of rows (R x C) will give the total number of people in the hall.

However, what if we need to count people in a non-rectangular hall, such as a stadium or where people are seated in irregular patterns? How would we approach population counting then?

Let’s devise a strategy for counting N people efficiently. In this strategy, everyone in the hall participates. Each person takes a paper and marks 0 and 1 on it, where 1 represents that the person has counted himself and 0 represents that the number of steps taken is zero. Participants then pair up, with one person passing their paper to the other and sitting down. The person left standing cuts out 1 and 0 from their paper, replacing them with 2 and 1, respectively, representing that they have counted two people and taken one step. After this step, the remaining standing individuals are halved (N/2). They pair up again and repeat the process. This process continues until only one person remains. The final numbers on the paper represent the number of people counted and the total number of steps taken. The total number of steps to count all the people is log N with base 2.

Imagine applying this approach to count the total number of atoms in the universe, with each atom participating. It would take only log N with base 2 steps to determine the total number of atoms. This type of computing, where multiple entities contribute to a task, is known as distributed computing. Modern-day cloud computing has also extended from distributed computing.

In this short course, we’ve explored logic building and strategy designing, essential components of computer science. In the next short course, we will learn how to program these algorithms, and we will look forward to you there!