The midterm will be similar to the midterms in Software I. It will be a written exam done in class. The topics covered will be everything from SortingMachine up to and including Context-Free Grammars. This also includes topics from labs, homework, and projects.  It will not include Recursive-Descent Parsing or Code Generation. You should also be familiar with general ideas of implementing kernel classes, such as the usage of instance variables, the representation, the correspondence, and the convention.

Questions may be on any of these topics, but you are not expected to memorize everything.  For example, if a question deals with something from a project, you will be given the relevant information from the project in order to complete the question. As another example, you will not be expected to remember any context-free grammars, but you should be able to understand and interpret a grammar if given one. Additionally, the exam will include the contracts from the API for any components that are needed to answer a question.

Topics:

•  SortingMachine

•  Sorting Algorithms – Insertion Sort, QuickSort, Heapsort

•  Heaps – siftDown, heapify

•  Linked Data Structures – Singly-linked List, Doubly-Linked List, Smart Nodes

•  Linked List Implementations of Components – Stack, Queue, List

•  Trees

•  Abstract Syntax Trees

•  Program and Statement

•  Context-Free Grammars

The format of the exam will  have different styles of questions, including true-false, multiple-choice, fill-in-the-blank, diagram drawing, short answer, and coding questions.

Below are some practice questions for the exam.

1.  Consider the following grammar that defines a subset of URLs for web addresses.  The symbol [a-z] means a|b|c|d|...x|y|z, that is, any lowercase character.

s t a r t → sub . domain . top

sub → www j ?1?

domain → char—seq

top → com j net j ?2?

char—seq → char j char char—seq

char →   [ a—z ]

1.1  Suppose the following string is in the langauge of the grammar.

print.osu.org

If this string is in the language, what are the values of ?1?  and ?2?  in the grammar?

1.2  What are the terminal symbols in the grammar?

1.3  what are the non-terminal symbols in the grammar?

1.4  Which of the following strings are in the langauge defined by the grammar?  If they are in the language, draw their derivation tree.

www.osu.com √

www.Mi.net ×

www.a.net √

2.  Implement the following pair of methods.  The methods convert a program so that any while loops in the program are modified to be infinite while loops (yes, it is a ridiculous method). You should think of what we did when implementing the simplify-if-else method and the rename method from the lectures.

public  static void infiniteLoop ( Program  p)  {

}

public  static  void infiniteLoop ( Statement  s)  {

}

3.  Draw the abstract syntax tree for the following BL snippet.

WHILE  true  DO

FindEnemy

infect

IF  next -is - friend  THEN

HighFive

turn left

ELSE

turnright

END  IF

END   WHILE

4.  Draw the heap that results from heapifying the following array of characters, assuming alpha- betical  order. You should  interpret the array of characters as a binary  tree  like  in the  Heap- Sort  project.   Remember that buildHeap  recursively  calls buildHeap on the  left  and right  subtrees and  the base case is a single  node .

Build  the  heap  for