Category Archives: Algorithms

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 provides foundation for understanding theories and techniques behind cloud computing and block chain technology.

Architectures, protocols and algorithms introduced in distributed systems are necessary for creating complicated software too.

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 computation.

You will be prepared to learn about cloud computing and block chain technology.

What should I do now?

Please audit this Distributed Systems, UC Santa Cruz Baskin School of Engineering, 2021 course to familiarize yourself with core concepts and protocols.

Afterward, audit this MIT 6.824, Distributed Systems, Spring 2020 course to learn how to design large-scale distributed systems.

At the same time you can read
– this Maarten van Steen and Andrew S. Tanenbaum (2023). Distributed Systems. Maarten van Steen book, and
– this Martin Kleppmann (2017). Designing Data-Intensive Applications – The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O’Reilly Media book to solidify your knowledge.

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 learning about computer networks please click Topic 26 – Introduction to Cloud Computing to continue.

 

Algorithms, Computer Science Curriculum, Programming Languages, Software Engineering Curriculum

Topic 21 – Introduction to Computation and Programming using Python

Leave a comment

Why do I need to learn about computation and programming using Python?

Computational thinking and Python are fundamental tools for understanding many modern theories and techniques such as artificial intelligence, machine learning, deep learning, data mining, security, digital imagine processing and natural language processing.

What can I do after finishing learning about computation and programming using Python ?

You will be prepared to learn modern theories and techniques to create modern security, machine learning, data mining, image processing or natural language processing software.

That sounds useful! What should I do now?

Please read this John V. Guttag (2013). Introduction to Computation and Programming using Python. 2nd Edition. The MIT Press book.

Alternatively, please watch
– this 6.0001 Introduction to Computer Science and Programming in Python. Fall 2016 course (Lecture Notes) and

– this MIT 6.0002 Introduction to Computational Thinking and Data Science, Fall 2016 course (Lecture Notes).

Terminology Review:

  • Big O notation.
  • Monte Carlo Simulation.
  • Random Walk.
  • K-means Clustering.
  • k-Nearest Neighbors Algorithm.

After finishing reading the book please click 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?

Please read this Jay Wengrow (2020). A Common-Sense Guide to Data Structures and Algorithms. Pragmatic Bookshelf first.

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

After that please read this Thomas H. Cormen et al. (2022). Introduction to Algorithms. The MIT Press book to learn in depth about algorithms and data structures.

Alternatively, please audit this MIT 6.006 – Introduction to Algorithms, Fall 2011 course (Lecture Notes).

After that, if you are interested in delving deeper into data structures and algorithms, you can audit this MIT 6.046J – Design and Analysis of Algorithms, Spring 2015 course (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 Topic 5 – Object-Oriented Programming to continue.