Unit 3: Algorithms and Problem Solving — Short Questions

Ans A computational problem is one that can be solved using an algorithm, a clear set of steps that a computer can follow to turn input into output.

Ans The three parts are: input (what you start with), process (steps to solve it), and output (the result after processing).

Ans An algorithm is a step-by-step plan to solve a problem, like a recipe that tells a computer exactly what to do.

Ans Algorithms help computers solve problems quickly and correctly. They are the core of all software and apps we use every day.

Ans Input is the data or information given to the algorithm at the start, like a list of numbers or a word to search for.

Ans Process means the steps taken to solve the problem, like sorting a list or finding a specific item.

Ans Output is the final result produced by the algorithm, like a sorted list or a "yes/no" answer.

Ans A well-defined problem has clear goals, known inputs, a defined process, and expected outputs, making it easier to solve with algorithms.

Ans An ill-defined problem lacks clarity in one or more areas, such as unclear goals or unknown inputs, making it harder to model and solve.

Ans It generates possible solutions and tests them one by one until the correct or best one is found.

Ans It's useful when there's no clear shortcut to solving a problem, and you have to try multiple options.

Ans Avoid it when the solution space is very large, as it can take too long and waste time checking many wrong options.

Ans A decision problem is one where the answer is either "yes" or "no," like checking if a number is even.

Ans A search problem involves finding a specific item or solution from a large amount of data, like looking up a name in a phone book.

Ans An optimization problem aims to find the best possible solution, such as the fastest route or the cheapest way to build something.

Ans A counting problem asks how many ways something can be done, like how many different paths exist between two points.

Ans A solvable problem is one where an algorithm exists that will always give an answer in finite time.

Ans An unsolvable problem is one where no algorithm can solve it for all possible inputs, like the Halting Problem.

Ans The Halting Problem asks whether a program will stop or run forever. It's unsolvable because no general algorithm can predict this for all programs.

Ans Studying unsolvable problems helps us understand the limits of computing and avoid wasting time trying to solve what cannot be solved.

Ans A tractable problem can be solved efficiently, usually in polynomial time, meaning it stays manageable even with large inputs.

Ans An intractable problem takes too long to solve as the input size grows, often requiring exponential time.

Ans P includes problems that can be solved quickly (in polynomial time), like sorting or searching.

Ans NP includes problems where solutions can be checked quickly, but finding them may take a long time, like solving a Sudoku puzzle.

Ans It asks whether all problems whose solutions can be checked quickly can also be solved quickly, one of the biggest open questions in computer science.

Ans It helps us understand how efficient an algorithm is in terms of time and memory, so we can choose the best one for the job.

Ans Time complexity measures how long an algorithm takes to run based on the size of its input.

Ans Space complexity measures how much memory an algorithm uses as the input size increases.

Ans Big O notation describes how fast or slow an algorithm gets as the input becomes larger, helping compare different algorithms.

Ans Divide and Conquer breaks a big problem into smaller ones, solves them separately, and combines their results, used in Merge Sort and Quick Sort.

Ans A Greedy Algorithm makes the best choice at each step hoping it leads to the best overall solution, like in coin change.

Ans It can fail when choosing the best local option doesn't lead to the best global solution, like in some path finding problems.

Ans Dynamic Programming solves complex problems by breaking them into overlapping sub-problems and storing results to avoid recomputing.

Ans Problems with overlapping sub-problems and optimal substructure, such as Fibonacci numbers or the Knapsack Problem.

Ans Backtracking builds solutions step by step and goes back if a path doesn't work, often used in puzzles and combinatorial problems.

Ans Bubble Sort is simple and easy to learn, but it's slow for large datasets due to its O(n²) time complexity.

Ans Binary Search cuts the search area in half each time, making it much faster, especially for large sorted lists.

Ans Because Binary Search works by dividing the list in half, which only works if the data is in order.

Ans Sorting Algorithms arrange data in a specific order, making it easier and faster to search, analyze, and process.

Ans Searching Algorithms help find specific items in a dataset quickly and efficiently, like finding a name in a phone book.

Ans Linear Search checks each item in a list one by one until it finds the target, it works on both sorted and unsorted data.

Ans Binary Search finds an item in a sorted list by repeatedly dividing the search interval in half, it's fast with O(log n) time.

Ans BFS explores a graph level by level using a queue, it's good for finding the shortest path in unweighted graphs.

Ans DFS explores as far down a branch as possible before backtracking, it uses less memory than BFS and is good for exploring all paths.

Ans BFS is better for shortest paths; DFS is better for deep exploration. BFS uses a queue; DFS uses a stack.

Ans Graph algorithms help analyze relationships between nodes, like social networks, maps, or web links.

Ans Selection Sort finds the smallest element and moves it to the front, it has O(n²) time and is easy to implement.

Ans Bubble Sort compares adjacent elements and swaps them if they're in the wrong order, it repeats until the list is sorted.

Ans Because it has O(n²) time complexity, which means it gets very slow as the data size increases.

Ans Understanding algorithms helps you write better code, solve problems efficiently, and make smart decisions about which tools to use.