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 this assessment is to assess students’ ability to write algorithmic programs by apply sorting and searching techniques and implementing graphs. Students will also design and perform. tests to check the correctness of the algorithms.

Assessment Information

1.      This  is  an  individual  open  book  assessment  and worth  60%  of your total assessment weighting of the entire course.

2.        Resources and/or equipment that maybe used for this activity:

•   NZSE issued material; and

•   your own course notes.

3.        You have 7 days to complete this assessment.

4.        Up to 15% of the content  may be quoted or paraphrased from other sources  provided you acknowledge and cite the original source of the material you use.

5.        You have the opportunity for one resubmission for one failed assessment per course. The maximum mark available for any reassessed failed assessment event is 50%.

6.       You can make a request for the resubmission within three working days of the return of the assessment and negotiate aresubmission date.

7.       The agreed resubmission date will be adhered to, and no further extensions will be

given. In all cases, the grade achieved on the resubmission will be the grade used to calculate the final course grade.

8.       Failing two  or  more  assessments within a course equates to a failed course and a re- enrolment of that course.

9.       You are required to keep a soft copy of the submitted assessment.

10.     You need to submit your assessment through Turnitin via Canvas.

11.     Students  are   required  to  check  their  course  outlines   in  relation  to  assessment extension requirements.

12.     Extensions   of  time  to  complete   an  assessment  are  only  given  in  exceptional circumstances.  If  you  anticipate  difficulty  in  meeting  the  due  dates  to  submit  an assessment  and/or  sit tests or examinations and/or attempt  any  missed  practical assessment activity which may have been timetabled to occur once only during the programme, you may request an extension of time.

13.     A formal written request must be made prior to the due date for an extension. The agreed extension date will be adhered to, and no further extensions will be given.

Learning Outcomes

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

LO 3              Apply  appropriate  sorting  and  searching  techniques  to  meet  the  needs  of  the algorithms.

LO 4              Implement tree and graph concepts in algorithms for optimizing searches.

LO 5               Design  and   perform. tests  on  algorithms  to  verify   correctness   based   on  its requirements.

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.

GPO 3: Apply a range of software quality assurance techniques to verify correctness of systems on a range of platforms to meet requirements and document results.

Plagiarism

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

Assessment

Task 1:                                                                                                                                                  15 marks

Write a program to implement the following Sorting task:

LO3: Apply appropriate sorting and searching techniques to meet the needs of the algorithms.

Step 1: Ask the user to enter 10 postcodes of New Zealand.

Step 2: Add all these values into an array

Step 3: Using a recursive approach you are required to call the Bubble Sort algorithm to compare each of the postcode values

Step 4: Sort all the 10 postcodes in an arranging order and print them

Step 5: Exit the program.

Task 2:                                                                                                                                      35 marks

Write a program to implement the following Graph task:

LO4: Implement tree and graph concepts in algorithms for optimizing searches.

Consider a walk W in graph G, which consists of L vertices W1, W2, …, Wn. A string S of L letters ‘A’ – ‘E’ is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.

For example, S = ‘ABBECCD’ is realized by W = (0, 1, 6, 9, 7, 2, 3). Determine whether there is a walk W which realizes a given string S in graph G, and if so then find the lexicographically least such walk. The only line of input contains one string S. If there is no walk W which realizes S, then output -1 otherwise, you should output the least walk W which realizes S.

Example of output screen:

Input : s = 'AEE' Output: 049

Explanation: As we can see in the graph the path from AEE is 049.

Input : s = 'AAEE' Output :-1

Explanation: As there is no path that exists, hence output is -1.

Task 3:                                                                                                                                      Total: 15 marks

Write aprogram to implement Binary Search algorithm:

LO3: Apply appropriate sorting and searching techniques to meet the needs of the algorithms.

Step 1: Create a balanced Binary tree by inserting nodes into the tree

Step 2: Ask the user to enter a value to be searched in the Binary Tree

Step 3: If the element is found in the tree, it returns the node value

Step 4: If the element is not found, it returns a negative number (-1)

Step 5: Using In-Order Traversal for trees, traverse through the entire Binary Tree and display all the nodevalues (which will be in sorted order if the Binary Search Tree algorithm has been used correctly).

Step 5: Exit the program

Task 4:

Write Unit Tests to test the given program:

LO5:

Design and perform tests on algorithms to verify.