Computer-Science

Programs related to the field of Computer Science are expessed here. More on Computer Science is at the following link: https://www.pinterest.com/HamedShahHosseini/

1. Determinant from scratch with Python by converting matrix to triangular one.
2. Cramer's rule for solving a system of linear equations.
3. Matrix inversion by the cofactor matrix from scratch in Python.
4. Matrix inversion by Gauss-Jordan elimination from scratch in Python.
5. Fast Fourier Transform (FFT), one-dimensional, from scratch in Python. Also, Discrete Fourier Transform (DFT) from scratch is also included.
6. Divide and Conquer: Quicksort from scratch in Python.
7. Dynamic Programming: Fibonacci numbers in Python.
8. Singly Linked Lists from scratch with Python. An example is also given to implement a stack having functions: push and pop.
9. Complex numbers, introduction: Here, we review complex numbers in both rectangular and polar forms by reminding Euler's formula and De Moivre's formula. Also, we review doing arithmetic for complex numbers in Python.
10. Absolute and relative errors are reviewed. When we don't know the true value, we may use approximate value in measuring the mentioned errors. A Python example is also provided.
11. Root finding, Bisection method: It is a bracketing method to find one root of a continuous function, given the interval [a,b] in which the root exists. It is assumed that f(a)f(b)<0.
12. Root finding, False Position method: This root finding method is also a bracketing method with the same assumptions we make for the bisection method. However, it is usually faster than the bisection method.
13. Root finding, Fixed Point Iteration: This is an open method such that it starts by an initial guess of the root, and then it uses an iteration to get closer to the real root.
14. Root finding, Secant method: We give two initial guesses of the root. Then, the method creates a secant line which intersects the x-axis at a value that is usually a better estimate of the root.
15. Matrix-vector multiplication as a linear combination: It is possible to express the product of a matrix by a vector as a linear combination of the columns of the matrix by the components of the vector as weights. Here, we mention this property with an example in Python code.
16. Trace of a matrix: Trace is defined on a square matrix, which is the sum of the elements on the main diagonal of the matrix. We review the trace function with some properties of the trace. Also, we check those properties in an example with Python code.
17. Determinant: Determinant is reviewed again here with some of its properties. The Laplace expansion is also mentioned. Moreover, minors and cofactors of the given matrix are computed.
18. Euler method: The Euler method is used to find solutions to ordinary differential equations(ODEs). It is a simple method which is also easy to implement. In fact, it is a numerical method for integration, which can be used for initial value problems (IVPs). Here, we bring the Python code with an example.
19. Monte Carlo method (algorithms): A Monte Carlo method (algorithms) refers to a broad class of computational methods that use random sampling to estimate numerical results, especially when analytical solutions are difficult or impossible to obtain. These methods are named after the Monte Carlo Casino in Monaco, due to their reliance on randomness and chance. In the Python code here, we give some applications of Monte Carlo method including numerical integration, optimization, and PI estimation.
20. Enumeration algorithms: An enumeration algorithm finds all pssible solutions to a given problem, ony by one, often without duplicates in an efficient way. Thus, it lists all valid solutions to the problem. Here, we review the concept of enumeration algorithms, and then give an example to find all subsets of a given set in two versions: Recursive and Iterative. Also, as a bonus, we express an algorithm to enumerate all permutations of the letters in a word.
21. Heap: A heap is a tree-based data structure, which satisfies the heap property. The heap property for a min-heap requires each parent to be smaller than or equal to its children. Similarly, for a max-heap, each parent is required to be greater than or equal to its children. Here, we first define a heap from scratch in Python. Then, we use it in practice and explore the operations defined for it. It is noted that we have a built-in module in Python for working with heaps. The module is called heapq.
22. Queue: A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. This means that the first element added to the queue will be the first element to be removed. Here, we mention queue by implementing it with three differents methods: list, collections.deque, and linked list. Finally, we compare their performance in terms of time in which deque obviously wins.
23. Priority queue: A priority queue is an abstract data type, similar to queue, with an added feature: Each element has a priority associated with it; and consequently, elements with higher priority are serverd (processed) first. Here, we talk about priority queues and how to implement them in Python. Actually, we use module heapq to do the job. In addition, we show how to employ module queue for priority queue. Also, we provide examples to clear the topic.
24. Disjoint-set data structure: A disjoint-set data structure, also called union-find data structure is a data structure that efficiently tracks a collection of non-overlapping (disjoint) sets, supporting fast union (merge sets) and find (determine set membership) operations. Here, we implement the disjoint-set data strcture from scratch in Python. Then, we use it in an example. As a bonus, we employ union-find for friend groups in social networks.