The Always Learning Marty

Category: Algorithms

  • Imperative and Functional Merge Sort in OCaml

    So happy to be back!  The last two week I was running around seeing doctors, lab technicians, etc because I had a mysterious lump on my neck.  It’s still there, but they figured out that it’s nothing worrisome.  I’m so grateful!  I’ve always been healthy so this was really shocking.  I realized that when I’m…

  • Merge Sort and the Divide and Conquer Approach

    Algorithm Design Techniques In earlier posts, I went through the insertion sort and the selection sort algorithms.  They both use the incremental approach.  Each step of the algorithms sorts one element, and thus the algorithms solve the problem incrementally. The divide-and-conquer is another approach.  It includes 3 steps that are executed recursively until the problem…

  • Functional Style Selection Sort in OCaml

    In this post I talk about what I have tried and learnt in the process of writing the functional correspondence of the imperative selection sort I wrote earlier in OCaml.  I learnt a lot in this practice because functional selection sort is not straight forward! The First Attempt At the beginning, I thought functional selection…

  • Imperative Style Selection Sort in OCaml

    Exercise 2.2-2 of the book Introduction to Algorithms introduced the selection sort algorithm.  I decided to write it in OCaml in imperative style. The selection sort algorithm sorts a list first by switching places of the smallest element of a given list with the first element of the list.  Then, it selects the smallest element…

  • The Efficiency of an Algorithm

    We need to analyze algorithms to choose the most efficient algorithm to implement.  One important aspect we look at is the running time of an algorithm, which often depends on the size of input.  (See Chapter 2-2 of Introduction to Algorithms.) Size of Input Examples in measuring the input size of a problem: The number…

  • Imperative and Functional Insertion Sort in OCaml

    I wrote the insertion algorithm in both imperative and functional styles in OCaml!  I talk about the fun and challenges of each style below: Imperative Insertion Sort I strictly follow the pseudocode on p.18 of the book Introduction to Algorithms.  The pseudocode is in imperative style so all I need to do is to translate…

  • Pseudocode, Insertion Sort and Loop Invariant

    Pseudocode In Chapter 2 of Introduction to Algorithms, the authors introduce pseudocode.  Pseudocode is a way to describe algorithms.  Pseudocode is not computer code and is not typically concerned with issues of software engineering (e.g., data abstraction, modularity, and error handling).  The pseudocode conventions in this book are: Syntax/format: Indentation indicates block structure.  The body…

  • Introduction to Algorithms

    What is an algorithms? From chapter 1 of Introduction to Algorithms, an algorithm is any well-defined procedure that transforms a set of input to a set of output with desired properties.  It is a tool for solving a computational problem, which specifies the desired input/output relationship. Input → Algorithms → Output The input is organized in a…

  • Algorithms

    To be an awesome software engineer, you should know the common algorithms and data structure well.  I’m starting my algorithms learning with this book.  It is commonly regarded as the best book for learning algorithms.  I’ll go through this book chapter by chapter, and work on the exercises as I finish each chapter.