CourseCourseQ BankQuestion BankDocsDocuments

D1.1 - Algorithms

Syllabus
2019
Topic
D1.1
Level
AS

Learning objectives

D1.1.1Algorithms and flow-chart implementationThe general ideas of algorithms and The order of an algorithm is not expected. the implementation of an algorithm given by a flow chart or text.; Whenever finding the middle item of any list, the method defined in the glossary must be used.D1.1.2Bin packing, sorting and binary searchStudents should be familiar with When using the quick sort algorithm, the pivot should be bin packing, bubble sort, quick sort, chosen as the middle item of the list. binary search.

Trace an algorithm exactly

An algorithm is a precise, finite sequence of instructions that transforms permitted inputs into outputs. To implement an algorithm written as text or a flow chart, follow its arrows and decisions exactly, updating variables in the stated order until its stopping condition is reached.

Make a trace table with one row for each completed pass through the process. Record every variable after the assignments, the result of the decision test, and any output. Use the updated value in the next row; do not reuse the previous value or stop merely because successive values look close.

For the text algorithm 'input xx; while x<20x<20, replace xx by x+3x+3; output xx', input 8 gives successive values 8, 11, 14, 17, 20. The test is then false, so the output is 20.

\text{middle position}=\begin{cases}(N+1)/2,&N\text{ odd},\(N+2)/2,&N\text{ even}.\end{cases}

Positions are counted from 1. Thus a list of 9 items uses the 5th item, while a list of 6 uses the 4th: the right-hand one of the two central items. Apply the same rule whenever a middle item is required.

Check that the input satisfies every stated condition and that the algorithm actually reaches its exit. Analysis of the order or computational complexity of an algorithm is not required in this unit.

Choose and carry out the four list algorithms

These four list algorithms have different jobs: bin packing allocates, bubble and quick sort order, and binary search locates. Preserve the given order unless the method explicitly changes it.

Algorithm Required method Completion or validity check
first-fit bin packing in given order, place each item in the first bin with room capacity is never exceeded
first-fit decreasing sort descending, then apply first-fit reaching ⌈total/capacity⌉\lceil\text{total}/\text{capacity}\rceil bins proves optimality
bubble sort scan adjacent pairs from the left; swap wrong-order pairs; repeat show a pass with no swaps
quick sort choose the middle pivot, partition, then repeat on each sublist mark pivots; stop at sublists of size 0 or 1
binary search on a sorted list, compare the target with the middle and reject the impossible half target found or no candidates remain

For every quick-sort sublist and binary-search candidate list, use (N+1)/2(N+1)/2 when NN is odd and (N+2)/2(N+2)/2 when NN is even, so an even list uses its right-hand middle item.

Quick-sorting [7,2,5,3,6][7,2,5,3,6] starts with pivot 5: [2,3]∣5∣[7,6][2,3]\mid5\mid[7,6]. To binary-search sorted [2,3,5,6,7][2,3,5,6,7] for 6, compare with 5 and search [6,7][6,7]; its right-middle item is 7, then 6 is found.

Binary search cannot use an unsorted list, and first-fit decreasing sorts before packing. Reaching the bin lower bound proves optimality; using more bins does not by itself prove that fewer are possible.