Skip to main content

Algorithms in Python (Under Construction)

Python’s collections module​

  • Named tuples
  • Deque
  • Ordered dictionaries
  • Default dictionary
  • ChainMap object
  • Counter objects
  • UserDict
  • UserList
  • UserString

Introduction to Algorithm Design​

  • Introducing algorithms
  • Performance analysis of an algorithm
    • Time complexity
    • Space complexity
  • Asymptotic notation
    • Theta notation
    • Big O notation
    • Omega notation
  • Amortized analysis
  • Composing complexity classes
  • Computing the running time complexity of an algorithm

Algorithm Design Techniques and Strategies​

  • Algorithm design techniques
  • Recursion
  • Divide and conquer
    • Binary search
    • Merge sort
  • Dynamic programming
    • Calculating the Fibonacci series
  • Greedy algorithms
    • Shortest path problem

Linked Lists​

  • Arrays
  • Introducing linked lists
    • Nodes and pointers
  • Singly linked lists
    • Creating and traversing
    • Improving list creation and traversal
    • Appending items
    • Querying a list
    • Deleting items
  • Doubly linked lists
    • Creating and traversing
    • Appending items
    • Querying a list
    • Deleting items
  • Circular lists
    • Creating and traversing
    • Appending items
    • Querying a list
    • Deleting an element in a circular list
  • Practical applications of linked lists

Stacks and Queues​

  • Stacks
    • Stack implementation using arrays
    • Stack implementation using linked lists
    • Push operation
    • Pop operation
    • Peek operation
    • Applications of stacks
  • Queues
    • Python’s list-based queues
    • Linked list based queues
    • Stack-based queues
    • Applications of queues

Trees​

  • Terminology
  • Binary trees
    • Implementation of tree nodes
    • Tree traversal
    • Expression trees
  • Binary search trees
    • Binary search tree operations

Heaps and Priority Queues​

  • Heaps
    • Insert operation
    • Delete operation
    • Heap sort
  • Priority queues

Hash Tables​

  • Introducing hash tables
    • Hashing functions
    • Perfect hashing functions
  • Resolving collisions
    • Open addressing
    • Linear probing
    • Implementing hash tables
    • Separate chaining
  • Symbol tables

Graphs and Algorithms​

  • Graphs
    • Directed and undirected graphs
    • Directed acyclic graphs
    • Weighted graphs
    • Bipartite graphs
  • Graph representations
    • Adjacency lists
    • Adjacency matrix
  • Graph traversals
    • Breadth-first traversal
    • Depth-first search
  • Other useful graph methods
    • Minimum Spanning Tree

Searching​

  • Introduction to searching
  • Linear search
    • Unordered linear search
    • Ordered linear search
  • Jump search
  • Binary search
  • Interpolation search
  • Exponential search
  • Choosing a search algorithm

Sorting​

  • Technical requirements
  • Sorting algorithms
    • Bubble sort algorithms
    • Insertion sort algorithm
    • Selection sort algorithm
    • Quicksort algorithm
    • Timsort algorithm

Selection Algorithms​

  • Technical requirements
  • Selection by sorting
  • Randomized selection
    • Quickselect
  • Deterministic selection
    • Implementation of the deterministic selection algorithm

String Matching Algorithms​

  • Technical requirements
  • String notations and concepts
  • Pattern matching algorithms
    • The brute force algorithm
    • The Rabin-Karp algorithm
    • The Knuth-Morris-Pratt algorithm
    • The Boyer-Moore algorithm