Description

Homework #2
Course Policy: Read all the instructions below carefully before you start working on the assignment, and before you make a submission.
• It is not a group homework. Do not share your answers to anyone in any circumstance. Any cheating means at least -100 for both sides.
• Do not take any information from Internet.
• No late homework will be accepted.
• For any questions about the homework, send an email to gizemsungu@gtu.edu.tr
• The homeworks (both latex and pdf files in a zip file) will be submitted into the course page of Moodle.
• The latex, pdf and zip files of the homeworks should be saved as ”Name Surname StudentId”.{tex, pdf, zip}.
• If the answers of the homeworks have only calculations without any formula or any explanation -when needed- will get zero.
• Writing the homeworks on Latex is strongly suggested. However, hand-written paper is still accepted IFF hand writing of the student is clear and understandable to read, and the paper is well-organized. Otherwise, the assistant cannot grade the student’s homework.
Problem 1: Relations (15 points)
Draw the Hasse diagram for the “greater than or equal to” relation on {0, 1, 2, 3, 4, 5}. Show each step to build the diagram. In order to draw the diagram, you can choose one of the following options:
• You can use an online drawing tool such as https://app.diagrams.net/.
• You can draw the diagram by hand, take a picture of it to put on Latex as a figure.
• Word Office, Libre Office are also options to use them as drawing tools. (Solution)
1
– Homework #2 2
Problem 2: Relations (15 points)
Answer these questions for the poset ({{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}}, ⊆).
(a) Find the maximal elements.
(Solution)
(b) Find the minimal elements.
(Solution)
(c) Is there a greatest element?
(Solution)
(d) Find all upper bounds of {{2}, {4}}.
(Solution)
(e) Find the least upper bound of {{2}, {4}}, if it exists.
(Solution)
(f) Find all lower bounds of {{1, 3, 4}, {2, 3, 4}}.
(Solution)
(h) Find the greatest lower bound of {{1, 3, 4}, {2, 3, 4}}, if it exists.
(Solution)
– Homework #2 3
Problem 3: Relations (70 points)
Remember that a relation R on a set A can have the properties reflexive, symmetric, anti-symmetric and transitive.
• Reflexive: R is reflexive if (a, a) ∈ R, ∀ a ∈ A.
• Symmetric: R is symmetric if (b, a) ∈ R whenever (a, b) ∈ R, ∀ a, b ∈ A.
• Anti-symmetric: R is antisymmetric if ∀ a, b ∈ A, (a, b) ∈ R and (b, a) ∈ R implies that a = b.
• Transitive: R is transitive if ∀ a, b, c ∈ A, (a, b) ∈ R and (b, c) ∈ R implies that (a, c) ∈ R.
For the details about the properties, please check the 4th lecture slide on Moodle.
As we solved the problem 3 in PS4 document – which is available on Moodle – in the problem session, we can determine any given relation if it is reflexive, symmetric, anti-symmetric, and transitive.
Write an algorithm to determine if a given relation R is reflexive, symmetric, anti-symmetric, and transitive.
Your code should meet the following requirements, standards and tasks.
• Read the relations in the text file ”input.txt”.
• Let R be a relation on a set A where ∃a,b ∈ A,(a,b) ∈ R. Each relation R is represented with the lines in the file:
1. The first line says how many relations in R.
2. The second line gives the elements of the set A.
3. The following lines give each relation in R.
• After determining each relation in input.txt whether it is reflexive, symmetric, anti-symmetric and transitive with your algorithm, write its result to the file which is called ”output.txt” with the following format.
• output.txt:
1. Start a new line with ”n” which indicates a new relation.
2. The set of R
3. Reflexive: Yes or No, explain the reason if No (e.g. ”(a, a) is not found”).
4. Symmetric: Yes or No, explain the reason if No (e.g. ”(b, a) is not found whereas (a, b) is found.”)
5. Antisymmetric: Yes or No, explain the reason if No (e.g. ”(b, a) and (a, b) are found.”)
6. Transitive: Yes or No, explain the reason if No (e.g. ”(a, c) is not found whereas (a, b) and (b, c) are found.”)
• An example of the output format is given in ”exampleoutput.txt”. The file has the result of the first relation in ”input.txt”.
• When explaining why a property does not exist in the relation, one reason is enough to explain if there are more. For example, in ”exampleoutput.txt”, the relation is not symmetric because (b, a) and (e, a) are not found. Detecting one of them is enough to explain the reason.
• Bonus (20 points): If you can explain why a property exists in the relation, it brings you bonus of 20 points.
• You can implement your algorithm in Python, Java, C or C++.
• Important: Put comments almost for each line of your code to describe what the line is going to do.
• You should put your source code file (file name is problem1.{.c,.java,.py,.cpp}) and output.txt into your homework zip file (check Course Policy).