Unit 5 Lab 1: Algorithms, Page 3

List Processing Algorithms

EK 4.1.2A Languages for algorithms include natural language, pseudocode, and visual and textual programming languages.
EK 4.1.2B Natural language and pseudocode describe algorithms so that humans can understand them.

On this page, you will test if the elements of a list are distinct (no duplicates).
are the numbers of (list {7, 47, 88, 62, 9, 11}) distinct? reporting false

Suppose you have a list of items and want to know if the elements of the list are distinct (unique). This kind of question pops up frequently: for example, a Web search engine would want to be sure all of the search results are different from each other.

Here is one algorithm to solve the problem:

Brian wants us to delete every single place we say pseudocode. To be revisited another day. --MF, 12/27/17

Algorithms can be expressed in natural language or in pseudocode, text that describes the steps a program might carry out. These languages for human understanding may help write the algorithm in a programming language.

Step 1. Compare the first item of the list with each of the later items in the list (the second item, the item, etc.). If you see the first item again, report that the numbers are not distinct (false).
Step 2. If you complete Step 1 without stopping, compare the second item with each of the later items (the third, the, etc.). If you see the second item again, report that the numbers are not distinct (false).
Step 3. Repeat Step 2 for each number in the list. Compare that item with each of the later items in the in the list.
Step 4. If you complete Step 3 without finding any duplicates, report that the items are distinct (true).

Build a predicate that implements the above algorithm.
If you doubled the length of the list, would this algorithm take the same amount of time? Twice as long? More than twice as long?

Alphie: Our predicate tells us if the elements of a list are distinct. I want more.

Gamal: What would you like?

Alphie: If there are any duplicates in the list, I'd like to see what they are. That way, I could remove them.

Betsy: Ok, let's write a reporter that produces the list of duplicates in a list.

Build a reporter that returns all the duplicated items in a list:

duplicates in (list{3,10,7,3,20,12,7}) reporting {3,7}

Build a reporter, remove duplicates, that takes a list as input and reports a new list that has the same elements as the input list but has no duplicate elements.