Category Archives: Algorithms

Algorithms, Computer Science Curriculum, Software Engineering Curriculum

Topic 27 – Introduction to Blockchain

Leave a comment

Why do I need to learn about blockchain?

Blockchain offers an interesting and unique solution for applications that require distributed consensus.

Today, a key skill for software developers is the ability to use blockchain-based platforms and tools to solve real-world problems involving distributed agreements.

What can I do after finishing learning about blockchain?

You will be to create decentralized applications (dApps) using platforms like Ethereum or Hyperledger, and smart contract programming language like Solidity.

That sounds fun! What should I do now?

First, please read this book to learn about the core protocols and algorithms in cryptography: Bruce Schneier (1996). Applied Cryptography – Protocols, Algorithms and Source Code in C. Wiley.

After that, please read this book to learn about the core concepts of Bitcoin: Arvind Narayanan et al. (2016). Bitcoin and Cryptocurrency Technologies – A Comprehensive Introduction. Princeton University Press.

After that, please read the books below to learn programming with Bitcoin:

After that, please read this book to learn programming with Ethereum: Andreas M. Antonopoulos and Gavin Wood (2018). Mastering Ethereum. O’Reilly Media.

After that, please read this book to learn programming blockchain using Hyperledger Fabric: Matt Zand et al. (2021). Hands-On Smart Contract Development with Hyperledger Fabric V2. O’Reilly Media.

After that, please audit this course to gain some ideas about the application of blockchain: MIT 15.S12 Blockchain and Money, Fall 2018 (Lecture Slides).

Terminology Review:

  • Public Keys.
  • Private Keys.
  • Digital Signatures.
  • Digital Signature Scheme.
  • Cryptographic Hash Functions.
  • Merkle Tree: Binary Data Tree with Hashes.
  • Bitcoin: Digital money ecosystem.
  • bitcoin: Unit of currency.
  • Bitcoin Users.
  • Bitcoin Wallets.
  • Bitcoin Addresses.
  • Bitcoin Transactions.
  • Blockchain Explorer.
  • Bitcoin Mining, Miners.
  • The Chain of Transactions.
  • Bitcoin Core: The reference implementation of the bitcoin system.
  • Bitcoin Exchanges.
  • Bitcoin Network.
  • Double‐Spending Attacks.
  • Block Chain: Timestamped Append-Only Log.
  • Sybil Attack: Copies of nodes that a malicious adversary can create to look like there are a lot of different participants.
  • Proof of Work: Find a number, or nonce, such that H(nonce || prev_hash || tx || tx || … || tx) < target.
    51‐Percent Attack.
  • Account-Based Ledger: The ledger keeps track of account balances.
  • Unspent Transaction Output: A transaction output that can be used as input in a new transaction.
  • Transaction-Based Ledger: The ledger keeps track of individual transaction outputs.
  • Coinbase Transactions.
  • Bitcoin Scripting Language.
  • Turing Incompleteness.
  • Stateless Verification.
  • Candidate Block.
  • Genesis Block.
  • Ethereum: The world computer.
  • Ether.
  • Externally Owned Accounts (EOAs).
  • Contract Accounts.
  • Solidity.
  • Smart Contracts.
  • Ethereum Clients.
  • Ethereum Networks.
  • Permissionless Blockchain.
  • Permissioned Blockchain.

After finishing blockchain, please click on Topic 28 – Introduction to AI Agent Development to continue.

 

 

Algorithms, Computer Science Curriculum, Software Engineering Curriculum

Topic 25 – Introduction to Distributed Systems

Leave a comment

Why do I need to learn about distributed systems?

Distributed systems provide the foundation for understanding the theories and techniques behind cloud computing and blockchain technology.

The architectures, protocols, and algorithms introduced in distributed systems are also necessary for creating complex software.

What can I do after finishing learning distributed systems?

You will be able to design software that can

  • tolerate faults,
  • shard data,
  • handle massive number of requests, and
  • perform expensive computations.

You will also be prepared to learn about cloud computing and blockchain technology.

What should I do now?

First, please audit this course to familiarize yourself with the core concepts and protocols of distributed systems: Distributed Systems, UC Santa Cruz Baskin School of Engineering, 2021.

Afterward, please audit the course and read the books below to learn how to design large-scale distributed systems:

