Collections / List object question

Each object in a collection called items has two variables, a String name and an int number. The collection is ordered in ascending order of number.

The collection supports the following methods:

  • isEmpty()
  • getFirst()
  • getNext()
  • getNthObject(int n)
  • hasNext()
  • length()
  • insertAtStart(Obj o)
  • insertAtEnd(Obj o)
  • insertAtN(int n, Obj o)
  1. Write an algorithm using a for loop that prints the names of each object (4 marks)
  2. Write an algorithm using a while loop that prints the names of each object (4 marks)
  3. Write an algorithm that inserts an object o at the correct place in the list (6 marks)
  4. Write an algorithm to sort the collection in descending order (2 marks)

My Answers below. These aren’t the only right answers. There are lots of different ways you can code these.

for(int i = 0; i < items.length(); i++){
if (!items.isEmpty()) {
if (items.isEmpty()){
 else {
      Object tmp = items.getFirst();
      count = 0;
      while (items.hasNext()){
           if (o.number > items.getNthObject(count).number){
                 items.insertAt(count, o);
 for (int i = 0; i < items.length(); i++) {

Standard algorithms

Standard Level

  • Print all items in an array
  • Find the max/min value in an array
  • Finding the index of a particular value in an array
  • Inserting a value in an array
  • Removing a value from an array
  • Sorting an array using bubblesort
  • Sorting an array using selectionsort

Higher Level

  • Binary search of an array
  • Stack.push()
  • Stack.pop()
  • Queue.enqueue()
  • Queue.dequeue()
  • Adding a node to a linked list
  • Removing a node from a linked list
  • Adding a node to a binary tree
  • Removing a node from a binary tree
  • Preorder, Inorder and Postorder binary tree traversals

Thoughts on the Case Study

We covered a lot of material in class and you should have taken some notes. Just in case you didn’t, here are some of our thoughts:

Convergent technology: The  tendency for different technological systems to evolve toward performing similar tasks. Mobile phones can now run applications and be used to surf the internet, and at the same time computers can be used to make phone calls.

  • Popular demand
  • Small components
  • Cheaper components


  • ROM (firmware): Where the operating system is installed. Can be written to (for instance updating the operating system) but generally is only read from.
  • Cache Memory: Same as in a PC. Small, fast memory that stores data that the processor is using right now.
  • RAM: The main store of the device, which stores data and instructions of the programs currently running on the device.
  • Flash Memory: Expansion storage where large files and some installed programs are saved. Can be detached from the device and used to move data to another device, eg a PC.

Operating System:

The most popular is Symbian (Blackberry). Not any more! Some domination by Android and iOS.


RISC (Reduced Instruction Set Chip): Simpler instructions, faster execution, lower power. As opposed to CISC (Complex Instruction Set Chip).


  • Short range
  • No line-of-sight required
  • Devices can be paired (remembered, trusted)
  • Device can be set to visible/invisible
  • IDs can be used to confirm authenticity of connections

Piconets: A temporary Bluetooth network. The master/slave architecture allows one device to be “in charge” of the communications in the piconet and therefore prevent collisions between two devices trying to communicate at the same time.


  • USB: Wired connection to nearby devices. Newest versions have quite high bandwidth. Ubiquitous.
  • Bluetooth: Wireless connection to nearby devices eg headphones, printers. Lower bandwidth. Range up to around 10m.
  • Ethernet: Wired network protocol. Very common. High bandwidth.
  • Wi-Fi: Wireless network communication. High bandwidth. Range up to around 100m.
  • Mobile Phone (Cell Phone) Networks: Very large range (worldwide). 3G bandwidth low. 4G bandwidth much higher.
  • Infra-Red: Needs line-of-sight. Low bandwidth.
  • WiMAX: Like a better version of WiFi. Higher bandwidth. Longer range. But high installation cost and high energy consumption.
  • Firewire: Alternative to USB. Much higher bandwidth. Not widely supported. 

Keyboard vs Touch Screen vs Stylus

  • Stylus good for handwritten notes.
  • Touch screen good for typing because key sizes and functions can be changed easily (they are software). No tactile feedback, but haptic feedback can simulate it. 
  • Keyboard provides tactile feedback. 

Mobile phone generations: 4G promises to be very fast — perhaps faster than WiFi. This means that mobile internet will be just as fast if not faster than wired internet. Buses, cars, coaches, planes, trains could all support high-speed internet.


Man in the middle attack: Data is sent from A to B but is intercepted by C. A thinks C is B. B thinks C is A. C forwards all communications from A to B and from B to A so they don’t suspect anything is wrong. However, all the time C is listening to the communications.

Virtual Private Network: A connection over an unsecured network, eg the internet, in which all data is encrypted. The data can be intercepted, but the person intercepting it cannot make any sense of it because it is encrypted. Hence it’s “virtually private”.

Jail-breaking: Deliberately by-passing the limitations imposed by the manufacturer on a Smartphone. Allows installation of unauthorised and potentially harmful applications.

Encryption: Remember that encryption does not stop data from being intercepted, stolen, deleted or destroyed. All it does is make the data unintelligible.

Kill switch: A facility that could be triggered remotely that renders a smartphone totally inoperable. It could be used to prevent loss of sensitive data if a phone is stolen, but note that it would not prevent access to the memory card, and it would not stop the thief from putting the SIM card in a different phone.

Potential users:


  • Looking up patient data
  • Being informed of emergency
  • Looking up symptoms/diagnoses
  • Remote consultations


  • Attendance
  • Behaviour
  • Assessment
  • Getting feedback from students
  • Remote collaboration with other schools
  • Educational apps


  • Navigation
  • Traffic black spots
  • Use GPS to mark location of car
  • Remote breakdown assistance
  • BUT very distracting if used while driving


  • Vehicle identification
  • Criminal records
  • Location of social unrest / criminal activity


  • Data logging using accelerometers, GPS, thermometers, compass, etc
  • Remote collaboration 
  • Astronomical phenomena apps
  • Simulations


From a security point of view, compare keeping data on your phone with keeping data online




Last topic 4 task

This is the last work we did in class. There will be no more work on this in class, but please come to tutorials if you think you might need a little more practice.


Case Study: Broad areas for research

  • Glossary and key technical information. Definitions of all technical terms. Advantages and disadvantages of alternatives.
    • Appendix 1
    • Appendix 2
  • Security
    • All aspects
  • Article 1: Effects on employees
  • Article 2: Effects on children
  • Medical uses: generic and specific
  • Other uses and general implications for all uses. Useful points to include in any question.