Have to design a coding interview question in Python that tests a candidate’s knowledge and skill in both basic data structures and algorithms. Along with the question, you also need to develop sample solutions with complexity analysis of the problem including Python codes and test cases.
COMP1819 (2020/21) Algorithms and Data Structures Faculty Header ID: 300977 Contribution: 50% of course Course Leader: Dr Tuan Vuong COMP1819 Algorithms and Data Structures Deadline Date: Tuesday 23/03/2021 This coursework should take an average student who is up-to-date with tutorial work approximately 25 hours. Feedback and grades are normally made available within 15 working days of the coursework deadline. Learning Outcomes: 1. Select and employ data structures appropriate to various problems. 2. Understand the relationship between algorithms and data structures. 3. Formulate and solve programming problems using learned concepts. 4. Understand the complexity of algorithms in terms of time and memory. Plagiarism is presenting somebody else's work as your own. It includes: copying information directly from the Web or books without referencing the material; submitting joint coursework as an individual effort; copying another student's coursework; stealing coursework from another student and submitting it as your own work. Suspected plagiarism will be investigated and if found to have occurred will be dealt with according to the procedures set down by the University. Please see your student handbook for further details of what is / isn't plagiarism. All material copied or amended from any source (e.g. internet, books) must be referenced correctly according to the reference style you are using. Code snippets from open source resources or YouTube must be acknowledged appropriately. Your work will be submitted for plagiarism checking. Any attempt to bypass our plagiarism detection systems will be treated as a severe Assessment Offence. Coursework Submission Requirements • An electronic copy of your work for this coursework must be fully uploaded on the Deadline Date of Tuesday 23/03/2021 using the link on the coursework Moodle page for COMP1819. • For this coursework you must submit a single PDF document. In general, any text in the document must not be an image (i.e. must not be scanned) and would normally be generated from other documents (e.g. MS Office using "Save As .. PDF"). An exception to this is hand written mathematical notation, but when scanning do ensure the file size is not excessive. • For this coursework you must also upload a single ZIP file containing supporting evidence. • There are limits on the file size (see the relevant course Moodle page). • Make sure that any files you upload are virus-free and not protected by a password or corrupted otherwise they will be treated as null submissions. • Your work will not be printed in colour. Please ensure that any pages with colour are acceptable when printed in Black and White. • You must NOT submit a paper copy of this coursework. • All courseworks must be submitted as above. Under no circumstances can they be accepted by academic staff The University website has details of the current Coursework Regulations, including details of penalties for late submission, procedures for Extenuating Circumstances, and penalties for Assessment Offences. See http://www2.gre.ac.uk/current-students/regs http://www2.gre.ac.uk/current-students/regs Algorithms and Data Structures (ADS) - COMP1819 Design and develop an interview question and its solution using algorithms and data structures in Python. This is a GROUP coursework Detailed Specification As part of a summer internship, your group are joining a growing start-up company. The start-up is hoping to expand its technical team and are looking for junior developers. Your manager wants your team to be involved in the interview process for the appointment for a new team member to your group. Your group are asked to design a coding interview question in Python that tests a candidate’s knowledge and skill in both basic data structures and algorithms. Along with the question, you also need to develop sample solutions with complexity analysis of the problem including Python codes and test cases. Since your manager will only allow a maximum of 1 hour for the interview, 45 minutes will be allocated for this technical element. The proposed exercise should be concise and clear. The manage requests that your question needs to involve with a list of string for input. Your group also need to provide your different sample solutions with Python code. The algorithms and data structures can include the following topics: • Topic 1: Basic data types: array, list, stack, queue • Topic 2: Trees • Topic 3: Recursion • Topic 4: Sorting • Topic 5: Maps, Hash tables • … So your team need to deliver the following: 1. A short description of the problem and a set of inputs that to test the correctness and the complexity of a solution. 2. Different Python code solutions. Each solution needs to be individual and can use Python built-in libraries and should NOT be longer than 100 lines of code. 3. An algorithm analysis of your different solutions, including a diagram to compare the time complexity of the different solutions with different inputs. 4. A reflection of the team collaboration and contribution mark. Deliverables Deliverable 1 – the report in PDF format Your report must contain: 1. The description of the interview question including the problem name, description, constraints and requirements, some short examples of input and output of the problem. This should NOT be longer than 300 words. The extended large input test cases be in Appendix or might need to include in separate files. [20%] 2. Your proposed different solutions, one for each member. Individually you need to briefly explain your own approach and solution. This should NOT be longer than 300 words. The codes need to be added to the Appendix and uploaded as files in Deliverable 2. Your solutions should cover different topics of algorithms and data structures. [45%] 3. An algorithm analysis of your different solutions, including a diagram to compare the running time complexity of the different solutions with different inputs. You might need more than 5 inputs to plot clearly. State the big-O performance of each solution. This should NOT be longer than 300 words. [20%] 4. A reflection of the team collaboration from each members and contribution mark for each member, that is agreed by your team. This should NOT be longer than 300 words. [15%] Deliverable 2 – Source code & test case input files (marks included in Deliverable 1. 2) The Python source code (one for each solution), test cases (one file for each test input). They should be placed in a zip file which must be uploaded separately from the report. You must implement your solution using the Python programming language. You may use any sample code provided in the course lectures and laboratories/tutorials as an aid, but make sure you reference any source code. Unreferenced codes may involve an investigation into an academic misconduct offence. You are strongly advised to commence working on this coursework as it becomes available and contact the Module leader with your query as early as possible. Grading Criteria Criteria for Assessment 80-100 70-79 60-69 50-59 40-49 30-39 0-29 Content, knowledge and understanding Demonstrates exceptional systematic understanding of problem solving, computer programming and algorithmic performance. There is exceptional evidence of engagement with all key elements. Demonstrates an excellent systematic understanding of problem solving, computer programming and algorithmic performance. There is also excellent evidence of engagement with all key elements. There is a very good systematic understanding of problem solving, computer programming and algorithmic performance. There is also some very good evidence of engagement with all key elements. Has demonstrated a good understanding problem solving, computer programming and algorithmic performance. There is also some good evidence of engagement with most key elements with some omission of detail. Has demonstrated a satisfactory level of understanding of problem solving, computer programming and algorithmic performance. There are a few notable omissions and there is limited evidence of engagement with all key elements. Overall a satisfactory attempt at these criteria A poor understanding of one or more of the following - problem solving, computer programming and algorithmic performance. There is insufficient evidence of engagement with the key elements. Overall an unsatisfactory attempt. Little or no understanding of one or more of the following - problem solving, computer programming and algorithmic performance. There is very little evidence of engagement with the key elements. Overall a very unsatisfactory attempt. Cognitive/Intellectual Skills Demonstrates exceptional use of a critical analysis of information leading to the proposal of a robust and detailed solution. There is exceptional evidence of reflection that identifies the strengths and weakness of the approaches undertaken. Demonstrates an excellent use of a critical analysis of information leading to the proposal of a robust and detailed solution. There is also excellent evidence of reflection and judgement based on the interpretation of the results obtained. Demonstrates a very good use of a critical analysis of information leading to the proposal of a detailed solution. There is also some very good evidence of reflection and judgement based on the interpretation of the results obtained. Demonstrates some good critical analysis of information leading to the proposal of a detailed solution. There are some exposed weaknesses of cognitive skills. There is also some good evidence of reflection and judgement based on the interpretation of the results obtained. Has shown some satisfactory level of critical analysis of information. There is evidence of reflection and judgement based on the interpretation of the results obtained at a threshold pass level.