# Algorithms and Data Structures- Assignment

Added on 2019-09-26

4 Pages1005 Words182 Views

55-4793 Algorithms and Data Structures IReferral Assignment 1(Individual Work)As indicated in the module description, the learning outcomes for this unit are thatthe student should be able to:1.describe the importance of algorithms;2.explain the concept of algorithms and their use to manipulate data;3.describe fundamental data structures in an appropriate notation;4.describe algorithms in an appropriate abstract notation;5.implement algorithms and data structures using a suitable language.Accordingly, for this assignment, you are required to demonstrate understandingof a problem solving technique called stepwise refinement and its application tosolve a set of problems. Hence, this assignment directly addresses learningoutcomes 1, 2 and 4.This module is assessed on a 100% coursework basis. This assignmentrepresents 50 of the (100) total coursework marks available in thismodule.For this assignment you should be working individually.HAND-IN DateRefer to BlackboardPlease ensure that your work is handed in to Cantor reception on or before thedeadline. Make sure that you write my name on the assignment form before youhand your assignment to reception as I will be marking your assignment report.1of 4

SPECIFIC TASKS1.Consider the proposition and complete the following tasks associated with it: (p q) → (p q), where p and q are statements (or verbal assertions).i.find the truth table of the proposition;(4 marks)ii.explain how the stepwise refinement technique can be applied to find the truth table and briefly discuss the benefits of this approach;(6 marks)iii.Assume that there are two procedural abstractions that calculate conjunction and disjunction of given two truth values. They are as follows: procedure and(IN p, IN q, OUT result) procedure or(IN p, IN q, OUT result), where p and q represent Boolean values (i.e. T or F) and result represents the outcome (i.e. T or F). For example, to calculate outcome p q you can write the following step in ADL (Algorithmic Definition Language taught in lectures), using the CALL statement:CALL and(p, q, outcome)Assume further that there is a procedural abstraction that negates the truth value of a given truth value. It is as follows:procedure not(IN p, OUT result), where p represents a Boolean value (i.e. T or F) and result represents the outcome (i.e. T or F).(a) Using the above abstractions write a simple algorithm using the ADL notation that inputs p and q, and displays the outcome of the above proposition. Explain your problem solving strategy.(20 marks)(b)Discuss the suitability of using procedural abstractions to solve thisproblem and suggest an alternative abstraction mechanism for thisproblem, and illustrate it.(5 marks)2of 4

## End of preview

Want to access all the pages? Upload your documents or become a member.