Lecture Discrete mathematics and its applications (7/e) – Chapter 3: Algorithms. This chapter presents the following content: Algorithms, example algorithms, algorithmic paradigms, growth of functions, big-o and other notation, complexity of algorithms.
The following chapters contain core material supported by pen and paper exercises together with computer-based exercises where appropriate. In addition there are web links to: worked solutions, computer codes, audio-visual presentations, case studies, further reading. Codes are written using Scilab (a Matlab clone, downloadable for free from http://www.scilab.org/) and also Matlab.
2.1 PROPERTIES OF BINARY SHIFT REGISTER SEQUENCES
Let us deﬁne a polynomial h(x) = h0 x n + h1 x n−1 + · · · + hn−1 x + hn (2.1)
in a discrete ﬁeld with two elements hi ∈ (0, 1) and h0 = hn = 1. An example of a polynomial could be x 4 + x + 1 or x 5 + x 2 + 1. The coefﬁcients hi of the polynomial can be represented by binary vectors 10011 and 100101, or in octal notation 23 and 45 (every group of three bits is represented by a number...