To: Students Enrolled and Students on the Waiting List for QMCS 350

To: Students Enrolled and Students on the Waiting List for QMCS 350

From: Thomas P. Sturm, QMCS Department

Students:

An advance welcome to QMCS 350!

I have had an unusually large number of inquiries regarding QMCS 350 for next fall. I thought that you might all benefit from my replies, so I have put together the following FAQ's for QMCS 350.

Q. What are FAQ's?

A. FAQ stands for "frequently asked question" and FAQ's is pronounced "facts". By tradition, the questions are edited versions of the questions that people actually asked, or consolidations of many variants of the same question, or totally made up by the author in anticipation of actual questions or follow-up questions.

Q. What is QMCS 350?

A. QMCS 350 is course in data and file structures. It is a required course for all QMCS majors and an elective course for the science QMCS minor. Traditionally, it is the course in our curriculum that requires the most programming. The course covers the development of algorithms, the mathematical analysis of algorithms, efficiency issues (both theoretical and practical), and the implementation of algorithms. Most of the algorithms deal with handling collections of data.

Q. What programming language will be used in QMCS 350?

A. Java.

Q. What happens if I don't know Java?

A. Contact me as soon as possible. In general, I will recommend that you postpone taking QMCS 350 until you take QMCS 280. However, I want to talk with you specifically about your total academic program and explore all of your options. The only blanket advice I can give you is don't show up for class in September without seeing me first if you don't know Java.

Q. What are all the pre-requisites for the course?

A. As stated in the catalog, the pre-requisites for QMCS 350 are QMCS 280 and MATH 128. QMCS 280 in turn has a pre-requisite of another programming course and MATH 128 in turn has a pre-requisite of a calculus course.

Q. Calculus? Are we going to need to know calculus?

A. I use very little calculus in QMCS 350. I do expect you to be able to differentiate a simple polynomial. I do expect you to know that relative maxima and minima occur when the derivative is zero. So I will expect you to be able to find the extrema points of a polynomial. Read my lips: No Integration! No Trigonometry!

Q. What about MATH 128? Can I take it at the same time as QMCS 350?

A. I like to make a distinction between what you know and what you have received credit for. You can be receiving credit for MATH 128 at the same time you are receiving credit for QMCS 350, but you need to know all of the material in MATH 128 before you begin QMCS 350. Our heaviest use of the material from MATH 128 will occur in the first weeks of the course. If you want to self-study the material in MATH 128 over the summer, here is a list of materials that might be helpful:

1. The current MATH 128 textbook. Check with the bookstore.

2. Essential Computer Mathematics by Seymour Lipschultz (Schaum's Outline)

3. Discrete Algorithmic Mathematics by Stephen Maurer and Anthony Ralston

4. Some of my web pages:

http://www.cs.stthomas.edu/faculty/tpsturm/courses/qm300/NUMBERS.html

http://www.cs.stthomas.edu/faculty/tpsturm/courses/qm300/ARITH.html

http://www.cs.stthomas.edu/faculty/tpsturm/courses/qm300/FLOATPT.html

Q. So what from MATH 128 will we need to know?

A. It's a long list, but here goes:

I. Number Systems: binary numbers, octal numbers, hex numbers, unsigned integers, one's complement, two's complement, and sign/magnitude integers.

II. Computer Arithmetic: addition (addend, augend, sum), subtraction (subtrahend, minuend, difference), multiplication (multiplicand, multiplier, product), division (dividend, divisor, quotient) of both signed and unsigned binary numbers.

III. Logic: Boolean algebra including and, or, not, exclusive or, selective set, selective complement, logical product, logical sum, DeMorgan's law, distributive laws.

IV. Computer Implementation and Shortcuts: Electronic and/or/not/xor gates, conversion of Boolean expressions to truth tables and logic diagrams and back. Half-adders and full adders. Shifting and masking, shifting as multiplication by powers of two, rapid multiplication and division algorithms including restorative and non-restorative division.

V. Algorithms: Algorithms and their properties, including step counting, combinatorics, factorials, logarithms, exponentials, analysis of algorithms, and recursion.

VI. Mathematical Functions: Concept of domain and range. Exponential and logarithm functions. Polynomial functions. Factorial functions. Sterling's formula (a biggie!). Size of binary numbers, rapid estimation of powers of 2 (an essential). Summation and product notation. Series. Sequences and their limits. Generating functions. Infinite processes.

VII. Finite Mathematics: Matrix algebra. Set theory. Mathematical induction, counting methods, permutation and combinations, binomial theorem, inclusion and exclusion, pigeonhole principle. Difference equations and finite differences.

VIII. Probability and statistics: Probability and random variables, expectation. Mean and standard deviation. Binomial, Normal, and Poisson distributions.

Q. What textbooks are we going to be using?

A. The main textbook for the course will be:

A Practical Introduction to Data Structures and Algorithm Analysis: Java Edition by Clifford A. Shaffer (Prentice-Hall, 1998, hardcover, ISBN 0-13-660911-2)

There is also a recommended supplemental textbook, but it's just your old QMCS 280 textbook:

Java Software Solutions: Foundations of Program Design by John Lewis and William Loftus (Addison-Wesley, 1998, softcover, ISBN 0-201-57164-1)

Q. I'm on the waiting list. What do I do?

A. I recommend the following for those on the waiting list:

1. Make alternative fallback plans in case we cannot fit you into the course this semester.

2. SHOW UP ON THE FIRST DAY OF CLASS. If you are not present on the first day of class, I can only assume you have made other arrangements and no longer want to enroll in QMCS 350 in the fall. Any places that may be available will be given to others.

3. Be prepared for class. Students on the waiting list who are questionably prepared for the course (in terms of pre-requisites) will have a lower priority on the waiting list than those well prepared.

4. Be prepared to write a statement on the first day of class indicating why you, of all people on the waiting list, are the most deserving of the first available place in the course. Note that University policy specifies that the instructor has sole discretion of who on the waiting list is admitted to the course, and that it is not necessarily first come first served.

Q. Some of my friends also want to get into this course. What should they do?

A. Tell them to go to the UST Registrar's office and ask to be placed on the waiting list. This is the only way we have of knowing what the actual demand for the course is. The department attempts to meet student demand for courses based on pre-registration information.

Q. I want to get a head start. What can I study over the summer?

A. Well, since you asked (this is not a made-up question), here is my advice:

1. Review your Java skills. Write programs and test language features.

2. Review your Math skills. Look at the self-study reference list and the MATH 128 topic lists above to provide you with a study guide.

3. Obtain the textbook and start working through the first few chapters. The bookstore won't have books for a while, but they are probably cheaper from BarnesandNoble.com or Amazon.com anyway.

4. Check into my home page later on in the summer. By fall I will have extensive web-based resources available for your use during the course. These resources will be not only on St. Thomas's public internet site, but also on our WebCT instructional password-protected intranet site. A mechanism will be set up for obtaining your password later in the summer.

Good luck in your finals.

Have a safe, productive summer.

See you in the fall.

Tom Sturm