Computational Thinking Using

Python
CSE1500
[L-T-P-C: 2-0-2-3]

MODULE – 2
Algorithm Design & Problem-Solving
Strategies

1
Algorithm Design Strategies
Different problems require different approaches.
Some common algorithm design strategies are:
• Brute Force
• Divide and Conquer
• Greedy Method
• Dynamic Programming
• Backtracking
• Branch and Bound

In these we will discuss about Brute fore, Divide and Conquer approaches only.
Note: Other approaches will be learned in higher semesters (Design and analysis
of algorithms DAA)

2
Brute Force

Brute Force

Brute force is the simplest problem-solving technique where all possible solutions are
tried until the correct one is found. It does not use optimization or shortcuts.

Key Features:
• Straightforward and easy to implement.
• Guarantees a correct solution.
• Often inefficient for large inputs (time-consuming).
• Works well for small problem sizes.

3
Applications of Brute Force
Steps Involved
[Link] all possible candidate solutions.
[Link] each candidate against the problem requirements.
[Link] the candidate(s) that satisfy the conditions.

Examples:
1. Searching
• Linear Search: Checking each element one by one in a list/array until the target is found.
• Used when the dataset is small or unsorted.
2. String Matching
• Comparing a pattern with every possible substring in a text.
3. Traveling Salesman Problem (TSP):
• Trying every possible route and picking the shortest one.

4
Applications of Brute Force
Advantages
• Simple to design and implement.
• Can be applied to a wide range of problems.

Disadvantages
• Very slow for large input sizes.
• Not efficient in terms of time and memory.

5
Divide and Conquer
Divide and Conquer:

Divide and Conquer is a problem-solving technique that breaks a large problem into
smaller sub-problems, solves them recursively, and then combines their results to get the
final solution.

Key Features
• Recursive approach.
• Efficient for large data sets.
• Reduces problem complexity compared to brute force.

6
Divide and Conquer
Steps Involved
1. Divide: Break the problem into smaller sub-problems of the same type.
2. Conquer: Solve the sub-problems recursively (if sub-problems are small, solve them
directly).
3. Combine: Merge the solutions of the sub-problems into a final solution.

Examples
• Binary Search: Divide the array into halves and search only one half each time.
• Merge Sort: Divide the array into halves, sort each half, then merge.
• Quick Sort: Partition the array around a pivot and recursively sort sub-arrays.
• Matrix Multiplication (Strassen’s Algorithm): Breaking down matrix multiplication into smaller
multiplications.

7
Divide and Conquer

Advantages
• Faster and more efficient than brute force for many problems.
• Can be applied to complex problems like sorting, searching, and optimization.
• Provides a clear recursive structure.

Disadvantages
• Recursive calls may use more memory (stack overhead).
• Not always the most efficient if the problem is small.
• Requires careful design to avoid recomputation (may need dynamic programming in some
cases).

8
Iteration: Loops

Python supports 2 types of iterative statements.

While loop:
It executes a sequence of statements repeatedly as long as a condition remains true. The syntax
of the while loop is given as follows:

while test-condition:
#Loop Body
statement(s)

Here while is a key word and test-condition is a relational or logical expression which results True
or False values. Condition must be followed by colon.

9
while loop

As long as the test condition is true, the statements (body of the loop) are executed. Once the
condition becomes false, the iteration terminates and control continues with the first statement
after the while loop.

Note that if the condition false very first time then body of the loop would never be executed.

Example)
# to display numbers from 1 to 5
n=1
while n<=5:
print(n)
n=n+1
print(“end of the program")
Note : we use indentation to define body of the loop.

10
for loop

The for loops in Python are slightly different from the for loops in other programming languages
(such as c and java).
The Python for loop iterates through sequences such as list, tuple, dictionary, set, or a string.
It iterates through each value in a sequence.

The syntax of for loop is given as follows:

variable -> takes the value of each item in the sequence one by one.
sequence -> a collection (like list, tuple, string, range, dictionary, etc.).
The block of code executes once for each value in the sequence.

11
for loop
Example 1) iterating a string using for loop:

skill = 'Python’
# iterate over each character in skill
for x in skill:
print(x)

Example 2) Using range()

for i in range(5):
print(i,end="\t")

Output: 0 1 2 3 4

Note: By default, range(n) generates numbers from 0 to n-1.

12
for loop
Example 3) Custom Range with Step

for i in range(10, 20, 2):

Output :
10
12
14
16
18

Note: optional keyword else can be used with while and for loop.

13