Homework 3 Breadth-First Search (BFS)

CSE 321 Homework 3

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 divideand-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.