CSE logo University of Washington Department of Computer Science & Engineering
 CSE 142 Winter 2004 -- Homework #1

   

CSE 142 Homework #1

Due:  Monday, January 12, 2003 by 5:00 p.m. You may turn your written assignment during lecture that day, or you may turn it in at the front desk of the CSE main office in the Allan Center before the office closes at 5:00 pm. No late assignments will be accepted.

Directions: Answer the following questions. Use full sentences when answering questions that require explanations. Remember to acknowledge any help you receive from individuals outside the course staff. These questions are based on material from lecture and from Ch. 0 and Sec. 1.1-1.2 of Nino & Hosch (2nd ed.), which you should have already read before starting this homework.

Your answers should be typed and printed out for turnin.

Get started right away. Don't wait until Monday afternoon to begin, or you are not likely to finish on time.

Grading Guidelines: Each part of the following questions is worth 2 points. To gain the full 2 points, your answer must have no significant flaws, must be clear to the reader, and must be complete (but remember that complete does not mean verbose - be concise and to the point). One point will be awarded to answers that are partially correct, are somewhat unclear, or are incomplete. You must show credible effort to gain at least one point per question.

Questions

  1. Assume that you need to select a set of courses to attend this quarter. Define and describe the following aspects of a solution to this task. (See the discussion in sec. 0.1.2 of the textbook for a discussion of what it means to "provide an algorithm" or data description.)
    1. Select a processor
    2. Provide an algorithm
    3. Provide a data description
    4. List several representative data values

  2. Describe an algorithm for each of the following location-finding tasks. These algorithms do not have to be be super-detailed or completely fool-proof. The idea is that you write out the steps in some useful level of detail, and show the decisions and looping that you would need to do. Use statements like "if the seat is full then look at the next seat in the row" or "for all rows, do the following set of statements".
    1. Find a place to sit on an airplane with assigned seating.
    2. Find a place to sit or stand at a large concert with no assigned seating.

  3. Consider the concert algorithm you gave above in question 2(b).
    1. Describe two assumptions you have made about the environment that affect how your algorithm operates (no standees allowed, etc). Is it possible that under some circumstances these assumptions would not be valid?
    2. Describe a situation in which your algorithm would fail altogether (never terminate, come up with an invalid answer, etc).
    3. Describe a situation in which your algorithm would provide an answer, but one that you would consider less than satisfactory (for example, if your algorithm always picks a seat in the absolute back row, or has you sit far from your friends, or always picks a seat behind a partition, etc). For example, if you assume that you enter at the back of the arena, and your algorithm always picks the first available seat, then your algorithm would essentially always pick the worst available seat. Think about your assumptions, think about your algorithm, and then try to identify a combination that would result in a "sub-optimal" selection.

  4. For each of the following applications, suggest at least two objects that might be included in the system design. Remember that an object in a program does not have to represent a physical object. Objects can be used to represent any conceptual unit that has state and functionality. Give two responsibilities (queries or commands) that might be assigned to each object.
    1. A program modeling the air traffic control system.
    2. A program that assists the handicapped typist by attempting to guess the word they are typing and providing a list of possible completions for them.
    3. A program that translates English into French.

  5. This question helps ensure that you will be able to use the software for this course without problems, either in the labs at school or on your computer at home, wherever you prefer. The question is not intended to test your programming ability.

    If you are working on a machine that does not have the software installed, instructions for downloading and installing the course software can be found on the Computing at Home page on the CSE142 web. You need to install the Sun Java SDK, DrJava, and the UW CSE software libraries and folders.

    Once you have either installed the software on your computer or found a lab computer where it is already installed, start DrJava. If you have installed it on your own machine, follow the instructions on the Computing at Home page. If you are using the IPL or other UW public lab, select Programs from the Start menu, find the CSE items, and run DrJava from there. Once DrJava has started, type the following commands in the interactions window, the bottom window of the screen, right after the > symbol. Hit the Enter key after typing each line. Note that you may have to click in the interactions window to make it active again after entering the statement that starts with "GWindow w". 

      import uwcse.graphics.*;
  GWindow w = new GWindow(200,50);
  w.add(new TextShape("Hello World!",65,15,java.awt.Color.RED));
    After you have typed these commands, describe what you see on the screen (i.e, what is displayed, what color is it, roughly where is it in the drawing window - center, lower-right, etc.). This is not a trick question - the display is about as simple as it gets. In fact, this is a version of the classic "Hello World" program that everybody writes to make sure that their tools are operating correctly. The idea is to help you get things working now so you won't be fighting the software mechanics later.