MO640 - Exercises - Informatics Concepts, Setubal and Meidanis 1997 - chapter 2

Exercises marked with (*) require further reading/search beyond the suggested texts.

Design and analyze an algorithm that checks whether a string p is a substring of another string t. Can you design an algorithm that runs in time O(|p| + |t|)?
Write a computer program using your favorite programming language that accepts as input a DNA sequence of any size and returns its reverse complement.
Give adjacency matrix and adjacency list representations for the graphs depicted below.
Explain how an O(n²) algorithm can be faster than an O(n) algorithm for small values of n.
Say that you have two algorithms A1 and A2 for the same problem, whose input size is defined by parameter n. If A1 runs in time O(n/log n) and A2 runs in time O(n^1/2), which one is the fastest asymptotically?
It is known that a graph has an Eulerian path if and only if it is connected (except for possible isolated vertices), and exactly two vertices have odd degree. Based on this observation, propose an algorithm that finds an Eulerian path in a graph if such a path exists.
Suppose you have a problem X whose complexity is unknown. You succeed in reducing it to a known NP-complete problem. What can you say about X's complexity?