CSNB 143 Discrete Mathematical Structures

CSNB 143 Discrete Mathematical Structures Chapter 3 Sequence and String OBJECTIVES Students should be able to differentiate few characteristics of sequence. Students should be able to use sequence and strings. Students should be able to concatenate string and know how to use them.

What, which, where, when Knowledge about sequence Finite (Clear / Not Clear ) Infinite (Clear / Not Clear ) Recursive (Clear / Not Clear ) Explicit (Clear / Not Clear ) Increasing (Clear / Not Clear ) Decreasing (Clear / Not Clear )

String Clear ) Concatenation Clear ) Subsequence Clear ) (Clear / Not (Clear / Not (Clear / Not Sequence

A list of objects in its order. That is, taking order as an important thing. A list in which the first one should be in front, followed by the second element, third element and so on. List might be ended after n, n N and it is named as Finite Sequence. We called n as an index for that sequence. List might have no ending value, and this is called as Infinite Sequence. Elements might be redundancy.

Ex 1: S = 2, 4, 6, , 2n S = S 1, S 2 , S 3, S n where S1=2, S2= 4, S3=6, Sn = 2n Ex 2: T = a, a, b, a, b

where T1=a, T2=a, T3=b, T4=a, T5=b If the sequence is depending on the previous value, it is called Recursive Sequence. If the sequence is not depending on the previous value, in which the value can be directly retrieved, it is called Explicit Sequence.

Ex 3: An = An-1 + 5; A1 = 1, recursive sequence 2 n < , this is a where: A2 = A1 + 5 A3 = A2 + 5 Ex 4: An = n2 + 1;

1 n < , this is an explicit sequence where: A1 = 1 + 1 = 2 A2 = 4 + 1 = 5 A3 = 9 + 1 = 10 That is, we can get the value directly, without any dependency to previous value. Both recursive and explicit formula can have both finite and infinite sequence. Ex 5: Consider all the sequences below,

and identify which sequence is recursive/explicit and finite/infinite. a)C1 = 5, Cn = 2Cn-1, 2n6 b)D1 = 3, Dn = Dn-1 + 4 c) Sn = (-4)n, 1n d)Tn = 92 5n, 1 n 5 Both sequences also can have an Increasing or Decreasing sequence.

A sequence is said to be increased if for each Sn, the value is less than Sn + 1 for all n, Sn Sn + 1 ; all n A sequence is said to be decreased if for each Sn the value is bigger than Sn + 1 for all n, Sn Sn + 1 ; all n Ex 6: Determine either this sequence in increasing or decreasing. Sn = 2(n + 1), n 1 Xn = ()n,

n1 S = 3, 5, 5, 7, 8, 8, 13 String Sequences or letters or other symbols that is written without commas are also referred as strings. An infinite string such as abababa may be regarded as infinite sequence of a,b,a,b,a,b,a The set corresponding to sequence is simply

the set of all distinct elements in the sequence. E.g 1: 1,4,8,9,2 is {1,4,8,9,2} E.g 2 : a,b,a,b,a,b,a is simply {a, b} A string over A set is a finite sequence of elements from A. Let A = {a, b, c}. If we let A1 = b, A2 = a, A3 = a, A4 = c Then we obtain a string over A. The string is written baac. Since a string is a sequence, order is taken into

account. For example the string baac is different from acab. Repetition in a string can be specified by superscript. For example the string bbaaac may be written b2a3c. The string with no element is call the null string and is denoted as . We let set A* denote the set of all strings over A, including the null string. Ex 10:

Let say A = {a, b, c, , z} Then A* = {aaaa, computer, denda, pqr, sysrq, } Or let X = {a, b }. Some elements of X* are: a, b, baba, , b2a29ba That is, all finite sequence that can be build from A, contains all words either it has any meaning or not, regardless its length. The number of elements in any string A is

called Elements Length, denoted as |A|. Ex 11: If A = abcdez, then |A| = 26. Concatenation If W1 and W2 are two strings, the string consisting of W1 followed by W2 written W1. W2 is called concatenation of W1 and W2 : W1.W2 =A1A2A3AnB1B2B3Bm where W1.W2 And it is known that

W1. = W1 and .W1 = W1 Ex 12: Let say R = aabc, dacb So, R.S = aabcdacb dacbaabc R. = aabc

S= S.R = .R = aabc Subsequence It is quite different from what we have learn in subset A new sequence can be build from original sequence, but the order of elements must remains. Ex 13:

T = a, a, b, c, q where T1=a, T2=a, T 3=b, T4=c, T5=q S = b, c is a subsequence of T but R = c, b is not a subsequence of T *Take note that the order in which b and c appears must be the same with the original sequence. Exercise 1.List all string on X = {0, 1}, with length 2. 2.With your own words, explain the meaning of sequence. What is the basic difference between sequence and set?

Recently Viewed Presentations

• "Web opens world for young Chinese . . ."-Christian Science Monitor, May 14, 2007. Bejing -- "Excited and emboldened by the wealth of information they find on the Internet, Chinese teens are breaking centuries of tradition to challenge their teachers...
• Organs and blood of infected fetus, placenta, amniotic fluid, meconium . Following an acute infection, SBV RNA can be detected up to several weeks in different tissues like semen, lymphatic organs (esp. mesenteric lymph nodes), and spleen
• CISI - Financial Products, Markets & Services. Topic - Investment Funds. Lesson: Unit Trusts and Open Ended Investment Companies (OEICs) What are unit trusts? A unit trust is a collective investment scheme. The scheme is in the form of a...
• By the end of 2019, digital transformation spending is expected to reach \$1.7 trillion worldwide, a 42% increase from 2017.. Transformation is Happening. Source: IDC. This evolution is being driven by transformation - Digital transformation is happening - IDC predicts...
• By Stefan Rummel 05/05/2008 Prof. Rudowsky CIS 9.5 Brooklyn College Observing nature to find new solutions Observing behaviour of social insects Living in swarms Transfer behaviour to artificial models Explaining swarm intelligence using ants as an example Explaining swarm intelligence...
• The Japanese Space Gravitational Wave Antenna DECIGO TAUP2007 @Sendai, Japan Aug 11, 2007 Seiji Kawamura, Masaki Ando, Takashi Nakamura, Kimio Tsubono, Takahiro Tanaka, Ikkoh Funaki, Naoki Seto, Kenji Numata, Shuichi Sato, Nobuyuki Kanda, Takeshi Takashima, Kunihito Ioka, Kazuhiro Agatsuma ...
• (C, E, G, H) 7.7 Analyze the origins and impact of different sects within Islam, Sunnis and Shi'ites. 7.9 Describe the establishment of trade routes among Asia, Africa, and Europe and the role of merchants in Arab society. (E, G,...
• ENG 213 MIDSEMESTER EXAM An Introduction to Language (8th Edition, 2007) by Victoria Fromkin, Robert Rodman and Nina Hyams, Chapters 1-6 CONTRAST 1 allophones-phonemes bound-free morphemes competence-performance complementary opposites (alive/dead) complementary distribution-contrastive distribution-free variation diphthong-digraph gradable opposites (hot/cold) CONTRAST 2...