Search Results

Here is an index of Past Year Question Papers of B.Sc. (Hons.) Computer Science.

I hope you already know about Breadth First Search Algorithm - and even if you don't, you won't have a problem understanding this article. Breadth First Search Algorithm gives us the shortest path in an unweighted graph. However, when the graph is weighted, Breadth First Search Algorithm fails. Here is where Dijkstra's Algorithm comes in. Suppose we have the following graph - We have to start from the START node and reach the FINISH node. The weights of the edges are given. Let's say the weights are the time it takes for us to cover an edge. So, if the weight of an edge is 2, it means it takes us 2 minutes to cover that edge. If we run breadth-first search algorithm on the graph, we will get the following result- According to BFS, the shortest path between START and FINISH takes 7 minutes. However, just by observation, we can see that this is not the case. We can go from START to B in 2 minutes, B to A in 3 minutes and A to FINISH in 6 minutes. Here, the total time taken is 6 minutes. We can see that the Breadth First Algorithm does not work for weighted graphs. Let's now apply Dijkstra’s Algorithm. This algorithm works in four steps. Step One: Find the cheapest node. You’re standing at the start, wondering if you should go to node A or node B. How long does it take to get to each node? It takes 6 minutes to get to node A and 2 minutes to get to node B. The rest of the nodes, you don’t know yet. Because you don’t know how long it takes to get to the finish yet, you put down infinity. Step Two: Node B is the closest node … it’s 2 minutes away. Calculate how long it takes to get to all of node B’s neighbours by following an edge from B. Hey, you just found a shorter path to node A! It used to take 6 minutes to get to node A. But if you go through node B, there’s a path that only takes 5 minutes! When you find a shorter path for a neighbour of B, update its cost. In this case, you found • A shorter path to A (down from 6 minutes to 5 minutes) • A shorter path to the finish (down from infinity to 7 minutes) Step Three: We repeat the above steps. Find the node that takes the least amount of time to get to. You’re done with node B, so node A has the next smallest time estimate. Update the costs for node A’s neighbours. Woo, it takes 6 minutes to get to the finish now! You’ve run Dijkstra’s algorithm for every node (you don’t need to run it for the finish node). At this point, you know It takes 2 minutes to get to node B. It takes 5 minutes to get to node A. It takes 6 minutes to get to the finish. Now, we can easily trace the path to the FINISH node. Please note that Dijkstra’s Algorithm works only on Directed Acyclic Graphs. This algorithm can work on unweighted graphs as well because unweighted graphs are nothing but weighted graphs with 0 as weight for all edges. Also please note that Dijkstra’s Algorithm cannot work with negative weights. For that, we have another interesting algorithm known as the Bellman-Ford algorithm, which we shall discuss in further articles.

