COR-IS1702 Computational Thinking Notes PDF

Preview

Summary

💻Computational ThinkingCreated TagsPaper AssignmentCountingBasic Counting PrinciplesThe two basic counting principles: Product Rule Sum Rule The product rule applies when a procedure is made up of separate tasks.💡 Product Rule: tasks. If there are ways to do the first task and for each of these ways...

Description

Computational Thinking

Paper Assignment

Counting Basic Counting Principles The two basic counting principles: Product Rule Sum Rule The product rule applies when a procedure is made up of separate tasks.

Product Rule: Suppose that a procedure can be broken down into two tasks. If there are n1 ways to do the first task and for each of these ways, there are n2 ways of doing the second tasks, then there are n1 n2 ways to do the procedure

Example: 1) A new company with just two employees rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees? No. ways = 12 x 11 = 132 2) The chairs of an auditorium are to be labeled with an uppercase Eng letter followed by a positive integer not exceeding 100. What is the largest number of chairs that can be labelled differently? positive integer does not include 0 No. ways = 26*100 = 2600 3) There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many diff ports to a microcomputer in the center are there. no.ports = 32 x 24 = 768 4) How many different bit strings of length seven are there? Each of the seven bits can be chosen in two ways (1 or 0). Hence, no. diff bit strings = 27 = 128. Counting Functions How many funcitons are there from a set of m elements to a set with n elements ? Answer = nm

Sum Rule

both things cannot be done at the same time

Example:

More complex counting problems require both rules

Inclusion-Exclusion Principle If two things can be done at the same time, the sum rule will lead to double counting. In this case, we add the number ways to do each task and then subtract the number of ways to do both tasks.

A∪B = A + B − A∩B

Example: How many integers from 1 to 1000 are multiples of 3 or multiples of 5? Multiples of 3 = 1000/3 = 333 Multiples of 5 = 1000/5 = 200 Multiples of 3 AND 5 = 1000/15 = 66 Total = 333 + 200 -66 =467

Permutations A permutation of a set of objects is an ordered arrangement of these objects. Number of permuations of a set of length n is n!

An r-permutation of a set of n objects is an ordered arrangement of r of the n objects.

Number of r-permutations of a set of length n is nPr = n! /(n-r)! Note: nPn = n! 0! = 1 n! = n[(n-1)!]

Permuation with Replacement Same as choosing when each, r, has n options

nr

The number of permutations of r objects drawn from n distinct objects with replacement is nr Imagine filling up r slots where r = 4 and n=10 ____ since the no. of options for each slot is always n no. ways =

10 4

Permutation Involving Identical Objects Example: a) Permute the letters AAB there are 3 ways only since the 2 As are identical No. ways = 3! / 2! = 3 b) Permute the letters ABBA No. ways = 4!/2!2! = 6

In a set of n objects if there are n1 of them of the 1st kind, n2 of them of the 2nd kind, ...., nk of them of the kth kind, where n1+n2+....+nk = n Then the number of permutations of these n objects taken all at a time is

n!/(n1 !n2 !...nk !)

Other examples: Case Situations A box contains 4 B and 3 W balls. 5 balls are taken out of this box and arranged in a row from left to right. How many possible arrangements are there? Cases: Case 1: 4 Black and 1 White No. ways = 5! / 4! Case 2: 3 Black and 2 White No. ways = 5! / 3!2! Case 3: 2 Black and 3 White No. ways = 5! / 2!3! Total ways = 5 +10+10 = 25

Permutation with Restrictions Arrange three math books and four science books where the three math books have to be together No. ways to arrange within math books = 3! No. ways to arrange math + 4 science books = 5!

Total ways = 3! x 5! Consider math books as one block and science books as 4 blocks → total 5 blocks Example How many ways can the letters of the word "CREATION" be arranged if total num letters = 8 num_vowels = 4 1. First letter is a vowel v________ no. ways = 4 x 7! =20160 2. The letter I is next to letter O group I and O together as one block total blocks now = 7 No. ways = 7! x 2! (ways to arange I and O) 3. I and O are separate (take compliment) Solving this directly is tedious So, find total num ways - ways where they are together Total ways = 8! No. ways separate = 8! - (7! x 2!)

Circular Permutations The Number of ways to arrange n distinct objects in a circle is (n-1)!