Terminology Review:

  • Fault Tolerance
  • Consistency
  • System Models
  • Failure Detectors
  • Communication
  • Ordering
  • State Machine Replication
  • Primary-Backup Replication
  • Bully Algorithm
  • Ring Election
  • Multi-Leader Replication
  • Leaderless Replication
  • Cristian’s Algorithm
  • Berkeley Algorithm
  • Lamport Clocks
  • Vector Clocks
  • Version Vectors
  • Chain Replication
  • Consensus
  • FLP
  • Raft
  • Paxos
  • Viewstamped Replication
  • Zab
  • Consistent Hashing
  • Distributed Transactions
  • ACID
  • Two-Phase Commit
  • Three-Phase Commit
  • Serializability
  • Two-Phase Locking
  • Distributed Locks
  • CAP
  • Consistency Models
  • Linearizability
  • Distributed Architectures
  • Distributed Programming
  • Hadoop
  • Spark
  • Tensorflow
  • PyTorch
  • Kubernetes
  • Bitcoin
  • Smart Contracts

After finishing distributed systems, please click on Topic 26 – Introduction to Cloud Computing to continue.

 

Algorithms, Computer Science Curriculum, Software Engineering Curriculum

Topic 21 – Introduction to Computational Thinking

Leave a comment

Why do I need to learn about computational thinking?

Computational thinking is a fundamental tool for understanding, implementing, and evaluating modern theories in artificial intelligence, machine learning, deep learning, data mining, security, digital image processing, and natural language processing.

What can I do after finishing learning about computation thinking?

You will be able to:

  • use a programming language to express computations,
  • apply systematic problem-solving strategies such as decomposition, pattern recognition, abstraction, and algorithmic thinking to turn an ambiguous problem statement into a computational solution method,
  • apply algorithmic and problem-reduction techniques,
  • use randomness and simulations to address problems that cannot be solved with closed-form solutions,
  • use computational tools, including basic statistical, visualization, and machine learning tools, to model and understand data.

These skills foster abstract thinking that enables you not only to use technology effectively but also to understand what is possible, recognize inherent trade-offs, and account for computational constraints that shape the software you design.

You will also be prepared to learn how to design and build compilers, operating systems, database management systems, and distributed systems.

That sounds useful! What should I do now?

First, please read this book to learn how to apply computational methods such as simulation, randomized algorithms, and statistical analysis to solve problems such as modeling disease spread, simulating physical systems, analyzing biological data, optimizing transportation, and designing communication networks: John V. Guttag (2021). Introduction to Computation and Programming using Python. 3rd Edition. The MIT Press.

Alternatively, if you want to gain the same concepts through interactive explanations, please audit the following courses:

After that, please read chapters 5 and 6 of the following book to learn about the theory of computing and how a machine performs computations: Robert Sedgewick and Kevin Wayne (2016). Computer Science – An Interdisciplinary Approach. Addison-Wesley Professional.

Alternatively, if you want to gain the same concepts through interactive explanations, please audit the following courses: Computer Science: Algorithms, Theory, and Machines.

After that, please read the following book to learn what is going on “under the hood” of a computer system: Randal E. Bryant and David R. O’Hallaron (2015). Computer Systems. A Programmer’s Perspective. Pearson.

After that, please audit this course to learn how to build scalable and high-performance software systems: MIT 6.172 Performance Engineering of Software Systems, Fall 2018 (Lecture Notes).

Terminology Review:

  • Algorithms.
  • Fixed Program Computer, Stored Program Computer.
  • Computer Architecture.
  • Hardware or Computer Architecture Primitives, Programming Language Primitives, Theoretical or Computability Primitives
  • Mathematical Abstraction of a Computing Machine (Turing Machine, Abstract Device), Turing’s Primitives.
  • Programming Languages.
  • Expressions, Syntax, Static Sematics, Semantics, Variables, Bindings.
  • Programming vs. Math.
  • Programs.
  • Big O notation.
  • Optimization Models: Knapsack Problem.
  • Graph-Theoretic Models: Shortest Path Problems.
  • Simulation Models: Monte Carlo Simulation, Random Walk.
  • Statistical Models.
  • K-means Clustering.
  • k-Nearest Neighbors Algorithm.

After finishing computational thinking, please click on Topic 22 – Introduction to Machine Learning to continue.

 

Algorithms, Software Engineering Curriculum

Topic 4 – Introduction to Data Structures and Algorithms

Leave a comment

Why do I need to learn data structures and algorithms?

Your software should address real-world problems. While knowing a programming language is important for writing software, it doesn’t help you leverage existing solutions to save time and effort when building a system.

