Breadth Exam – Sample Questions

CS 250 – Problem Solving/Programming

Define Abstract Data Type (ADT); How does it differ from a Class ? What programming language features evolved specifically to support ADTs? What programming language features evolved specifically to support objects/classes? What impact have ADTs and classes had on techniques for performing high-level and low-level design?

Consider the problem of adding two fractions to get a simplified answer (e.g., 1/6 + 1/3 => ½). You presumably know how to do this – find the LCM of the two denominators multiply each fraction by the appropriate value to change its denominator to that LCM, add the rescaled numerators, and simplify.

  A) Give at least the first few steps of a stepwise refinement / top-down design for this process.
  B) Does the function you are designing have pre-conditions? 
     If so, state them.  How can you protect your code against violations of the pre-conditions?

What is object-oriented programming? Explain the concepts of encapsulation, inheritance, and polymorphism as related to object-oriented programming.

CS 270 – Computer Architecture

How are exceptions handled in a pipeline architecture? What is the role of OS in handling these exceptions?

Portions of page tables are often placed in a special cache location, sometimes called the “translation lookaside buffer.” This was the first cache introduced in processors. Explain why and how it is used.

(with CS 250): You are given a task to write a program in your favorite programming language to multiply two matrices. If you are interested in having least amount of cache misses, how would you store the matrices and how will you structure your program to access various elements of the matrices.

(with CS 471): What is pipelining and how does it improve the processor performance? What are the approaches used in a modern architecture to support pipelining? Explain few of the major bottlenecks in realizing pipelining.

CS 361 – Data Structures/Algorithms

A concordance for a document is a list of all distinct words appearing in the document, each with a list of locations in the document where that word is found. Propose a data structure for representing a concordance and an algorithm for building one, assuming that the input is a plain ASCII text file. What is the worst-case complexity of your algorithm? Suppose that you have been supplied with a “dictionary” in the form of a file of English words, one per line, in alphabetic order. Give an algorithm for a spell-check program that takes a concordance and this dictionary as inputs. What is its worst-case complexity?

Simulation programming languages allow one to express the concept of ‘events’ happening at a given ‘time’. The set of all (event, time) pairs for a given program is called the event set, which you can imagine to be sequenced upon a timeline in time order. The simulation controller advances time by proceeding from one event to another in their time order. (You may assume that the controller skips ticks of the clock that occur between two consecutive events.) When the controller reaches an event, the event ‘fires.’ One of the consequences of an event firing may be that one or more new events with later times are created and added to the event set. What are the desirable properties of an implementation of the event set data structure? Discuss several possible implementations including at least unsorted list, sorted list and heap with respect to those properties.

We want to build a data structure for doing the operations INSERT, DELETE, and SEARCH dynamically where elements are drawn from a totally ordered domain (like natural numbers). Discuss the various data structures that can be used with associated worst case and/or expected case run times for various operations.

CS 390 – Theory

Consider a simple regular expression language in which the following operators are used.

*: a repetition of the previous expression 0 or more times is recognized; for example a* 
recognizes 0 or more occurrences of a.
+:  the previous or following  expression is recognized; for example a+b recognizes either a or b.
(): the expression within the parentheses is considered to be a single expression; for example (a+b)* 
recognizes a sequence of zero or more intermixed as or bs.

Two regular expressions may be equivalent in the sense that they recognize exactly the same 
set of inputs.  For example a* and (a)* and (a*)+(a*) are all equivalent.

Suppose you had the problem of deciding whether two regular expressions were equivalent or not, How would you approach the problem? What algorithms would you investigate? What data structures would be appropriate to each?

What is the Chomsky hierarchy for languages? Why can C++ not be recognized by a FA? What kind of languages are recognized by available tools for lexical scanning, what languages for tools to parse a programming language such as C++? Can you name such tools?

What is a regular language? What is a context-free language? Give an example of a context-free language that is not a regular language? Are regular languages closed under intersection? Provide a proof/justification for your answer. Are context-free languages closed under intersection? Provide a proof/justification for your answer.

CS 471 – Operating Systems

Operating systems have alternatives on how to store files on disks. They can implement directories using lists or hash tables and there are many ways to allocate blocks for these files – variations of contiguous allocation, linked allocation, indexed allocation. Discuss the trade-offs for two methods. How does the system keep track of blocks from deleted files and how does it space for new files?

Explain the concept of paging in operating systems. Why was it introduced? Name and describe some basic page replacement algorithms.