Syllabus for IST 230:
Language, Logic, and Discrete Math

Spring 2001

Section 1: MWF, 1:25 to 2:15 PM, 367 Willard
3 credits

Frank Ritter
512 Rider Bld
University Park
865-4453
School of IST
ritter@ist.psu.edu

updated 3 May 01

 

Office hours:    M 3-4, W 4-5 pm  512 Rider, and by appointment

TABLE OF CONTENTS

 

 

Please note, this is a live document. Changes announced in class and on the list server will be incorporated from time to time. Announcements in class and their mirror here are the definative version.

COURSE OVERVIEW

Introduction to formal languages, mathematical logic, and discrete mathematics, with applications to information sciences and technology. The course will consist of a number of modules, each introducing a group of mathematical concepts and presenting applications of those concepts to problems of information storage, information retrieval, information management, etc. in both computers and humans.

IST 230 is one of the five introductory core courses for the Baccalaureate degree program in Information Sciences and Technology. The purpose of IST 230 is to provide students with an understanding of an array of mathematical concepts and methods that form the foundation of modern information science, in a form that will be relevant and useful for IST students. Exams and assignments will be used to assess that understanding.

IST 230 will draw some of its material from several mathematical disciplines: formal language theory, mathematical logic, and discrete mathematics. In-depth treatments of each of these subjects are offered elsewhere in the University as advanced mathematics and computer science courses. The difference is that IST 230 will present these concepts in a more elementary way than CSE260, with more emphasis on IST applications. Understanding of these concepts will be tested through assignments and examinations.

IST 230 can be viewed as a small number of modules. Each module will introduce a group of mathematical concepts and present applications of those concepts to problems of information storage, information retrieval, information management, in both humans and machines. These include: Module 1: induction and recursion; Module 2: set, relations, functions, numbers; Module 3: graphs and trees; Module 4: logic and boolean algebra; Module 5: combinatorics and probability; Module 6:grammars, languages and finite state. These vary slightly from the text, which we will follow for convenience.

We will explore these topics through in-class presentations, homework sets, discussions, readings (from both text and on-line sources), exercises (done in groups assigned the first week), and exams.  

COURSE OBJECTIVES

At the conclusion of this course, students will be able to:

  • Define in a quantitative way aspects of information and information technology.
  • Be familiar with mathematical theories, problems, and terms in the information sciences and technology.
  • Define and illustrate the underlying theory in such concepts as computability, algorithms, HCI, social informatics and relate these to the planning, development, and use of information technologies in organizations.
  • Represent and communicate calculations, and have some better intuitions based on working with mathematical theories in this area.

Note to students with disabilities: It is Penn State's policy to not discriminate against qualified students with documented disabilities in its educational programs. If you have a disability-related need for modifications in your testing situation, your instructor should be notified during the first week of classes so that your needs can be accommodated. You will be asked to present documentation from the Office of Disability Services (located in 105 Boucke Building) that describes the nature of your disability and the recommended remedy. You may refer to the Nondiscrimination Policy in the Student Guide to University Policies and Rules 1999.

Americans with Disabilities Act: The School of Information Sciences and Technology (IST) welcomes persons with disabilities to all of its classes, programs, and events. If you need accommodations, or have questions about access to buildings where IST activities are held, please contact the Dean's Office (814) 865-3528 in advance of your participation or visit. If you need assistance during a class, program, or event, please contact any member of our staff or faculty in charge.  

COURSE ORGANIZATION

Teaching Staff and Structure. Dr. Frank Ritter is the course coordinator. There are also a teaching assistant (TA). The TA for our section is Dr. David Mudgett (email: drm1@psu.edu, phone 865-4455).

The IST 230 Web Site. This course has an active web page that contains the syllabus, assignments, links to useful sites, and other valuable material (such as how to correctly prepare assignments, citations templates, and other academic and recreational information). We will post late-breaking information and updates to the web page. This page can currently be found at uniform resource locator (URL) ritter.ist.psu.edu/ist230, and later will be available through links from the IST home page via course listings.

The IST 230 Listserv. Each section has a mandatory listserv that we will use to post course and class information, conduct on-line discussions, and share information.

