Algorithms and Complexity (Week 1, Lesson 3) PDF

Task of the Day 1 def has_duplicates(arr): n = len(arr) for i in range(n): for j in range(i + 1, n): if arr[i] == arr[j]: return True return False Task of the day 2 def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j=i-1 while j >= 0 and key < arr[...

Task of the Day 1 def has_duplicates(arr): n = len(arr) for i in range(n): for j in range(i + 1, n): if arr[i] == arr[j]: return True return False Task of the day 2 def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j=i-1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr Algorithms and Complexity Bitwise Algorithms Winter semester 24/25 Excerpt from "Cracking the Coding Interview" Definitely Prepare: As a web-based company, Google cares about how to design a scalable system. So, make sure you prepare for questions from "Scalability and Memory Limits." Additionaly, many Google interviewers wil ask questions involving Bit Manipulation, so you are advised to brush up on these topics as well. What's Different: Your interviewers do not make the hiring decision. Rather, they enter feedback which is passed to a hiring committee. The hiring committee recommends a decision which can b e though rarely is-rejected by Google executives. Excerpt from "Cracking the Coding Interview" You're usualy only expected ot know the basics. Here's alist of the absolute, must-have knowledge: For each of the topics above, make sure you understand how to use and implement them and, where applicable, what the space and time complexity is. Bit Bit stands for binary digit. A bit is the basic unit of information and can only have one of two possible values that is 0 or 1. In our world, we usually with numbers using the decimal base. In other words. we use the digit 0 to 9. However, there are other number representations that can be quite useful such as the binary number systems. Manipulating Bits Unlike humans, computers have no concepts of words and numbers. They receive data encoded at the lowest level as a series of zeros and ones (0 and 1). These are called bits, and they are the basis for all the commands they receive. This is why it's important to know algorithms for manipulating bits. Bitwise Algorithms Bitwise algorithms refer to algorithms that perform operations on individual bits or bit patterns within computer data. These algorithms uses the binary representation of data and use the fundamental bitwise operations such as AND, OR, XOR, NOT, and bit shifting to manipulate and extract information from the data. Bitwise Algorithms - Efficiency Bitwise algorithms are usually faster and use less memory than regular arithmetic operations because they work directly with the binary representation of data. This often leads to faster execution times and reduced memory usage. Bitwise Operators An algorithmic operation known as bit manipulation involves the manipulation of bits at the bit level (bitwise). They improve the efficiency of programs by being primitive, fast actions. Bitwise Operators The computer uses this bit manipulation to perform operations like addition, subtraction, multiplication, and division are all done at the bit level. Arithmetic Logical Unit This operation is performed in the arithmetic logic unit (ALU) which is a part of a computer’s CPU. Inside the ALU, all such mathematical operations are performed. Bitwise Operators There are different bitwise operations used in bit manipulation. These bit operations operate on the individual bits of the bit patterns. Bit operations are fast and can be used in optimizing time complexity. The main bitwise operators are: AND (&) OR (|) XOR (^) NOT (~) Left Shift () Bitwise Operator Truth Table Bitwise AND Operator (&) The bitwise AND operator is denoted using a single ampersand symbol, i.e. &. The & operator takes two equal-length bit patterns as parameters. The two-bit integers are compared. If the bits in the compared positions of the bit patterns are 1, then the resulting bit is 1. If not, it is 0. Example Take two bit values X and Y, where X = 7= (111)2 and Y = 4 = (100)2. Take Bitwise and of both X & Y, Example - Code a=7 b=4 result = a & b print(result) Bitwise OR Operator (|) The | Operator takes two equivalent length bit designs as boundaries; if the two bits in the looked-at position are 0, the next bit is zero. If not, it is 1. Example Take two bit values X and Y, where X = 7= (111)2 and Y = 4 = (100)2. Take Bitwise OR of both X, Y Example - Code a=7 b=4 result = a | b print(result) ​Bitwise XOR Operator (^) The ^ operator (also known as the XOR operator) stands for Exclusive Or. Here, if bits in the compared position do not match their resulting bit is 1. i.e, The result of the bitwise XOR operator is 1 if the corresponding bits of two operands are opposite, otherwise 0. Example Take two bit values X and Y, where X = 7= (111)2 and Y = 4 = (100)2. Take Bitwise and of both X & Y Example - Code a=7 b=4 result = a ^ b print(result) Bitwise NOT Operator (~) All the above three bitwise operators are binary operators (i.e, requiring two operands in order to operate). Unlike other bitwise operators, this one requires only one operand to operate. The bitwise Not Operator takes a single value and returns its one’s complement. The one’s complement of a binary number is obtained by toggling all bits in it, i.e, transforming the 0 bit to 1 and the 1 bit to 0. Example Take two bit values X and Y, where X = 5= (101)2. Take Bitwise NOT of X. Example - Code a=5 print("Value of a without using NOT operator: " , a) print("Inverting using NOT operator (with sign bit): " , (~a)) print("Inverting using NOT operator (without sign bit): " , int(not(a))) Left-Shift ( 2) Example Input: Right shift of 5 by 3. Binary representation of 5 = 00101 and Right shift of 00101 by 3 (i.e, 00101 >> 3) Application of Bit Operators Bit operations are used for the optimization of embedded systems. The Exclusive-or operator can be used to confirm the integrity of a file, making sure it has not been corrupted, especially after it has been in transit. Bitwise operations are used in Data encryption and compression. Bits are used in the area of networking, framing the packets of numerous bits which are sent to another system generally through any type of serial interface. Digital Image Processors use bitwise operations to enhance image pixels and to extract different sections of a microscopic image. Algorithms and Complexity Practice Problems on Bitwise Algorithm Winter semester 24/25 How to Set a bit in the number If we want to set a bit at nth position in the number ‘num’, it can be done using the ‘OR’ operator( | ). How to Set a bit in the number If we want to set a bit at nth position in the number ‘num’, it can be done using the ‘OR’ operator( | ). First, we left shift 1 to n position via (1