The 0/1 knapsack problem is a common problem that involves maximizing the value of items in a knapsack while ensuring that the total weight of the items doesn't exceed the knapsack's capacity. Let's first use greedy algorithms to solve this problem. Suppose you’re a greedy thief. You’re in a store with a knapsack, and there are all these items you can steal. But you can only take what you can fit in your knapsack. The knapsack can hold 35 pounds. You’re trying to maximize the value of the items you put in your knapsack. What algorithm do you use? Let us say we use the greedy strategy. It is pretty simple: Pick the most expensive thing that will fit in your knapsack. Pick the next most expensive thing that will fit in your knapsack. And so on. Except this time, it doesn’t work! For example, suppose there are three items you can steal. Your knapsack can hold 35 pounds of items. The stereo system is the most expensive, so you steal that. Now you don’t have space for anything else. You got $3,000 worth of goods. But wait! If you’d picked the laptop and the guitar instead, you could have had $3,500 worth of loot! The greedy strategy doesn’t give you the optimal solution here. But it gets you pretty close. Let's try it with another approach. The simplest algorithm is this: you try every possible set of goods and find the set that gives you the most value. This works, but it’s really slow. For 3 items, you have to calculate 8 possible sets. For 4 items, you have to calculate 16 sets. With every item you add, the number of sets you have to calculate doubles! This algorithm takes O(2ⁿ) time, which is very, very slow. We can solve the Knapsack problem using Dynamic Programming.  Dynamic programming starts by solving subproblems and builds up to solving the big problem. For the knapsack problem, you’ll start by solving the problem for smaller knapsacks (or “sub-knapsacks”) and then work up to solving the original problem. Every dynamic programming algorithm starts with a grid. Here’s a grid for the knapsack problem. The rows of the grid are the items, and the columns are knapsack weights from 1 lb to 4 lb. You need all of those columns because they will help you calculate the values of the sub-knapsacks. The grid starts out empty. You’re going to fill in each cell of the grid. Once the grid is filled in, you’ll have your answer to this problem! Start with the first row. This is the guitar row, which means you’re trying to fit the guitar into the knapsack. At each cell, there’s a simple decision: do you steal the guitar or not? Remember, you’re trying to find the set of items to steal that will give you the most value. The first cell has a knapsack of capacity 1 lb. The guitar is also 1 lb, which means it fits into the knapsack! So the value of this cell is $1,500, and it contains a guitar. Like this, each cell in the grid will contain a list of all the items that fit into the knapsack at that point. Let’s look at the next cell. Here you have a knapsack of capacity 2 lb. Well, the guitar will definitely fit in there! The same for the rest of the cells in this row. Remember, this is the first row, so you have only the guitar to choose from. You’re pretending that the other two items aren’t available to steal right now. At this point, you’re probably confused. Why are you doing this for knapsacks with a capacity of 1 lb, 2 lb, and so on, when the problem talks about a 4 lb knapsack? Remember how I told you that dynamic programming starts with a small problem and builds up to the big problem? You’re solving subproblems here that will help you to solve the big problem. Remember, you’re trying to maximize the value of the knapsack. This row represents the current best guess for this max. So right now, according to this row, if you had a knapsack of capacity 4 lb, the max value you could put in there would be $1,500. Let’s do the next row. This one is for the stereo. Now that you’re on the second row, you can steal the stereo or the guitar. At every row, you can steal the item at that row or the items in the rows above it. So you can’t choose to steal the laptop right now, but you can steal the stereo and/or the guitar. Let’s start with the first cell, a knapsack of capacity 1 lb. The current max value you can fit into a knapsack of 1 lb is $1,500. Should you steal the stereo or not? You have a knapsack of capacity 1 lb. Will the stereo fit in there? Nope, it’s too heavy! Because you can’t fit the stereo, $1,500 remains the max guess for a 1 lb knapsack. Same thing for the next two cells. These knapsacks have a capacity of 2 lb and 3 lb. The old max value for both was $1,500. The stereo still doesn’t fit, so your guesses remain unchanged. What if you have a knapsack of capacity 4 lb? Aha: the stereo finally fits! The old max value was $1,500, but if you put the stereo in there instead, the value is $3,000! Let’s take the stereo. You just updated your estimate! If you have a 4 lb knapsack, you can fit at least $3,000 worth of goods in it. You can see from the grid that you’re incrementally updating your estimate. Let’s do the same thing with the laptop! The laptop weighs 3 lb, so it won’t fit into a 1 lb or a 2 lb knapsack. The estimate for the first two cells stays at $1,500. At 3 lb, the old estimate was $1,500. But you can choose the laptop instead, and that’s worth $2,000. So the new max estimate is $2,000! At 4 lb, things get really interesting. This is an important part. The current estimate is $3,000. You can put the laptop in the knapsack, but it’s only worth $2,000. Hmm, that’s not as good as the old estimate. But wait! The laptop weighs only 3 lb, so you have 1 lb free! You could put something in this 1 lb. What’s the maximum value you can fit into 1 lb of space? Well, you’ve been calculating it all along. According to the last best estimate, you can fit the guitar into that 1 lb space, and that’s worth $1,500. So the real comparison is as follows. You might have been wondering why you were calculating max values for smaller knapsacks. I hope now it makes sense! When you have space left over, you can use the answers to those subproblems to figure out what will fit in that space. It’s better to take the laptop + the guitar for $3,500. The final grid looks like this. There’s the answer: the maximum value that will fit in the knapsack is $3,500, made up of a guitar and a laptop! Now, let's generalize this with a06. formula. Each cell’s value gets calculated with the same formula. Here it is. You can use this formula with every cell in this grid, and you should end up with the same grid I did. Remember how I talked about solving subproblems? You combined the solutions to two subproblems to solve the bigger problem. We finally figured out the Knapsack problems. But there are a few important things you need to keep in mind for the Knapsack problem. We have studied Knapsack Problem and how to solve it. However, while solving the problem, keep the following things in mind. It is possible that the best solution doesn’t fill the knapsack completely. Suppose you could also steal a diamond. This is a big diamond: it weighs 3.5 pounds. It’s worth a million dollars, way more than anything else. You should definitely steal it! But there’s half a pound of space left, and nothing will fit in that space. Dynamic programming only works when each subproblem is discrete—when it doesn’t depend on other subproblems. You cannot steal fractions of items. With the dynamic-programming solution, you either take the item or not. There’s no way for it to figure out that you should take half an item. The order of rows of grid does not matter. The value of column cannot go down in subsequent iterations. This was it. Thankyou for reading.

