This repository contains my homework and the final project of the Data structure and algorithms course taught by Prof. Bagheri at the Amirkabir University of Technology- Tehran Polytechnic. It was a privilege for me to have this class with him. We do have 4 homework and 1 final project. You can send me a message if you found a problem or question about the solutions, I'll be happy to respond.
basically, the first assignment was for analyzing the running time and complexity of some simple algorithms such as insertion sort. problems being solved by approaches like two-pointers and induction. for the last problem, we compared 10 couple of functions for their order of growth.
The Second Assignment is the first coding homework that we had in this course. for having the same language for the whole course I used C++ for implementing all of the given coding problems. for the first problem of this assignment I used an exciting approach for using the input streams and also we used stack for solving the first problem, this assignment was mostly for using different data structures because we were taught about them in the previous weeks. the second problem got easy when I used stacks in it, without pre-defined stacks in C++ I should declare a Stack class using other data structures like arrays, this problem was an implementation problem with stack to giving us some ideas of usage of stacks in this kind of problems. The third problem was a little bit more challenging compared to the last two problems because, it needed more code and thinking, although it was also another implementing problem in my opinion this was the most complex problem of the assignment, It gave me happiness that I solved this problem in a short time like others too. The fourth problem got solved by reversing the vector and it doesn't have more to say. last but not least the fifth problem was an implementation of a doubly directed linked list with several functions.
For this Assignment we discussed mostly tree-based data structures like heap and Red-Black trees(RB tree), we solved some problems about rotation moves in RB trees. gave basic pseudo-codes about inorder, postorder, preorder in binary search trees, wrote a simple DFS for traversing in trees like checking if a binary tree is or isn't a BST. For the last problem, I traced the add and removal from the RB tree step by step alongside telling which type of rotation was used for that step.
the last assignment before our final exam was this homework. the base discussion of this homework was mostly about graph algorithms and dynamic programming. The first
problem of this assignment was a dynamic programming problem with BFS. The second problem was an implementation problem because of mostly using HashMaps the third problem
was also a dynamic programming question in a table, the Fourth problem was mostly logical, it was easy to implement but you should firstly think about your approach of
solving this problem. The last question of our homework was about finding the necessary distances with DFS, I think it was the most challenging problem of this assignment,
I'm happy that I solved this question without a big problem.
Last but not least it was our final project. It is a routing project for finding the shortest path from one point to another point in a given city map, with updating the traffics of the roads when users are traveling on their road. when a user sends a query to the program that he wants the shortest path from point A to point B the program gives him the shortest path at the current map and while the user is traveling in the route given from point A to point B the program will update the traffic of the roads to give the next users appropriate shortest paths based on the knowledge of the traffics and the time that will take for a person to pass a road with other users inside it. for this problem, I used OOP with C++ and implemented a Dijkstra algorithm. I hope you enjoy it.