1-) Propose a decrease and conquer algorithm for each of the following problems:
Breadth-First Search (BFS) Depth-First Search (DFS)
Implement your algorithms with Python. Use the Excel file given on Moodle for the input data. Use the first vertex which is on the first line of the Excel file as the root node of the search. Print search results as shown in the following:
A - B - C - D …
A is the root node and B is the first visited node according to search algorithm etc.
2-) One-Pile NIM is a game that initially starts with n chips which are in the pile. The game is played with two players and each player takes at least one and at most m chips from the pile at their own turns (the number of chips taken can vary from move to move). The winner is the player who takes the last chip/s. Propose a decrease and conquer algorithm that calculates which player wins the game, i.e. the player who made the first move or the other player, and implement the algorithm using Python. The algorithm should work with various size of m and n.
You can watch the video that is on the link below for an example game. Remember that m is two in the video but it should be varying in your implementation.
https://www.youtube.com/watch?v=YUilALQqfA4
3-) Given a sorted array of distinct integers A[1; … ; n], propose a divide-and-conquer algorithm that finds out whether there is an index i for which A[i]=i. Implement your algorithm using Python.
4-) Given an array of integers A[1; … ;n], propose a divide-and-conquer algorithm that finds a contiguous subset having the largest sum within A.
For example, let A=[5, -6, 6, 7, -6, 7, - 4, 3]. The contiguous subset with the largest sum is [6,7,-6,7] whose sum is 14.
Implement your proposed algorithm using Python.
5-) Suppose that there is a formatted string which called as pattern. The pattern consists of letters that are representations of words. As an example:
If given string : “Tobeornottobe”,
The pattern holds A for “to”, B for “be”, C for “or”, D for “not”; hence, the pattern is ABCDAB.
Propose a recursive algorithm that checks whether a given pattern is valid on a given string and implement this algorithm using Python.
Prepare a Jupyter Notebook for your homework. Add clear explanations, complexity analysis of algorithms and the codes to the Jupyter Notebook. Also attach your raw code file to your homework folder and don’t forget to zip your homework before upload it to the Moodle.
You can download Jupyter Notebook from the link below:
http://jupyter.org/install.html
You can find instructions to how you can install Jupyter Notebook on the link that shown above.
Note:
Submit your homework on Moodle.
You can send an email to b.koca@gtu.edu.tr to ask any question about the homework
Do your homework personally, group studies will be considered as cheating.
