My Computer Science notebooks with Golang 📝. From my bachelor's degree + Books I read recently + Some code snippets.
- It's your laptop or your mobile device. Or your Microwave! but let's have a concise definition of what a computer is : any device that receives, stores, and process information
- We have:
- Different types of computers: desktops, servers, embedded systems
- Different uses of computers: automobiles, graphics, finance, gaming
- Different Manufactures of computers : Intel, Apple, Microsoft, IBM
- Different underlying technologies and different costs
A computer consist of 💻:
- Software
- Operating System
- Compilers
- End user programs : Web Browsers, Email, Video Game
- Hardware
- CPU, Main storage (DRAM,SRAM), secondary storage (Hard Drive, CD), Cache
- I/O Devices : Keyboard, Monitor, Printer
- data : numbers, text, audio, video, images... (eventually it will be represented as binaries)
-
So any computer may have all these things above or some of them. but we can summarize the underlying architecture as the Von Neuman Architecture which represent the components of any modern computer:
- Input/output devices
- Inputs : Keyboard, Microphone, Mouse
- Outputs : Monitor, Printer
- CPU : the brains of the computer, responsible of controlling the internal working of the memory.
- Memory : stores instructions and data, they store information in binary digits or bits (0 or 1)
https://www.youtube.com/watch?v=Ml3-kVYLNr8&t=70s&ab_channel=Computerphile
- Input/output devices
- computers are digital devices which means that they only store information in the shape of binary digits. A single binary digit is a unit of data that corresponds to one of two potential values : 0 or 1 . which is just means true or false , open(1) or close(0) , volt(1) or no-volt(0).
- But again, what is open(1) and close(0) ?
- All the underlying hardware of computers (CPU, RAM, hard-drive, Motherboard...) has been constructed using physical logic gates
- Before we talk about logic gates, let's talk about Boolean algebra and how it impacted significantly the computer science field
- in 1845, a British self-taught mathematician called George Boole Published a book entitled "An Investigation of The law of Thought" which describes the mathematical theories of logic and probabilities. And this is basically Boolean algebra, the foundation of computers today.
- Boolean algebra is a mathematical branch in which you express logic or normal human reasoning mathematically.
- Boolean algebra only has 2 mathematical operations which is add and multiplication, these operations are associated with OR gate and AND gates
- Boolean Algebra operations: Add , multiplication .. let's see how it works !
- We represent all types of information(video, audio, images , documents) using binary digits which is just electrical signals, then it will be carried through a bus (physical wire), the combinations of binary digits will allows us to represent any needed operation and type of data. so combine binary digits and manipulate them through logic gates which opens the the actual gate for the binary signal to pass through or to close the gate on the signal
- A logic gate is defined as a electronics circuit with two or more input signals and one output signal (s)
- Electronic gates require a power supply.
- All the inputs of logics gates are binaries 0 (voltage of 0V) and 1 (voltage of 5V), and the output for a logic gate is a single binary
- Gate Inputs (A,B) are driven by voltages having two nominal, values, e.g. 0V and 5V representing logic 0 and logic 1 respectively.
- in 1938 Claude Shannon, research assistant in a electrical collage published his master's thesis entitled " A symbolic Analysis of Relay and switching circuits". As result of his work, Boolean algebra is the foundation of circuit designs in computers today.
- types of data in the real world
- Text
- Numbers
- Video
- Audio
- Image
- We understand now how computers store information in the form of binary digits, but how we map an image or any type of data to a binary digit ?
- humans invented a system to represent quantity of things based on symbols, and these symbols are numerical symbols (0, 1,2,3...). The most common number systems are: Base 10 and Base 2
- In the human world we use base 10 to describe day to day numerical needs, and it's base 10 because we have 10 possible values 0-9 , why only base 10 not 12 or 13 ? most likely because we have 10 fingers ! so we started to count things based on our fingers.
- but in the computer world we don't have 10 possible values. remember , we only have 0s and 1s . So the second most common number system is base 2, which only holds to possible values 0 or 1
- So any type of data, either it's an image , text, number or anything will be converted to binaries , and from binaries we could store that binary, process it, and convert it back to original human readable form whether it's audio or any other types of data
- In this illustration we can see how we represent numbers in both system (Base 10, and base 2)
- a text is just a collection of characters, and representing characters in computers happens in 2 steps
- Images are collection of colors, and representing colors in a computer happens in 2 steps
- A system to map a color to number
- Most common system is RGB
- converting the number to binary digits
- A system to map a color to number
- A Video is a collection of images
Extra resources :
- Introduction to number systems and binary (video) | Khan Academy
- Decimal to Binary Converter
- CS50: Lecture 0
- An algorithm is every function you created in Golang or any other programming language you programmed in. Any steps (programming statements) you wrote to solve a problem. And all programming problems is about processing data. So, in Computer Science there is field of Algorithms. which focuses on dealing with processing data at scale, and analyzing the performance of an algorithm to solve programming problems such as sorting, searching, removing and so on.
- So before we talk about Algorithms, let's talk about a data that a program might have
- First of all any data in a program has a type. A data type help us define 2 things
- a domain of allowed values
- a set of operations on these values
- And a program compiler will through an compilation error if we misuse a data type, for example performing multiplication on chars
- z = x*y is not allowed
- true/false is not allowed
- Have no component parts. E.g int, char , float, etc
- types that can be broken into parts. for example a Person object consist of two properties : name and an age, both of them are atomic data types (string, int respectively )
- object ⇒ broken into properties
- array ⇒ broken into indeces
- So a data structure is a data type whose values
- can be decomposed into a set of atomic data or another data structure (2D Array)
- include a structure involving the component parts (a fixed technique on how to search, store, remove and so on)
- Possible Structures: Set, Linear, Tree, Graph
- Provide a level of Abstraction : I want to use a data structure but I don't want to know how it's implemented, for example in Golang you can append to a slice but you don't care of the implementation at the time of using the slice data structure
While designing ADTs, a designer has to deal with two types of questions:
-
What values are in the domain? What operations can be performed on the values of a particular data type?
-
How is the data type represented?
-
How are the operations implemented?
-
Generally, the performance factors of a program
- Code Algorithims
- Languages + compilers
- Processer (CPU) speed + Memory ⇒ how fast instruction will be executed
- I/O and number of CPU cores
-
How we can determine the performance of an algorithm.
-
Or compare algorithms and determine which one is better ?
-
first, we need to determine what we mean of "better"
- time complexity ⇒ the time it takes to execute
- space complexity ⇒ the memory it needs to execute
- We will focus on time complexity right now
- Experimental analysis ⇒ compare the running time (benchmarking)
- inputs ⇒ array or objects or any data
- Theoretical analysis ⇒ analyze the algorithms independently of the implementation (software or hardware)
- High-level description of the algorithm instead of an implementation (benchmarking/running-time)
- Characterize running time as function of the input size, n
- takes into account all possible inputs (int, string, float...)
- Allows us to evaluate the speed of an algorithm independently of the hardware/software environment
- So an algorithm depends on the inputs of size n, so the time complexity or running time will vary from input to input. for example sorting an array of 10 numbers is much less time consuming then sorting an array of 100000 numbers! maybe your algorithm in the best vase scenario will take 100 array elements to be sorted. BUT you always count the worst case scenario. which is maybe 10000000 elements. remember, when your input grow your algorithm time and space complexity will increase. and may increase in a huge way
- There is 3 types of possible scenarios
- best case : you count it maybe through some sort of statistics
- average case : you count it maybe through some sort of statistics
- worst case : you defiantly to imagine the worst case scenario (what if the inputs scaled)
- We focus on the worst case running time
- easier to analyze
- critical to games, finance and robotics
- There is 3 types of possible scenarios
- An algorithm is said in-place if it does not require more than O(log n) space in addition to the input.
- An algorithm is said in-place if it does not require more than O(log n) space in addition to the input.