CSC1001: Introduction to Computer Science

Programming Methodology

Assignment 4

Assignment description:

This assignment will be worth 16% of the final grade.

You should write your code for each question  in a  .py file  (please  name  it  using the question name, e.g. q1.py). Please pack all your .py files into a single .zip file, name it using your student  ID  (e.g. if your student  ID  is  123456, then the file should  be  named as 123456.zip), and then submit the .zip file via Blackboard.

Please also write a text file, which provide the details about how to run your code for each question. The text file should be included in the .zip file as well.

Please  note that, the teaching assistant  may ask you to  explain the  meaning of your program, to ensure that the codes are indeed written by yourself. Please also note that we may check whether your program is too similar to your fellow students’ code using Blackboard.

This assignment is due on 5:00PM, 12 Dec (Sunday). For each day of late submission, you will lose 10% of your mark in this assignment. If you submit more than three days later than the deadline, you will receive zero in this assignment.

Question 1 (20% of this assignment):

Write a Python function to implement a recursive algorithm which counts the number of nodes in a singly linked list. The input of the function should be a reference pointing to the first node of the linked list. The output of the function should be the number of nodes in that linked list. Your function should be robust enough to handle possible inappropriate inputs.

Note:

You also need to implement the constructor and insert method (which takes data to be inserted  as  argument) for  SinglyLinkedList class. You  may also  implement any other method within the class as you want.  Your class should look like the following. (Please follow the same names of class and methods in the following example)

Question 2 (30% of this assignment):

Follow the same setting  in Q1. Write a  Python function to  implement the quick sort algorithm over a singly linked list. The input of your function should be a variable pointing to the first node of a linked list, and the output of your function should also be a variable pointing to the first node of a linked list, in which the data have been sorted into the ascending order. You may use the LinkedQueue class we introduced in the lecture directly in your program.

NOTE:

Note that you also need to implement the constructor and insert method (which takes data to be inserted as argument) for SinglyLinkedList class.

You may also implement any other method within the class as you want.  Your class     should look like the following. (Please follow the same names of class and methods in the following example)