Coursera-Data_Structures_and_Algorithms

My solutions to assignments of Data structures and algorithms (by UCSD and HSE) on Coursera. All problems from course 1 to course 5 have been solved.

Course 1: Algorithmic Toolbox [Certificate]

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
7. Last Digit of the Sum of Fibonacci Numbers Again
8. Last Digit of the Sum of Squares of Fibonacci Numbers

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

Divide and Conquer

1. Binary Search
2. Majority Element
3. Improving Quick Sort
4. Number of Inversions
5. Organizing a Lottery [naive] [faster]
6. Closest Points

Dynamic Programming 1

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

Dynamic Programming 2

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

Course 2: Data Structures [Certificate]

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

Priority Queues and Disjoint Sets

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

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

Binary Search Trees

1. Binary tree traversals
2. Is it a binary search tree? [in-order traversal] [min/max constraint]
3. Is it a binary search tree? Hard version
4. Set with range sums
5. Rope [naive method] [rope structure]

Course 3: Algorithms on Graphs [Certificate]

Undirected Graphs

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

Directed Graphs

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

Most Direct Route

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

Fastest Route

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

Minimum Spanning Trees

1. Building Roads to Connect Cities
2. Clustering

Course 4: Algorithms on Strings [Certificate]

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. Advanced Problem: Find the Shortest Non-Shared Substring of Two Strings

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

Algorithmic Challenges

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. Advanced Problem: Construct the Suffix Tree from the Suffix Array

Course 5: Advanced Algorithms and Complexity [Certificate]

Flows in Networks

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

Linear Programming

1. Infer Energy Values of Ingredients [1] [2]
2. Optimal Diet Problem
3. Advanced Problem: Online Advertisement Allocation (Two-Phase Simplex)

NP-completeness

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

Coping with NP-completeness

1. Integrated Circuit Design
2. Plan a Fun Party
3. School Bus (Traveling Salesman)
4. Advanced Problem: Reschedule the Exams