When the seat are numbered, the number of ways to arrange n distinct objects in a circle is n!

Combination A combination of a set of objects is an unordered selection of these objects

The number of combinations of a set of length n is 1 Note that a set contains no duplicates

An r-combination of a set of n objects is an unordered selection of r objects out of the n objects.

In-Class Exercises Q1. Every car registered in Singapore has a license plate number, which begins with a letter‘S’, followed by two other letters, 4 digits, and another letter (all upper case) How many possible license plate numbers are there? S _ _ {d}{d}{d}{d}_ Num uppercase letters = 26 Num digits = 10 (0-9) Possible choices = 26**3 x 10**4 Q2. It turns out that all plate numbers begining with SH are for taxis only. How many possible license plate numbers for private car owners? S {all but H}{alpha){d}{d}{d}{d}{alpha} Possible choices = 25 x 26**2 x 10**4 Q3. You are supposed to create a new password. Min 6 characters and max 8 characters. Alphanumeric characters (letters & numbers). Case insensitive. The password has to contain at least one digit. How many possible passwords are there? Min 6 Chars, Max 8 Alphanumeric = 26 + 10 = 36 6 Chars = 36**6 - (26**6) [no digit]

7 Chars = 36**7 - (26**7) [no digit] 8 Chars = 36**8 - (26**8) [no digit] Total Possible = (36**6 - 26**6) + (36**7 -26**7) +(36**8 -26**8)

at least one digit means auto do complementary

Q4. If passwords may contain lower case letters and digits, how many 6-character passwords start with a lower case letter ‘a’ or ends with a lower case letter ‘z’? 3 situations Start with a: a_ _ _ _ _ 36*5 End with z: _____z 36 * 5 Start with a and end with z: a____z 36 * 4 Total: 36^5 + 36^5 - 36^4 Q5 (i) How many permutations of the letters A to H if the three letters ABC have to occur consecutively? (ii) What if they must appear together, but not necessarily consecutively? 1) Group ABC as 1 block or letter. So total num of letters = 8 - 3 +1 = 6 Num permutations = 6! 2) If they must appear together but not consecutively Num permutations of blocks = 6!

Num permutations of ABC = 3! Total = 6! x 3! Q6. You are inviting 3 other guests (so there are 4 diners including yourself) to have dinner at home. Your dining table can seat 6. How many different seating arrangements can you have? 6 seats , 4 diners 6P4 = 6!/2! = 360 Q7. We would like to form a 7-member committee, consisting of 3 faculty members and 4 students. There are 40 faculty members and 300 students. How many different ways can we form the committee? 40C3 x 300C4 = 3,268,216,809,000 Q8. How many ways are there for 3 men and 3 women to stand in a line so that no two women stand next to each other? WMWMWMW Permute man = 3! Permute women = 4P3 Total = 4P3 x 3! = 14

Questions to ask; Qn 7

Week 2: Algorithms Problem: Prime Numbers A number is prime if it cannot be written as the product of two smaller numbers. Eg. 5,11,73,9967 Composite if it is not a prime number. E.g. 10(2 x5), 99(3x3x11) The Sieve of eratosthenes → used to return a list of prime numbers from 1 to n

Sieve of Eratosthenes Pseudocode 1. Make a list of numbers from 2 to n 2. Repeat until list is empty a. the 1st number in the list is prime b. cross off multiples of the most recent prime

Implementing an Algorithm as a Program The method described on the prev slide works well for short liist

What about finding prime numbers between 2 and 100 or 1000?

Python considers strings and lists to be special cases of a more general type of object called a sequence, which means operators and methods defined for lists often do a similar operation on strings, and vice versa.

Sieve of Eratosthenes

first two elements is None because 0 and 1 are none first prime number is 2, hence for loop starts at 2.

Week 3: Algorithms and Complexity Complexity Characterizing the effeciency of Algorithms Measurement of Efficiency Big O notation Orders of Complexity

Algorithms Defined: A specification for how to carry out a computation An algorithm contains a complete description of The set of inputs or starting conditions A full specification of the problem to be solved The set of outputs

Description of valid solutions to the problem A sequence of operations that will eventually produce the output Steps must be simple and precise can be described as a program, pseudo-code or a less formal step by step explanation An algorithm must be Correct Efficient Time complexity Space complexity When n (input) is small there is a possibility that a better algo might take longer than a less efficient one