Many real-world problems have already been solved, and their solutions are documented as data structures and algorithms. It’s important to learn these so you don’t reinvent the wheel, enabling you to apply them to your specific problems, thereby reducing time and effort, or optimizing your solutions.

Additionally, learning algorithms and data structures will help you develop algorithmic thinking and problem-solving skills, which are essential for any software developer.

What can I do after finishing learning algorithms and data structures?

Given a problem, you’ll be able to choose the appropriate data structures to represent concepts in a computer.

You’ll be capable of writing a program that instructs the computer to:
– store and search for data efficiently,
– sort information,
– compute irrational numbers,
– find the shortest path between two locations, or
– encrypt and decrypt sensitive information.

When examining source code, you’ll also be able to determine which program will run faster.

That sounds useful! How can I learn algorithms and data structures?

First, please read this book to gain intuitive understanding of data structures and algorithms: Jay Wengrow (2020). A Common-Sense Guide to Data Structures and Algorithms. Pragmatic Bookshelf.

After that, please read this book to learn about graph theory: Richard J. Trudeau (1993). Introduction to Graph Theory. Dover Publications.

After that, please read this book to learn how to formally define, implement, and evaluate data structures and algorithms: Thomas H. Cormen et al. (2022). Introduction to Algorithms. The MIT Press.

Alternatively, please audit this course and read its lecture notes to learn the core data structures and algorithms through interactive explanations: MIT 6.006 – Introduction to Algorithms, Fall 2011, (Lecture Notes).

After that, you can audit this course and read its lecture notes to delve deeper into the design and analysis of data structures and algorithms through interactive explanations: MIT 6.046J – Design and Analysis of Algorithms, Spring 2015 (Lecture Notes).

Terminology Review:

  • Arrays.
  • Selection Sort.
  • Invariant Reasoning.
  • Order of Growth, Big O, Big Theta.
  • Insertion Sort. Complexity: O(n²).
  • Merge Sort, Recursion Tree. Complexity: O(nlgn).
  • Bubble Sort. Complexity: O(n²).
  • Quick Sort. Complexity: O(nlgn).
  • Counting Sort. Complexity: O(n + k).
  • Radix Sort. Complexity: O(nlogₙk).
  • Sets.
  • Stacks.
  • Queues.
  • Lists, Linked Lists, Sorted Lists.
  • Trees, Binary Trees, Heaps.
  • Heapsort. Complexity: O(nlgn).
  • Hash Tables, Maps, Dictionaries: Chaining, Division Method, Multiplication Method, Open Addressing, Linear Probing, Double Hashing, Cuckoo Hashing.
  • Linear Search.
  • Binary Search.
  • String Matching: Karp-Rabin Algorithm, Rolling Hash ADT.
  • Binary Trees: Depth, Height, Traversal Order.
  • Binary Search Trees (BST).
  • AVL Trees, Rotations, AVL Sort.
  • Sequence Binary Trees.
  • Red-Black Trees.
  • 2-3 Trees.
  • B-Trees.
  • B+ Trees.
  • Comparison Model of Computation, Decision Tree, Search Lower Bound, Sorting Lower Bound.
  • Hierarchical Structure.
  • Karatsuba’s Algorithm.
  • Newton’s Method for Computing Square Roots.
  • Graphs: Complete Graphs, The Handshaking Lemma, Identical Graphs, Graph Isomorphism,  Adjacency Lists, Implicit Graphs, Adjacency Matrix, Incidence Matrix.
  • Breadth-First Search: Shortest Paths.
  • Depth-First Search: Tree Edges, Nontree Edges (Back Edges, Forward Edges, Cross Edges), Cycle Detection, Job Scheduling, Topological Sort.
  • Dijkstra’s Algorithm.
  • Bellman–Ford Algorithm.
  • Single-source Single-target Dijkstra.
  • Bi-Directional Search.
  • A* Algorithm.
  • Dynamic Programming: Subproblems, Guessing, Recursion and Memoization, Bottom-up, Topological Order, Original Problem and Parent Pointers.
  • Dynamic Programming Examples: Fibonacci Numbers, Text Justification, Parenthesization, Edit Distance.
  • Computational Difficulty: P, NP, EXP, R.
  • Hardness and Completeness: NP-hard, NP-complete, EXP-hard, EXP-complete.

After finishing learning about data structures and algorithms, please click on Topic 5 – Object-Oriented Programming to continue.