Applied Discrete Mathematics
This assessment will assess the following Course learning outcomes:
For Examiner’s Use Only
Total Marks: |
Project Objective
The project consists of four practical tasks and the Oral defense. Practical tasks should be complete by each team. A report detailing all work should be prepared and submitted as a hard-copy at the end. There will be an oral-defense/viva to assess individual contribution and the knowledge acquired by doing the project. The project weight is 25% of your total CIS 2203 mark. Group work worth 50% of the mark and the oral defend worth 50% (presentation + viva).
General Instructions
- It is a group project: 3-4 students.
- All required project deliverables should be submitted on BBLearn.
Project Description.
Part 1 (CLO1): Logic and proof (12 marks)
Give an example (complete truth tables) for each of the following:
- Two equivalent propositions. 3 marks
- Contradiction combined proposition. 3 marks
- Tautology combined proposition. 3 marks
- Three events (components) proposition (i.e., p, q, and r). 3 marks
Part 2 (CLO2): Sorting Algorithms (8 marks)
- For Linear search and Insertion sort algorithm, answer the following:
| # | Point (1 mark each) | Linear search | Insertion sort |
| A | Give an example for each using a list of 10 elements. | ||
| B | Calculate the total number of operations inside the loop statements based on your implementation. | ||
| C | Find the total number of operations in the code execution based on your implementation. | ||
| D | Find the function in terms of f(n), time complexity of your algorithm implementation and Terminology. |
1 mark each.
- Develop a Python application that accepts a list of integers and displays the unrepeated elements. Give an example of 20 integers list. 2 marks
- Develop a Python application that accepts a list of integers and displays the maximum repeated number. Give an example of 20 integers list. 2 marks
Part 3 (CLO3): Complexity of algorithm (6 Marks)
- Suppose that you have four different algorithms for solving problems as follow:
- Algorithm uses exactly 2n
- Algorithm uses exactly
- Algorithm uses exactly
- As n grows, put the four algorithms in order starting with the best performance. 3 marks
- Illustrate the for algorithms in one chart. 3 marks
Part 4 (CLO4): Graph Coloring (6 Marks)
- Select a suitable map for the Arab World. Develop a dual map as follows:
The dual Graph of a map is obtained by replacing each country with its capital and then putting an edge between two capitals if the countries share a border.
- Convert the map into its dual. 1 mark
- Color the map/graph with the minimum number of colors. 2 Marks
- Write an algorithm (simple English) to explain of coloring steps. 2 Marks
- Write the chromatic number of the graph and Justify. 1 Mark
Weighted graphs (6 Marks)
- Study the weighted undirected graph below and answer the questions follow:
- Write down all routes between A and F vertices (nodes). Indicate the total weights (distances) for each route. 4 marks
- Find the shortest route (path) between A and F vertices (nodes)? 1 mark
- Find the most expensive route (path) between A and F vertices (nodes)? 1 mark
Tree (12 Marks)
Implement Kruskal’s algorithm to convert the below graph into a tree using Kruskal’s table, and illustrate the resultant tree and calculate the weights total cost.
Good Luck.
Report Rubrics-CIS2203 (50% of Project CW marks)
| Q1: (CLO1) | Logic and proof | ||||
| 0 | |||||
| Absent | Emerging | Competent | Mastering | ||
| Score Area | |||||
| Logic operation
|
At least two logical operations are correct. | At least four logic operations are correct.
|
All logic operations are correct.
|
||
| Q2: (CLO2 ) | Sorting algorithms | ||||
| 0 | |||||
| Absent | Emerging | Competent | Mastering | ||
| Score Area | |||||
| Binary and Selection Sort Algorithm
|
Either Binary Search OR Selection Sort Algorithm is implemented without any syntax error and all steps of algorithm clear with occasional ambiguities. Code is not commented properly.
|
Both Binary Search and Selection Sort Algorithms are implemented without any syntax error and all steps of algorithms are clear with No ambiguity. Code is not commented properly.
|
Both Binary Search and Selection Sort Algorithms are implemented without any syntax error and all steps of algorithms are clear with No ambiguity. Code is properly commented.
|
||
| Analysis of Binary Search and Selection Sort
|
Analysis of either Binary Search OR Selection Sort is implemented without any syntax error and total operations inside code and loop are correct. Code is not commented properly.
|
Analysis of both Binary Search and Selection Sorts are implemented without any syntax error and all steps of calculating total operations inside the loops and in the whole code are correct and there is no syntax error. Code is not commented properly.
|
Analysis of both Binary Search and Selection Sorts are implemented without any syntax error and all steps of calculating total operations inside the loops and in the whole code are correct. Code is commented properly.
|
||
| Sorting algorithm | Algorithm code to create a list | Algorithm code that takes as input a list of n integers in nondecreasing order. | Algorithm that takes as input a list of n integers in nondecreasing order and produces the list of all values that occur more than once | ||
| Q3: (CLO3) | Complexity of algorithm | ||||
| 0 | |||||
| Absent | Emerging | Competent | Mastering | ||
| Score Area | |||||
| Solving algorithm
|
Complexity analysis not completed fully
|
Completed analysis using both algorithms. | Analyzed the correct algorithm and proved.
|
||
| Q4: (CLO4) | Graphs and Tree | ||||
| 0 | |||||
| Absent | Emerging | Competent | Mastering | ||
| Graph color model | List of neighbors is correct. The map is original, and coloring is partially correct. The number of nodes in graph are less than 5. Arity of tree is incorrect or missing. | List of neighbors is correct. The map is original and map coloring is correct. Minimum node in the graph for map coloring are 5. Arity of the tree is correct but lacks justification.
|
List of neighbors is correct. The map is original and map coloring is correct. Minimum node in the graph for map coloring are 5. Arity of the tree is correct, and a valid justification is given.
|
||
| Weighted graph | All possible paths correct and pass through between Newark and Camden, and between Newark and Cape May, using these roads. each path is not calculated. Shortest path is correct.
|
All possible paths correct and pass through between Newark and Camden, and between Newark and Cape May, using these roads.. The shortest path is valid and correct. Cost of all paths including shortest path is partially correct. | All possible paths correct and pass through between Newark and Camden, and between Newark and Cape May, using these roads.. The shortest path is valid and correct. The cost of shortest path is also given. | ||
| Trees | Some implementation of Kruskal’s algorithm, weight and total cost not calculated correctly. | Most Kruskal’s algorithm implemented correctly, weight and total cost calculated correctly. | All Kruskal’s algorithm implemented correctly, weight and total cost calculated correctly. | ||
Sample Questions for Project Presentation
| Question 1 |
| What do you know about disjunction?, give example. |
| What do you know about conjunction?, give example. |
| What do you know about exclusive or?, give example. |
| What do you know about negation or?, give example. |
| What do you know about implication or?, give example. |
| What do you know about biconditional?, give example. |
| Question 2 |
| Explain the written binary search Algorithm |
| Explain the written binary search Implementation |
| Explain the written selection Sort Algorithm |
| Explain the written selection Sort implementation |
| Explain your answer of the following:- The defined function for Binary search implementation The total operations inside the loop The total operations in the entire implementation How did you find the binary search time complexity |
| The defined function for selection Sort implementation The total operations inside the loop The total operations in the entire implementation How did you find the selection Sort time complexity |
| Question 3 |
| How did you find all possible paths via B node? |
| How did you find the shortest path?, Why we have to find the shortest path? |
| How did you calculate the graph vertices degrees? |
| How did you find the graph vertices neighborhoods |
| How did you implement the Map-coloring? |
| Discuss the concept of chromatic number of graphs in part 4. |
| Describe how did you find the arity of a tree? |
| Is the given tree in the assessment full m-ary tree, explain? |