If you are in Section1 you need to subscribe to l-ist230-1@lists.psu.edu.

Instructions on how to subscribe are available at cac.psu.edu/~santoro/110sp00/conf.htm. Please note that (a) you must use your PSU account, and (b) the web server accepting confirmations is sometimes down. If the server is down, read the email and use the reply option to confirm your subscription. This appears to always work. (c) The instructions are for IST110. Replace 230 for 110 where appropriate!

Required Texts (available at the PSU Bookstore)

(W) Discrete mathematical structures, Kolman, Busby, & Ross (2000). Prentice-Hall, ISBN 0-13-083143-3

Papers and online references will be available as supplements.                List of errata

Previously unreported mistakes in the text are worth 0.1 points (out of 2 or 3 on a homework). Reports must come via email.

Optional Texts and Interesting Resources

Forum for Advancing Software engineering Education       Wolfram Research seems to have a nice online library

http://www.counterpane.com A newsletter on cryptography that illustrates math occasionally.

Grimaldi, Discrete and Combinatorial Mathematics, is another, longer, more detailed textbook. The library has returned my copy and has replaced it with 2 copies available in Patee reference. IST230 books in reference library

Maxfield, Clive. Bebop to the Boolean Boogie, An Unconventional Guide to Electronics Fundamentals, Components & Processes.  TK7868.D5M323 1995.

Student's solutions manual to accompany Discrete Mathematics, Sherwood   Washburn, Thomas Marlowe, Charles Ryan. / Paul Lorczak ; solutions to   computer exercises provided by Atanas Rountev and Matthew Arnold. Reading,   Mass., Addison-Wesley, 2000. Call#: QA39.2.W369 2000     4th Floor Paterno QA39.2.W369 2000 -4th Floor Paterno-   Now in Reserve Reading Room. 2 Available. ISBN - 0-201-61925-3

The Washburn book should appear in the library as well.

PSU STATEMENT ON ACADEMIC INTEGRITY

According to the University Advising Handbook: "Academic integrity is the pursuit of scholarly activity free from fraud and deception, and is the educational objective of this institution. Academic dishonesty includes, but is not limited to cheating, plagiarism, fabrication of information or citations, facilitating acts of academic dishonesty by others, unauthorized possession of examinations, submitting work of another person, or work previously used without informing the instructor, or tampering with the academic work of other students. Any violation of academic integrity will be thoroughly investigated, and where warranted, punitive action will be taken." Students should be aware that standards for documentation and intellectual contribution may depend on the course content and method of teaching, and should consult instructors for guidance. 

In this course, academic integrety needs two explanations. The first is that you are expected to contribute to your group. This means making time in your schedule for the group's meetings, being in touch via email, and preparing for those meetings. The second explanation is that your group's homework set is to be done only by your group. This means that while you can discuss the problems with others, and we agree that this is a good thing, the writing up needs to be solely by your group. If you have a question as to whether or not two homework writeups are too similar, then use the following standard:

If a pair of writeups are sufficiently similar that you can tell by reading them that the two groups worked together, then they are too similar.

By all means, talk to your colleagues, get help if necessary, but prove to us that, in the end, you understand what you are doing, and can and must express it in your own words. If you and your group don't understand the material well enough to write it up on your own, and you need to copy, then four things are lost: Your integrety, useful feedback to us on how you are doing, your ability to perform well on the exam, and ultimately, your knowledge.

Similarly, if your group splits up the work, and turns in accidentally multiple copies of the same problem, they will not be graded. This is not the intent of the group work. Your group should discuss the answers and choose the best. At the least you should choose sets that do not overlap, see section 1.2 of the book for details.

Learning Disabilities

As each student is an individual with specific needs, academic accommodations are provided on an individual basis based on the student's documentation. A reasonable accommodation is a modification or adjustment to a course, program, service, job, activity, or facility that provides the qualified individual with a disability to have an equal opportunity. An equal opportunity provides the means to attain the same level of performance or to enjoy benefits that are available to students without disabilities. For more information about services for individuals with learning disabilities, please contact the Office for Disability Services at (814) 863-1807.

