Course aim

This course provides students with the introduction to the concepts and techniques of data structures and  designing  and writing  associated  algorithms to solve  problems  using sorting,  searching,  and graphing algorithms to write efficient and optimized computer programs.

Purpose

The  purpose of the assessment is to assess students’ ability to implement abstract data types in programs and develop recursive algorithms to solve problems.

Assessment Information

1.  This is an individual open-book assessment which is worth 40% of your total assessment weighting of the entire course.

2.    Resources and/or equipment which may be used for this activity:

•   NZSE issued material;

•   your own course notes; and

•   other resources (referenced and cited).

3.    You have 7 DAYS to complete this assignment

Learning Outcomes

This assessment is mapped to the following learning outcomes for this course:

LO 1       Implement abstract data types in programs to solve problems.

LO 2       Write recursive algorithms to solve problems.

Graduate Profile Outcomes (this course is mapped to)

GPO 2                 Write and maintain complex programs using design patterns, data structures and algorithms to meet specifications and software development standards 

Plagiarism

•   Any submitted assessment or part of an assessment which has plagiarised content will not be marked.

•   All cases of plagiarism and/or cheating will be investigated and dealt with according to A08: Misconduct in Assessment Policy.

Submission Instructions

You are required to ensure you have carried out the following before submitting your assessment:

•    Signed assignment coversheet

•    Place your Name, Student ID number, Assessment and Task Number on all loose documents you are submitting with the assessment.

•    All answers must be written in your own words.

•    Proofread and spell check all written assessment work carefully.

•    DO NOT email your document to your tutor, it must be uploaded to the NZSE LMS

Evidence Submission

You are required to submit the below documents as the evidence of the work done towards the assessment on Canvas

•    Visual Studio  projects  (.sln) file containing all the  relevant  project files and folders  using appropriate naming convention for Task and subtasks wherever applicable(For ex: Task 2_Part A, Task 2_Part B etc) - as a zipped folder

•    Documentation that  contains  screenshots of your output  screen  and code with  properly labelled ( .pdf or .docx file) - should not be zipped

•    Every document submitted online on Canvas should follow the naming convention as below:

Course Code_ Assessment Number_ Assessment Name_ Student Number_Document number

For example, SWD504_A1_Practical_7647XXXXX_1.

Assessment

Task 1:

7OT: lmdlaman? oqs?JoO? po?o ?(das in dJo6Joms ?o solva dJoqlams.

A] Write a program to implement the following Queue task:                                                      10 marks

Create a queue that will prompt the user to enter the choice for one of the operations (e.g. insert (enqueue), delete (dequeue), display (peek) ) to be carried out according to the functions stated below and exit program.    Based on the option entered, access its respective function using a conditional statement.

Operation 1: insert() function which will take the number to be inserted as input and add it to the queue and print the total elements in the queue.

Operation 2: delete() function which will first check if the queue is empty. If it is, then print the output as “Queue Underflow” . Otherwise print the first element of the queue and remove one value from the front. Print the total elements in the queue.

Operation 3: display() function which will peek the first element as well as using a for loop print all the elements of the queue starting from front to rear.

Task 2:

7OT: lmdlaman? oqs?JoO? po?o ?(das in dJo6Joms ?o solva dJoqlams.

A] Write a program to implement the following scenario using STACK:                                    10 marks

1.   Ask the user to enter 10 values from 1-100

2.    Insert these values into a stack (PUSH) and count the elements available in the stack

3.    Display all elements of the stack (PEEK).

4.    Remove all values from the stack (POP)

5.    Exit the program.

B] Write a program to implement the following LinkedList task:                                               10 marks

1.   Ask the user to enter 10 places in New Zealand.

2.   Add each of the user input places into a LinkedList using the addLast method.

3.   Allow the  user to  select the  places   required to  be  removed  using the  remove  method. However, to remove these values you are required to use a switch loop where the user can choose the way they choose to remove the values.

Case 1: Remove specific value (if user wants to remove any specific place_name) Case 2: Remove first node (if user wants to remove first place_name)

Case 3: Remove last node (if user wants to remove last place_name)

Case 4: Remove all nodes (if user wants to remove all place_name)

4.   After the removal operation has been successfully executed, display the remaining values in

the LinkedList and allow the user to check if any given place_name chosen to be searched if it exists or not using the contains method.

5.   Ask the user, if they now want to add more values into the LinkedList or if they wish to exit the program.  If the user desires to add more values into the LinkedList, continue the same operation from Step 3 after the values have been added else exit the program

Task 3:

7O T: lmdlaman? Dqs?JDO? pD?D ?(das in dJo6JDms ?o solva dJoqlams.

A] Write a program to implement a simple Binary Tree traversal for the following tree:

1. In-order Tree Traversal

a.   Traverse the left subtree, i.e., call Inorder(left-subtree)

b.   Visit the root.

c.    Traverse the right subtree, i.e., call Inorder(right-subtree)

2. Pre-order Tree Traversal

a.    Visit the root.

b.   Traverse the left subtree, i.e., call Preorder(left-subtree)

c.    Traverse the right subtree, i.e., call Preorder(right-subtree)

3. Post-order Tree Traversal

a.   Traverse the left subtree, i.e., call Postorder(left-subtree)

b.   Traverse the right subtree, i.e., call Postorder(right-subtree)

c.    Visit the root.

Task 4:

LO2: Write recursive algorithms to solve problems.

A] Write a program to implement the following Double Linked List using Recursive Algorithm:

10 marks

Consider  two  Linked  lists  A  (7->4->1->9)  and  B  (7->4->1->9)  are  identical  –  both  in  data  and arrangement. Write a program to:

1.    Create two LinkedList and ask the user to enter the values into the LinkedList

2.   Check if the two linked lists are identical in data and arrangement.

3.    Use a recursive algorithm to make a call for checking the same.

B] Write a program to implement the following Double Linked List using Recursive Algorithm:

10 marks

Write a program to create a Double Linked List.

1.   Ask the user to enter the input  for the LinkedList

2.    Reverse the List.

3.    Print the reversed List

4.   Exit the program.

Task 5:

LO2: Write recursive algorithms to solve problems.

6.     Create a system that generates the sequence of random Fibonacci numbers given the coding scheme scenario below. The algorithm must take five input numbers between 1 to 14 from the user and generate a Fibonacci sequence for each of the input number and then combine in a sequence(see sample below)                                                                                                       10 marks

E.g.  If the inputs are 5 and 6, F(5) = 0, 1, 1, 2, 3 and F(6) = 0, 1, 1, 2, 3, 5 then

the sequence is 0, 1, 1, 2, 3, 0, 1, 1, 2, 3, 5

7.     A combination formula is used to find the number of ways of selecting items from a collection, such that the order of the selection doesn’t matter. We can implement combination formula using recursive algorithm.

10 marks

There are n number of servers in a datacentre. A customer can choose r number of servers at a time to use where r < n.

By using a recursive algorithm, calculate the number of different combinations the customer could have.

You are required to get the user input for the number of collection (n) and selection (r).

nCr = n!/r!(n-r)!