Exploring NP-Hard Problems, Online Exams, and AI in Algorithms Course

This assignment delves into the realm of NP-hard problems, real-life examples, and their implications in computer science and artificial intelligence. It requires the identification of two NP-hard problems from daily life, supported by visual evidence and a clear explanation of their NP-hardness. Furthermore, the assignment challenges the student to formulate an engaging online exam question, accompanied by a sample solution. The student also answers basic questions related to computer science concepts. The assignment extends to the exploration of media, asking for two songs, movies, paintings, or artworks that relate to algorithms or NP-hardness, with explanations of their relevance. The assignment touches on related concepts such as amortized and average case analysis, probabilistic algorithms, and the network flow problem. The provided solution showcases the student's understanding of these complex topics and their ability to apply them to practical scenarios, with the goal of enhancing the student's knowledge of algorithms and artificial intelligence, and the application of these concepts in real-world problems.

Question:
Look around your daily life, and find out two interesting real-life NP-hard problems. Turn in
pictures of these two problems and state the two problems clearly. Also explain why they are
NP-hard. (Length of your answer: 1-2 page) 5. (20 pts.)
If a problem is a nondeterministic polynomial it is called NP. The solution of this problem can be
guessed and polynomial time can be used to solve the problem. While solving NP problems, we
don’t have to follow any rule but we just guessed about the topic. [3] Also, if the problem is NP
and the other NPs are polynomial time reducible then we refer it as NP complete. Therefore,
finding a productive calculation for any NP-complete issue suggests that a proficient calculation
can be found for every such issue, since any issue having a place with this class can be recast
into some other individual from the class. It is not known if any polynomial-time calculations
will be found for NP-complete issues, and thinking if these issues are traceable or obstinate stays
one of the most significant inquiries in hypothetical software engineering. At the point when a
NP-complete issue must be comprehended, one methodology is to utilize a polynomial
calculation to inexact the arrangement; the appropriate response in this way gotten won't really
be ideal yet will be sensibly close.
Example [3]
• We can look at the problem shown above
• The kind of questions we shall ask ourselves include the following
• What are the problems that are hardest in NP?
• That notation means that L1 is reducible in polynomial time to L2.

• < Less than symbol use describes that the time that will be taken to solve L1 is not bad
that a polynomial factor away from the time taken to solve L2.
For example, low maintenance educator in OR (Operations Research) who I worked with, had
significantly more involvement in explaining huge (I) LPs. He clarified that he comprehended
that the issues may not be unraveled following 3 hours of running the solver, and one had no clue
on the off chance that they'd need to hold up another 3 hrs. or 3 minutes. He kind of
comprehended this entire complain about NP-culmination, yet all he thought about whether his
concern was unraveled inside X hours. If not, he'd loosen up certain limitations and rerun. [2]
Question:
Give the most interesting Online-Exam question that you can think of. State this question
precisely and give a sample solution to this question. (Length of your answer: 1-2 page) 6.
(5pts)
Online has become one of the most important tools to post and answer questions. However, there
are questions that are mostly ask on online platforms which include the following stated below.
1. What is a computer program?
Answer:
A computer program is a set of instructions designed to tell the computer what to do? These
instruction are coded and organized in some particulars ways by humans. A computer works like
the way human brain works.
2. How does the computers come into being?
Answer:
Computer originates from nowhere other from the psychological concern in which a veteran
mathematician decided to come up with something which can make the mathematical calculation
so simple. [2] The guy come up with a calculator which was only performing arithmetic
calculations. From there the computer evolves until recently the engineers came up with high-
speed modern computers.
3. Give two types of computer software?

Answer:
i. System software.
ii. Application software.
4. What is operating system?
Answer:
This is system software that controls the various parts of the computer system and acts as an
interface between the user and computer hardware.
5. What type of software is operating system?
Answer:
It is system software.
6. Why is the processor referred to as the brain of the computer?
Answer:
The processor is termed as the brain of the computer because it is designed in such a way that it
thinks like the way human beings think. Also, when the computer is instructed to perform a
particular task, it has to go through it and confirmed that that was what was instructed to do.
7. Briefly explain how the computer works.
Answer:
A computer is a human made device that was developed and instructed to perform
some specific tasks as instructed by the user. The instructions are entered into the
computer, the processor converts it into a computer readable form and the interpreter
will interpret it and give out the results to be displayed in a human readable form
8. Why are computer working like human beings?
Answer:
Computers are electronic devices designed to human resources easier. Hence, computers were
program to hold the thoughts of a human so that it can perform the work the way human beings

do. So the processor is known as the brain of the computer since it has to process the data and
give out the results
9. What is machine learning?
Answer:
Machine learning is the process in which computers uses the data already available on the
internet to give out some results needed by the internet users.
What are the three types of memories?
Answer:
i. Hard disk memory capacity. [2]
ii. RAM memory size.
iii. Processor speed.
Question: Give two songs/movies/paintings/artworks that are related to Algorithms or NP-
Hardness. Put down a title and an URL (link) for each of them, and briefly explain how it is
related to Algorithms or NP-Hardness.
Title: The terminator (movie one)
The terminator is a movie acted by Cameron. Cameron is a great enthusiastic character who had
his ambition in building a movie world. The story was acted in a very imaginative way in which
it will leave the reader wondering how things can happen that way. (NP-complete) The reader
will be left hanging thinking what was happening in the story. At long last, Cameron chose that
just reading a marsh measured pitch was not exactly getting the message crosswise over and,
prior to gathering with the autonomous generation organization Hemdale, convinced Henriksen
that the official dependable should have been indicated the intensity of what he planned.
https://www.youtube.com/watch?v=k64P4l2Wmeg

"I went in decked out like The Terminator," recalls the actor. "With gold foil from a cigarette
packet over my teeth and a cut on my head. I kicked the door open and the poor secretary just
about swallowed her typewriter. I sat in the room with (the executive) and wouldn't talk to him. I
just kept looking at him. After a few minutes of that he was ready to jump out the window." [1]
Movie 2
Title: Traveling Salesman Problem - NP-complete Problem
The Traveling Salesman Problem is regular of an enormous class of "hard" Mathematicians and
programmers have been interested for quite a period of time. The movie indicates some of the
stages the salesman is going through in order to cover a shorter distance which applies in most
parts of our programs we run on the daily basis as programmers. . It is imperative to decide the
best request in which a laser will bore a large number of gaps. An effective answer for this issue
diminishes creation costs for the maker. [1]
URL:https://www.coursera.org/lecture/advanced-algorithms-and-complexity/traveling-salesman-
problem-4N8Ys
References
[1] B. Dick, IT Project Management Essentials: Information Systems Project Methodology Kindle
Edition, New York: Amazon Digital Services LLC, 2018.
[2] E. Elmasri,Database Systems: Models, Languages, Design and Application Programming, India:
PEARSON EDUCATION,2013.
[3] E. Ramez, Database Systems: Models, Languages, Design and Application Programming
/ International Edition Paperback, India:PEARSON EDUCATION,2015.