EVALUATION

You earn your grade but it will be assigned by me. The criteria for each assignment will be discussed in detail, as will the grading scheme. Each written assignment will be evaluated on how well it addresses the questions posed, the clarity of thinking, the organization and presentation of the material, the quality of writing, and its timeliness. 

Your grade will be based on 100 possible points. You earn points with each assignment (see below). As a maximum scale (i.e., cutoffs may be lowered): A: 100-74, A-: 73-70, B+ 69- 67, B: 66- 64, B-: 63- 60, C+: 59- 57, C: 56- 50, D: 49- 40, F: 39- 0. 

There are written assignments, two in class midterms, and a final exam. Please consult the schedule to see when papers/ assignments are due and exams scheduled. You will receive more written instructions for each assignment well in advance of the due date. Here is a brief summary of each:
   

Assignment

Weight

Due Date

Current Affairs and Additional Readings Assignment

Schedule

5% (option with homework)

Once during the semester your group may find an additional resource that addresses or relies upon topics covered that week in class. In one page or less, you will comment on how that article relates to the current class discussion/ topic. You will share both the article and your comments with the class.

Once, varies by group

Homework sets

Tips on doing them

25% 

You will do a varietyof homework sets. Each set nominally 3 points, with maximum contribution to the final grade allowed of 25%. They are finalised the week prior to their due date.

Fridays

Mid-Term Exam 1

Example Probs from HW4

25% 

In class

9 feb 2001

Mid-Term Exam 2

Example Probs from HW7

25% 

In class

28 mar 2001

Final Examination

Review

Example questions from HWK10

25% 

This will be a comprehensive examination that incorporates both new and old material.

May 2001

Total

100%

COURSE CONDUCT

  • Classes will start on time and end as scheduled. Please take your seat prior to the start of class.
  • You should attend each class and actively participate in the discussions during class. If you are uncomfortable with public speaking, or if English is not your native language, we must meet in the first two weeks of school to establish ways to make you more comfortable in speaking and interacting with your peers.
  • For every hour of lecture, I anticipate that you will need to budget about 3 hours of out-of-class time. This implies that you need to budget about 140 hours of out-of-class time over the course of the semester. This time estimate is a guide and you may need to budget more or less. For example, if the material is new to you or difficult to comprehend, it will require more of your time. 
  • You are responsible for all the readings, even if the material is not explicitly covered in class. You should read the class materials prior to class and be prepared to discuss and ask questions about the readings and assignments. You should also re-read the material after class as not every topic will be covered during class time. Many passages in the text may need to be read several times to gain clarity. Also, taking notes on the material you are reading and reflecting on the reading and these notes will help you better understand the issues, concepts and techniques that are being presented.
  • All work must be completed and turned in at the start of class on the assigned date. No late work will be accepted. Late means after the class has begun. Note that a computer's failure is not an excuse (it represents poor planning on your part). If you miss a deadline, a written explanation of a university recognized excuse and written documentation (e.g., a doctor's note) must be handed to me at the end of a lecture.
    Assignments that are simply late can be turned in for feedback but 0 marks.
  • All assignment should be double-spaced, on 8.5"x 11" paper. All pages should have 1" margins. Papers should be stapled and collated. Please do not use report covers; they will not be returned.
  • Carefully proofread your work. Mistakes include spelling, grammatical errors, and typos. You should assume that your reader is about as smart as you, not smarter. You must also show your work, even if you just note 'by inspection'. The marker will want to know that you know how to get the answer.
  • I expect individual work should be just that -- it should be done by you, alone.
  • I expect group work should be just that -- from all of the group. If I become aware that you are not contributing to your group equally, I will intervene.
  • Students who participate in University-sanctioned events (such as athletics) must make prior arrangements and give ample notice.
  • The official language of this course is English.
  • Requests for regrading must be turned in with this form.

IST 230 CLASS SCHEDULE (subject to revisions)

Date

Focus

In Class

Read/Prepare

Due

1*

8/Jan/01

Introduction, start of initial exercise

Course overview, Introductions

Preview of material *

big factorial problem

Review of algebra

nil

2*

