Assessed Coursework

This set of exercises is Assessed Coursework, constituting 25% of the final mark for this course. It is due on Wednesday, 10 January 2024 at 4:00pm (GMT).

The work should be yours only. You may not work in groups or even discuss these problems with anyone else. You have to upload your work on Moodle at the Gradescope links that will be provided. By submitting your solutions, you would be confirming that you have read and understood the School’s rules on Plagiarism and Assessment Offences, which can be found here and here.

Please submit your solutions to these questions on Gradescope in a PDF file.

Exercise 7.1

(a) Explain how to implement a queue using two stacks. Analyse the running time of the queue operations enqueue and dequeue.

(b) Explain how to implement a stack using two queues. Analyse the running time of the stack operations pop and push.

Please submit the solutions to these questions on Gradescope in two separate Python files: LinkedList.py and SortedDLL.py.

Exercise 6.1

Please submit the solutions to these questions via Gradescope in a PDF file.

Exercise 5.1.

(a) Give an example showing that the implementation of the QuickSort algorithm discussed in the lecture is not stable.

(b) Suppose you can use additional space. Explain how the Partition procedure can be modified so that QuickSort becomes stable.

Please submit the solutions to these questions via Gradescope in a PDF file.

Exercise 4.1

(a)What is the running time (in asymptotic notation) of the Quicksort version we saw in the lecture for the following input sequences? Explain why.

$$A_n =1,2,...,n−1,n \\ B_n = n,n−1,...,2,1$$

This set of exercises will introduce you to a particularly efficient method to search for an entry in a sorted list, which is called binary search. The basic idea of binary search is that the section of the list where the entry is searched is halved in each iteration.

More precisely, suppose you have a sorted list $x[0],...,x[n−1]$ of integers in non-decreasing order. We call these integers keys and allow repetitions in the list. When searching for an entry with value key in x, binary search first looks at the middle element $x[⌊ \frac{n}{2} ⌋]$ and compares

Consider the following Python function which takes a list A of integers as input.

def process(A):
    for i in range(len(A) - 1):
        m = i
        for j in range(i + 1, len(A)):
            if A[m] < A[j]:
                m = j
        A[i], A[m] = A[m], A[i]

Since the times of the Ancient Greeks, prime numbers have held much fascination for math- ematicians. Although today we know quite a lot about them, many questions remain open and they are still a topic under intensive study. (For example, only in 2004 it was proved by Green and Tao that the primes contain arbitrarily long arithmetic progressions.)

Notebook

使用命令行运行 Jupyter Notebook 的具体流程如下：

1. 思考🤔：你想在哪里运行你的项目 or 你想把代码存储在哪里？「确定路径」
2. 启动 CMD：在文件夹上面的路径中，直接输入 cmd 回车「Enter」目标🎯：为了更快速的到达目标路径。（还有多种方法，以后再讲）
3. 确保安装了 Jupyter Notebook：

jupyter notebook

1. 待解决问题🙋

• Pandas 数据，为什么会有 dtype: float64？

公众号：AI悦创【二维码】

In this exercise, you are asked to write a simple Python function to count the number of words in a text. To complete this task, it would be useful to identify which characters in a string are whitescape that separates words (that is, consecutive non-whitespace characters).

You can use the following function, which helps you detecting whitespace, that is a space or tab or similar character in a string. For a String or a character variable text, you can find out whether the String or the character is a whitespace by using