"Programming" Problems for Computer Science: An Overview

The following is a chapter-by-chapter list of problems for readers of Computer Science: An Overview (10th edition) who already have programming experience in an object-oriented language. These are not always precisely defined assignments. Instead, many are suggestions for assignments that can be refined depending on the particular environment.

If you have suggestions for additional problems, I would appreciate hearing from you via email at glennb@mscs.mu.edu.

Last update: December 19, 2007

Chapter 1 Data Storage

1.1 Write a program that initializes a variable of type integer to the value 1 and then repeatedly multiplies the variable by 2 eighty times while displaying the results. Explain the values that are displayed.

1.2 Does the programming language you know provide a convenient technique for detecting and handling overflow?

1.3 Write a program that initializes a real variable at 0.01 and then repeatedly increments the variable by 0.01 one hundred times while displaying the results. Are the values displayed correct? Why would you expect that they may not be?

1.4 Write a program that applies LZW encoding to compress a string of 0s and 1s.

Chapter 2 Data Manipulation

2.1 Pick a simple statement in the programming language you know and translate it into the machine language of Appendix C.

2.2 Write a program to simulate the machine described in Appendix C.

Chapter 3 Operating Systems

3.1 What utility/application programs do you use to prepare a program in the programming language you know? Should these programs be called application programs or utility programs? Justify your answer.

3.2 If you are using an interactive time-sharing system to develop programs, how can you find out how many other users are using the system with you? Does the system's response become sluggish as this number increases? Why might you expect it to do so?

3.3 Identfy two instructions in your programming language that would cause the program to interact with the operating system and explain what that interaction would be.

3.4 Write a simple utility program--perhaps a simple editor.

3.5 Explore the directory system on the computer system you are using. How does the operating system protect sensitive/critical files? What steps can you take to protect your own files?

Chapter 4 Networking and the Internet

4.1 If you have access to a computer with a Web server, implement a simple Web page such as the one described in Section 4.3 of the text.

4.2 Search the Web for information about the programming language JavaScript. How does that language compare to the language you know? How does that language relate to the material in this chapter?

4.3 If you know the language Java, use the tools provided in the Java API to build simple server and client. Your client should be designed to contact the server and receive a message from the server that it then displays to the client's user.

4.4 If you know the language Java, use the tools provided in the Java API to build a simple chat room.

Chapter 5 Algorithms

5.1 Identify the statements in your programming language that are designed for loop control. In each case, identify what parts of the loop control are provided automatically and what parts the programmer must specify explicitly.

5.2 Write a program that implements the sequential search algorithm.

5.3 Write a program that implements the binary search algorithm.

5.4 Use your solutions to problems 5.2 and 5.3 to compare the efficiency of the sequential and binary search algorithms.

5.5 Write a program that implements the insertion sort algorithm.

5.6 Use the Web to research other sorting algorithms such as the selection sort, the bubble sort, and the quick sort. What are the advantages and disadvantages of each? Write programs that implement one or more of these algorithms.

Chapter 6 Programming Languages

6.1 What features are used in the programming language that you know to help a translator isolate the various statements in a program? What features are used to help a translator identify the various components within a single statement?

6.2 Design a set of mnemonics for the machine language described in Appendix C, and write an assembler to translate programs expressed in these mnemonics into machine language programs.

Chapter 7 Software Engineering

7.1 What features are provided in the programming language you know that encourage well-designed programs?

7.2 What kinds of modular structures are provided by the programming language you know? What forms of data coupling are provided by that language? What forms of control coupling are provided?

Chapter 8 Data Abstraction

8.1 What feautres are provided in the programming language you know for building a) user-defined types, b)abstract data types, and c) classes?

Chapter 9 Database Structures

9.1 Design a system to implement relations that is compatible with the programming language that you know and write routines for performing the select, project, and join operations.

Chapter 10 Computer Graphics

10.1 Write a report summarizing the features of either OpenGL or Direct3D.

Chapter 11 Artificial Intelligence

11.1 Write a program that uses the techniques described in this chapter to solve the eight-puzzle.

11.2 Write a program that simulates an artificial neural network.

Chapter 12 Theory of Computation

12.1 Write a program that simulates a Turing machine.

12.2 Write an interpreter for the Bare Bones language that was described in this chapter.