- Computer Memory and CPU Overview
- Binary
- Flow Chart
- Time & Space Complexity
- Data Structure
- Sorting & Searching
- Algorithms
(click to expand/hide)
- Byte: Consists of eight bits.
- Bit: Simplest form of computing memory.
- Memory Capacity: Number of bytes a computer can hold.
- Core of a computer.
- Processes both information and instructions.
- Works faster than the transfer of information.
- Switches tasks to allow info transfer to cache.
- Closest and fastest memory to the CPU.
- Most expensive type of memory.
- Function: When CPU gets an instruction, it checks cache first.
- If info is in cache: it gets processed.
- If not: CPU accesses main memory.
- Organized in zones: Zone 1 (most important) and subsequent zones (lesser importance).
-
RAM (Read Access Memory):
- Volatile: Info is lost when power is cut.
- Holds data and instructions currently in use.
- More RAM = Faster system due to improved transfer rate.
-
ROM (Read Only Memory):
- Non-volatile: Info retained when power is off.
- Pre-programmed and cannot be altered.
- Contains critical instructions/data, especially during startup.
- External memory solutions.
- Slower access compared to main and cache memory.
- Must transfer info to RAM for access.
- Examples: Cloud storage, external hard drives, memory sticks.
- Memory can be stored side-by-side or spread out throughout your computer. For some insights on this, you might be interested in reading more about heap versus stack memory
(click to expand/hide)
space complexity = input space + auxiliary space
- A discussion of time and space costs and plus some helpful examples
- A Scaler Topics article about space complexity
(click to expand/hide)
- This Array basics article provides an excellent write-up on arrays and how they are initialized and used.
- This article called Immutable data structures in F# provides an analysis of mutable versus immutable data structures:
- This article about First-class objects outlines what a first-class object is
- This article about Understanding Java tree APIs provides some excellent additional insight into different types of trees and the various attributes associated with them.
- This article about Binary trees in C gives a breakdown of how trees are used in C. The focus is on the binary tree and the various types of binary trees and how one would implement them.
- This article about C# collections gives an overview things like arraylist, hashtable, lists and so on implemented in C#.
- This article about Trees provides an informative analysis of trees.
- This article about Array-based lists gives more information relating to lists that are backed by arrays.
- This article called What are static and dynamic data structures gives an interesting breakdown and analysis of static and dynamic data structures
- When discussing hashing the probability of collisions was introduced. Learn more about the statistics behind the birthday paradox.
- An excellent breakdown of graphs with associated terminology;
- Information on heaps how to add and remove from them/
(click to expand/hide)
- Worst case: O(N^2)
- Average case: O(N^2)
- Best case: O(N^2)
- Space complexity: O(1) Auxiliary
- Worst case: O(N^2)
- Average case: O(N log N)
- Best case: O(N log N)
- Space complexity: O(N) Auxiliary
- Worst case: O(N)
- Average case: O(N)
- Best case: O(1)
- Space complexity: O(N) Auxiliary
- Worst case: O(log N)
- Average case: O(log N)
- Best case: O(1)
- Space complexity: O(N) Auxiliary
- Here is an article on Time and space complexity of selection sort. It includes an implementation of selection sort and how one can calculate the complexity involved.
- Here is an article about Quick-sort with a video tutorial and pseudocode. It provides a detailed analysis of various sorting algorithms, comparisons and further links to video explanations.
(click to expand/hide)
- This article provides a comprehensive breakdown of various algorithms that are graph specific. In this article, you will gain both an understanding of the data structure as well as insights into its implementation.
- This article discusses space complexity. In it, you will find a comparison between implementing iterative solutions versus recursive ones.
- This article explains what recursion is and which datatypes are most congenial for its implementation.