10/Jan/01

Logs / H

Fitts law, Shannon's H, plots,
information

Short log review1
short log review2

Get on listserver


Review of Hwk warmup

More on Shannon's H
More on Shannon's H2

Examples of H wrt Boston Harbour and
Forests

 

Survey  due at end of day (optional, will help adjust class pace and provides alias for grade postings)

3*

12/Jan/01

Sets, Subsets, Binary strings*  

Kolman 1.1

Canadian Set Site
Indiana Set Site
Binary web site

 

4*

15/Jan/01

Set Operations   1.2  

5*

17/Jan/01

Sequences   1.3  
6* 19/Jan/01

Mod stuff

Integers mod n, examples mod 2, exponentials

 

GCD calculator

Application: UPCs
Hamming code

Multiplicative Inverse in modular arithm.

Finding inverses

RSA   RSA-more

Intro to encryption

1.4

HW1: (ready)

Exp growth (1 point)

Shannon's H (1 point)

Book stuff (1 point)

  p. 5 #14, 18, 26, 28

  p. 11-12 #10, 14, 23 (show work), 24, 30, 38a

7*

22/Jan/01

Integers, primes, gcd, lcm, Euclidean algorithm, unique factorization, Fermat Factorization*

Explanation of Euclidian algorithm

Notes on Hamming and Fibbonaci

 

8*

24/Jan/01 More on integers      

9*

26/Jan/01

Matrices  

1.5

HWK2 (partially ready)

Fitts law (1 point)

Sequences: (1 point)
p. 20-21#6, 10,26,28

Describe the sequence "6798686"

Integers: (1 point)
p. 29-30#8,24,30,32

compute a multiplication table for mod9 numbers, e.g. 2x2 mod9=4, and
3*4 mod9=3

Project to do in class.

10*

29/Jan/01

Matrices*   1.6 (may be read on your own)

 

11*

31/Jan/01

Logic, prepositional calculus, truth tables
software for it *
  2.1, 2.2

 

12*

2/Feb/01

Proof techniques   2.3

 

13*

5/Feb/01

Induction*

Example proof from Leonard 2.4 (Induction)

HWK3

Example web problem (ready)

p. 37-38#4,6,8,16
How many operations to do A+B, A*C, AVB, A^T, A^P?

p. 57-58#10,12,18,22,28

14*

7/Feb/01

Induction

   

15*

9/Feb/01

Review/Questions session  

HWK4A (1 point)

p. 69#4,8,10,14

16*

12/Feb/01

 

** In class Midterm Examination on
Ch 1-2.
260 Willard ***

 

 

17*

14/Feb/01

Probability

random.org

  3.1 (permutations)  

18*

16/Feb/01

continued

 

3.2 (combinations)

 

19*

19/Feb/01

Pigeonhole principle   3.3 Pigeon hole principle

HWK4B (2 points)

p. 69#2,6,18,22,24

p. 77-78#4,6,8,12,16

20*

21/Feb/01

continued
(central limit theorem)
 

3.4 elements of Prob.

Probability in monoply!

 

21*

23/Feb/01

Recurence

Factorial, etc.

3.5 Recurrence relations

 

 

22*

26/Feb/01

Recurence

 

 

HWK5 (3 points)

Create a table or a figure that notes how to sort all combination/permutation problems into their type.

p. 81-82#6,12,14,19 (show work and explain why this is included), 26,28

p. 85-86#6,8,10,19 (by inductive proof)

23*

28/Feb/01

Functions and Relations, composition of functions, injective, surjective, bijective, equivalence relations

 

4.1 product set

 

 

24*

2/Mar/01

Graphs, directed, complete

4.2 relations

 

5/7/9/Mar/01 SB

 

Spring Break

 

25*

12/Mar/01

    4.3 paths

 

26*

14/Mar/01

matrix representations

 

4.4 Properties


27*

16/Mar/01

 

 

5.1 functions

HKW6 (3 points)

p. 94#18 (do both known and unknown birthdays), 30, (35&36). p. 100#10,12

p. 100#16
p. 105-106#26, any even problem on p. 106 that will help you, done on a seperate sheet for possible handing out
p. 114-115#6,10 (also draw digraph for each)

