Graph Theory & Applications
Graph Theory – Types of Graphs
There are various types of graphs depending upon the number of vertices, number of edges, interconnectivity, and their…
August 13, 2021 · Taylor EmmaAuthor: Taylor Emma
A senior editor for The Mars that left the company to join the team of SenseCentral as a news editor and content creator. An artist by nature who enjoys video games, guitars, action figures, cooking, painting, drawing and good music.
Design & Analysis of Algorithms
Maximum Matching in Bipartite Graphs
In many situations we are faced with a problem of pairing elements of two sets. The traditional example…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
The Simplex Method
We have already encountered linear programming (see Section 6.6)—the general problem of optimizing a linear function of several…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
Iterative Improvement
The greedy strategy, considered in the preceding chapter, constructs a solution to an optimization problem piece by piece,…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
Huffman Trees and Codes
Suppose we have to encode a text that comprises symbols from some n-symbol alphabet by assigning to each of…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
Dijkstra’s Algorithm
In this section, we consider the single-source shortest-paths problem: for a given vertex called the source in a weighted connected graph,…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
Kruskal’s Algorithm
In the previous section, we considered the greedy algorithm that “grows” a mini-mum spanning tree through a greedy…
August 13, 2021 · Taylor Emma
Design & Analysis of Algorithms
Prim’s Algorithm
The following problem arises naturally in many practical situations: given n points, connect them in the cheapest possible way so…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
Greedy Technique
Let us revisit the change-making problem faced, at least subconsciously, by millions of cashiers all over the world: give change…
August 13, 2021 · Taylor EmmaDesign & Analysis of Algorithms
The Knapsack Problem and Memory Functions
We start this section with designing a dynamic programming algorithm for the knapsack problem: given n items of known weights w1,…
August 13, 2021 · Taylor Emma