Skip to content

Latest commit

 

History

History
39 lines (33 loc) · 2.5 KB

README.md

File metadata and controls

39 lines (33 loc) · 2.5 KB
Raw

Algorithms_Part_II

Code for programming assignments in Algorithms part 2 by Princeton.
All the material for the course is free and available online at Coursera. It is best done as a progression to Algorithms Part 1 on Coursera
This course is significantly difficult than ALgorithms Part 1. It covers topics related to graphs, trees and tries in depth.
The course consists of 5 programming assignments, each targetting a specific data structure or algorithm and it's real world application. To complete an assignment you require a score above 80% on automated tests.

Week 1: Wordnet

Using Digraphs and Traversal algorithms to compute ancestors in Digraphs.
Completed: 93%
Features to implement:

  • Timing and memory related issues when finding Shortest Ancestral Path

Week 2: Seam

Using Djikstra's algorithm to enable dynamic and content aware resizing of images.
Completed: 81%
Features to implement:

  • Failing to find least energy seam for large images like chameleon.png, despite working for smaller images

Week 3: Baseball

Applying Maxflow-Mincut properties to eliminate teams in a Baseball tournament. Uses Flowgraph and Ford-Fulkerson algorithm.
Completed: 95%
Features to implement:

  • Failing to clear memory constraint for large test case
  • Apply check for illegal arguments

Week 4: Boggle

Using suffix tries and traversal algorithms to find all valid words in a boggle board.
Completed: 98%
Features to implement:

  • Fails last timing test.

Week 5: Burrows

Implementing MoveToFront and CircularSuffixArray for Burrows-Wheeler Transform.
Completed: 86%
Features to implement:

  • Fails to inverseTransform a compressed message.

Comment:

It is increasingly difficult and requires a lot of time. I had to read the assignments many times to understand the question. Seam and BUrrows were challenging to implement. I enjoyed Boggle and Wordnet the most. Boggle specially because it is a game we have all played and algorithms provides a solution to it. Also it uses tries which is a very intuitive data structure.