Attributes of Algos PRECISE They must be written in terms understandable by anyone EFFECTIVE A step must help the algorithm progress to the final goal PRACTICAL A sequence of precise and effective steps may not be useful in practice Example: hypothetical algorithm for winning a chess tournament: “for each game, consider all possible moves, choose the best”

Algorithm Supports Abstraction

There can be more than one algorithm to transform the input to the desired output

INPUTS : Two Non-Negative Integers a and b ALGORITHM: ??? OUTPUT: The gcd of a and b

First Algo: Brute Force

Second Algorithm: Djikstra's Algorithm

What makes a good Algorithm? Correctness: Produces the right output given the input Efficiency Uses as little memory as possible (Efficient in space) Related to data structures Runs as fast as possible (efficient in time)

Performance Is a Function of Input Size!! An algorithm's time performance is a function of the input size Most of the time, we use the letter n to represent the input size Example: Problem: find the largest number in an array a of n numbers

def findMax(a): max_a = a[0] for i in range(1, len(a)): if max_a < a[i]: max_a = a[i] return max_a

Number of comparisons = (n-1) Number of comparisons = at most n

a) assignment = 1 Comparison = 9 Assignment at most 9 Total = 18

Efficiency Efficiency is a matter of growth rate How the number of operations grows as the input size increases

A more efficient algorithm has a slower growth rate in running time as the input size increases

Note that when n is small, the more efficient algorithm might be slower than the less efficient one But with that input size, the difference in time is negligible

Asymptotic Order of Growth Asymptotic analysis is about describing the behaviour of mathematical functions "in the limit" we want to know how the function behaves as the input gets larger and larger without bound, towards infinity Why "in the limit" ? Small input sizes have fast running times and cause no issue We are usually concerned with the worst-case complexity Why worst case and not best case or average case?

Best case is often a "special" situation that does not apply to most inputs Average case is difficult to determine without knowledge of the real world frequencies of input occurrences Worst case is a good predictor of "difficulty" of problems

Big O notation Capital letter O to specify an algorithm's order of complexity Represents the concept of "Upper bound" EG

O(n2 ) means an algorithm is of the order n2 For large n the number of operations is approximately n**2

Algorithms with the same order of complexity are asymptottically equal in efficiency

Dominance rules for Big O notation Exponential dominates polynomial, which dominates logarithmic If number of operations is 2**n + n**2, complexity is O(2**n) If number of operations is n**2 + log n, complexity is O(n**2) Higher order dominates lower order If number of operations is n**3 + n**2 + n, the complexity is O(n**3) Ignore multiplicative constants in the highest-order term If number of operations is 3n**2, the complexity is O(n2)

3n**2 is not the same as (3n)**2. we do not drop the latter

Why Drop Multiplicative Constant?

✦ When we use big-O notation, we drop constants and low-order terms. This is because when the problem size gets sufficiently large, those terms don't matter. ✦ However, this means that two algorithms can have the same big-O time complexity, even though one is always faster than the other. For example, suppose algorithm 1 requires N**2 time, and algorithm 2 requires 10 * N**2 + N time. For both algorithms, the time is O(N2), but algorithm 1 will always be faster than algorithm 2. In this case, the constants and low-order terms do matter in terms of which algorithm is actually faster. ✦ However, constants do not matter in terms of how an algorithm "scales" (i.e. how does the algorithm's time change when the problem size doubles). Although an algorithm that requires N**2 time will always be faster than an algorithm that requires 10*N**2 time, for both algorithms, if the problem size doubles, the actual time will quadruple. When two algorithms have different big-O time complexity, the constants and low order terms only matter when the problem size is small. For example, even if there are large constants involved, a linear-time O(n) algorithm will always eventually be faster than a quadratic-time O(n**2) algorithm.

Steps towards Big O

Complexity Helps to Answer These Questions

Question For addition of Functions eg. f(n) and g(n) if f(n) complexity is O(n) and g(n) complexity is O(n**2)

Week 4: Iteration and Decomposition Learning outcomes Understand the concept of iteration and decomposition as exemplified by searching and sorting algos Analyze the best cases and the worse cases of an algo Able to compare the complexity of algorithms

Linear Search Aka sequential search Concept Start at the beginning of a collection and compare items one after another Terminologies

item to be searched = Key Type of search also called scan if key not found, search fails

Search Function

