Coursera-Data_Structures_and_Algorithms

This repository contains my solutions to the Data Structures and Algorithms assignments offered by the University of California, San Diego (UCSD) and the National Research University Higher School of Economics (HSE) on Coursera. All of the problems from courses 1 through 6 have been solved using Python.

These solutions are intended to serve as a reference for those working on these assignments or seeking an alternative perspective on how to approach the problems. It is recommended that you try solving the assignments independently before consulting these solutions, as the best way to improve your skills is through practice. However, if you encounter difficulties or require additional guidance, these solutions are available for reference.

I hope that this repository proves to be a useful resource for your studies in data structures and algorithms.

Algorithmic Toolbox: Certificate

This online course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming.

Week 1: Welcome

1. Sum of Two Digits.
2. Maximum Pairwise Product.

Week 2: Algorithmic Warm-up

1. Fibonacci Number
2. Last Digit of a Large Fibonacci Number
3. Greatest Common Divisor
4. Least Common Multiple
5. Fibonacci Number Again
6. Last Digit of the Sum of Fibonacci Numbers Again

Week 3: Greedy Algorithms

1. Money Change
2. Maximum Value of the Loot
3. Car Fueling
4. Maximum Advertisement Revenue
5. Collecting Signatures
6. Maximum Number of Prizes
7. Maximum Salary

Week 4: Divide and Conquer

1. Binary Search
2. Binary Search with Duplicates
3. Majority Element
4. Improving Quick Sort
5. Number of Inversions
6. Organizing a Lottery
7. Closest Points

Week 5: Dynamic Programming I

1. Money Change Again
2. Primitive Calculator
3. Edit Distance
4. Longest Common Subsequence of Two Sequences
5. Longest Common Subsequence of Three Sequences

Week 6: Dynamic Programming II

1. Maximum Amount of Gold
2. Partitioning Souvenirs
3. Maximum Value of an Arithmetic Expression

Data Structures: Certificate

In this online course, we consider the common data structures that are used in various computational problems.

Week 1: Basic Data Structures

1. Check brackets in the code
2. Compute tree height
3. Network packet processing simulation
4. Extending stack interface
5. Maximum in Sliding Window

Week 2: Priority Queues and Disjoint Sets

1. Convert array into heap
2. Parallel processing
3. Merging tables

Week 3: Hash Tables and Hash Functions

1. Phone book
2. Hashing with chains
3. Find pattern in text
4. Substring equality
5. Longest common substring
6. Pattern matching with mismatches

Week 4: Binary Search Trees

1. Binary tree traversals
2. Is it a binary search tree?
3. Is it a binary search tree? Hard version
4. Set with range sums
5. Rope

Algorithms on Graphs: Certificate

In this online course, first learned what a graph is and what are some of the most important properties. Then we learned several ways to traverse graphs and how one can do useful things while traversing the graph in some order. Then we learned shortest paths algorithms — from the basic ones to those which open door for 1000000 times faster algorithms used in Google Maps and other navigational services. We finished with minimum spanning trees which are used to plan road, telephone and computer networks and also find applications in clustering and approximate algorithms.

Week 1: Decomposition of Graphs I

1. Finding an Exit from a Maze
2. Adding Exits to a Maze

Week 2: Decomposition of Graphs II

1. Checking Consistency of CS Curriculum
2. Determining an Order of Courses
3. Checking Whether Any Intersection in a City is Reachable from Any Other

Week 3: Paths in Graphs I

1. Computing the Minimum Number of Flight Segments
2. Checking whether a Graph is Bipartite

Week 4: Paths in Graphs II

1. Computing the Minimum Cost of a Flight
2. Detecting Anomalies in Currency Exchange Rates
3. Exchanging Money Optimally

Week 5: Minimum Spanning Trees

1. Building Roads to Connect Cities
2. Clustering

Week 6: Advanced Shortest Paths

1. Friend Suggestion
2. Compute Distance Faster Using Coordinates
3. Compute Distance with Preprocessing
4. Compute Distance with Preprocessing on Larger Road Networks
5. Travelling Salesman Problem

Algorithms on Strings: Certificate

Textual information abounds in the world and on the internet. We read webpages, books, emails, and textual inquiries to conduct information searches. From the perspective of computer science, each of those are strings. Search engines employ a variety of string algorithms to make sense of all that data and improve the effectiveness of searches. In addition, a variety of search methods are used in the developing field of personalized medicine to identify mutations in the human genome that cause disease. You will master important pattern matching ideas in this online course, including attempts, suffix trees, suffix arrays, and even the Burrows-Wheeler transform.

Week 1: Suffix Trees

1. Construct a Trie from a Collection of Patterns
2. Implement TrieMatching
3. Extend TrieMatching
4. Construct the Suffix Tree of a String
5. Find the Shortest Non-Shared Substring of Two Strings

Week 2: Burrows–Wheeler Transform and Suffix Arrays

1. Construct the Burrows–Wheeler Transform of a String
2. Reconstruct a String from its Burrows–Wheeler Transform
3. Implement BetterBWMatching
4. Construct the Suffix Array of a String

Week 3 & 4: Algorithmic Challenges: Suffix Arrays

1. Find All Occurrences of a Pattern in a String
2. Construct the Suffix Array of a Long String
3. Pattern Matching with the Suffix Array
4. Construct the Suffix Tree from the Suffix Array

Advanced Algorithms and Complexity: Certificate

Week 1: Flows in Networks

1. Evacuating People
2. Assigning Airline Crews to Flights
3. Stock Charts

Week 2: Linear Programming

1. Infer Energy Values of Ingredients
2. Optimal Diet Problem
3. Online Advertisement Allocation

Week 3: NP-completeness

1. Assign Frequencies to the Cells of a GSM Network
2. Cleaning the Apartment
3. Advertisement Budget Allocation

Week 4: Coping with NP-completeness

1. Integrated Circuit Design
2. Plan a Fun Party
3. School Bus
4. Reschedule the Exams

Week 5: Streaming Algorithms

1. Nice vs Naughty

Genome Assembly Programming Challenge: Certificate

Week 1: Assembling phi X174 Using Overlap Graphs

1. Assembling the phi X174 Genome from Error-Free Reads Using Overlap Graphs
2. Assembling the phi X174 Genome from Error-Prone Reads Using Overlap Graphs

Week 2: Assembling Genomes Using de Bruijn Graphs

1. Puzzle Assembly
2. Finding an Eulerian Cycle in Directed Graph
3. Finding a k-Universal Circular String
4. Assembling the phi X174 Genome from its k-mer Composition

Week 3: Genome Assembly Faces Real Sequencing Data

1. Finding a Circulation in a Network
2. Selecting the Optimal k-mer Size
3. Bubble Detection
4. Tip Removal
5. Assembling the phi X174 Genome from Error-Prone Reads using de Bruijn Graphs