Before reading further, make sure you understand what queues and graphs are. Suppose you’re in San Francisco, and you want to go from Twin Peaks to the Golden Gate Bridge. You want to get there by bus, with the minimum number of transfers. Here are your options. What’s your algorithm to find the path with the fewest steps? Well, can you get there in one step? Here are all the places you can get to in one step. The bridge isn’t highlighted; you can’t get there in one step. Can you get there in two steps? Again, the bridge isn’t there, so you can’t get to the bridge in two steps. What about three steps? Aha! Now the Golden Gate Bridge shows up. So it takes three steps to get from Twin Peaks to the bridge using this route. There are other routes that will get you to the bridge too, but they’re longer (four steps). The algorithm found that the shortest route to the bridge is three steps long. This type of problem is called a shortest-path problem. You’re always trying to find the shortest something. It could be the shortest route to your friend’s house. It could be the smallest number of moves to checkmate in a game of chess. The algorithm to solve a shortest-path problem is called breadth-first search. Now, let us get into the technicalities. Breadth First Search is applied on graphs. Breadth First Search helps us answer two kinds of questions. Question 1: Is there a path from node A to node B? Question 2: What is the shortest path from node A to node B? Now, let's understand this completely with another example. Suppose your dog is looking to buy mangoes on LinkedIn. He's connected with three people - Bob, your cat, Claire, your pig and Alice, your mouse. Let's call them 1st Degree connections. Also, each of these people are connected to some other animals. Let's call them 2nd Degree connections of your dog. Your dog will prefer a first-degree connection to a second-degree connection, and a second-degree connection to a third-degree connection, and so on. So he shouldn’t search any second-degree connections before he makes sure he doesn't have a first-degree connection who is a mango seller. Well, breadth-first search already does this! The way breadth-first search works, the search radiates from the starting point. So it'll check first-degree connections before second-degree connections. We'll first explore all the nodes nearest to your dog and then explore all the nodes on the second level, the third level, and so on. (Although there are only two nodes in this example, you get the idea). If there is an unvisited node in Breadth First Search, we can say that there is no connection between the starting point and the node. Now, let's see how we can implement this. We use queues to implement Breadth First Search. We will refer to the graph above with the first-degree and second-degree connections. We start with an empty queue. Now, we add the nearest connections to our starting point in our queue. From our graph, we can see that the nearest connections are Bob, Claire and Alice. So, we add all three of them in the queue (in no particular order). Now, we will pop elements off the queue. Popping an element means that we have visited that element. After popping an element, we add neighbours of that element to our queue. So, let us visit Alice. If Alice is a mango seller, then we have found a mango seller and we can stop our operation right here. Else if Alice is not a mango seller, we add all its neighbours to the queue. Please note that some authors use 'enqueue' instead of 'push' and 'dequeue' instead of 'pop'. Both of them mean the same thing. We do this with all the remaining elements until we find a mango seller. Please note that if we have visited a node, we do not need to visit it again. So, for example, we have added Peggy to our queue while popping Alice. Now, when we pop Bob, we only need to add Anuj to the queue. We do not need to add Peggy again. If we do not find a mango seller in the queue, then mango seller does not exist in the graph. This was the implementation of Breadth First Search using queues. Breadth First Search can be applied on Trees much the same way it is applied on Graphs.