Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment No. 8

EECS 210

Discrete Structures

Due: 11:59 PM, Thursday, December 8, 2022

Submit deliverables in a single zip file to Canvas

Name of the zip file: FirstnameLastname_Assignment8 (with your first and last name) Name of the Assignment folder within the zip file: FirstnameLastname_Assignment8

Deliverables:

1.   Copy of Rubric8.docx with your name and ID filled out (do not submit a PDF).

2.   Source code.

3.   Screen print showing the successful execution of your code or copy and paste the output from a console screen to a Word document and PDF it.

Assignment:

•   You may use any language you want, but if you want help from me or one of the SIs, you should probably use C++, Python, or Haskell.

•   Your output should make it easy for the grader to determine which part of the assignment it is for.

1.   Write a program for finding an Euler circuit, if one exists, using the algorithm   from the lecture on Euler circuits and paths. If an Euler circuit does not exist,    print out the vertices with odd degrees (see Theorem 1). If an Euler circuit does

exist, print it out with the vertices of the circuit in order, separated by dashes, e.g., a-b-c.

a)   Debug your program with the Example 1 graphs G1, G2, G3, and the graph of the Bridges of Kӧnigsberg from the Euler, Hamilton, & Shortest Path  Problems” lecture slides.

b)   Test your program with this graph:

 

2.   Write a program that uses Dirac’s theorem to determine if a graph has a Hamilton circuit. You do not have to find the circuit.

a)   Debug your program with the Example 5 graphs G1 , G2 , and G3  from the “Euler, Hamilton, & Shortest Path Problems” lecture slides.

b)   Test your program with this graph:

 

3.   Write a program that uses Ore’s theorem to determine if a graph has a Hamilton circuit. You do not have to find the circuit.

a)   Debug your program with the Example 5 graphs G1 , G2 , and G3  from the “Euler, Hamilton, & Shortest Path Problems” lecture slides.

b)   Test your program with this graph:

 

4.   Write a program that creates a min-max strategy for the game of Nim. Display the strategy in a manner that will be clear to the grader and includes all of the              elements shown in the Minmax Strategy for Nim (11.2.5)” slide in the                  “Application of Trees” lecture.

a)   Debug your program with a version of Nim with the starting position where there are 3 piles of stones containing 2, 2, and 1 stone each,      respectively (same as one in the Minmax Strategy for Nim (11.2.5)” slide.

b)  Test your program with a version of Nim with the starting position            consists of three piles with one, two, and three stones, respectively. When drawing the tree represent by the same vertex symmetric positions that     result from the same move.

c)   Who wins the game if both players follow an optimal strategy?

5.   Provide comments that explain what each line of code is doing. See rubric below.

Rubric for Program Comments

Exceeds Expectations

(90-100%)

Meets Expectations

(80-89%)

 

Unsatisfactory

(0-79%)

 

Software is adequately            commented with prologue      comments, comments             summarizing major blocks of code, and comments on every line.

Prologue comments are present but missing some items or some major blocks of code are not      commented or there are              inadequate comments on each   line.

Prologue comments are missing all together or there are no         comments on major blocks of   code or there are very few         comments on each line.

Adequate Prologue Comments:

•   Name of program contained in the file (e.g., EECS 210 Assignment 3)

•    Brief description of the program, e.g.:

o Python code for demonstrating operations on relations and properties of relations.

•    Inputs (e.g., none, for a function, it would be the parameters passed to it)

•    Output, e.g.,

o Print out of the name of each exercise, followed by the exercises output.

•    Author’s full name

•   Creation date: The date you first create the file, i.e., the date you write this comment

Adequate comments summarizing major blocks of code and comments on every line:

•    Provide comments that explain what each line of code is doing.

•   You may comment each line of code (e.g., using //) and/or provide a multi-line comment (e.g., using /* and */) that explains what a group of lines does.

•   Multi-line comments should be detailed enough that it is clear what each line of code is doing.

Remember:

•    Your Programming Assignments are individual-effort.

•   You can brainstorm with other students and help them work through problems in their programs, but everyone should have their own unique assignment programs.