CS计算机代考程序代写 algorithm NAME:                                                                                                                                                                                                                                                                                                                                                            CMPSC   442 

NAME:                                                                                                                                                                                                                                                                                                                                                            CMPSC   442 
SID:                                                                                                                                                                FINAL   EXAM:    100   points                                                                                       FALL   2017 

INSTRUCTIONS:    Write   your   name   and   SID   at   the   top   of   every   page.   Write   your   answers   on   the   exam 
sheet   in   the   white   space   below   the   questions.   When   you   have   finished,   show   your   id   when   you   turn   in 
your   exam.  
 

Question  Maximum   Points  Actual   Points 

1a  2.5   

1b  2.5   

1c  2.5   

1d  2.5   

1e  10.0   

2a  2.5   

2b  2.5   

2c  5.0   

2d  10.0   

3a  2.5   

3b  2.5   

3c  10.0   

4  25.0   

5a  2.5   

5b  2.5   

5c  2.5   

5d  2.5   

5e  2.5   

5f  2.5   

5g  2.5   

5h  2.5   

TOTAL  100.0   

 

 
 
NAME                                                                                                                                                                                                                                                                                                                                                                                                                                 2 
SID  

 

1.   Uninformed   Search   (5   parts,   20   points   total) 
 
Search   is   evaluated   by   completeness,   optimality,   and   space   &   time   complexity.  
1a.    Define   completeness    (2.5   points) .  
 
 
 
1b.    Define   optimality    (2.5   points) .  
 
 
 
1c .   Space   &   time   complexity   are   analogous;   how   are   they   different    (2.5   points) ?  
 
 
 
 
1d.    What   are   the   three   aspects   of   an   uninformed   search   algorithm   used   to   express   time 
complexity   and   space   complexity    (2.5   points) ?  
 
 
 
 
1e .   Fill   in   the   rest   of   the   following   table.   Use   big   O   notation   for   complexity.    (10   points) 
 
 

  Breadth­first  Depth­first  Iterative   Deepening 

Complete       

Optimal       

Time       

Space       

  
 
2.   Informed   Search   (4   parts,   20   points   total) 
 
2a.    What   is   the   definition   of   an   admissible   heuristic   h   (2.5   points)?  
 
 
 
 

 
 
NAME                                                                                                                                                                                                                                                                                                                                                                                                                                 3 
SID  

 

2b.    What   is   the   definition   of   a   consistent   heuristic   h   (2.5   points)? 
 
 
 
 
 
 
2c .   What   is   a   strategy   to   find   a   good   heuristic   for   a   search   problem   P   (5   points)? 
 
 
 
 
 
 
2d.    Give   an   example   of   an   admissible   heuristic   for   the   8­puzzle   that   we   reviewed   in   class,   and   a 
relaxation   of   the   8­puzzle   rules   that   the   heuristic   is   a   solution   for   (10   points). 
 
 
 
 
 
 
 
3.   Games   and   adversarial   search   (3   parts,   15   points   total) 
 
3a.    In   alpha­beta   pruning   applied   to   minimax   adversarial   search,   what   does   alpha   keep   track   of 
(2.5   points) ? 
 
 
 
 
 
3b.    What   does   beta   keep   track   of    (2.5   points) ? 
 
 
 
 
 
 
 
 
 

 
 
NAME                                                                                                                                                                                                                                                                                                                                                                                                                                 4 
SID  

 

3c.       Apply   alpha   beta   pruning   to   the   graph   shown   here:   assign   the   number   at   each   of   the   nodes 
that   the   minimax   algorithm   with   alpha   beta   pruning   will   pass   up   the   tree.   Mark   through   arcs   that 
are   pruned   away,   if   any,   and   nodes   that   are   pruned   away,   if   any.   To   mark   an   arc   as   pruned 
away,   place   an   =   over   the   arc.   To   mark   a   node   as   pruned   away,   place   an   X   over   the   node    (10 
points) .  

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4.   Shift­reduce   parsing   (25   parts,   25   Total   Points).       Given   the   grammar   rules   shown   below, 
write   out   the   steps   in   a   shift­reduce   parse   for   the   following   sentence:   “Students   at   PSU   are   very 
intelligent   and   hardworking.”   The   next   page   shows   how   to   start.   Fill   in   the   remaining   rows, 
marking   each   row   as   S   for   Shift   or   R   for   reduce. 
 

S   →   NP,   VP 
CONJ   →   “and” 
NP   →   NNS 
NP   →   NN 
NP   →   PRO 
NNS   →   “students” 
NP   →   NP,   PP 

PP   →   PREP,   NP 
PREP   →   “at” 
NP   →   NE 
NE   →   “PSU” 
VP   →   V,ADJP 
ADJP   →   ADJP,   CONJ,   ADJP 
 

ADJP   →   ADV,   ADJ 
ADJP   →   ADJ 
ADV   →   “very” 
ADJ   →   “intelligent” 
ADJ   →   “hardworking” 
V   →   “are” 
 

 
 
 

 
 
NAME                                                                                                                                                                                                                                                                                                                                                                                                                                 5 
SID  

 

Fill   in   the   remaining   rows   below   to   illustrate   each   next   step   in   the   shift­reduce   parsing. 
 

  [  *  Students  at  PSU  are  very  intelligent  and  hardworking  ] 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
NAME                                                                                                                                                                                                                                                                                                                                                                                                                                 6 
SID  

 

5.   Machine   learning,   perceptrons,   and   neural   nets   (8   parts,   20   points   total) 
 
5a.    How   can   a   linear   regression   be   used   as   a   classifier    (2.5   points) ?  
 
 
 
5b.    How   is   an   understanding   of   linear   regression   used   as   a   classifier,   or   of   classification   with 
logistic   regression,   related   to   a   perceptron    (2.5   points) ?  
 
 
 
5c.    In   a   feedforward   network   of   perceptrons,   how   are   the   neural   units   connected    (2.5   points) ?  
 
 
 
5d­h.    In   the   unlabeled   picture   of   a   percepton   shown   below,   fill   in   the   content   for   5d.   ­   5h    (2.5 
points   each   of   d   through   h) .