Learn To Think Like A Computer Scientist. Master the fundamentals of the design and analysis of algorithms.
Contains solutions to selected programming assignments.
Course 1- Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Course 2 - Graph Search, Shortest Paths, and Data Structures
Course 3 - Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
Course 4 - Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Useful resources on learning the Python programming language and designing and implementation of algorithms can be found below.
- Algorithms Illuminated
- Learning Python 5th Ed
- Introduction to Algorithms 3rd Ed
- Mathematics for Computer Science
- Coursera- Stanford University Algorithms Specialization Course
- An Introduction to Algorithmic Thinking
Print the number of inversions present in a given array of arbitrary size and order. To ensure a fast run time (namely O(nlogn), MergeSort is employed.
Note that an inversion is where two consecutive integers, i and j, exist in an array such that i > j when the list should be non-decreasing.
See Module_2_Assignment.py
- MergeSort - sorting of an array in non-decreasing order.
- Recursion usage - in MergeSort.
- Usage of global variable to count number of inverses.
- Reading data from a file.
QuickSort, where the pivot is chosen as the median of three elements (the first, middle, and last element in an array).
Counts number of comparisons made between elements in an array.
The aim of choosing the median of three elements increases the chance of an optimal 25-75 split (which is 'good enough for
See Module_3_Assignment_Part_3.py
- QuickSort - sorting of an array in non-decreasing order.
- Recursion usage - in QuickSort.
- Usage of global variable to count number of comparisons.
- Reading data from a file.
Kosaraju's Algorithm, used for finding the sizes of SCCS (strongly connected components) in a given graph.
Finds size of five largest SCCS, prints final answer.
See Module_1_Assignment.py
- Setting recursion limit - using import sys.
- Modified Insertion Sort - limits array size to 5, buts keeps the array sorted.
- Depth-First Search (DFS) usage to search for SCCS.
- Usage of
if __name__ == "__main__"and main() function. - Docstring usage.
Dijkstra's Algorithm, used for finding the shortest paths from a starting node to all other connected nodes in a graph.
Finds and prints the shortest path from the start node (1) to ten other nodes (7,37,59,82,99,115,133,165,188,197).
See Module_2_Assignment.py
- Dijkstra's Algorithm - to find shortest paths from a starting node to ten other nodes.
- Dictionary usage - to implement 'look-ups' in
$O(1)$ time instead of$O(n)$ time.
- Modified DFS - to check for connected nodes, so unconnected nodes can be ignored.
Prim's minimum spanning tree (MST) algorithm, used for finding the minimum cost spanning tree in a graph.
Finds and prints the overall cost of the MST.
See Module_1_Assignment_Part_3.py
- Prim's Algorithm - to find the cost of the MST in a graph.
- Dictionary usage - to implement 'look-ups' in
$O(1)$ time instead of$O(n)$ time.
Dynamic programming algorithm used to find an optimal solution to the Knapsack Problem.
Finds and prints the overall value of the optimum knapsack.
See Module_4_Assignment_Part_1.py
- Dynamic programming usage.
- Usage of a testing file - using pytest.
Uses a heuristic to generate a solution to the Travelling Salesman Problem (TSP).
Finds and prints the overall cost (distance) of the TSP tour found using the heuristic.
See Week_3_Assignment.py
- Heuristic - non-accurate fast algorithm designed to be able to handle large files.
- Shell script usage (Linux) - automated testing and running of the program..