p. 120-121# 1-8, 26

28

19/Mar/01

 

Carley's work

5.2, 5.3 functions for CS

29

21/Mar/01

Karnaugh maps1 and here

Boolean algebra, functions, and gates

6.5 Functions on booleans

 

 

30

23/Mar/01

Disjunctive and conjunctive normal forms,production rules

6.6 Circuits

HWK7

p. 127-128#16,34

p. 168-170#14,26

p. 173-174#25 (show work, and note why this is a useful problem)

p. 179-180#4,14,16

p. 229-230#14,18

Example web problem (ready)

31

26/Mar/01

Trees   7.1 Trees

32

28/Mar/01

Review    

33

30/Mar/01

spanning trees, Breadth first, depth first, traversals of binary trees

 

7.2 lableled trees

7.3 Tree searching

NoHwk week2

34

2/Apr/01 

 

** Class Midterm Examination on
Ch 3-6. ***

 

35

4/Apr/01

Network Algorithms, spanning trees,

Kruskal's algorithm

7.4 Undirected trees

7.5 Spanning trees

 

36

6/Apr/01

 

Petri networks: reading1 reading2
reading3


Nardi article


BNF forms

8.1 Graphs

NoHwk week3

37

9/Apr/01 

Application    

 

38

11/Apr/01 

Eulerian cycle, circuit, More on Eulerian, Hamiltonian circuit, TS

planar graphs

semantic networks

Example: used in search engines

8.2 Euler graphs

8.3 Hamiltonian

 

 

39

13/Apr/01

network flows

with networks

8.4 Transport networks

HWK8 (4 points)

1. Compare tictactoe and hex pawn.

2. p. 253#16,18

p.262#20, p. 271#18,20

3. Why use different orders of searching trees? Use an example from part 1 and provide a URL from the net of an application that illustrates your point. Include a printout of the URL.

4. p. 275-276#4,8,13,
p. 292#12, compare & contrast differnt min. spanning tree algorithms.

40

16/Apr/01

Language, grammars, regular expressions  

10.1 Languages

 

41

18/Apr/01

continued

 

 

10.2 BNF  

42

20/Apr/01

Pascal’s Triangle, simple recursion, binomial coefficients
Applet to calculate PT
Notes on Pascal

Binomials

 

HWK9 (3 points)

p.296#8,10,12,18

p.305#4,6,12

p. 364-365#6,9,12

Example web problem (ready)

43

23/Apr/01

Careers/review

 

 

 

44

25/Apr/01 

Finite state machines

 

10.3 FSMs

 
45 27/Apr/01

The Future  / Review

Group 10 report

 

 

HWK10 (2 points)

p.374-375#12,18,22
p.380-381#6,8

draw the FSM for an actual coke machine (give its location) and test your theory

 

 

 

 

   
     

Compression

Markov models

(Task modelling languages not yet covered)  

 

 

FINAL EXAMINATION WILL BE HELD ON

Official dates:

Section 1:   R 12:20 pm 369/367 Willard

This should be on information that the university sends to you. If it is not, you must contact me.


 

 

Homework for IST 230 and Teaching assistant

 

Spring 2001

 

 

Instructor 

Office

Office Hours 

Phone

Email

David Mudgett

ACS Lab

near 512 Rider 1 Bld.

Monday 11 am - 1 pm
Thursday Noon - 2pm

and by appointment

865-4455

drm1@psu.edu

Homework OVERVIEW

The laboratory/homework portion of IST 230 provides students with the chance to become familiar with using the concepts. It is absolutely essential for understanding the material and will be useful for passing the exams.

You have been put into small groups to do your homework because we believe this generally leads to better learning. That means that you must turn in one homework set per group, that confering within your group is not a violation of academic policy or of ethics on the homework section of this course, and that conferring with other groups *is* a violation of academic policy and ethics.

The best way is to attempt all the homework and then meet to disucss the answers. The worst way is to have each member of the group do (and thus learn) one of the problems.

As we explore these topics, we will also practice skills in working together, analytical skills, and information problem-solving approaches.