Performance how many comparuisons will linear search algo make as it searches through an array with n items aka how many iterations, For an unsuccessful search make n comparisons For a successful search, anywhere between 1 and n best case: 1 worst case: n average: (n+1)/2

Binary Search Divide and conquer strategy to search through an array

The Array must be Sorted!!!

The array must be sorted wont work if not sorted

Method To search a list of n items, first look at the item in the middle location n / 2 Then search either: the region from 0 to n/2-1 the region from n/2+1 to n-1

Detailed Description The algorithm uses two variables to keep track of the boundaries of the region to search lower = index value one below leftmost region upper = index value one above rightmost region

Perform iteration that keeps making the region smaller and smaller The initial region is the complete array the next one is either the upper half or lower half The one after that is one quarter, then one eight then....

Example: Searching for 57 is list of size 15

Unsuccessful Searches

Full Algo

Complexity

Summary for Linear and Binary

Sorting Insertion Sort

The important property of the insertion sort algorithm: at any point in this algorithm left part of the array is already sorted The item we currently want to find a place for will be called the key items to the left of the key are alr sorted The goal on each iteration is to insert the key at its proper place in the sorted part Basic idea: Pick up an item, find the place it belongs, insert it back into the array Move to next item and repeat

Algo Insertion sort algorithm 1. the initial key is the second item in the array (the Q in this example) 2. use your left hand to pick up the key 3. Try to move the key to as left as possible, until you find an item lower than the one in your left hand, or the front of the array, whichever comes first 4. the new key is the item to the right of the location of the previous key 5. go back to step 2 ✦ This new version is precise enough that we can write a Python function that implements this algorithm

Example

Python

Complexity

Scalability

Merge Sort algo works from the bottom up start by solving the smallest pieces of the main problem keep combining results into larger solutions eventually the original problem will be solved

but max number of comparisons is (2xgs)-1

(2*g) -1 is worst case only a requires 4 comparisons only b requires 7 comparisons (aka 2 * g -1)

Complexity

Scalability

ICE:

Week 5: Recursion Expressing a problem in terms of smaller version of itself A recursive algorithm is an algorithm that, as part of its operations, invokes itself over a smaller problem space. It is also based on the key idea of decomposition Breaking a large problem into smaller subproblems An alternative to iterative algorithms relying on loops In terms of definition, recursive algorithms are simpler and more elegant In terms of computation, they are not always more efficient than iteration

To iterate is human, to recurse divine

1st Example of Recursion Calculating compound interest rate If we place a deposit of x dollars with interest rate of r percent per year y number of years, how much money do we have upon maturity ? Solution using iteration:

# x is principal, y is no. years def maturity_iter(x,r,y): for i in range(y): x *= (100 + r)/100 return x

Fundamentals of Recursion A recursive algorithm calls itself to solve the smaller pieces Each recursive call should deal with a smaller instance of the same problem Reduction step A set of rules that reduce other cases towards the base case There must be a stopping point, otherwise the result is infinite recursion Base Case The simplest possible cases that cannot be reduced anymore

2nd Example of Recursion: Factorial Compute the factorial n! of an integer n

n! = n x (n-1) x (n-2) x .... x 1 Reduction step: n! = n x (n-1) ! 4! = 3! = 4 x 3 x 2! = 4 x 3 x 2 x 1! Base case: 1! = 1

Recursive Algorithm for Factorial Let's write a recursive algorithm factorial(n) to compute n! Reduction step: Factorial (n) = n x factorial(n-1) Base case: factorial(1) = 1

def factorial(n): if n == 1: return 1 else: return n * factorial(n-1)

Tracing Recursive Calls

Iterative vs. Recursive for Factorial

Worst-case complexity is O(n) for both iterative and recursive algorithms

3rd Example of Recursion: Fibonacci

Recursive Algorithm for Fibonacci Reduction: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) Base Cases: when n = 0, return 0 when n = 1, return 1 Can have 2 base cases

def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2)

Every invocation leads to two recursive calls with similar problem size ~n

Tracing Recursive Calls Base cases do not lead to further recursive calls For fibonacci → fibonacci(0) and fibonacci(1)

no. of additions for fibonacci(3) = no.additions for fibonnaci(2) + 1 In general, no. of additions for fibonacci(n) = no. additions for fibonacci(n-1) + no. additions for fibo...