Intro to Computational Thinking and Problem Solving Unit-1 part 2 PDF

# Example ## Black and White Image A black and white image in a grid could be encoded using the bits shown: | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |---|---|---|---|---|---|---|---| | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | 0...

# Example ## Black and White Image A black and white image in a grid could be encoded using the bits shown: | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |---|---|---|---|---|---|---|---| | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | ## 5. Sound Digital audio has emerged as the primary method for recording, processing, and distributing sound through various platforms like online music stores, DVD movies, and phone calls. Sound, a physical phenomenon conveyed through waveforms in the air, undergoes conversion to digital format using a microphone, which captures an analog electric signal. The signal is then sampled at regular intervals, generating a sequence of numerical values. The pitch of the sound, determined by its frequency measured in hertz (Hz), lies within the human ear's perceptible range of 20Hz to 20kHz. The Nyquist-Shannon sampling theorem states that the rate at which samples are taken must be at least twice that of the sampling of the highest frequency signal that is to be measured. To encompass the full range of human hearing, a minimum sampling rate of 40kHz is necessary. As a result, CDs are sampled at 44.1kHz, DATs at 48kHz, and DVDs at 96kHz. For instance, if a five-minute song is sampled at 48kHz, it would be encoded as a sequence of 14,400,000 samples. Assuming each sample is an 8-bit string, the song's size would be approximately 1.4MB. However, using more than 8 bits per sample would proportionally increase the encoding size. For example, CDs employ 16 bits per sample, while DVD mastering involves 24 bits per sample. ## Classic Puzzle Solving In the sphere of problem-solving, evident recurring patterns emerge when transitioning between various domains of problems. Recognizing parallel solved and unsolved issues can yield highly valuable insights, enhancing the effectiveness of problem-solving endeavors. This section delves into timeless puzzles that extend beyond the realm of programming, offering enlightening principles that can be applied to programming challenges. ### The Fox, the Goose, and the Corn **Problem**: How to cross the river? A farmer needs to cross a river with a fox, a goose, and a sack of corn. He uses a boat to cross the river. He can carry only one of the three items with him on the boat. He can't leave the fox and the goose alone because the fox will eat the goose. He also can't leave the goose and the sack of corn alone because the goose will eat the corn. So how will the farmer cross the river with all three items? **Solution**: We are left with only one option - the farmer takes the fox with him and crosses the river. So, he leaves the fox there. But the goose is also there, so he takes the goose and comes back. Now, he keeps the goose there and takes the sack of corn with him and crosses the river. Now the fox is left with the sack of corn on the other side of the river. The farmer comes back and takes the goose with him and crosses the river. Now the farmer and all of his items are safely on the other side of the river. ## Sliding Tile Puzzles **Problem**: The Sliding Eight The puzzle has eight square tiles numbered 1-8, plus a black space on a 3x3 grid. The goal is to arrange the tiles in row-major order using as few moves as possible. You can move tiles vertically or horizontally into the blank space. **Solution**: A strategy known as the "train" technique entails cyclically rotating a sequence of tiles around an empty space to preserve their relative positions, facilitating puzzle solving resolution. This strategy's applicability extends to larger puzzles, underscoring the practicality of dissecting challenges into more manageable constituents. The core lessons gleaned from this journey in puzzle solving underscore the importance of employing systematic approaches, even when a conclusive solution is not immediately apparent. Additionally, the effectiveness of sub-dividing problems into achievable subtasks is highlighted as a means to accumulate insights and accomplish distinct goals. ## Sudoku **Problem**: Completing a Sudoku Square A 9x9 grid is partially filled with single digits (from 1-9), and the player must fill in the empty squares while meeting certain constraints: - In each row and column, each digit must appear exactly once. - In each marked 3x3 area, each digit must appear exactly once. **Solution**: The ultimate goal is to ensure that each digit appears exactly once in a row, column, and 3x3 sub-grid. Starting with the least restricted region, like an incompletely filled 3x3 sub-grid, aids in narrowing down potential choices. Once a value is established for a cell, subsequent decisions are influenced by existing placements. This methodology underscores the quest for cells with the minimal numbers of possible values. The core takeaway from Sudoku involves pinpointing the most constrained aspects of a challenge, as constraints aid in simplifying decision making by limiting options. This principle extends beyond the realm of Sudoku, being relevant in fields such as artificial intelligence. In scenarios involving constraint-based problems, the "most constrained variable" principle is pivotal for efficient resolution. This principle suggests initiating tasks by addressing variables with the fewest feasible values, thereby streamlining the problem-solving process. ## The Quarrasi Lock **Problem**: Opening the Alien Lock A hostile alien race, the Quarrasi, has landed on Earth, and you've been captured. You've managed to overpower your guards, even though they are enormous and tentacled, but to escape the (still grounded) spaceship, you have to open the massive door. The instructions for opening the door are, oddly enough, printed in English, but it's still no piece of cake. To open the door, you have to slide the three bar-shaped Kratzz along tracks that lead from the right receptor to the left receptor, which lies at the end of the door, 10 feet away. That's easy enough, but you have to avoid setting off the alarms, which work as follows: - On each Kratzz are one or more star-shaped crystal power gems known as Quinicrys. - Each receptor has four sensors that light up if the number of Quinicrys in the column above is even. - An alarm goes off if the number of lit sensors is ever exactly one. - Note that each receptor has four alarms, and each alarm is separate. You can't ever have exactly one receptor's alarm or one sensor lit for the left receptor or for the right receptor. The good news is that each alarm is equipped with a suppressor, which keeps the alarm from sounding as long as the button is pressed. If you could press both suppressors at once, the problem would be easy, but you can't, since you have short human arms rather than long Quarassi tentacles. Given all of this, how do you slide the Kratzz to open the door without activating either alarm? **Solution**: This is a tricky puzzle. The key to solving it lies in understanding the Quarrasi lock's alarms. - **You need to slide the three Kratzz bars, currently in the right receptor, to the left receptor without setting off either alarm.** This can be done by understanding how the alarms work. - **A sensor is lit when an even number of star-shaped Quinicrys appear in the column above, and an alarm sounds if exactly one connected sensor lights up.** - **Suppressors can keep an alarm from sounding, but only for the receptor where you are standing.** **Therefore, here's how to do it:** - **Slide the upper Kratzz to the left receptor.** This will leave the right receptor out of reach. - **The second sensor for the right alarm is lit because an even number of Quinicrys appears in the column above, and an alarm sounds when exactly one of its sensors is lit.** This strategy leverages the fact that you can manipulate the alarms by strategically positioning the Kratzz bars. By keeping the right receptor out of reach, you eliminate the risk of accidentally triggering its alarms. The left receptor's alarms also work in your favor since only one sensor lighting up will cause the alarm to go off, ensuring the right number of Quinicrys on each Kratzz can prevent this from happening. ## General Problem Solving Techniques - **The depicted examples underscore essential problem-solving techniques.** Integrating these guidelines into your methodology will provide a consistent structured approach to effectively tackle problems. ### Always Have a plan: - The cardinal principle emphasizes the necessity of creating a plan rather than proceeding without direction. Even if the problem remains partially unsolved in your mind, formulating a plan to uncover the solution is indispensable. - Although plans might require adjustments or complete overhauls, their significance lies in the act of planning itself. - Drawing parallels to military strategy underscores this point: while plans might falter in tumultuous situations, planning plays a pivotal role in orchestrating efforts and comprehending the task at hand. ### Restate the Program: - Restating a program can unveil a misconstrued original objective. - A narrative involving a grandmother and her crying baby exemplifies this concept. Through revisiting the problem, it became evident that the aim wasn't to confine the baby, but to enable the grandmother to knit undisturbed. - Despite restatement's potency, its indirect link to coding or solution formulation might cause programmers to underestimate its value. This accentuates the importance of planning, which can integrate "formally restate the problem!" as a pivotal initial step. - Even if restatement doesn't yield immediate insights, it bears advantages. - For instance, when assigned a task by a supervisor or instructor, presenting a rephrased version can validate your understanding. ### Divide the Program: - Breaking down a problem into distinct steps or phases can greatly simplify its resolution. - Dividing a problem into smaller segments can yield more manageable solutions, often even more so than just halving the challenge for each segment. - This concept is illustrated by the example of sorting tiles using insertion sort and categorizing them into groups for alphabetical arrangement. - The integration of programming techniques can be more intricate than using them individually, as demonstrated by intricate nested control structures. ### Start with What You Know: - The common advice given to new writers, encouraging them to write about familiar topics, also translates well to programming. - Much like writers should begin with subjects they are well acquainted with, programmers should initiate their work by leveraging their existing knowledge and then expanding upon it. - Fragmenting a problem and addressing the components within their grasp can yield insights into resolving the remaining aspects of the task. - This step-by-step approach, built upon utilizing existing expertise, not only enhances confidence and sustains progress but also aligns with the principle of achieving substantial strides in problem-solving. ### Reduce the Problem: - The problem-solving technique under discussion entails the simplification of intricate problems by adjusting their constraints: either by introducing new ones or eliminating existing ones, until a version of the problem that's within your capability to solve is attained. - This method is illustrated through an example involving the identification of the closest coordinates among a collection of three-dimensional points. Confronted with a formidable original problem, you possess the flexibility to modify it in diverse ways to enhance comprehension. - For instance, you could reduce it to a two-dimensional context or even distil it to a comparison of two numbers, focusing on the minimum absolute difference. - This technique empowers you to engage with a more manageable rendition of the problem in scenarios where a direct division into steps is less apparent. ### Look for Analogies: - An analogy is a similarity between a current problem and a problem already solved that can be exploited to help solve the current problem. - The similarity may take many forms. Sometimes it means the two problems are really the same, like we discussed earlier in the fox, goose, and corn problem and the Quarrasi lock problem. - Sometimes similarity concerns only part of the problems. - For example, two number processing problems might be different in all aspects except that both of them work with numbers requiring more precision than that given by built-in floating-point data types. - You can't use this analogy to solve the whole problem, but if you are already figured out a way to handle the extra precision issue, you can handle that same issue in the same way again. - Although recognizing analogies is the most important way you will improve your speed and skill at problem-solving, it is also the most difficult skill to develop. Why difficult? Because at first, you can't look for analogies until you have a storehouse of previous solutions to reference. ### Experiment: - It is important to experiment with different methods and observe the outcomes. It's a systematic process where you formulate hypotheses about code behavior, test them, and assess their accuracy. - Experimentation holds particular value when navigating application programming interfaces (APIs) or class libraries. - For example, when working with a new library class, like a dynamic vector, you can create a separate program to explore its functionalities and assess specific scenarios of interest. - This program, known as a "vector demonstrator," can become a valuable reference for the future. ### Do Not Get Frustrated: - Strive to avoid frustration: frustration hampers clear thinking, efficiency, and productivity. - While new programmers might argue that managing frustration is challenging, unlike a physical reflex, the frustration induced by programming is self-directed, arising from the programmer's own thoughts. - To avoid frustration while dealing with that, take a break. - During breaks, detach from the problem and engage in unrelated tasks, only returning to the issue and examining the problem properly once the break concludes. ## Pseudocode - Pseudocode is a way to describe what a computer program or algorithm should do in a readable, formal style. - It's a blueprint for translating the logic of the code into any programming language. - It does not use any programming language; instead, it uses the simple English language text as it is intended for human understanding. **Here's an example illustrating pseudocode, outlining a fundamental algorithm to compute the sum of two numbers:** ``` Start Input num1 Input num2 Sum = num1 + num2 Output sum End. ``` - In this example, "START" and "END" signify the initiation and conclusion of the algorithm. - "INPUT" and "OUTPUT" are utilized to indicate collecting input from the user and displaying output to the user. - The operations themselves are described using straightforward, language resembling English, providing a structure of the steps involved without delving into the specifics of syntax associated with a specific programming language.