What is the time complexity of the following three algorithms? Express your answer in terms of Big- O notation and justify your answer:

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Section 1 – Algorithm Efficiency

Question 1

What is the time complexity of the following three algorithms? Express your answer in terms of Big- O notation and justify your answer:

Question 2

Write a Python function that returns the nth Fibonacci number, where n is an integer passed as a parameter to the function.

Section 3 – Stacks

Question 3

Evaluate the following postfix expressions, giving your answer as a single number: a) 5 4 * 9 +

b) 8 3 7 * + 4 –

c)   16 12 + 4 * 2 /

[3 marks]

Convert the following infix expressions to postfix: d) 9 + 2 * 20 – 4

e) 4 + 5 * 7 / 3

f) (20 – 8) * (42 – 16) / (21 + 6)

[3 marks]

Section 4 – Queues

Question 4

First implement a Stack to insert your student ID digit by digit in order such as 213xxxxx then empty your stack and insert the output into the Queue. What will be the output if you empty the Queue? Demonstrate your work by showing the steps for both Stack and Queue and screenshot of your code and output. Assuming both stack and queue are initially empty.

 

[8 marks]

 

Section 5 – Linked Lists

Question 5

Write a Python program that creates an unordered, singly-linked list consisting of 8 items. Each item in the linked list should be a number. You can use the code given in the lecture slides for your Node and UnorderedList classes.

Your node class should contain the following functions:

• a constructor

• get_data() – returns the data in the node

• get_next() – returns the next node in the list

• set_data() – sets the data in the node to the value given as a parameter

• set_next() – sets the node that this node links to, to the node given as a parameter

 

Your UnorderedList class should contain the following functions:

• a constructor

• add() – adds a node to the head of the list, containing the number given in the parameter

• is_empty() – returns True if the list is empty, and False otherwise

• size() – returns the size of the list

• print_list() – displays the contents of all nodes in the list

 

Add code to create an UnorderedList object, and call its add() function to add 8 items to the list. Call the is_empty(), size() and print_list() functions to show that they work. In your logbook, show your code and the output when you run the code.

The 8 numbers you will add them to the list should be your student ID. Example output:

 

 

 

 

 

 

[5 marks]

 

 

Add a function called search() to your UnorderedList class in Question 5.1. This function should take a number as a parameter and return True if the number is contained in the linked list, or False if the number is not in the list.

 

Add code to your program to allow the user to enter a number, and search for the number in your linked list. Display a message to the user indicating if the number they entered was found in the list or not. In your logbook, include your code, and also output that shows you have tested the search function for a number in the list and a number not in the list.

Example output:

[3 marks]

 Section 6 – Sorting

Question 6

Selection sort: use your student ID as list of integers to be sorted by a selection sort algorithm. Show the contents of the list after each pass through the list.

The list should be your 8-digit student ID.

Example: If your student ID is 21234567 then your list will be [2, 1, 2, 3, 4, 5, 6, 7]

[3 marks]

Insertion sort: use your student ID as list of integers to be sorted by a insertion sort algorithm. Show the contents of the list after each pass through the list.

The list should be your 8-digit student ID.

Example: If your student ID is 21234567 then your list will be [2, 1, 2, 3, 4, 5, 6, 7]

 

Attachments:

Expert's Answer

353 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of