Areas of study for the final.
The final is May 3, 11:00-1:30 in R205Instructor: Richard Varron, Programmer I,
WPUNJ
Phone: 1-973-720-3307
Section: CS 260-01
Time: MW 11:00-12:45
Room: R205
Mailbox: Atrium
Office Hours: MW 12:30-1:30 (College Hall 220 call first); MTWR
3:30-4:30 Y125; by appointment.
E-Mail:
rich@wpc.wpunj.edu
E-Mail For Non-text Material: varronr@gw.wpunj.edu
Forums:
CS 260-01 FORUMS CONFERENCE
Prerequisites: CS 230 syllabus
, MATH115 or equivalent
Reading and Programming Assignments (3rd
and 4th editions)
Departmental
syllabus for this course
Syllabus from
the University of Colorado's Discrete Structure's Course which uses the same book so
that you can compare what we cover with what some other
universities are doing.
These are the tentative scores on the final. The scores ranged from 35 to 95 with an average score of 64 and a standard deviation of 16. I am going to go over the tests again tonight to make sure that I did not miss any answers.
| Score on Final | Grade on Final | % | # |
| 80-100 | A | 22% | 5 |
| 70-79 | B | 17% | 4 |
| 57-69 | C | 30% | 7 |
| 46-56 | D | 9% | 2 |
| 30-45 | F | 22% | 5 |
| Average Score: 64 | high: 95 low: 35 |
This is the tentative grade distribution for the course along with a comparison with the historical grade distribution for the course. This assumes that all asignments are handed in and there are no changes on the second reading of the tests. Any close grades were resolved in favor of the student. The average grade was 2.9 or slightly below B. (The average grade for those who attended was 3.0 or B.) The historical average grade for this course is 2.5 or between a B- and C+.
Grade For CS260-01 |
Grade Distribution For CS260: 92-98 | ||
| Grade | # of grades |
% of grades (Average grade:2.9 or just below B) |
Expectation value for grade in this course: 2.5 or between a B- and C+ |
| A | 6 | 25% | 10% |
| A- | 2 | 8% | 12% |
| B+ | 1 | 4% | 10% |
| B | 6 | 25% | 16% |
| B- | 1 | 4% | 9% |
| C+ | 1 | 4% | 9% |
| C | 6 | 25% | 9% |
| C- | 0 | 0% | 7% |
| D+ | 0 | 0% | 2% |
| D | 0 | 0% | 7% |
| F(did not attend) | 1 | 4% | 18% |
Areas of study for the final.
The final is May 3, 11:00-1:30 in R205
A 50-regular graph with 100 vertices has 2500 edges. Each vertex is of degree 50 so there are 50 edges coming out of every vertex for 5000 edges (50*100). BUT, each out edge also forms the in edge for some other vertex. Therefore, of the 5000 edges, half a duplicates, so we get 5000/2 or 2500.
Since we cover the two sections on regular grammars and
their recognition (10.3/4), the only new item for Monday is a few short remarks on Turing
machines.
The rest of the time on Monday and Wednesday will be spent
reviewing for the final. My general idea for these two days is to have people either work
in small groups on problems and/or have people come to the board (especially since we have
two blackboards) and work on problems. With graphs, trees and transition diagrams, it is
easier to think through problems on a blackboard. While I will answer questions at some
point, I want you to initially work together on the problems. What you should be able to
do is to explain to me (and others) how you are developing your answers. (I also
want to see how you are attacking problems so that I can give you tips on how to take a
test.)
One last point. If you look at page xv in your text, you will see that
we have covered all of the core material that the author recommends for a sophmore level
course along with 2 of the optional sections (ch 8/10) directed at computer science
majors. You should be proud of the work that you have put into this course. Even if you do
not completely understand every last concept, you have a basic foundation for most of the
computer science courses that you will be taking in the future. The payoff for this course
will come when you take your subsequent courses and find that you already know the basics
thus allowing you to work on more advanced topics. In the computer field, every time you
bybass a chance to learn something new, you fall further behind.
This is the CS
department prereq chart. Compare this with your homework diagram.
The next 6 classes will be covering one section each.
We should be able to cover the sections in less than a period, so we will have time for
review questions. Depending on the time used for questions, we may want to cover a little
more than a section a day and then use the last day or so to review. I am open to either
idea. At this point I want to do the two sorts and then cover formal grammar and finite
state machines. The first draft of the test I did had a few questions on 6, more on 7, the
most on 8 and a little less on 10. If there are areas that you want to cover, let me know
by e-mail so that I can get an idea of what people are interest in.
On Wednesday we will look at traversing a tree,
pre/in/postfix notation and how to evaluate them (8.3) and the use of trees to represent
context-free grammars (derivation trees in section10.1). [I want to look at context-free
languages at this point as another example of the use of trees in CS; if we don't cover
them completely, we will do them when we do 10.1.] These are important topics to know
before you take Data Structures as much of the course deals with tree transversal. We will
also discuss recursive searches, another major topic in Data Structures. This will give
you some of the basic concepts that you will need for Data Structures. This material is
also used in Compiler Construction and understanding how computers parse language. On
Monday, April 12, we will look at using trees in sorting. We will look at the Bubble Sort
and Merge Sort. This is another major area that comes up in Data Structures.
[Sections 8.5 and 8.6 on spanning trees, will have been covered when we do
graphs.] I made these adjustments on the asssignment
page.
After we finish with trees, we will take a look at a few topics in Modeling Computation. The first topic is a discussion of formal language theory and related grammar. (This also includes a section on how to write notation for a language/grammar) These include phase structure, context-sensitive, context-free and regular grammars. This is important for Compiler Construction as well as in Language Design and Artificial Intelligence. We will start by looking at context-free langauges and how trees and stacks can be used to model them. Next we will look at Finite State machines in more detail with and without output. These machines model regular grammars. This topic is also useful in Compiler Construction as well as Automata. It also is a way to model making change in a Coke machine. Next, we will look at the recognition of Languages, particularly Regular Grammars. Lastly, we will deal with Turing Machines which can recognize all 4 types of grammars. Turing machines can do anything a computer can do. This is a fascinating area of computer sciences as it connects human language theory with computer language theory and is an active area of research. It also gives us an insight into how we think both as humans and as machines. I did much of my Master's Degree in Second Language Acquisition and there is a lot of crossover between teaching someone a second language (English) and a second language (C++). In fact, I studied Norm Chomsky's theories in both my English and Computer Classes. I also did work on teaching a second computer language to people. The problems of computer language interference are the same as you see with ESL (English as a Second Language). If you learned C as your first language, you will tend to write programs in other languages with a "C accent." The book that I use to teach ESL has more tree diagrams than our text book..
Something to think about: Is it possible to take a walk through each of the 6 gates on campus such that you only go through each gate once? That is, is there a Hamilton path that connects all six gates. If so, is there a minimum path that can be taken? This is one of the subjects of section 7.5 and 7.6. This problem is known as the Traveling Salesman Problem and is an NP problem; that is, it can't be solved in polynomial time. (See section 2.2, p 110 for an explanation of P/NP problems. I delayed this discussion until we had some real P/NP problems to discuss.)
There is a writing assignment due
for chapter 7. There is a selection of questions from the "Writing Projects"
section at the end of chapter 7. I want you to choose one topic and write a 2 to 3 pager
paper on the topic. It is due 4/7/99. The purpose is to get you to do some
additional reading on a topic covered in the chapter as well as to get you to do some
independent work. There may be a test question based on the reports..
I ran off a few samples of graphs
that represent scheduling of tasks. These were done using SAS. These graphs were done
from inputs of project order, earliest start time, project length etc. This gives you some
idea how graphs can be used in modeling real world situations.
Project 2 has been posted so that you can get started on it.
Most of the tests looked pretty good. (See answers and explanations on Answer Page.). Every question on the test was answered by at least one person. I counted partial answers as almost full credit when the work was shown and did not take off for arithmetic errors. I think that I have given credit for anything that was close enough to question. If there were several ways a question might be read, I accepted any correct answer. If you have questions on the grading, check the Answer Page first. If there is something I overlooked, I will be more than happy to change the grade. The number of correct answers ranged from 8 to 21 with an average of 13.2, a median of 13 and a standard deviation of 3.3.(The percent correct range was from 40% to 100% with an average of 65% which is a rather standard distribution with a mean at C. This means that there was no real need for a curve.)
The distribution of grades for this test (subject to change) is listed below. I also included the grade distribution for this course over time so that you can get a sense of the grading pattern for this course over the last 8 years. In some years the D/F rate was over 30%. The answers with explanations are on the Answer Page.
Grades on Mid-Term |
Grade Distribution For CS260: 92-98 | |||
| Grade | # right |
# of test in grade range |
% of tests in grade range |
Expectation value for grade in this course: 2.5 or between a B- and C+ |
| A | 18+ | 3 | 14% | 10% |
| A- | 16-17 | 2 | 9% | 12% |
| B+ | 14-15 | 5 | 23% | 10% |
| B | 12-13 | 5 | 23% | 16% |
| B- | 11 | 4 | 18% | 9% |
| C+ | 10 | 1 | 9% | 9% |
| C | 8-9 | 3 | 14% | 9% |
| C- | N/A | 0 | 0% | 7% |
| D+ | N/A | 0 | 0% | 2% |
| D | N/A | 0 | 0% | 7% |
| F | N/A | 0 | 0% | 10% |
There are a number of topics that are included in the Departmental
syllabus for this course in chapters 1-4 that we have not fully covered. These include
Predicates and Qualifiers (1.3), Complexity of Algorithms (2.2), Methods of Proof (3.1),
Induction (3.2), Recursion(3.3/5.1/5.2) and Program Correctness (3.6). I held off on these
topic since they are easier to understand in the context of the practical problems of
Graphs and Trees. For example, many of the proofs of Graphs Theory use inductive
reasoning. When it comes to Scanning Trees, recursion is a natural way to talk about the
process. When we talk about Minimal Spanning Trees, the Traveling Salesman Problem and
Euler/Hamiltonian paths, we will have examples to explain the differences between problems
with P and NP complexity which are hinted at in section 2.2.
In many ways, the second half of the semester gives us a chance to explore some of the
uses of the the material we talked about in earlier chapters. You will see how matrices
are applied in the programming of graphs and trees. You will see how recursion is used to
solve real problems (rather than the trivial problems mentioned in section 3.3 which could
be better solved via non-recursion). The second half of the semester also gives us a
chance to discuss real problems in computer science such as sorting, searching,
transversing trees and graphs and finding the best solution to these problems as well as
examining their complexities. This will give you a foundation in such courses as CS342 Data
Structures, CS372
Design and Analysis of Algorithms and CS 440 Database
Management It also gives us a chance to look at networks CS430 Data
Communications and Computer Networks and how they are designed. Lastly, the section on
Modeling Computation gives us a way to look a CS420 Compiler
Construction and language theory which is used in CS282 Programming
Languages. In short, the material in the second half provides an overview of many of
the courses that you will be talking in the future as well as the basic terminology that
you will need to know. It also provides a way to see how these diverse subjects are
linked.
|
Check CS 260-01 FORUMS CONFERENCE for additional discussions / questions or to post a question or comment. |
I also use CS 260-01 FORUMS CONFERENCE for explanations of items presented in class that may need additional clarification and/or details. Forums allows HTML pages to be posted. I can update Forums quicker than the WEB pages, so an initial comment may appear in Forums followed up by something in Notes. Check both source; if it is in notes, I won't post it to forums though I may put a reminder there. |
If you find any errors or items that are not clear on the WEB pages, e-mail me. |
Required For: Linear Programming and Operations Research (CS 330)
Computer Architecture (CS 341)
Data Structures (CS 342)
Computer Calculus (CS 360)
Computer Simulation (CS 362)
BACKGROUND OF INSTRUCTOR
Deadlines to Drop Course
Texts
Discrete Mathematics and Its Applications, Kenneth Rosen, 4th Edition. (3rd ed. can be used.) ($80.00)
The bibliography contains additional titles that may be of interest.
There are three fundamental aspect to this course.
- First, this course aims to give you a systematic way to approach solving problems along with a means to verify the validity of your approach.
- Second, the course aims to show you how different techniques are related and can be used together to solve problems. For example, sets, logic and circuit design all share an underlying Boolean Algebra. Relations, graphs and trees can be processed by means of Matrix and Linear Algebra. Trees can be used to explain probability, greatest common denominator, sorting and language. Frequently converting one structure into another allows for a new insight into the problem. In fact, all of the topics covered can be analyzed in terms of Algebraic Structures, a set of objects along with the set of operations on those objects.
- Third, this course will give you an introduction into the terminology and notations used in mathematical aspects of computer science.
If you glance at the book, you will find that it is filled with unfamiliar material and notations. Most of these topics are not covered in detail in most lower level math courses, or are just skimmed over. However, after reading the book step by step and working through the examples, you will be able to relate many of the concepts to material that you are already familiar with. In some ways, there are no assumptions in this course. All terms must be defined before they are used and all rules must be derived before they can be applied. On occasion, alternative notations in common use will be presented so that you will be able to read a variety of texts.
What will be expected of you? The most important task that you can do is to read the material to be covered before class. When you read the text, you should go over all the examples; if you have questions, make sure that you make notes on specific items that are not clear. If you do not read the material ahead of time, you will be lost in class. The second task that you need to accomplish is to be actively engaged in the subject. You need to look for connections and expansions on previously covered themes.
The teaching method includes lectures along with some in class projects. For the most part, we will be following the book; however, when other parts of the book relate to the topics under discussion, these will be pointed out. In additions, applications that are not in the book will also be pointed out. I will be including material from other sources when there is a need to apply material in the text or when there are different was of approaching a subject. On occasion, I will be presenting advanced material that will not be included on the mid-term or final. These examples will give you something to think about after the course is over and you have the time to explore these topics in more depth. These will be so indicated. Other than these topics, everything covered or assigned may be on the test. Unannounced quizzes will be given, though I generally will post them on the WEB.
If you get lost after spending a reasonable about of time working on a topic, let me know. There is frequently an alternative way to look at a problem that may make it easier to see a solution.
Since we will not be able to get to all the material in class, I will be putting material on the WEB that will expand on the material covered in class or clarify point that were left unresolved in class. A more general discussion Forum will be provided as outlined below. In addition, I will be linking you to WEB sites that may give you some additional material or a different insight.
In terms of compute programming, a variety of languages will be used. These include Microsoft Access SQL , C, JavaScript and Java as well as other languages for specific projects. There may also be some written research projects. The projects will be geared to practical applications of the ideas that you learn.
ATTENDANCE:
E-JOURNAL:
If there are extenuating circumstances for absences or handing in assignments late, the reason should be submitted in a well written formal E-mail message as soon as is feasible.
Requests for extensions should be made via E-mail prior to the due date outlining the reasons for the extension and including what work has been done thus far. In addition to writing practice, this will provide you with the communications skills needed in today's business world by having you present your concerns and requests in writing. As in any business situation, how you state your case will have an effect on whether or not your request will be granted. As in business, there will be times when you need to call because of time constraints and then follow up in writing. Verbal request must be followed up in writing.
FORUMS
Other sources of information: On NETSCAPE / WWW, WPUNJ has a home page at http://www.wpunj.edu. It has information on E-mail, campus events and much more such as other listservers that may be of interest to you either for this course or other courses that you are taking.
GRADING Midterm 40% Final 40% Projects 10% Homework 10%
|
GRADES
|
| Plagiarism is trying to pass off someone else's work as your own without
proper citation. This includes not only paraphrasing material from outside
sources without citation but also includes using programs and work from your
sources without citations. It includes taking ideas from sources without
attribution (including a classmate's work). It also includes copying from your source by
changing a few items here and there. In all respects, your work should be your own
voice except where you have indicated that you have incorporated ideas from others.
Remember, it is not improper to use outside sources-- in fact it is frequently a good idea
to do so-- as long as you clearly indicate what are your ideas and what are the ideas of
others. If you work with a classmate on a work, put both your names on both papers to indicate the collaboration. If only part of the work was worked on jointly, then cite those parts. Not only is this the correct thing to do, but it avoids the problem of who was/were the original writer(s) when, by sharing ideas, you come up with a work that is similar to someone else's. In any event, both works/programs should be distinct with each writer contributing his or her own ideas. (i.e.. if two people are working on an assignment, the ideas may be similar, but the papers should be written by each person.) Work which is in whole or substantially identical will both receive an "F" since it is plagiarized unless there is proper citations. If you are unsure about what constitutes plagiarism or what you need to avoid it, make sure you ask or put a note on your work. Why is plagiarism frowned upon? The reason is that you are submitting work that was done by others and handing it in to be graded as you own work. In addition, it is not fair to the people that do their own work. The minimum penalty is an F on the paper. Subsequent violations may result in an "F" for the course. (See Student Handbook for College policy.) |
You are the visitor to this site.