KEMBAR78
ALG - Assignment | PDF | Time Complexity | Computational Complexity Theory
Scribd
Upload
170 views2 pages

ALG - Assignment

This document outlines the coursework requirements for an Algorithmics assignment. It is comprised of two parts - Part A focuses on evaluating algorithms and determining their time complexity, while Part B examines the P vs NP complexity classification. Students must identify problems that can be solved through algorithms, analyze the time complexity of potential solutions, and discuss examples of P and NP problems. The assignment will be assessed based on submitted documentation that addresses the tasks and includes proper referencing of sources.

Uploaded by

Wilson Wong
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
170 views2 pages

ALG - Assignment

This document outlines the coursework requirements for an Algorithmics assignment. It is comprised of two parts - Part A focuses on evaluating algorithms and determining their time complexity, while Part B examines the P vs NP complexity classification. Students must identify problems that can be solved through algorithms, analyze the time complexity of potential solutions, and discuss examples of P and NP problems. The assignment will be assessed based on submitted documentation that addresses the tasks and includes proper referencing of sources.

Uploaded by

Wilson Wong
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Algorithmics Assignment Page 1 of 2

The coursework is 50% of the assessment for the module.

Learning Outcomes

1 Evaluate the operation and complexity of various algorithms and Part A


data structures by determining their asymptotic complexity
functions (C5, PLO7)
2 Compare the fundamental concepts of complexity including the P Part B
Vs NP conjecture by determining the time complexity of the
algorithms (C4, PLO7)

INTAKE
HAND OUT DATE As stated in Moodle
SUBMISSION - PART-A (Algorithms and As stated in Moodle
Complexity)
SUBMISSION - PART-B (Complexity As stated in Moodle
Classification)

Assessment Criteria

IMPORTANT: This is a group assignment. All submitted components must be your


own work or appropriately accredited.

Referencing: If you use ideas from external sources, e.g. books / magazines / internet
/ forums, then proper citation should be done using the Harvard Name
convention within your solution. Failure to reference design / ideas
properly is considered as plagiarism.

Tasks

PART A: Algorithms and Complexity

Algorithms play a major role in how efficient a computing programs can solve problems.
Numerous well-known algorithms were designed and written to solve various
computational problem such as sorting, searching, matching and etc
Identify a problem that is solved using computer program. Problem could involve sorting,
searching, path tracing, routing, graph traversals and the like. Identity and explain any 2
algorithms that could be used to solve the problem.
[15 Marks]

Asia Pacific University of Technology and Innovation 2021


Algorithmics Assignment Page 2 of 2

Explain the time complexity of the chosen algorithms (Best-Case / Worst-Case). Use the
time complexity measures to explain the suitability of the algorithms to sort a given data.
You may consider various attributes such as size/ volume of the data, desired speed of
processing etc. to justify your answer
[15 Marks]
Guideline: Length approximately 2000 words.

Deliverables (Part – A)

You are required to submit:

Documentation (hardcopy)
1. Cover page
2. Marksheet
3. Results
4. References

Tasks

PART B: Complexity Classification

i) Explain P (Deterministic Polynomial time) problems with a suitable example.


[10 Marks]
ii) Identify and discuss a problem that is considered to be NP (Non-deterministic
Polynomial time).
[10 Marks]
Guideline: Length approximately 1000 words.

Deliverables

You are required to submit:

Documentation (hardcopy)
1. Cover page
2. Marksheet
3. Results
4. References

Asia Pacific University of Technology and Innovation 2021

You might also like