Final Exam Solution - Test Paper Final Exam Solution - Test Paper

lOMoARcPSD|36771882
Final Exam Solution - test paper
computer organisation (The University of the South Pacific)
Scan to open on Studeersnel
Studocu is not sponsored or endorsed by any college or university

Downloaded by Breman Wiener ([email protected])
lOMoARcPSD|36771882
CS211: Computer Organisation

Faculty of Science, Technology and Environment
School of Computing, Information and Mathematical Sciences
Final Examination
Semester 1 2017
F2F & Blended Mode
Duration of Exam: 3 hours + 10 minutes
Reading Time: 10 minutes
Writing Time: 3 hours
Total Marks: 100
Instructions:
There are three sections in this paper
Answer all questions in the answer booklet provided
This exam is worth 50% of your overall mark
The minimum mark to pass the final exam is 20/50
The total number of pages including this cover sheet is 11
This is a closed book exam

lOMoARcPSD|36771882
Section A: Multiple Choice (10 Marks)
1) The circuit used to store one bit of data is known as ________________.

A. Register
B. Encoder
C. Decoder
D. Flip Flop
2) 2FAOC is equivalent to
A. 195 084 in decimal
B. 001011111100011101100
C. Both A and B
D. None of the above
3) In Reverse Polish notation, expression A*B+C*D is written as ________________

A. AB*CD*+
B. A*BCD*+
C. AB*CD+*
D. A*B*CD+
4) A page fault
A. Occurs when there is an error in a specific page.
B. Occurs when a program accesses a page of main memory.
C. Occurs when a program accesses a page not currently in main memory.
D. Occurs when a program accesses a page belonging to another program.
5) If an instruction takes 3 cycles for execution, then how many cycles are needed for executing 4
instructions of the same type in a sequence using a 3-stage pipeline? Assume that there are no
interrupts or exceptions while executing them.
A. 12 cycles
B. 6 cycles
C. 9 cycles
D. 4 cycles
6) Which of the following architecture has the fixed instruction length feature?
A. CISC
B. RISC
C. X86

lOMoARcPSD|36771882
7) How do Direct Addressing Mode instructions compare with respect to the Indirect Addressing
Mode instructions?
A. Faster
B. Slower
C. No difference
8) The first person who attempted to build a digital computer was _______________
A. Charles Babbage
B. Blaise Pascal
C. Baron Wilhelm
D. Alan Turing
9) Any computer must at least consist of

A. Data bus
B. Address bus
C. Control bus
D. All of the above
10) When you transfer the record from a Big Endian system to a Little Endian system over the
network in order to get the original value, you must:
A. Reverse the byte within a word
B. Reverse the bytes in an integer
C. Reverse the characters in a word
D. There is no simple solution

lOMoARcPSD|36771882
Section B: Short Answer and Problem Solving (80 Marks)
1. The truth table for the Boolean expression is given below.
x y z F(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
a. Write the disjunctive normal form (DNF) for the above truth table. (2 marks)
b. Simplify the DNF form in part a) using Boolean algebra. (3 marks)
c. Draw the logic diagram for the simplified expression in part b). (2 marks)
d. Draw a multiplexor for the above truth table. (3 marks)
2. For the following three questions, assume that memory locations contain the values shown in
the following table:
Location Value
-------- -----
100 150
110 130
120 110
130 100
140 120
150 140
What value will be loaded into the accumulator if the following instructions are encountered? (3
marks)
a. Load immediate 100
b. Load direct 100
c. Load indirect 100
Answer:
1 mark each
a) 100
b) 150
c) 140

lOMoARcPSD|36771882
3. Consider the following infix assignment statement:
X = ((A-B)+((C-D)/E))*F
Use this statement to answer the following five questions.

a. Using two-operand instructions and no more than 4 registers (R0-R3), show the instructions
required to implement the statement. Assume that MOVE A,B moves A to B, ADD A,B adds A
to B, SUB A,B subtracts A from B, MUL A,B multiplies A times B, and DIV A,B divides A into B.
In all cases, A or B can be a register or memory address, and the result is always stored in B.
( 2 marks)
b. Assuming each instruction takes 16 bits if only registers are referenced, and 16 additional
bits for each memory reference, how many bytes long is your program? (1 mark)
c. Using 0-operand instructions on a stack-oriented machine, show the instructions required to
implement the statement. Assume that PUSH A pushes the contents of location A onto the
stack, ADD replaces A B with A + B, SUB replaces A B with A - B, MUL replaces A B with A * B,
DIV replaces A B with A / B, SWAP replaces A B with B A, and POP A takes the top item off
the stack and stores it to location A. (In the above, if A B are on the stack, consider B to be
the top of the stack and A to be the one below.) (2 marks)
d. Assuming each instruction takes 8 bits for the opcode and 16 bits for a memory address, if
any, how many bytes long is your program? (1 mark)
Answer:
a)
MOVE A,R0
SUB B,R0
MOVE C,R1
SUB D,R1
DIV E,R1
ADD R0R1
MUL F,R1
MOVE R1,X
b) 7 operands * 2 bytes per operand + 8 instructions * 2 bytes per instruction = 30 bytes.

c)
PUSH A
PUSH B
SUB
PUSH C
PUSH D
SUB
PUSH E
DIV
ADD
PUSH F

lOMoARcPSD|36771882
MUL
POP X
d) 7 operands * 2 bytes per operand + 12 instructions * 1 byte per instruction =

26 bytes.
4. A register has contents in hexadecimal of ABC01234. After right arithmetic shift of 8 bits, what
are the contents of the register? Give your answer in hexadecimal. ( 2 marks)
Answer:
1010 1011 1100 0000 0001 0010 0011 0100 ½ mark
1111 1111 1010 1011 1100 0000 0001 0010 1 mark
=> FFABC012 ½ mark
5. Justify whether it is possible to design an expanding opcode to allow the following to be

encoded in a 16-bit instruction? An address is 4 bits. (5 marks)
15 instructions with three addresses
14 instructions with two addresses
31 instructions with one address
16 instructions with 0 address
Answer:
0000 R1 R2 R3
…. 1 mark
1110 R1 R2 R3
1111 0000 r2 r3
& 1 mark
1111 1101 r2 r3
1111 1110 0000 r3
&. 1 mark
1111 1111 1110 r3
1111 1111 1111 0000
&& 1 mark
1111 1111 1111 1111
Therefore, this design is possible. 1 mark

lOMoARcPSD|36771882
6. What is one major problem in Clocked SR latch and explain how a clocked D latch solves the
problem? ( 3 marks)
Answer:
An error (ambiguity) occurs in the SR latch when S and R inputs are both 1 (1.5 marks)
It prevents both inputs S and R being 1 at the same time by providing one input D and its
complement (1.5 marks)
7. List three different ways to achieve processor –level parallelism when designing computers.
(3 marks)
Answer:
Array computers
Multi processors
Multi computers
8. For the page references given below, answer the questions that follow.
A, B, C, D, B, E, C, G, D, A, G, D, B, E, C
a. How many page faults will occur if optimal page replacement algorithm is used? Show all
working. [2 marks]
b. How many page faults will occur if LRU page replacement algorithm is used? Show all
working. [2 marks]
c. How many page faults will occur if FIFO page replacement algorithm is used? Show all
working. [2 marks]
Answer:
a) 8 page faults 1 mark. 1 mark for table
b) 11 page faults 1 mark. 1 mark for table

lOMoARcPSD|36771882
c) 11 page faults 1 mark. 1 mark for table
9. Assume you have a superscalar CPU with in-order issue and in-order instructions that uses 8
registers (R0-R7). The usual rules include: up to two instructions can be issued in one cycle;
instructions have to complete in the order they are issued; an instruction attempting to write to
a register that is being read by any incomplete instruction cannot be issued until the incomplete
instruction completes; any instruction attempting to read a register that is being written to by
any incomplete instruction cannot be issued until the incomplete instruction retires; no new
instructions can be issued in a cycle when instructions are retiring; multiplication/division
instructions takes 3 cycles to complete while addition/subtraction instructions take only 2
cycles. Suppose you need to run the following four instructions:
1. R3 = R1 + R2
2. R1 = R4 * R5
3. R5 = R2 * R8
4. R6 = R1 + R4
a. How many cycles in total will the CPU take to complete the four instructions above. Use a
scoreboard as shown below to illustrate your answer. (4 marks)
Cycle Instruction # Decoded Issued Retired

1 1 R3 = R1 + R2 1

lOMoARcPSD|36771882
b. How many cycles will the CPU take if out-of-order instruction issue and execution is allowed.
Use a scoreboard as shown above to illustrate your answer. (4 marks)
Answer:
a. 11 cycles (0.5 mark)
Cycle Instruction # Decoded Issued Retired Mark

1 1 R3 = R1 + R2 1 1
2 R1 = R4 * R5 -
2
3 1 0.5
4 2 0.5
3 R5 = R2 * R8 -
5
6
7 2 0.5
8 3 0.5
4 R6 = R1 + R4 4
9
10
11 3 0.5
4
b. 5 cycles (0.5 mark)
Cycle Instruction # Decoded Issued Retired Mark

1 1 R3 = R1 + R2 1 1
2 S1 = R4 * R5 2
2 3 S2 = R2 * R8 3 1
4 R6 = R1 + R4 4
3 1 0.5
4 2 1
4
5 3 0.5
10. Suppose you are designing a computer from scratch and that your company’s budget allows a
very small amount of memory bandwidth. Which of the following characteristics would you
choose in the ISA and the microarchitecture? Explain your answer. (6 marks)
a. Variable length or fixed length instructions?
b. Complex instructions or simple instructions?
c. A large cache or a small cache?
Answer:

lOMoARcPSD|36771882
a. Variable length =>smaller code therefore less bandwidth to transfer instructions 2 marks
b. Complex instructions => smaller program because each instruction is more powerful
therefore less bandwidth to transfer instructions. 2 marks
c. Large cache => higher cache hit rate which will result in less need to access memory. 2
marks
11. Two processors with different ISA need performance evaluation. The first processor with ISA A
performs at the rate of 10 instructions per cycle where as the second processor with ISA B
performs at the rate of 2 instructions per cycle. The first processor has 500 MHz clock while the
second processor has 600 MHz clock.
a. What is the performance in MIPS of the processor implementing ISA A? (1 mark)
b. What is the performance in MIPS of the processor implementing ISA A? (1 mark)
c. Which is the higher performance processor? Explain your answer. (2 marks)
Answer:
a. 10 IPC X 500 MHz = 5000 MIPS 1 mark
b. 2 IPC X 600 MHz = 1200 MIPS 1 mark
c. Not enough information provided. We don’t know the number of instructions
executed on each processor, so we can’t compare performance. Processor A for
example may have very simple instructions . Processor B could be faster if its
instructions actually accomplish significantly more work than Processor A’s. The
MIPS metric does not take into account number of executed instructions, which also
affects the performance (i.e. execution time) of each processor. 2 marks
12. What would be the code word if you encode the data word 10011010 to allow one bit error
detection and correction using hamming code with even parity? (4 marks)
Answer:
_ _ 1 _ 0 0 1 _ 1 0 1 0 (0.5 mark)
 Position 1 checks bits 1,3,5,7,9,11: (0.75 mark)

? _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0
 Position 2 checks bits 2,3,6,7,10,11: (0.75 mark)
0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1 _ 1 0 1 0
 Position 4 checks bits 4,5,6,7,12: (0.75 mark)
0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1 _ 1 0 1 0
 Position 8 checks bits 8,9,10,11,12: (0.75 mark)
0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1 0 1 0 1 0
 Code word: 011100101010. (0.5 mark)
13. The instruction execution cycle consists of six steps. The second step is <Increment the program
counter=. Explain the purpose for the second step? (2 marks)
Answer: Program counter points to the next instruction to execute. To make progress in
program execution.

lOMoARcPSD|36771882
14. A segmented address space uses paged virtual memory. Each virtual address has a 2 bit segment
number, a 2 bit page number and an 8 bit offset within the page. In the following page tables, a
<-= indicates that the page is not in memory, which has 8 page frames.
segment 0 segment 1 segment 2 segment 3
page frame page frame page frame page frame

0 - 0 - 0 - 0 -
1 1 1 5 1 3 1 4
2 - 2 6 2 2 2 -
3 0 3 - 3 - 3 7
a. What is the lowest hexadecimal virtual address in segment 2 that will cause a page fault?
(2 marks)
b. Find the real memory address (in hexadecimal) if the virtual hexadecimal address is FAA.
(2 marks)
c. Find the virtual address (in decimal) if the real memory decimal address is 1000.
(2 marks)
a. 10 00 00000000 = 800
(1.5 marks) (0.5 mark)
b. C12 = 1111 10101010  Segment 3 Page 3, Frame 7 = 111 10101010 = 7AA

c. 1000= 11 11101000  Frame 3, Segment 2 Page 1= 10 01 11101000 = 1256
15. Which value does this two’s complement binary number 11110100 represents? (2 marks)
Ans: 00001011
+ 1
---------------------
00001100 =>12 (1.5 marks)
-12 (0.5 marks)
16. Suppose the hard disk above has 1024 cylinders, 8 tracks per cylinder, 32 sectors per track and
512 Bytes per sector. The maximum seek time is 450 msec, the time to move between adjacent
cylinders is 10 msec, the rotation time is 14. If the entire disk was full of data stored
consecutively, how much time would it take to read the entire disk if the read/write head is
already positioned on the first sector of the first track of the first cylinder of the disk? (3 marks)

lOMoARcPSD|36771882
Answer:
Total time = cylinder read + track switch + track switch wait + cylinder switch/wait
= (8*14)*1024 + (0) + (0) + (1023*14)
= 129010 msec
17. On computer 1, all instructions take 10 nsec to execute. On computer 2, they all take 5 nsec to
execute. Can you say for certain that computer 2 is faster? Explain your answer. (3 marks)
Answer:
You cannot say anything for sure. If computer 1 has a five-stage pipeline, it can issue up to 500 million
instructions/second. If computer 2 is not pipelined, it cannot do any better than 200 million
instructions/sec. Thus without more information, you cannot say which is faster.
18. A machine instruction is needed during execution. The instruction could be in an instruction
cache (with probability 0.65) or in memory (with probability 0.3) or on disk. The access times for
cache and disk are 50 ns and 6000 ns respectively. Assume each instruction source is checked
before a slower one to find the instruction. What minimum memory access time (in ns) will give
an expected access time of 800 ns? (3 marks)
Answer:
Let memory access time = m

[50 x 0.65] + [(50 + m) x 0.3] + [(50 + 6000 + m) x 0.05] = 800
32.5 + 15 + 0.3 m + 302.5 + 0.05 m = 800
0.35 m = 450
m = 1285.71 ns
19. Why do you think John von Neumann’s original basic design of a computer, known as von
Neumann machine, is still the basis for nearly all digital computers? (2 marks)
Answer:
His machine has 5 basic parts (memory, control unti, ALU, input and output) which are still found and
are important components of a digital computer.

lOMoARcPSD|36771882
Section C: Assembly Language Programming (10 Marks)
Extend the Wombat 3 accumulator based assembly language to the Wombat 4 addressing modes.
Addressing modes will be used only on STORE and LOAD machine instructions. There are three modes
that can be used: Direct, Indirect and Immediate. For example, LOAD IMM 122 will load the value 122
into the accumulator and STORE IND L2 will store the contents of the accumulator to address stored at
location L2.
Write a complete Wombat 3 assembly language main and subprogram. The main program tests the
subprogram: it reads in exactly one integer, checks that the integer is valid input, calls the subprogram
and writes out the result. The subprogram must compute the function: f(n) = 4 × n × f(n − 1)
where f(0) = 3. The program must be properly commented.
Answer:
L1: read ; read n -> acc

jmpn L1 ; jump to Done if n < 0.
push ; add sum to the acc
call Sub ; call subprogram
main: pop ; pop value returned from subprogram
write ; write the final value
stop ; stop
Sub: pop ; pop n from stack to acc

store DIR m ; store n to loc m
L2: jmpz L3 ; if n = 0, go to L3
store DIR n ; store n to loc n
mult const3; n X 4
push ; push result
load DIR n;
subt const ; n – 1
jmp L2 ; go to loc L2
L3: load IMM 3; acc = 3
push ;push 3 on to stack
load DIR m ; acc = m
L4: jmpn L5 ; if acc < 0, goto loc L5
pop ;
mult storage; acc = acc * storage
store DIR storage; storage = acc
load DIR m ; acc = m
subt const ; acc = acc – 1
store DIR m ; m = acc
jmp L4 ; jump to loc L4
L5: load DIR storage;
push ; push calculated value on stack for main
return main; return to main program
n: .data 2 0 ; storage for n
m: .data 2 0 ; storage for m

lOMoARcPSD|36771882
const: .data 2 1 ; storage for constant 1

const2: .data 2 3 ; storage for constant 3
const3: .data 2 4 ; storage for constant 4

lOMoARcPSD|36771882
Lecture notes 1 "What is AI" and History
Artificial Intelligence and Neurocognition (Universiteit Leiden)

lOMoARcPSD|36771882
ArtiÞcial intelligence LEC 1
What is AI?
- Cognitive psychology: the study of computations that make it possible to
perceive, reason and act. (Input Ñ> processing Ñ> output)
- AI: The study of how to build or program computers to enable them to do what
minds can do
- AI=/= psychology or computer science, but draws form these disciplines:

• Puts greater emphasis on computation than psychology
• Puts greater emphasis on perception, reasoning and action than computer
science
Why AI in psychology?
- Psychology is one big inverse problem (too many ways to interpret something)
- Set of observations (behavior, psychophysiological measurements, EEG, fMRI)
- We then try to infer the processes producing such observations. Limited /
sometimes impossible to make
- AI can use forward modeling start from scratch

- We design a (simple) system, see how that behaves
History of AI
- 90Õs Ôneural networksÕ, 70Õs Ôcomputer chessÕ; starts with a hype, followed by
disappointment, followed by lack of funding Ñ> AI winter
Philosophy of mind
- How does the physical brain give rise to the mental mind?
- RenŽ Decartes (1596-1650): dualism because the mind is not physical
- Materialists: All mental states are caused by (or identical to) physical states. If we
agree to this, it means copying a physical state means copying a mental state
(copying a brain copies someone consciousness).

lOMoARcPSD|36771882
1940 1960 1980 2000 2020
1943 1965 1986 2010s

Walter-Pitts neuron ELIZA PDP handbook Deep reinforcement
learning
1950 1971 1997 2012

Computing Machinery STRIPS Deep Blue vs Kasparov Personal assistants
and Intelligence Siri, Google Go
1951 1972 2015

SNARC MYCIN AlphaGo
1956 1974-1980Õs
Dartmouth AI winter
Conferences
1940Õs
- Warren McCulloch and Walter PittÕs 3 principles:
• Basic physiology
• Propositional logic
• TuringÕs theory of computation
- Any computable function can be computed by a network of neurons
(combinations of neurons and their connections can compute anything)
- All logical operators can be implemented by simple neural networks
Weak AI
Turing test = human talks to 2 voices, one AI other human, determine which is which
- Non-sentient AI (chat bots)
- Imitation game: a machine is intelligent if we cant distinguish it from a human in
conversation
- How does a judge determine intelligence?
• Complex grammatical structures
• Realistic world knowledge (not too much, not too little)

lOMoARcPSD|36771882
Searle
- Collection of cells can lead to thought/action/consciousness
- Consciousness requires actual physical-chemical properties of human brains
- Only brains make minds
- Chinese room argument (1980):
• In a room containing only a large book and a door under which pieces of paper
can be passed
• Chinese people on the outside of the room can ask me questions by wiring
them down and passing pieces of paper under the door
• Large book contains every possible question + answer, so you can answer in
Chinese.
- Ñ> intelligence? no, looking up question (input) Ñ> processing it (looking up
the right answer) Ñ> writing it down (output). Rule-based manipulation of
symbols does not constitute intelligence: the inhabitant of the Chinese room
does not understand Chinese.
- Chinese room criticism: AI really is just an ongoing program showing Chinese
room is false
- No matter how intelligent machine behavior may seem, it does not reßect
true intelligence.
- Where do we draw the line between just a system and intelligence?
Strong AI
- ÒThe appropriately programmed computer with the right inputs and outputs would
thereby have a mind in exactly the same sense human beings have mindsÓ
- Strong AI proponents believe that intelligent systems can actually think

- Most people believe that strong AI should have a connectionist architecture
Problems
- Does an accurately enough simulated human mind have all the same properties
as an actual human mind?
- Can machines think?

• The question of whether a computer can think is no more interesting than the
question of whether a submarine can swim - (dijkstra)

lOMoARcPSD|36771882
• In other words: are we asking the right questions?

• Strong AI assumes that the human mind is an information processing system,
and that thinking is a form of computing (a basic tenet of cognitive psychology)
1950s
Minsiy and EdmondsÕ SNARC
- Built the Þrst randomly wired neural network learning machine (SNARC)
- 40 neurons
50Õs and 60Õs

- Dartmouth Conferences (1956): birth of AI
• Pioneers in the Þelds of computer science, maths and cognitive science got
together for a month-long conference at Dartmouth college. (coined the term
ArtiÞcial Intelligence)
Several successes:
- General problem solving using a physical symbol system.
- Computers playing checkers, proving theorems
- Invention of Lisp, the dominant high-level AI language
- Neural network (connectionist) research was pushed to the background
Symbolic AI
- Not concern itself with neurophysiology
- Human thinking is a kind of symbol manipulation (If A>B and B>C then A>C)
- Intelligence is thought of as symbols and the relations between them
- Knowledge-based, or expert systems were hugely successful
ELIZA
- Weizenbaum (1965): ELIZA was an early natural language processor
• Used simple techniques to create the illusion of understanding
• Regardless, some people felt like the computer did understand them

lOMoARcPSD|36771882
• Answers like : what makes you think so / tell me more about ..

- Response from public: computers can talk!
- weizenbaum: I had not realized that extremely short exposures to a relatively
simple computer program could induce powerful delusional thinking in quite
normal people
- Anthropomorphization of computers is just a mind trick
STRIPS
- Stanford Research Institute Problem Solver: an automated planner
- Realization of goals
- Divide the task into subgoals, identify necessary actions
- Early action planners were susceptible to the Sussman anomaly:
• Agent must stack the blocks with A on top of B and B on top of C. Only move 1
block at a time.
• 2 subgoals, but
either way, you
wonÕt get it with
the simple
planner.
Expert systems
- Emulates the decision-making ability of a human expert
- MYCIN (Stanford 70s) was designed to diagnose and recommend treatment for
certain blood infections
• Simple if-then rules with certainty factors

• Reached an accuracy of 69%, better than physicians at Stanford Medical
School
• Not used in practice due to ethical and legal difficulties (whoÕs to blame when it
goes wrong?)

lOMoARcPSD|36771882
60s-70s
- OverconÞdence in AI systems (too much faith in them)
- AI not as powerful as many thought Ñ> AI winter
- Many unanswered questions: how do we deal with perceptions robotics, learning
and pattern recognition?
- Symbolic AI does not suffice
Symbolic vs connectionist AI: Symbolic AI criticism

- Why do we need symbolic representation? DoesnÕt seem necessary for many
behaviors
- Brooks: ÒThe need for traditional symbolic representations soon fades entirely.
The key observation is that the world is its own best model, it is always exactly up
to date. It always contains every detail there is to be known. The trick is to sense
it appropriately and often enoughÓ
- It is unclear how processes like pattern recognition would work in a purely
symbolic way
- Representations dealing with noisy input are needed
Connectionist AI
- After the AI winter of the 70s, connectionism was revived
• Rumelhart & McClelland: the PDP research group
• Early PDP work: McClelland 1981
- Model of human memory
• Human memory is content-addressable
• First explicit theory on data storage in the
brain
• Memory is not stored in neurons but in the

connections between them
• Excitatory and inhibitory connections

• This allows us to:
- Find properties of one particular member
- Identify a member by properties (e.g.

lOMoARcPSD|36771882
who is a shark in his 20s?)
- Identify general characteristics of members of a gang, or members with a

certain characteristic (e.g. what characteristics are common to bookies in this
group?) shows generalization
- Visual demonstration
• Parallel distributed processing, connectionism, artiÞcial neural networks
- Biologically inspired
• Connectionism is based on the structure of the human brain
• Neurons receive input through dendrites and send output through axon
• Highly connected (1000s of synapses on axon and dendrites)
• 20x10^9 neocortical neurons, 15x10^13 cortical synapses
• Computation is massively parallel = efficient
- Lesion tolerant
• Lesioned or damaged networks can still process information
- Capable of generalization
• ANNs are capable of learning, and able to generalize rules to novel input
- Principles
• How do these neural networks compute anything?
• Neurons output a signal based on their input signal
• Multi-layer perceptrons are able to implement all logical operators, such as
AND, OR, XOR
• Mental states are represented as N-dimensional vectors of numeric activation

values over neural network units
• Memory is created by modifying the connection strength (weight) between units

- Solve complex, non-linear or chaotic classiÞcation problems
- No a priori assumption about problem space or statistical distribution
- ArtiÞcial neural networks can compute any computable function
- Pattern recognition

lOMoARcPSD|36771882
80s-90s
- 1997: Þrst time a computer (IBM;s Deep Blue) beat a grandmaster at chess
- 2005: last time a human beat a top chess computer under tournament conditions
- 2009: HTC touch HD running chess software equals Deep BlueÕs performance
2000s-present
- Data mining offers huge quantities of data
- Deep learning offers representation at many levels
- Bayesian networks deal with uncertain knowledge
- Deep reinforcement learning can learn to act from rich, noisy data
Deep Networks
- Adding more layers adds to dimensionality of classiÞcation
- Multiple representations offer multiple levels of abstraction
- Recurrent connections can maintain context, temporal information
- Combination is hot topic: google is investigating motion classiÞcation and content
classiÞcation
GO
- Critics said chess was too simple
- Ancient Chinese game Ô goÕ has +- 10^170 legal positions vs 10^43 legal
positions in chess Ñ> never mastered by a computer
- 2016 Google DeepMindÕs AlphaGo defeated the worldÕs number one player
- Software used deep reinforcement learning
Machine learning
- If we donÕt want to preprogram all knowledge, systems should be able to learn
• How to construct computer programs that automatically improve with
experience (mitchell 1997)

lOMoARcPSD|36771882
• A computer program is said to learn from experience E with respect to some

class of tasks T and performance measure P, if its performance at tasks in T, as
measured by P, improves with experience E
- Supervised learning:
• External knowledgable supervisors present the system with correctly labeled
training data
- Unsupervised learning:
• Discover hidden structure in data without labeled data
- Reinforcement learning
• Learning from feedback signal
- ClassiÞcation
• Determining group membership based on input data
• Ô Does this MRI image of someoneÕs head show a brain tumor?Õ
- Regression
• Predict outcome data based on input data
• Given its location, surface ara, and number of rooms, can we predict the value
of this house?
Conclusion
Philosophical implications:
- Weak AI; machines can simulate human intelligence using clever tricks
- Strong AI: well-programmed machine that exactly emulates the human brain is a
mind, and thereby intelligent
Approaches to AI:
- Symbolic AI: intelligent behavior through manipulation of symbols

- Connectionist AI: representations in the brain are distributed, processing
massively parallel

lOMoARcPSD|36771882
Lecture Notes
Artificial Intelligence and Neurocognition (Universiteit Leiden)

lOMoARcPSD|36771882
Artificial Intelligence
1. Introduction and history of artificial intelligence
Course objectives
- how AI became a science
- What are the different flavours of AI research (symbolic, artificial neural network)
- What are the techniques behind intelligence software (search techniques)
- How can robots seem so intelligent?
- How can computer systems learn new things (supervised, unsupervised, reinforcement
learning)
- How is AI used in practise?
Four kinds of AI (approaches):
Acting humanly we don’t care about the cognitive system, as long as it behaves
Cognitive psychologists are also called computationists: the study of computations that make it
possible to perceive, reason, and act. AI is not psychology or computer science, but it draws from
these disciples.
AI does forward modelling instead of reverse modelling. We design a simple system and see
how that behaves.
Algorithms = a set of unambiguous instructions that defines a

sequence of operations
Function = a list of instructions that can take input values (single
numbers, lists of numbers or text strings), perform calculations
with input (that is the algorithm) and it returns an output value.

lOMoARcPSD|36771882
How did the field of AI develop?
1940s - 1960s:
- Warren McCulloch and Walter Pitts’ three principles:

1. Basic physiology
2. Propositional logic
3. Turing theory of computation
- any computable function can be computed by a network of neurons

- All logical operators can be implemented by simple neural networks
Weak AI:
- Turing test
- How far have we come? Think of chatbots, they suck
- Weak AI assumes we can create intelligent behavior through simple tricks
- John Searle says that computers will never be intelligent. Consciousness requires actual
physical -chemical properties of actual human brains! His argument was the Chinese Room
argument.
Strong AI:
- the appropriate programme computer with the right inputs and outputs would have a mind
exactly in the same sense of human beings have minds
- So AI proponents believe that intelligent systems can actually think
Problems:
- are we asking the right question? It is like asking whether a submarine can swim
- Does an accurately enough simulated human mind have all the same properties as an actual
human mind?

lOMoARcPSD|36771882
1950s
- SNARC - first neural network computer with 40 neurons
Symbolic AI = (GOFAI) does not concern with physiology, human thinking is a kind of symbol
manipulation. Intelligence is thought of as symbols and the relations between them.
1965
- ELIZA was a computerised psychotherapist

- Response from the public: computers can have conversations!
- Weizenbaum “ i had not realised that extremely short exposures to a relatively simple computer
program could induce delusional thinking in quite normal people”.
- The anthropomorphization of computers is just a mind trick
1972
- PARRY - simulated a patient with paranoid schizophrenia, the replies are often inconsistent or
meaningless sentences but therefore realistic!
- 33 psychiatrists were asked to classify transcripts of conversations with PARRY or paranoid
schizophrenics; only 48% were correct
- STRIPS - an automated planner

- Divide the task into subgoals and identify
necessary actions
- Early action planners were susceptible to the
Sussman anomaly
- MYCIN - expert systems which emulates the decisions making ability of a human expert
- MYCIN was used to diagnose and recommend treatment for certain blood infection
- They use simple “if-then” with certainty factors
- 69% accurate diagnoses which was better than physicians at the Stanford Medical School
- However it was never used in practise due to ethical and legal difficulties (if a computer gets an
incorrect diagnosis who is to blame?”
60s-70s
- Overconfidence in AI systems led to an AI winter

- Symbolic AI does not suffice, hence the winter period
1986
- PDP handbook
____________________________________________________________________________________
Connectionist AI
- after the AI winter of the 70s, the connectionism was revived

lOMoARcPSD|36771882
- this allowed us to find properties of one particular member

- Identify a member by properties
- Identify general characteristics of members of a gang or members with a certain characteristics
-> this shows generalisation
Connectionist AI is
1. Biologically inspired
2. Lesion tolerant
3. Capable of generalisation
80s - 90s
1997: first time a computer beat a grandmaster at chess

2005: last time a human beat a top chess computer under tournament conditions
2009: an HTC Touch HD running chess software equals Deep Blue’s performance
2000s to present
- deep reinforcement learning can learn to act from rich, noisy data
- In 2016 Google DeepMIND alpha GO delegated the world number one player
Machine Learning
- supervised learning = external knowledgable supervisor presents the system with correctly
labeled training data
- Unsupervised learning = discover hidden structure in data without labelled data
- Reinforcement learning = learning from a feedback signal
Classification = determining group membership
based on input data, does the MRI image of
someone head show a brain tumour?
Regression = predict outcome based on input

data, given its location, surface area, and number
of rooms can we predict the value of this house?

lOMoARcPSD|36771882
2. Symbolic AI and search
Expert systems: reasonings with facts
An example -> the MYCIN

(from last lecture)
- the knowledge base represents facts about the world and about the way in which concepts
are related to each other, often using predicate logic; but it also represents more complex
relationships:
Leukaemia is a disease -> more complex -> leukaemia is an abnormality of blood
Controlling knowledge use (two important rules):
1. Forward chaining
We work from given statements to a

deduced conclusion. This requires a lot of
data and observations.
2. Backward chaining
We start with a conclusion and try to

support our conclusion. We start by forming
a hypothesis and using if-then rules to work
backward toward hypothesis supporting
assertions.
When to use what?
• Backward chaining is helpful in cases where not all facts are known yet
• Forward chaining is helpful when you want to know everything you can from a set of facts
Another test of human intelligence: Sudokus
- backtracking is used

lOMoARcPSD|36771882
- It requires 37,000 iterations (so can be solved under a millisecond), this is much better than
having a combinatorial explosion which is a naive brute force (1.09x10 to the power of 50 ways
to randomly put nine 1s, nine 2s, etc in 81 cells
- The backtracking method guarantees a valid result
Basic and optimal search:
What is search? The process of looking for a sequence of actions that reaches the goal
Input : problem
Output: solutions in the form of an action sequence
Algorithm: Depth first search (DFS)
When a dead end is reached the algorithm backtracks to the previous choice point
Breadth first search
We can check all paths of a given length before moving on to the next level
When to use what?
• DFS is preferred when you are confident that complete paths or dead ends are found after a
reasonable amount of steps
• BFS is preferred when you are working with very deep trees but not when you think that all
paths reach the goal at about the same depth (wasteful)
Non determinist search: nodes are expanded at random
Hill climbing: an algorithm that is similar to DFS but order possible options based on heuristics,
so it is a DFS but with preference
Greedy algorithms: choose the locally optimal choice at each stage
Beam search: performs BFS moving downwards only through the best w nodes

lOMoARcPSD|36771882
Brand and bound: can give us the optimal solution without wasting resources, it works by
expanding nodes ordered by traveled distance. Once it has found a solution it ignores paths with
distances that are equal or greater than the distance for that solution.
A* procedure: combines branch and bound, distance estimates, and redundant path removal. It
guarantees finding an optimal result efficiently
Basic search : is there a path from s to g
Optimal search : if there is a path from s to go what is the shortest path
Adversarial
search:
The alpha beta principle : if you have an idea that is surely bad, do not take time to see how truly
awful it is
The alpha beta algorithm does not consider moves that are considered useless
3. Supervised and unsupervised learning
Machine learning: programs that learn by observation and experience instead of having their
knowledge pre-programmed
Supervised learning = generalising based on training data. We provide examples and expect the
system to make sense of a new example that is hasn’t seen yet.
-> fundamentally, supervised learning is function approximation

lOMoARcPSD|36771882
Squares are called nodes in the decision trees, and the

nodes are questions we can ask.
The lines are edges, they represent values
The outcomes are called leaves
-> this is how we can make a decision
(Classification learning)
Artificial neural networks (another method)
- networks of interconnected units

- Connections have a certain weight
- In a feedforward network, activation propagates from
inputs units to output units through hidden units
How do we determine the weights? Supervised learning
-> to be more specific the back propagation of error is

used (used for adjusting network weights)
• Deep networks allow for hierarchical representation

• Together with convolution, one of the causes of the success of deep networks
Supervised learning: regression
- classification deals with discrete outputs (labels)

- Regression deals with continuous (real-valued) outputs
- overparameterzing a model leads to overfitting, decreasing training set error at the expense of
generalisability
Instance based learning:
Unsupervised learning:
- clustering
4. Cognitive robotics
Robots are an embodied computer, it has a body that moves around
- semi autonomous physical agent
3 primary categories:

lOMoARcPSD|36771882
1. Manipulators
2. Mobile robots
3. Humanoid robots
Robots also have sensors and effectors

sensor = allow robots to perceive the environment
effectors = the means by which robots move and change body configuration
- humanoids tend to have force and torque sensors in effectors
The science of psychology is founded on inverse modelling: given a set of observations

(behavior), infer the mechanisms causing the behaviour
This is often fundamentally impossible (inverse problem): there are always different mechanism
with identical behavior
When we analyse a mechanism, we tend to overestimate its complexity
So lets work the other way around: by building humans instead of analysing them
5. Reinforcement learning
3. Reinforcement learning
The goal is to maximise reward

The focus is on the interaction between agent and
environment
- agent selects actions
- Environment reacts with evaluative feedback
- Sequence : state, action, reward, state, action,
…. (SARSA)
Markov decision process:

lOMoARcPSD|36771882
Markov property: the conditional probability distribution for the system at the next time step
depends only on the current state
-> the effects of actions only depend on the current state, not the prior history (how the agent got
there)
Operant conditioning :
Law of effect (Thorndike 1944) : action leads to an

outcome
Learning: updating your predictions
* occasionally performing a random action (e-greedy action selection) can improve performance
in the long run
Monte Carlo RL = learning only from experience

lOMoARcPSD|36771882
6. Applications of AI
Dopamine can be used as a teaching signal (prediction error). Strong evidence for a reinforcement
learning mechanism in animals and humans
7. Q & A
Deep reinforcement learning : Alpha Go is the best example
Neural networks and reinforcement = deep reinforcement learning

lOMoARcPSD|36771882
Practice exam 17 November 2013, Questions
Imperative Programming (Rijksuniversiteit Groningen)

lOMoARcPSD|36771882
Answers Exam Imperative Programming

7 November 2013, 14:00-17:00h
Exercise 1: Assignments (20 points)
For each wrong answer 4 points are subtracted. In case of 5 or more wrong answers, the score is 0 points.
1.1 ANSWER B 1.4 ANSWER C
/* x == X */ /* y + z > 4 */
/* 42*x + 1 == 42*X + 1*/ /* z + 1 + y > 5 */
x = 42*x + 21; x = z + 1;
/* x == 42*X + 21 */ /* x + y > 5 */
y = x + y;
/* y > 5 */
1.2 ANSWER C 1.5 ANSWER B

/* x == 42*X + 21 */ /* x == X, y == Y */
/* x-21 == 42*X */ /* x + y == X + Y, y == Y */
/* (x-21)/42 == X */ x = x + y;
x = (x - 21)/42; /* x == X + Y, y == Y */
/* x == X */ /* x == X + Y, 2*x - y == 2*X + Y */
y = 2*x - y;
/* x == X + Y, y == 2*X + Y */
/* y - 2*x == -Y, y == 2*X + Y */
x = y - 2*x;
/* x == -Y, y == 2*X + Y */
/* x == -Y, x + y == 2*X */
y = x + y;
/* x == -Y, y == 2*X */
1.3 ANSWER B 1.6 ANSWER A

/* x == y*y */ /* x == X, y == X + Y, z == X + Y + Z */
/* x == (y+1-1)*(y+1-1) */ /* x == X, y == X + Y, z - y == Z */
y = y + 1; z = z - y;
/* x == (y-1)*(y-1) */ /* x == X, y == X + Y, z == Z */
/* x == y*y - 2*y + 1 */ /* x == X, y - x == Y, z == Z */
/* x + 2*y - 1 == y*y */ y = y - x;
x = x + 2*y - 1; /* x == X, y == Y, z == Z */
/* x == y*y */ /* x - z == X - Z, y == Y, z == Z */
x = x - z;
/* x == X - Z, y == Y, z == Z */

lOMoARcPSD|36771882
Exercise 2: Find the 5 errors (10 points)
Each deteced error + correction is worth 2 points.
1 void swap(int i, int j) {

2 int h;
3 h = arr[i];
4 arr[i] = arr[j];
5 arr[j] = h;
6 }
7
8 int partition(int length, int arr[]) {
9 int left, right, pivot;
10 left = 0;
11 right = length;
12 pivot = arr[0];
13 while (left < right) {
14 while ((left < right) && (arr[left] <= pivot)) {
15 left++;
16 }
17 while ((left < right) && (pivot <= arr[right-1])) {
18 right--;
19 }
20 if (left < right) {
21 /* (arr[left] > pivot) && (arr[right-1] <= pivot) : swap */
22 right--;
23 swap(left, right, arr);
24 left++;
25 }
26 }
27 /* put pivot in right location: swap(0,left-1,arr) */
28 left--;
29 arr[0] = arr[left];
30 return left;
31 }
32
33 void quickSort(int length, int arr[]) {
34 if (length <= 1) {
35 /* empty or singleton array: nothing to sort */
36 return;
37 }
38 boundary = partition(length, arr);
39 /* recursively sort the two partitions */
40 quickSort(boundary, arr);
41 quickSort(length - boundary, &arr[boundary+1]);
42 }
1. line 1: missing parameter, solution: void swap(int i, int j, int arr[]) {

2. line 17: wrong test, solution: while ((left < right) && (pivot < arr[right-1])) {
3. between line 29 and 30: missing line, solution: arr[left] = pivot;
4. between line 33 and 34: declaration missing, solution: int boundary;
5. line 41: wrong array length, solution: quickSort(length - boundary - 1, &arr[boundary+1]);

lOMoARcPSD|36771882
Exercise 3: Time complexity (20 points)

For each wrong answer 5 points are subtracted. In case of 4 or more wrong answers, the score is 0 points.
1. int i = 0, j = N;
while (i < j) {
i++;
j/=2;
}
Because y is halved in each iteration, the right answer is (a) O(log N ).
2. int i, j, s = 0;
for (i=0; i < N; i++) {
for (j=i; j < N-i; j++) {
s += i + j
}
}
Because these are two nested loops, in which both loop variables are incremented by 1, the rigth answer is (e) O(N 2 ).
3. int i = 0, j = 0;
while (i < N) {
i += 2*j + 1;
j++;
}
√
In each iteration it is true that i==j*j, so the right answer is (b) O( N ).
4. int i = 1, j = N;
while (i < j) {
i += i;
j--;
}
Because i is doubled in each iteration, the right answer is (a) O(log N ).
5. int i, j, s = 0;
for (i=1; i < N; i*=3) {
for (j=1; j < i; j++) {
s += j;
}
}
The inner loop is linear, but the outer loop is logarithmic. Therefore, the right answer is (d) O(N log N ).
6. int i, j, s = 0, t = 0;
for (i=1; i < N; i++) {
s += i;
for (j=1; j < s; j*=2) {
t += j;
}
}
The outer loop is linear. In each iteration the value of s is approximately i*i/2. The inner loop is therefore O(log N ∗ N ) =
O(2 log N ) = O(log N ). Therefore, the right answer is (d) O(N log N ).

lOMoARcPSD|36771882
Exercise 4: Iterative algorithms (10+10 points)

(a) The integer 125874, and its double, 251748, contain exactly the same digits, but in a different order. There exists a non-zero positive integer
x such that 2*x, 3*x, 4*x, 5*x and 6*x all contain the same digits as x. Write a program that computes this number x. [Note: The number
is less than the maximum integer/6, so you do not need to worry about integer overflow]
Answer:
#include <stdio.h>
#include <stdlib.h>
void histogram(int n, int hist[10]) {

int i;
for (i=0; i < 10; i++) {
hist[i] = 0;
}
while (n > 0) {
hist[n%10]++;
n /= 10;
}
}
int equalHistograms(int hist1[10], int hist2[10]) {

int i;
for (i=0; i < 10; i++) {
if (hist1[i] != hist2[i]) {
return 0;
}
}
return 1;
}
int main(int argc, char *argv[]) {

int found=0, i, x=1, dig[10], dig2[10];
while (!found) {
histogram(x, dig);
for (i=2; i < 7; i++) {
histogram(i*x, dig2);
if (!equalHistograms(dig, dig2)) {
break;
}
}
if (i == 7) {
printf("%d %d %d %d %d %d\n", x, 2*x, 3*x, 4*x, 5*x, 6*x);
break;
}
x++;
}
return 0;
}
(b) Given is the declaration of some square 2-dimensional array: int square[N][N];
You may assume that the array is already filled with data. Write a program fragment that determines whether the array is a Latin square. This
means that each row and each column must contain the values 1, 2, ..., N with no repeats. The time complexity of your solution must
not exceed O(N 2 ).
int row, col, present[N];

int islatin = 1;
for (row=0; (row < N) && islatin; row++) {
for (col=0; col < N; col++) {
present[col] = 0;
}
if ((square[row][col] < 1) || (square[row][col] > N)) {

lOMoARcPSD|36771882
islatin = 0;
} else {
present[square[row][col]-1] = 1;
}
}
islatin = islatin && present[col];
}
}
for (col=0; (col < N) && islatin; col++) {

for (row=0; row < N; row++) {
present[row] = 0;
}
present[square[row][col]-1] = 1;
}
islatin = islatin && present[row];
}
}
/* the final answer is in the variable islatin */
Exercise 5: Recursive algorithms (5+15 points)
(a) Write a recursive function mul with the following prototype: int mul(int a, int b);
The function call mul(a, b) should return the value a*b. You are not allowed to use loops (only recursion), and you are only allowed to
use addition and subtraction (multiplication or division is not allowed). Note that a or b might be a negative number.
Answer:
int mul(int a, int b) {
if (b == 0) {
return 0;
}
if (b > 0) {
return a + mul(a, b-1);
}
/* b < 0 */
return mul(a, b+1) - a;
}
(b) Consider the integer sequence s=[1, 4, 2, 6, 7, 3, 7, 8, 3, 9, 0]. The sequence t=[1,6,7,9] can be obtained from
the sequence t by crossing out elements from the sequence s:
[1, 4X, 2 X, 6, 7, 3 X, 7 X, 8X, 3X, 9, 0 X]
In fact, there is another way:
[1, 4X, 2 X, 6, 7X, 3 X, 7, 8 X, 3X, 9, 0 X]
These are the only two ways that we can obtain t from s. Note that the sequence [1,2,4] can not be obtained from s by crossing out
elements, since the elements occur in s in the wrong order.
Write a recursive function that determines the number of ways that one sequence (an int array) can be obtained from another sequence by
crossing out elements.
Answer: this is a (simple) variation on the ’Maximum profit’ lab exercise.

int cntSubsequence(int lenA, int a[], int lenB, int b[]) {
if (lenA == 0) {
return 1;
}
if (lenA > lenB) {
return 0;
}
if (a[lenA-1] == b[lenB-1]) {
return cntSubsequence(lenA-1, a, lenB-1, b) + cntSubsequence(lenA, a, lenB-1, b);
}
return cntSubsequence(lenA, a, lenB-1, b);
}

lOMoARcPSD|36771882
Exam November 7, 2013, questions
Imperative Programming (Rijksuniversiteit Groningen)

lOMoARcPSD|36771882
Exam Imperative Programming

7 November 2013, 14:00-17:00h
• Write on each sheet of paper your name, student number and study (discipline). Number each sheet, and write on the first
sheet the total number of sheets.
• You can earn 90 points. You will get 10 points for free.
• Write neatly and carefully with a pen (do not use a pencil).
Exercise 1: Assignments (20 points)

For each of the following annotations determine which choice fits on the empty line (.....). The variables x, y and z are of type
int. Note that X, Y and Z (uppercase!) are specification-constants (so not program variables).
1.1 /* x == X */ 1.4 /* y + z > 4 */

..... x = z + 1; y = x + y;
/* x == 42*X + 21 */ .....
(a) x = x/42 - 21; (a) /* x + y + z > 5 */

(b) x = 42*x + 21; (b) /* y + z > 6 */
(c) x = (x - 21)/42; (c) /* y > 5 */
1.2 /* x == 42*X + 21 */ 1.5 /* x == X, y == Y */

..... x = x + y; y = 2*x - y; x = y - 2*x; y = x + y;
/* x == X */ .....
(a) x = x / 42 - 21; (a) /* x == Y, y == X */

(b) x = 42*x + 21; (b) /* x == -Y, y == 2*X */
(c) x = (x - 21)/42; (c) /* x == 2*Y, y == -X */
1.3 /* x == y*y */ 1.6 /* x == X, y == X + Y, z == X + Y + Z */

..... z = z - y; y = y - x; x = x - z;
/* x == y*y */ .....
(a) y = y - 1; x = x + 2*y + 1; (a) /* x == X-Z, y == Y, z == Z */

(b) y = y + 1; x = x + 2*y - 1; (b) /* x == X, y == Y-X, z == Z */
(c) x = y + 1; x = (y - 1)*(y-1); (c) /* x == X, y == Y, z == Z-Y */

lOMoARcPSD|36771882
Exercise 2: Find the 5 errors (10 points)
The following program fragment (it is not a complete program) is supposed to implement the quicksort algorithm. There are, however, five
errors in this implementation. Find them, and give of each error the line number and a correction.
1 void swap(int i, int j) {

2 int h;
3 h = arr[i];
4 arr[i] = arr[j];
5 arr[j] = h;
6 }
7
8 int partition(int length, int arr[]) {
9 int left, right, pivot;
10 left = 0;
11 right = length;
12 pivot = arr[0];
13 while (left < right) {
14 while ((left < right) && (arr[left] <= pivot)) {
15 left++;
16 }
17 while ((left < right) && (pivot <= arr[right-1])) {
18 right--;
19 }
20 if (left < right) {
21 /* (arr[left] > pivot) && (arr[right-1] <= pivot) : swap */
22 right--;
23 swap(left, right, arr);
24 left++;
25 }
26 }
27 /* put pivot in right location: swap(0,left-1,arr) */
28 left--;
29 arr[0] = arr[left];
30 return left;
31 }
32
33 void quickSort(int length, int arr[]) {
34 if (length <= 1) {
35 /* empty or singleton array: nothing to sort */
36 return;
37 }
38 boundary = partition(length, arr);
39 /* recursively sort the two partitions */
40 quickSort(boundary, arr);
41 quickSort(length - boundary, &arr[boundary+1]);
42 }

lOMoARcPSD|36771882
Exercise 3: Time complexity (20 points)

In this exercise the specification constant N is a non-zero natural number (i.e. N>0). Determine for each of the following program fragments
the sharpest upper limit for the number of calculation steps that the fragment performs in terms of N. For an algorithm that needs N steps, the
correct answer is therefore O(N ) and not O(N 2 ) as O(N ) is the sharpest upper limit.
1. int i = 0, j = N;
while (i < j) {
i++;
j/=2;
}
√
(a) O(log N ) (b) O( N ) (c) O(N ) (d) O(N log N ) (e) O(N 2 )
2. int i, j, s = 0;
for (i=0; i < N; i++) {
for (j=i; j < N-i; j++) {
s += i + j
}
}
√
3. int i = 0, j = 0;
while (i < N) {
i += 2*j + 1;
j++;
}
√
4. int i = 1, j = N;
while (i < j) {
i += i;
j--;
}
√
5. int i, j, s = 0;
for (i=1; i < N; i*=3) {
for (j=1; j < i; j++) {
s += j;
}
}
√
6. int i, j, s = 0, t = 0;
for (i=1; i < N; i++) {
s += i;
for (j=1; j < s; j*=2) {
t += j;
}
}
√

lOMoARcPSD|36771882
Exercise 4: Iterative algorithms (10+10 points)

(a) The integer 125874, and its double, 251748, contain exactly the same digits, but in a different order. There exists a non-zero positive integer
x such that 2*x, 3*x, 4*x, 5*x and 6*x all contain the same digits as x. Write a program that computes this number x. [Note: The number
is less than the maximum integer/6, so you do not need to worry about integer overflow]
(b) Given is the declaration of some square 2-dimensional array: int square[N][N];
You may assume that the array is already filled with data. Write a program fragment that determines whether the array is a Latin square. This
means that each row and each column must contain the values 1, 2, ..., N with no repeats. The time complexity of your solution must
not exceed O(N 2 ).
Exercise 5: Recursive algorithms (5+15 points)

(a) Write a recursive function mul with the following prototype: int mul(int a, int b);
The function call mul(a, b) should return the value a*b. You are not allowed to use loops (only recursion), and you are only allowed to
use addition and subtraction (multiplication or division is not allowed). Note that a or b might be a negative number.
(b) Consider the integer sequence s=[1, 4, 2, 6, 7, 3, 7, 8, 3, 9, 0]. The sequence t=[1,6,7,9] can be obtained from
the sequence t by crossing out elements from the sequence s:
[1, 4X, 2 X, 6, 7, 3 X, 7 X, 8X, 3X, 9, 0 X]
In fact, there is another way:
[1, 4X, 2 X, 6, 7X, 3 X, 7, 8 X, 3X, 9, 0 X]
These are the only two ways that we can obtain t from s. Note that the sequence [1,2,4] can not be obtained from s by crossing out
elements, since the elements occur in s in the wrong order.
Write a recursive function that determines the number of ways that one sequence (an int array) can be obtained from another sequence by
crossing out elements.

lOMoARcPSD|36771882
opdracht os jaar 2
Operating Systems (Universiteit Leiden)

lOMoARcPSD|36771882
Operating Systems 2023

Assignment 1: Implementation of a System Program
Deadline: Friday, March 10, 2023, 18:00
1 Introduction
In the first couple of lectures of the course, we have seen how to interface with the operating
system kernel through the use of system calls. We will explore this system call interface in this
first assignment, to learn how programs can interact with and request services from an operating
system kernel. Furthermore, we will learn how the kernel can signal events to a user-mode program.
The goal of the first assignment is to implement a system program that runs on POSIX systems
and uses POSIX system calls. This year, we will be writing our own, simple text-based shell. The
shell should print a command prompt and allow the user to enter a command. After entering this
command, the shell should properly execute the command, this includes supplying the provided
arguments to the program. The user can exit the shell using the exit command. The shell should
also have a functioning cd command to change the current working directory and the shell should
show the current working directory in the prompt.
On POSIX systems, commands such as ls and cat are commonly implemented as separate
system programs and are not part of the shell itself. Within this assignment, we will not implement
such a system program, but you can try for yourself that it is trivial to implement a simple version
of the ls command. As we have seen in the Programmeertechnieken course, composite commands
(pipelines) can be created using these simple system commands and the pipe character (|), in which
case the output of one command is sent to the input of another. As part of this assignment you will
also implement support for handling pipes, so that your shell is capable of executing commands
such as cat Makefile | grep gcc. The simple composite commands will be restricted to a single
pipe. Furthermore, input/output redirections for commands will not be implemented as part of
this assignment.
Finally, for achieving a grade beyond 8 you will need to implement a rudimentary form of job
control that can handle suspending processes with CTRL+Z, bringing suspended processes to the
foreground or background using the fg and bg commands, and listing currently active jobs with
a jobs command.
2 Specification
The assignment is to implement a shell program that conforms to the specification given in this sec-
tion. The program may be written in C or C++. Do note that you will have to use POSIX system
calls, which are C functions that commonly expect C-style strings (!), even if you are programming
your shell in C++. Your program should adhere to the following design specifications:
❼ Print a command prompt that also displays the current working directory.
❼ Allow the user to enter commands and execute these commands.
❼ The entered command string must be tokenized into an array of strings by removing the space
delimiters. Also delimiters consisting of more than one space must be handled correctly.
❼ Implement exit (to exit the shell) and cd (to change the current working directory) as
built-in commands. The cd should display errors if necessary.
❼ You must write a routine yourself to perform a search of the executable. This routine should
only be used in case the name of the specified executable is not preceded by an absolute
or relative path. You are not allowed to use execlp or execvp which automate this path
search. Do not use access.
Initially, you can add a hard-coded array of standard locations to your program (e.g. ./,
/usr/bin, /bin and /usr/local/bin), which will be searched.
As a second step, read and parse the PATH environment variable (use getenv). This variable
is a :-separated list of paths to search.

lOMoARcPSD|36771882
❼ Display an appropriate error if a requested command cannot be found or is not executable.
❼ Your program must be capable of executing commands and correctly pass the provided
arguments to this command. This must be achieved using fork, execv, etc. system calls
and not a higher level API.
❼ Execute commands that contain a pipe character by starting two new processes that are
interconnected with a pipe. Your shell should be able to handle data streams of arbitrary
length. In case the command contains more than one pipe character, simply log an error.
Note that in order to simplify implementation you only have to deal with the case that
the pipe character is separated by spaces, so the tokenizer you have to implement already
creates a separate token for the pipe character. For instance a command of the form cat
Makefile|wc -l does not have to be handled correctly by your program.
❼ A Makefile should be included to build the software. The Makefile should be of decent
quality and should include a clean target. For a short tutorial on writing Makefiles, we refer
to the slides of the course Programmeertechnieken.
The rudimentary form of job control to be implemented consists of the following:
❼ Support a maximum number of jobs (say 16). Maintain the jobs using a data structure (e.g.
an array). If the user attempts to start a new job when the maximum number of jobs has
already been reached, simply refuse and output an error.
❼ Jobs are numbered. When a new job is started the smallest unused job number is assigned.
❼ The current job needs to be maintained using a stack. The job launched last is the current
job. Do note that the job number of the current job may be smaller than the maximum job
number in use.
❼ New jobs need to be started in a new progress group for signal handling to behave well (see
setpgrp and setpgid).
❼ By suffixing a command with & the job is sent to the background upon startup (e.g.
xclock &).
❼ Pressing CTRL+Z will suspend the current job on the foreground. This requires SIGTSTP to
be handled and SIGSTOP to be sent to the current process.
❼ Pressing CTRL+C will terminate the current job on the foreground. But the shell must remain
active! This requires SIGINT to be handled.
❼ fg should bring the current process to the foreground. fg 4 will bring job number 4 to the
foreground. A process (group) can be resumed by sending it the SIGCONT signal.
❼ bg should bring the current process to the background. bg 3 will bring job number 3 to the
background.
❼ jobs should list all active (running and suspended) jobs.
❼ Background jobs that are terminated should be cleaned up properly. To do so, you need to
implement a SIGCHLD signal handler.
If in doubt, try out the features in an existing shell such as bash or zsh to get an idea how they
should function.

lOMoARcPSD|36771882
3 Submission
You may work in teams of at most 2 persons. Your submission should consist of the source code of
the implemented system program and a Makefile to build the program. Make sure all files contain
your names and student IDs. Put all files to deliver in a separate directory (e.g. assignment1)
and remove any object files, binaries and other unrelated files. Finally create a gzipped tar file of
this directory:
tar -czvf assignment1-sXXXXXXX-sYYYYYYY.tar.gz assignment1/
Substitute XXXXXXX and YYYYYYY with your student IDs. Submit the tar-archive through the
BrightSpace submission site. Also note your names and student IDs in the text box in the sub-
mission website. Please, ensure only one team member submits the assignment, such that there is
a single submission per team!
Deadline: Friday, March 10, 18:00.
Notes:
❼ For those who need the weekend to finalize things: BrightSpace submission is open until
Sunday, March 12, 23:59. After this time, submissions will be considered late. Note that no
questions will be answered on the forum and mailing list after Friday 18:00.
❼ All source code that is submitted will be subjected to automatic plagiarism checks. Cases
of plagiarism will be reported to the board of examiners.
❼ As with all other course work, keep assignment solutions to yourself. Do not post the code
on public Git or code snippet repositories where it can be found by other students.
❼ In case you develop your shell on a macOS system (or Windows Subsystem for Linux), make
sure to also test it on a Linux-system before handing in! Preferably test on the university
Linux computers before handing in. In the case of disputes, the university Linux installation
is used as reference.
❼ We may always invite teams to elaborate on their submission in an interview in case parts
of the source code need further explanation.
4 Assessment
The maximum grade that can be obtained for this assignment is 10. The points are distributed
as follows:
❼ [1.0 out of 10] Code quality

❼ [2.5 out of 10] Command input handling & built-in cd and exit commands
❼ [2.0 out of 10] Path handling / path search
❼ [1.0 out of 10] Execution of simple commands
❼ [1.5 out of 10] Execution of commands including pipes
❼ [2.0 out of 10] Job control implementation
For code quality the following is considered: good structure, consistent indentation, presence and
quality of Makefile, comments where these are required.
Error handling and correct memory handling are considered for each of the different components.
5 Approach
The key to success is to implement the different features step by step and to not try to implement
everything at once. So, start with the bare minimum, thoroughly test it and only after that move
on to add the next feature. For example, the first steps could be:

lOMoARcPSD|36771882
1. Write a couple of functions to read commands to be executed from the terminal and properly
tokenize these commands into argument vectors. Set up these argument vectors such that
these can later be passed to execv().
2. Write the functions required to find the binary of the command to be executed. So, you
want to write a routine that turns ls into the full path /bin/ls (or /usr/bin/ls depending
on your operating system).
3. Write a toy example program that starts another program using fork(), execv(), wait().
4. Now, incorporate the functions you have written for command line parsing and path search
into the toy example program.
5. Implement the exit and cd commands.
6. Implement pipelines.
7. and so on ...
6 Working with the POSIX API

You will have to use C library functions to accomplish the various tasks. Some of these library
functions are wrappers around actual system calls (POSIX API), which are traps to the operating
system kernel (e.g. fork and execve). In this section we give some hints and advice on dealing
with C library functions in general, explain how to find more information about system calls and
give some hints on which system calls to use in the assignment.
6.1 Dealing with C functions

Many of the library functions that you will have to use to complete this assignment are C functions.
You can call C functions from a C++ program just fine, however, there are some things to
keep in mind. Most notably, C functions do not support C++ reference parameters and cannot
manipulate C++ data types such as STL containers and C++ strings. The latter is a problem
that you will likely come across if you decide to implement this assignment in C++: you cannot
pass std::string as argument to C library functions expecting strings, but must convert these
to char * (for instance using the .c str() method).
About every function in the standard C library is documented in the form of a manual (man)
page. For example, to learn more about the C function scanf use the command man scanf in
a terminal. The manual pages about library functions are always in section 3: man printf will
give you information about the shell command, but man 3 printf about the C library function.
Similarly, system calls are in section 2. man 2 fork will display the manual page on the fork
system call.
If you are writing a C++ program and the manual page tells you to include either <stdio.h>,
<stdlib.h> or <string.h>, then make sure to include the C++ safe variants instead: <cstdio>,
<cstdlib> or <cstring>.
6.2 Writing the entire program in C

You may implement this assignment in either C or C++. Because you will have to interface with
POSIX functions, which are C functions that expect C-style strings, it might be wise to write the
entire assignment in C. (Other than that, writing a program in pure C is also a fun exercise!).
If you choose to write the entire program in C, make sure to compile your code using a C and
not a C++ compiler (use .c as extension and not .cc or .cpp). When using plain C, you cannot
use C++ features such as classes, virtual methods and cout and cin for I/O. Instead of using cin
and cout, you can use the printf and scanf functions. You need to include <stdio.h> for these
functions.
To dynamically allocate memory, use the malloc and free functions instead of new and delete.

lOMoARcPSD|36771882
6.3 Overview of useful system calls

Reading and parsing user input. There are several ways to obtain input from the user. When
using plain C, we suggest to use fgets. The command string entered by the user will have to be
split (or tokenized) into an argument vector using the space character as delimiter. You can do
this tokenization manually, or use a provided string manipulation function such as strsep. Make
sure to properly deal with delimiters consisting of multiple spaces. If you are writing the program
in C++ it is fine to use the string class for tokenization.
Executing a program. To start a new process and execute a program the fork and execve
system calls should be all you need (like discussed in the lectures). Detailed information on these
calls can also be found using man (e.g. man 2 execve). You may also consider using the front-end
function execv described in man section 3.
When working with execv note that the first item in the argument vector indicates the program
to run. If this item does not contain a slash, it is not a relative or absolute path and you must
find out where this program is located in the file system. To do so, concatenate the name of the
program to each of the paths in the hard-coded path array and use, for example, the stat call to
test whether the file exists1 . This result is used as first argument to the execv function, note that
the first item of the argument vector must be left untouched.
Once a child process terminates it becomes a zombie. The parent must clean up such zombie
processes using the wait or waitpid functions. These calls also allow you to collect the exit code
of the child process.
Creating a pipe. To create a pipe you have to use the pipe system call. You need to pass an
array of two integers as an argument, which will be filled with the file descriptors of the input and
output end of the pipe. To reconnect standard input and output to the pipe, you will also need
the close and dup system calls. Also useful are the defines STDIN_FILENO and STDOUT_FILENO
that represent the file descriptors for stdin and stdout respectively.
Working with POSIX signals. You will need to implement a number of POSIX signal han-
dlers. Signal handlers are best installed using the sigaction function (see man 2 sigaction).
Initialize a sigaction structure and call the sigaction function for the appropriate signal num-
ber (for example SIGCHLD). General information on POSIX signals can be found in section 7 of
the manual: man 7 signal.
You can also send signals yourself. This is accomplished using the kill system call (man 2 kill)
or killpg to send the signal to a process group.
A final warning concerns the possibility of race conditions. Any signal handler that you install
may be invoked at any time. For example, while your program is running a function to manipulate
your jobs data structure, a signal handler may be invoked interrupting the current function. In
case this signal handler will update the same jobs data structure, the data structure will most
likely be corrupted! This must be avoided! Using sigaction you can block signals from being
delivered while a certain signal is being handled. Similarly, you may want to block signals while
modifying your jobs data structure from outside a signal handler. You can temporarily block
certain signals from being delivered using the sigprocmask call.
1 It is true that the state of the file system can change between the call to stat and execv, so checking the return
value of execv for errors remains important!

lOMoARcPSD|36771882
Exercises 8v2 - exericses
Foundations of Computer Science (Universiteit Leiden)

lOMoARcPSD|36771882
LIACS · Graphs II 17.11.23
54) Suppose that a undirected graph G contains two distinct simple paths
from a vertex u to a vertex v. Show that G has a cycle.
55) Given a connected undirected graph G = (V, E) without cycles (hence

a tree), with at least one edge.
a. Prove: G has at least one vertex of degree 1.
b. Using a. and induction on the number of vertices, prove that |E| =
|V | − 1.
56) a. G = (V, E) is an undirected cycle-free graph with c components, a

forest with c trees. Prove that |V | = |E| + c.
b. Show that Theorem 8.6 (ii) ⇒ (iii) can be easily derived using a..
57) Given an undirected graph G with more than 1 vertex.

a. Prove: if G is maximal acyclic, then G is a tree.
Note that G is acyclic, so we only need to show that G is connected.
b. Prove: if G is minimally connected, then G is a tree.
Note that G is connected, so we only need to show that G has no
cycles.
Reminder:
maximal acyclic: after adding an edge, a cycle is created;
minimally connected: after removing an edge, the result is no longer
connected.
58) a. The undirected graphs G1 and G3 below are isomorphic. Give an
isomorphism between G1 and G3 .
b. G2 is not isomorphic to the other two graphs. Give a simple argu-
ment why this is not the case.
0
4 5 6 b
4 1
a f c
5
3 2 1 2 3 d e
G1 G2 G3
59) Given the undirected graph G:

lOMoARcPSD|36771882
LIACS · Graphs II 17.11.23
1 2
5 6
7
a. Is G bipartite? Justify your answer.

b. Does G have an Eulerian circuit? If so, give one; if not, why not?
c. Does G have an Eulerian trail? If so, give one, if not why not?
d. G has no Hamiltonian cycle. Explain why not.
60) a. Draw the five non-isomorphic connected undirected graphs with five
vertices and five edges.
b. Indicate for each of the graphs in a. which are bipartite and which
are not. If a graph is bipartite, give a correct division of the vertices;
if not, please explain why not.
c. Do the graphs K2,4 (complete bipartite) and K6 (complete) have an
Eulerian circuit? If so, draw the graph, number the vertices and give
an Eulerian circuit; if not, indicate why not.
d. How many 5-regular graphs are there with 7 vertices? And how many
complete bipartite graphs with 7 vertices? Justify your answer and
draw them all.
61) Prove using mathematical induction that for all n ≥ 1 the number of
n (n − 1)
edges ℓ(n) in the complete graph Kn is .
2
Give the base case, formulate the induction hypothesis, and prove
the induction step.

lOMoARcPSD|36771882
Midterm 21 Oktober 2019, vragen

lOMoARcPSD|36771882
Fundamentele Informatica 1 & Foundations of Computer Science

Mid-term exam 21/10/2019, 11:00-13:00.
Kasper Dokter and Vedran Dunjko
The exam consists of 5 questions (1 page).
If you score x points, your grade equals x/5.
Mark clearly each question that you are answering.
Important: write your name, student id and the course name on your exam sheet.
Question 1. 10 P.
Draw the Venn diagrams for the following pairs of sets; determine the relationship of the pair: i.e. are they
equal, is one a subset of the other, are they disjoint, or incomparable (none of the previous relationships).
1. (A ⊕ B)c and Ac ⊕ B
2. (A ⊕ B) ∪ C and (A ∪ C) ⊕ (B ∪ C)
Hint: Draw a separate Venn diagram for each of the four expressions, and compare the shaded regions.
Question 2. 10 P.
Use the rules (laws/axioms) of set algebra to simplify the following expression as much as possible:
((B c ∪ A)c ∪ B) ∪ B.
Question 3. 6 P.
Consider the following binary relation R defined over the set {a, b, c, d}:
R = {(a, a), (a, b), (a, d), (b, b), (b, d), (d, a), (d, b), (d, d), (c, c)}.
Check if this relation is 1) reflexive; 2) symmetric; 3) antisymmetric; 4) transitive; 5) an equivalence relation;

6) a partial order. Motivate your answer, and in case the relation does not satisfy the property, provide a
counterexample.
Question 4. 12 P.
How many numbers from {1, . . . , 300} are not divisible by 2, 3 nor 5 (so by none of them)? Find the answer
by using the principle of inclusion and exclusion. Use a Venn diagram to illustrate the relevant sets and their
relationships.
Hints: For p ∈ N+ , let Dp = {k ∈ {1, . . . , 300} | p divides k} be the set of numbers between 1 and 300 that
are divisible by the number p. Then, the number of integers in {1, . . . , 300} that are divisible by either 2, 3 or
5 equals |D2 ∪ D3 ∪ D5 | (where |A| denotes the number of elements of A, i.e. the cardinality of A).
Note that |Dp | = 300
p , if p divides 300, and Dp ∩ Dq = Dp×q , if p and q are relatively prime, that is have no
common divisors. Specially, for p, q ∈ {2, 3, 5} and p 6= q, a number is divisible by p and q if and only if it is a
multiple of p × q.
Question 5. 12 P.
Let A = {1, 2, 3, 4} and B = {a, b, c, d}.
1. It is possible to find functions f : A → B, for which there exists a subset V ⊆ A such that f −1 (f (V )) 6= V .
Specify one such function, by giving all the pairs (x, f (x)) (so the set {(x, f (x)) | x ∈ A}) and also give
the corresponding set V ⊆ A.
2. It is possible to find functions g : A → B, for which there exists a subset W ⊆ B such that g(g −1 (W )) 6=
W . Specify one such function, by giving all the pairs (x, g(x)) (so the set {(x, g(x)) | x ∈ A}) and also
give the corresponding set W ⊆ B.
3. For the f and g you defined, determine if they are injective and or surjective.
Note that a function has to be total; it has a value for all the elements of its domain.

lOMoARcPSD|36771882
Exercises 9'

lOMoARcPSD|36771882
LIACS · Trees 24.11.23
62) a. Draw all (undirected) trees with exactly six vertices.

Hint: there are six.
b. How many rooted trees (directed) with six vertices are there? Explain
your answer.
63) Consider the ordered rooted tree T below.
B F J
C D E G H K
L M
a. (i) Give the leaves of this tree. (ii) List the children of node B. (iii)
What are the ancestors of node M ? (iv) Give all the nodes at level
2, from left to right. (v) What is the depth of the tree?
b. Draw the corresponding binary tree T ′ [in left-child right-sibling rep-
resentation].
c. Given an ordered rooted tree T with root R and subtrees T1 , T2 , . . . , TM .
A postorder traversal of T is defined as follows:
(1) Traverse the subtrees T1 , T2 , . . . , TM (in that order) in postorder.
(2) Visit the root R.
Let T be the ordered rooted tree above. Traverse T in postorder and
list the contents of the nodes in that order.
d. Give a recursive definition for the preorder traversal of an ordered
rooted tree T and determine the preorder ordering of the nodes for
the example tree above.
e. Consider the binary tree T ′ from b. Perform a preorder, postorder
and symmetric (also called inorder) traversal of T ′ and list the nodes
in each of these three orderings. Compare these traversals with the
preorder and postorder traversal of the original ordered rooted tree T .
64) a. Draw the five binary trees with three nodes.

b. If tn is the number of binary
Pn trees with n nodes, then the recurrence
relation holds: tn+1 = k=0 tk tn−k , with t0 = 1. Prove this.
c. How many binary trees with six nodes are there?
65) Given the following array of nodes: 48, 29, 59, 19, 43, 52, 100, 64, 49,
56, 45, 8, 99, 90, 20, 55, 84, 18, reconstruct the complete binary tree.

lOMoARcPSD|36771882
LIACS · Trees 24.11.23
66) Consider the trees T1 , T2 , T3 .

A A A
B C B C C B
D D D
T1 T2 T3
Identify those which represent the same:
a. rooted tree
b. ordered rooted tree
c. binary tree.
From Schaum, exercise 10.4.
67) a. The nodes of a binary tree T are given in pre-order as follows:
A, B, D, E, G, K, C, F, H, I. The symmetric ordering of the nodes of
T is: D, B, K, G, E, A, C, H, F, I. Reconstruct the binary tree T from
this and draw it. Explain clearly how you arrived at your answer.
b. From pre-order and post-order we cannot always reconstruct the
tree. Show this by drawing different binary trees for which a pre-
order traversal yields A, B, C, D, and a post-order traversal returns
D, C, B, A.
(3x − 5z)4
68) Consider the algebraic expression: E = .
a(2b + c2 )
a. Draw the corresponding ordered rooted tree T , using an arrow (↑)
for exponentiation, an asterisk (*) for multiplication, and a slash (/)
for division.
b. Use T to rewrite E in Polish prefix notation (pre-order).
c. Give the post-order and symmetric notation (postfix, respectively
infix).
d. From the prefix notation, reconstruct the expression tree from a.
69) a. Place a full set of parentheses in the expression 1 − 2 − 3 − 4.

In how many ways can you do this?
b. Idem for 1 − 2 − 3 − 4 − 5 − 6 − 7.

CSC312 Automat Theory
Assignment # 2.
Issue Date: 11-11-2013
Due Date: 19-11-2013 (Tuesday)
FA1 FA2
Q.1. Find DFA corresponding to FA 1 + FA2

Q.2. Find DFA corresponding to FA 2.FA1
Q.3. Find closure of the above given FA 2
You should observe the following important points for assignment

submission.
 All the assignments should be hand written; typed assignments will not be
accepted.
 Try to solve by yourself, do not copy. I have the right to cancel or deduct marks
of copy assignments.
 The title page should be according to given bellow template, it can be hand
written or typed.
Assignment # _______
CSC 312 Automata Theory
Registration No. ______________

Name: ________________
Section :_______________
Due Date: ______________
Previously most students didn’t follow these instructions I did not deduct marks for
this but this time I will deduct the marks for not following the instructions.
2G1505 Automata Theory
Solutions to Exam of: Dilian Gurov
16 October 2002, 14.oo - 19.oo KTH/IMIT/LECS
1. Give a DFA for the language defined by the regular expression a∗ a, and another one for a(ba)∗ . The 5p
union of the two DFAs defines a non-deterministic FA for the language a∗ a + a(ba)∗ .
(a) Apply the subset construction to this NFA to produce a DFA for this language. Omit the
inaccessible states. Draw the graph of the resulting DFA.
(b) Is this DFA minimal? If not, which states are equivalent?
..
Solution: The graphs to appear later. ^
2. Show that regular languages are closed under doubling: if language L is regular, then so is also 5p
∆ ∆
the language L2 = {two x | x ∈ L}, where string doubling is defined inductively by two = and
∆
two ax = aa · (two x).
Solution: Here is a standard solution using finite automata; alternative solutions exist using regular
expressions or homomorphisms.
Let L be regular. Then there is an NFA N = (QN , Σ, ∆N , SN , FN ) such that L(N ) = L. Define
a a
another NFA, N2 , as follows: start with N and replace every edge q −→ q 0 with two edges q −→ q 00
00 a 0 00
and q −→ q by inserting (for each edge!) a new state q . We can formalize this idea by taking as
states of N2 the states of N plus the edges of N , the latter represented for example as the set of triples
0 ) | q ∈ Q , q 0 ∈ ∆ (q , a)}. So, we can define N as follows:
{(qN , a, qN N N N N N 2
∆ 0 ) | q ∈ Q , q 0 ∈ ∆ (q , a)}
• QN2 = QN ∪ {(qN , a, qN N N N N N
• ∆N2 is given by the two defining equations:
∆ 0 ) | q 0 ∈ ∆ (q , a)} and
∆N2 (qN , a) = QN ∪ {(qN , a, qN N N N
∆
0 ), a) = if a = b then {q 0 } else ∅
∆N2 ((qN , b, qN N
∆
• SN2 = SN
∆
• FN 2 = FN
It is straightforward to show that, for the so constructed NFA, L(N2 ) = L2 , thus implying that L2 is
regular. Hence, regular languages are closed under doubling.
3. Consider the language L defined by the regular expression (a∗ + ba)∗ . Describe the equivalence classes 5p
of {a, b}∗ w.r.t. the Myhill–Nerode relation ≡L defined by: (cf. equation (16.1) on page 97)
∆
x1 ≡L x2 ⇐⇒ ∀y ∈ Σ∗ .(x1 · y ∈ L ⇔ x2 · y ∈ L)
Present these equivalence classes through regular expressions. Use ≡L to construct a minimal automa-
ton M≡L (cf. page 91) for the language L, and draw the graph of the automaton.
Solution: The states of the quotient automaton are:
Σ∗/≡L = {L((a + ba)∗ ), L((a + ba)∗ b), L((a + ba)∗ bb(a + b)∗ )}
The graph to appear later.
4. Consider the language: 15p
n o
∆
L = x · y ∈ {a, b}+ | y = rev x
where rev x denotes the reverse string of x (cf. HW 2.2, page 302).
(a) Use the Pumping Lemma to prove that L is not regular.

Solution: As a game with the Demon (cf. Lecture 11):
• Demon picks k > 0.
• We pick for example x = , y = ak , z = bbak , and we have xyz = ak bbak ∈ L and |y| ≥ k.
• Demon picks uvw = y = ak , v 6= .
• We pick for example i = 0.
Then xuv i wz = uwz = aj bbak for some j < k, and hence xuv i wz 6∈ A. We have a winning
strategy, and L is therefore not regular.
(b) Give a context–free grammar G for L.
Solution: S → aa | bb | aSa | bSb
(c) Prove your grammar correct (cf. Lecture 20): that is, prove L = L(G).
Solution: We have to prove:
∗
∀x ∈ {a, b}+ . (S →G x ⇔ x ∈ L)
We show the two directions of the equivalence separately.
(⇒) By induction on the length of the derivation of x.
0
Basis Holds vacuously, since S →G x is false: x = S is impossible since S 6∈ {a, b}+ .
n
Induction Step Assume x0 ∈ L for all x0 such that S →G x0 (induction hypothesis).
n+1 1 n
Let S → G x. Then, we must have S →G γ and γ →G x for some γ ∈ {a, b, S}+ . But then
γ can only be aa or bb or aSa or bSb. The first two cases imply n = 0 and x = γ, and then
n
obviously x ∈ L. In the case γ = aSa, it must be that x = ax0 a and S →G x0 for some x0 .
0 0
From the induction hypothesis, we have x ∈ L. But x = ax a, and therefore also x ∈ L.
The case γ = bSb is similar.
(⇐) By induction on |x|, which is even and positive.
1
Basis |x| = 2, then x ∈ L implies that x is either aa or bb. In both cases S →G x and
∗
therefore S →G x.
∗
Induction Step Assume S →G x0 for all x0 ∈ L such that |x0 | = n (induction hypothesis).
Let |x| = n + 2, and let x ∈ L. It must be that either x = ax0 a or x = bx0 b for some x0
∗
such that x0 ∈ L and |x0 | = n. From the induction hypothesis, S →G x0 . Then, in the case
∗ 1 ∗
x = ax0 a we also have aSa →G ax0 a = x, and since S →G aSa, then S →G x.
The case x = bx0 b is similar.
(d) Give an NPDA for L.
Solution: One possibility is to put G in GNF:
S → aA | bB | aSA | bSB
A→a
B→b
and then construct the NPDA canonically (cf. Lecture 24):
∆
Q = {q}
∆
Σ = {a, b}
∆
Γ = {S, A, B}
a
hq, Si ,→ hq, SAi
a
hq, Si ,→ hq, Ai
b
∆ hq, Si ,→ hq, SBi
δ= b
hq, Si ,→ hq, Bi
a
hq, Ai ,→ hq, i
b
hq, Bi ,→ hq, i
∆
s=q
∆
⊥=S
5. Give a detailed description of a total Turing machine accepting the palindromes over {a, b}: that is, 5p
all strings x ∈ {a, b}∗ such that x = rev x.
Solution: We build a machine which repeatedly scans the tape from left to right, trying to match the
first input symbol (which is directly replaced by the blank symbol) with the last input symbol (also
directly replaced by the blank symbol).
Graph to appear later.
n is not decidable: othat is, that there is no total Turing machine MA accepting 5p
6. Argue that acceptance
∆
the language LA = M̂ ]x̂ | M accepts x , by reducing from the Halting problem.
Solution: A TM halts on input x if it either accepts x or otherwise rejects x. We use this observation
to show that the Halting problem (cf. Lecture 31) can be reduced to the above acceptance problem.
Assume that there is a total Turing machine MA accepting LA . We can then build a machine MR
which, on any input M̂ ]x̂, first swaps the values of t and r in M̂ (that is, swaps the accepting and
the rejecting states of M ), and then behaves exactly like MA . Hence MR is a total Turing machine
deciding rejection. We can now combine MA and MR to produce a total Turing machine MH deciding
the Halting problem: for example, on any input M̂ ]x̂, let MH first run as MA and accept if MA
accepts, but continue as MR if MA rejects. MH will thus accept M̂ ]x̂ if M halts on x, and will reject
M̂ ]x̂ otherwise.
But the Halting problem is undecidable, and therefore there is no total Turing machine MA accepting
LA . The acceptance problem is therefore undecidable.
Solutions to Exam of: Dilian Gurov
17 December 2003 KTH/IMIT/LECS
1. Convert the nondeterministic automaton given below to an equivalent deterministic one using the
subset construction. Omit inaccessible states. Draw the graph of the resulting DFA.
a b
→ q1 q1 , q 2 q3 F
q2 − q4 F
→ q3 q4 −
q4 − q1 , q 4
Solution: (given as a table)
a b
→ {q1 , q3 } {q1 , q2 , q4 } {q3 } F
{q1 , q2 , q4 } {q1 , q2 } {q1 , q3 , q4 } F
{q1 , q3 , q4 } {q1 , q2 , q4 } {q1 , q3 , q4 } F
{q1 , q2 } {q1 , q2 } {q3 , q4 } F
{q3 , q4 } {q4 } {q1 , q4 }
{q1 , q4 } {q1 , q2 } {q1 , q3 , q4 } F
{q4 } {} {q1 , q4 }
{q3 } {q4 } {}
{} {} {}
2. For the deterministic automaton given below, apply the minimization algorithm of Lecture 14 to
compute the equvalence classes of the collapsing relation ≈ defined in Lecture 13. Show clearly the
computation steps. List the equivalence classes, and apply the quotient construction to derive a
minimized automaton. Draw its graph.
a b
→ q0 q0 q1
q1 q2 q3
q2 q2 q3
q3 q2 q4 F
q4 q0 q1
Solution: (incomplete) After applying the minimization algorithm we obtain that q0 ≈ q4 and q1 ≈ q2 .
Thus we obtain the following minimized automaton (given as a table).
a b
→ {q0 , q4 } {q0 , q4 } {q1 , q2 }
{q1 , q2 } {q1 , q2 } {q3 }
{q3 } {q1 , q2 } {q0 , q4 } F
3. Let A ⊆ Σ∗ be a language. We define its prefix closure as:
pref A = {x ∈ Σ∗ | ∃y ∈ Σ∗ . x · y ∈ A}
Prove that regular languages are closed under prefixing: if language A is regular, then so is pref A.
Solution: Let A ⊆ Σ∗ be regular. Then there must be a DFA MA = (Q, Σ, δ, s, F ) such that
L(MA ) = A. Now, based on MA , define another automaton M = (Q, Σ, δ, s, F 0 ) so that:
n o
F 0 = q ∈ Q | ∃y ∈ Σ∗ . δ̂(q, y) ∈ F
We will show that this automaton accepts the language pref A, and hence that pref A is regular.
Claim. L(M ) = pref A
Proof.
x ∈ L(M ) ⇔ δ̂(s, x) ∈ F 0 {def. L(M )}

⇔ ∃y ∈ Σ∗ . δ̂(δ̂(s, x), y) ∈ F {def. F 0 }
⇔ ∃y ∈ Σ∗ . δ̂(s, x · y) ∈ F {HW 1.3, page 301}
⇔ ∃y ∈ Σ∗ . x · y ∈ A {L(MA ) = A}
⇔ x ∈ pref A {def. pref A}
4. Consider the language:

A = {x ∈ {a, b}∗ | ]a(x) < ]b(x)}
(a) Give a context–free grammar G for A. Explain your choice of productions.

Solution: There are many possible solutions. One way of looking at the strings of the language
is to devide these into the ones which have exactly one occurrence of b more than occurrences of
a, and those that have more. A string is in the first group exactly when it can be represented
as a string of the shape e1 · b · e2 , where e1 and e2 are strings with an equal number of a’s and
b’s. Thus, e1 and e2 can be produced by the grammar E → | aEb | bEa | EE. A string is in
the second group exactly when it is the concatenation of two strings of A. So we arrive at the
following grammar:
S → EbE | SS
E → | aEb | bEa | EE
(b) Construct an NPDA accepting A on empty stack. Explain its workings.
Solution: Again, there is a number of good solutions. One elegant solution using ε-transitions
(proposed by one of the students at the exam) is based on the observation that if we use the
”standard” productions for comparing occurrences:
a b
hq, ⊥i ,→ hq, A⊥i hq, ⊥i ,→ hq, B⊥i
a b
hq, Ai ,→ hq, AAi hq, Bi ,→ hq, BBi
a b
hq, Bi ,→ hq, εi hq, Ai ,→ hq, εi
then a string is in A exactly when after reading it the stack contains only B’s (on top of ⊥). Note
that there must be at least one such B. So, we can obtain the desired behaviour by adding two
more productions:
b
hq, ⊥i ,→ hq, Bi
ε
hq, Bi ,→ hq, εi
5. Apply the Pumping Lemma for context–free languages (as a game with the Demon) to show that the
language: n o
A = an bn aj | j ≤ n
is not context–free.
Solution:
– Demon picks an arbitrary k ≥ 0.

+ We pick z = ak bk ak which is in A.
– Demon picks u, v, w, x, y such that z = uvwxy, |vx| > 0, |vwx| ≤ k.
+ If vwx = al bm for some l, m ≥ 0, we pick i = 0. Otherwise we pick i = 2.
Since |vwx| ≤ k, vwx has either the shape al bm or bm al for some l, m such that l + m ≤ k. In the first
case xv 0 wx0 y must be of the shape ap bq ak for some p, q such that p + q < 2k, and thus is not in A.
In the second case, xv 2 wx2 y will either not be in L(a∗ b∗ a∗ ) at all, and thus not in A, or else xv 2 wx2 y
must be of the shape ak bp aq for some p, q such that p + q > 2k, and thus not in A. Hence, we win the
game in all cases, which shows that A is not context–free.
6. Give a detailed description (preferably as a graph) of a total Turing machine accepting the language:

n(n+1)
n
A= a b 2 |n≥0
Explain the underlying algorithm.

Solution (just a very brief sketch for now) We use the well–known equation ni=1 = n(n+1)
P
2 . We
proceed in rounds, in each round marking an a and then marking as many b’s as there are marked a’s
(which equals the number of the current round).
Examination Problems Dilian Gurov
with Selected Solutions KTH CSC
19 May 2006, 14oo - 19oo 08-790 81 98
Give solutions in English or Swedish, each problem beginning on a new sheet. Write your name
on all sheets. The maximal number of points is given for each problem. The course book and own
notes as well as reference material are admissible at the exam.
1. Convert the nondeterministic automaton given below to an equivalent deterministic one using the 2p
subset construction, textbook Lecture 6. Omit inaccessible states. Draw the graph of the resulting
DFA.
a b
→ q0 {q1 } {q2 }
q1 {q0 , q1 } {q0 }
q2 F ∅ {q1 , q2 }
Solution: Easy: has 8 states, and hence no inaccessible ones!
2. For the deterministic automaton given below, apply the minimization algorithm of Lecture 14 of the 4p
textbook to compute the equvalence classes of the collapsing relation ≈ defined in Lecture 13.
a b
→ q0 F q1 q3
q1 q2 q3
q2 F q5 q2
q3 q4 q1
q4 F q5 q4
q5 q5 q5
(a) Show clearly the computation steps (use tables).

(b) List the computed equivalence classes.
(c) Apply the quotient construction of Lecture 13 to derive the minimized automaton. Draw its
graph.
Solution: As a table:
a b
→ {q0 } F {q1 , q3 } {q1 , q3 }
{q1 , q3 } {q2 , q4 } {q1 , q3 }
{q2 , q4 } F {q5 } {q2 , q4 }
{q5 } {q5 } {q5 }
3. Recall the Myhill–Nerode Theorem, textbook Lecture 16, with the equivalence relation ≡A on strings 4p
defined in equation (16.1). The latter gives rise to the following technique for proving that the minimal
DFA for a given regular language A over Σ has at least k states:
Identify k strings x1 , . . . , xk over Σ, for which you can show that:

xi 6≡A xj whenever i 6= j.
Then ≡A has at least k equivalence classes, and hence the desired result.
Now, let m be an arbitrary but fixed even number. Consider the language B over {a, b} consisting of
all strings of length at least m which have an equal number of a’s and b’s in the last m positions. Use
m
the technique described above to show that the minimal DFA for language B has at least 2 2 states.
Hint: Consider the strings of length m 2.
Solution: Consider the set X of strings of length m 2 over {a, b}. Let x, y ∈ X so that x 6= y. Let
x0 , y 0 be the shortest suffices of x and y respectively, such that |x0 | = |y 0 | and x0 6= y 0 . Then obviously
]a(x0 ) 6= ]a(y 0 ). Now let z = ar bs , where r = m 0
2 − ]a(x ) and s = m − (|x | +
0 r). Then x · z ∈ B while
m m
0 0
y · z 6∈ B, and hence x 6≡B y . Since X has 2 2 elements, ≡B has at least 2 2 equivalence classes, and
m
therefore the minimal DFA for language B has at least 2 2 states.
4. A context–free grammar G = (N, Σ, P, S) is called strongly right–linear (or SRLG for short) if all 6p
its productions are of shape A → aB or A → . Prove that SRLGs generate precisely the regular
languages.
Hint: Define appropriate transformations between SRLGs and Finite Automata – one for each direc-
tion! – and prove that these transformations are language preserving. State and prove appropriate
lemmas where needed to structure the proofs.
Solution: In two parts: the first part shows that the languages generated by SRLGs are regular,
while the second shows that every regular language is the language of some SRLG.
def
a) Let G = (N, Σ, P, S) be a SRLG. Define the NFA NG = (N, Σ, ∆, {S} , F ) where we define
def def
∆(X, a) = {Y ∈ N | (X → aY ) ∈ P } and F = {X ∈ N | (X → ) ∈ P }. Then:
x ∈ L(NG ) ⇔ ˆ
∆({S} , x) ∩ F 6= ∅ {Def. L(N )}
⇔ {X ∈ N | S →∗G xX} ∩ F 6= ∅ {Lemma A}
⇔ ∃X ∈ N. (S →∗G xX ∧ X →G ) {Def. F }
⇔ S →+G x {Def. →∗G }
⇔ x ∈ L(G) {Def. L(G)}
So L(G) = L(NG ) and hence L(G) is regular. In the proof, Lemma A states that
ˆ
∆({Y } , x) = {X ∈ N | Y →∗G xX}
which is proved by induction on the structure of x as follows.

Base case. n o
ˆ
∆({Y } , ) = {Y } ˆ
Def. ∆
= {X ∈ N | Y →∗G X} {Def. SRLG}
Induction. Assume the Lemma holds for x (the ind. hyp.); we show that it then also holds for xa.
n o
ˆ
∆({Y } , xa) =
S
ˆ ∆(X, a) Def. ∆ˆ
SX∈∆({Y },x)
= X∈{X∈N |Y →∗ xX } ∆(X, a) {Ind. hyp.}
G
} {Z ∈ N | (X → aZ) ∈ P } {Def. ∆}
S
= X∈{X∈N |Y →∗G xX
= {X ∈ N | Y →∗G xaX} {Def. →∗G }
b) This part is similar to the previous one and is only sketched here. Let A be a regular language.
def
Then there is a DFA MA = (Q, Σ, δ, s, F ) such that L(MA ) = A. We define the SLRG GA =
def
(Q, Σ, P, s) where P = {q1 → aq2 | δ(q1 , a) = q2 } ∪ {q → | q ∈ F }. We then show x ∈ L(GA ) ⇔
x ∈ L(MA ) = A, the proof of which is best structured by proving and using Lemma B:
q1 →∗GA xq2 ⇔ δ̂(q1 , x) = q2
5. Recall the Chomsky–Schützenberger Theorem, textbook Supplementary Lecture G. Show how this 3p
Theorem applies to the context–free language PAL of even–length palindromes over {a, b}, by identi-
fying a suitable number n, a regular language R, and a homomorphism (renaming) h.
Solution: PAL is equal to the language h(PARENn ∩ R) for n = 2, R = L(([1 +[2 )∗ (]1 +]2 )∗ ) and h
renaming [1 and ]1 to a and [2 and ]2 to b.
6. Consider the language: n o 5p

A = ak bl am | l = k + m
(a) Refer to the closure properties of regular languages to argue that A is not regular.
Solution: The regular lanuguages are closed under intersection, but A∩L(a∗ b∗ ) equals {an bn | n ≥ 0}
which is not regular, hence A cannot be regular.
(b) Refer to the closure properties of context–free languages to argue that A is context–free.
Solution: The context–free languages are closed under languagenconcatenation, o and since A can
be represented as the concatenation of the context–free languages a b | k ≥ 0 and {bm am | m ≥ 0},
k k
A must be context–free.
(c) Give a context–free grammar G generating A.
Solution: From the previous observation, and the construction on grammars we used to show
this closure property, we directly obtain the grammar:
S → AB
A → | aAb
B → | bBa
(d) Construct an NPDA accepting A − {} on empty stack. Explain your choice of productions.
7. Give a detailed description (preferably as a graph) of a Turing machine with input alphabet {a, b}, 4p
that on any input x halts with string y ∈ L(a∗ b∗ ) written on its tape, where ]a(x) = ]a(y) and
]b(x) = ]b(y). Explain how your Turing machine achieves its task.
Solution: (Idea) There are many possible solutions, but one simple idea is to use insertion sort:
Iteratively “swap” the left–most b with the first following a (using renaming), until there are no more
such a’s. (6 states suffice!)
8. Recall Rice’s Theorem, textbook Lecture 34. Explain why the trivial properties of the recursively 2p
enumerable sets are decidable, by suggesting suitable total Turing machines for these properties.
Solution: There are exactly 2 trivial properties: the empty set (of r.e. sets) and the set of all r.e.
sets. Since we represent every r.e. set by some (encoding of a) Turing machine accepting this set, the
two trivialnpropertieso can be represented, by using some
n fixedoencoding of Turing machines, as the
languages M̂ | false , which is the empty set, and M̂ | true , which is the set of all legal Turing
machine encodings.
A total Turing machine MF accepting the first language is simply one that upon reading ` immediately
enters its reject state, while a total Turing machine MT accepting the second language is one which
decides whether the input string is a legal encoding of some Turing machine according to the chosen
encoding scheme.
DD2371 Automata Theory
with solutions KTH CSC
19 May 2008 08-790 81 98
1. Consider the language over the alphabet {a, b} consisting of all strings that do not contain 2 or E
more consecutive a’s and do not end with b.
(a) Construct a deterministic finite automaton (DFA) that accepts this language. Draw its
graph.
Solution: For example, see solution to problem 2(c).
(b) Suggest a regular expression that generates this language.
Solution: For example, the regular expression (a + )(bb∗ a)∗ .
2. For the deterministic automaton given below, apply the minimization algorithm of textbook E,D
Lecture 14 to compute the equvalence classes of the collapsing relation ≈ defined in textbook
Lecture 13.
a b
→ q0 F q1 q3
q1 F q2 q3
q2 q2 q5
q3 q4 q6
q4 F q2 q6
q5 q2 q5
q6 q7 q3
q7 F q5 q6

Solution: The equivalence classes are: {q0 }, {q1 , q4 , q7 }, {q2 , q5 } and {q3 , q6 }.
(c) Apply the quotient construction of textbook Lecture 13 to derive the minimized automaton.
Draw its graph.
Solution: (as a table)
a b
→ {q0 } F {q1 , q4 , q7 } {q3 , q6 }
{q1 , q4 , q7 } F {q2 , q5 } {q3 , q6 }
{q2 , q5 } {q2 , q5 } {q2 , q5 }
{q3 , q6 } {q1 , q4 , q7 } {q3 , q6 }
3. Show that the class of regular languages is closed under the following unary operation on lan-
guages:
def
min A = {x ∈ A | no proper prefix of x is in A}
(a) Define a construction on finite automata that has the corresponding effect on the accepted D,C
language.
Solution: An important result about a deterministic finite automaton M = (Q, Σ, δ, s, F )
is that δ̂(s, x · y) = δ̂(δ̂(s, x), y). So, if both x and y are accepted by M , the unique path
from s to δ̂(s, x · y) ∈ F has to pass state δ̂(s, x) ∈ F . Then, to elimiminate all suffixes of
words in L(M ), one has to eliminate all paths starting (and ending) in accept states of M .
This is easily achieved by removing all outgoing edges from all accept states. Note that
this results in a nondeterminstic finite automaton! So, we define:
def
N = (Q, Σ, ∆, {s} , F )
def
∆(q, a) = {δ(q, a) | q 6∈ F }
(b) Prove the construction correct. B,A

Solution: ˆ
n o (Sketch) The important result that is needed here is that ∆({q} , x) equals
δ̂(q, x) exactly when the unique path from q to δ̂(q, x) does not pass through an accepting
state (since we removed all their outgoing edges), and is the empty set otherwise. Formally:
( n o
ˆ δ̂(q, x) if for no proper prefix y of x, δ̂(q, y) ∈ F
∆({q} , x) =
∅ otherwise
After proving this Lemma, it is straightforward to prove that x ∈ L(N ) ⇔ x ∈ min L(M ).
4. Consider the regular language A over alphabet Σ = {a, b} defined through the regular expression D,C
(ab + b)∗ . Recall the Myhill–Nerode Theorem, textbook Lecture 16, with the equivalence relation
≡A on strings over Σ defined by: (cf. equation (16.1) on page 97)
x1 ≡A x2 ⇐⇒ ∀y ∈ Σ∗ .(x1 · y ∈ A ⇔ x2 · y ∈ A)
def
(a) Show the equivalence classes of Σ∗ w.r.t. equivalence ≡A , represented as regular expressions.
Solution: There are three equivalence classes. They can be represented by the regular
expressions: (ab + b)∗ , (ab + b)∗ a and (ab + b)∗ aa(a + b)∗ .
(b) For every pair of (different) equivalence classes A1 and A2 , give the shortest distinguishing
experiment, by means of a string y ∈ Σ∗ such that x1 · y ∈ A ⇔ x2 · y 6∈ A for any x1 ∈ A1
and x2 ∈ A2 .
Solution: (ab + b)∗ is distinguished from (ab + b)∗ a by , (ab + b)∗ is distinguished from
(ab + b)∗ aa(a + b)∗ by , and (ab + b)∗ a is distinguished from (ab + b)∗ aa(a + b)∗ by b.
5. Consider the language family B,A
An = {x ∈ {a, b}∗ | for every prefix y of x, 0 ≤ ]a(y) − ]b(y) ≤ n}

def
Prove formally that for every n, the minimal DFA accepting An has exactly n + 2 states.
Solution: We know that the minimal DFA accepting An is unique up to isomorphism. Then,
one can prove the above result by exhibiting a DFA for An that has exactly n + 2 states, and is
minimal, in the sense that no two of its states are equivalent.
For a given n, define the DFA
def
Mn = ({q0 , . . . , qn+1 } , {a, b} , δ, q0 , {q0 , . . . , qn })
def def def def
where δ(qi , a) = qi+1 for 0 ≤ i ≤ n, δ(qi+1 , b) = qi for 0 ≤ i < n, δ(q0 , b) = qn+1 , δ(qn+1 , a) =
def
qn+1 , and δ(qn+1 , b) = qn+1 . Mn has n + 2 states, and it is easy to see that Mn accepts An .
We now show that Mn is minimal. For 0 ≤ i < j ≤ n, we have qi 6≈ qj with witness bi+1 (since
δ̂(qi , bi+1 ) = qn+1 6∈ F while δ̂(qj , bi+1 ) = qj−(i+1) ∈ F ). And for 0 ≤ i ≤ n, we have qi 6≈ qn+1
with the obvious witness .
6. Consider the context–free grammar:
S → | aS | Sb
(a) Which language does this grammar generate? D,C

Solution: It generates the language L(a∗ b∗ ).
(b) Prove your answer correct. B,A
Solution: The proof of S →+ ∗ ∗
G x ⇔ x ∈ L(a b ) is standard, as discussed in class.
7. Consider the following language:

def
L = {am bn | m 6= n}
over the alphabet Σ = {a, b}.
(a) Refer to the closure properties of context–free languages to show that L is context–free. E
def def def
Solution: We have L = A · C ∪ C · B for languages A = B = L(aa∗ ),
and C = L(bb∗ ),
n n
{a b | n ≥ 0}, all of which are context–free. Since CFLs are closed under concatenation
and union, L must also be context–free.
(b) Guided by your answer, give a context–free grammar G generating L. E
Solution: Using the constructions used for proving the corresponding closure properties,
we easily obtain the grammar:
S → SA SC | SC SB
SA → a | aSA
SB → b | bSB
SC → | aSC b
(c) Construct a deterministic pushdown automaton (DPDA) that accepts L on final states. E,D
(Recall that DPDAs rewrite ⊥ only to strings of shape γ⊥, so they never halt because of
an empty stack.) Draw its graph and explain its workings.
Solution: (Sketch) It is not difficult to come up with a DPDA for this language having
6 control states. The key idea is to push onto the stack a letter A for the first a of the
input word, but push a different letter B for all following a’s. This allows to detect the b
“matching” the first a, and to move to a non-final control state.
(d) Recall the Chomsky–Schützenberger Theorem (textbook Supplementary Lecture G). Show D,C
how this theorem applies to the above language L, by identifying:
• a suitable natural number n,
• a regular language R over the alphabet Σn of the n–th balanced parentheses language
PARENn , and
• a homomorphism h : Σn → Σ∗ ,
so that you can argue that L = h(PARENn ∩ R) holds.
Solution: Again guided by the decomposition in (a), one can take n = 3, regular language
R = L([1 [1 ∗ ]1 ∗ [2 ∗ ]2 ∗ + [2 ∗ ]2 ∗ [3 ∗ ]3 ∗ [3 ) and homomorphism h defined by h([1 ) = h([2 ) = a,
h(]2 ) = h(]3 ) = b, and h(]1 ) = h([3 ) = .
8. Consider the language: n o D,C

l m n
A= ab a |l<m<n
Use the Pumping Lemma for context–free languages, as a game with a Deamon, to prove that
A is not context–free.
Solution: (Sketch) By picking z = ak bk+1 ak+2 it is easy to win the game, by pumping out (i.e.
picking i = 0) or in (e.g. picking i = 2) depending on whether v · x overlaps with the last block
(in which case it cannot overlap with the first block) or not, respectively.
9. Give a detailed description, preferably as a graph, of a total Turing machine accepting the E,D
language: n 2 o
A = an | n ≥ 0
Explain the underlying algorithm.
Solution: (Sketch) One idea is to procede in rounds, by marking the letters on the tape with
single or double dots, so that at the end of round k the tape contents are:
k
z }| {
` ää
| . . . ä{zȧȧ . . . ȧ} aa . . . a
k2
Noticing that (k + 1)2 = k 2 + 2k + 1 and that a block of k 2 a’s and another one of k a’s are
readily present after round k, it is not difficult to compute the tape contents needed at the end
of round k + 1, namely:
k+1
z }| {
` ää
| . . . ä{zȧȧ . . . ȧ} aa . . . a
k2 +2k+1
The machine accepts if after some completed round all a’s are marked, and rejects if all a’s are
marked before completion of the latest round.
10. Show that the problem of whether a Turing machine eventually writes a given letter on its tape B,A
for exactly 777 input strings is undecidable. Or, in other words, show that the set
n o
def
P = M̂ ]â | for 777 inputs, M eventually writes a on its tape
is not recursive.
Hint: Find a suitable problem P 0 on recursively enumerable sets, for which you:
(a) argue that P 0 is not trivial and hence, by Rice’s Theorem, is undecidable, and
(b) reduce P 0 to the original problem P , by describing how from a total TM for P you can
build a total TM for P 0 .
Solution: The bottom–line idea in many problems like this one is to reduce acceptance to the
given problem, in this case eventual writing of some letter to the tape.
The problem P 0 of whether a Turing machine M accepts exactly 777 strings (i.e. whether
|L(M )| = 777) is obviously a nontrivial problem on recursively enumerable sets, and hence, by
Rice’s Theorem, is undecidable. We will reduce this problem to the original problem P above.
Assume MP is a total TM for P . Construct Turing machine N as follows. On input M̂ ,
machine N :
• modifies M̂ to M̂ 0 by adding: a new symbol a to the input alphabet of M , a new state tnew
which is made the accept state of M 0 , and transitions from the original accepting state (of
M ) to tnew that on any tape symbol rewrite this symbol to a, and
• overwrites the input with M̂ 0 ]â, rewinds, and continues as MP .
Then, we have:
N accepts M̂ ⇔ MP accepts M̂ 0 ]â

⇔ for 777 inputs, M 0 eventually writes a on its tape
⇔ for 777 inputs, M accepts
⇔ |L(M )| = 777
Since MP is total, we obtain that N rejects M̂ if |L(M )| =

6 777, and hence N is a total TM
deciding problem P 0 . But this problem is undecidable, and so we arrived at a contradiction.
Therefore no total TM for P exists, and hence problem P is undecidable.
2D1371 Automata Theory
with selected solutions KTH CSC
28 May 2007 08-790 81 98
1. Convert the nondeterministic automaton given below to an equivalent deterministic one using the
subset construction (textbook Lecture 6). Omit inaccessible states. Draw the graph of the resulting
DFA.
a b
→ q0 {q2 } ∅
→ q1 F {q0 , q2 } ∅
q2 F ∅ {q1 , q2 }
a b
→ {q0 , q1 } F {q0 , q2 } ∅
{q0 , q2 } F {q2 } {q1 , q2 }
{q1 , q2 } F {q0 , q2 } {q1 , q2 }
{q2 } F ∅ {q1 , q2 }
∅ ∅ ∅
2. For the deterministic automaton given below, apply the minimization algorithm of textbook Lecture 14
to compute the equvalence classes of the collapsing relation ≈ defined in textbook Lecture 13.
a b
→ q0 q2 q0
q1 q0 q2
q2 F q4 q3
q3 q0 q4
q4 F q4 q1

Solution: These are {q0 }, {q1 , q3 } and {q2 , q4 }.
(c) Apply the quotient construction of textbook Lecture 13 to derive the minimized automaton.
Draw its graph.
a b
→ {q0 } {q2 , q4 } {q0 }
{q1 , q3 } {q0 } {q2 , q4 }
{q2 , q4 } F {q2 , q4 } {q1 , q3 }
3. A context–free grammar G = (N, Σ, P, S) is called strongly right–linear (or SRLG for short) if all its
productions are of shape A → aB or A → . Let us call a SRLG deterministic if for each non–terminal
A ∈ N and terminal a ∈ Σ there is exactly one production of shape A → aB (while productions of
shape A → are optional).
Define a complement construction on deterministic SRLGs. That is, for deterministic SRLGs G define
the complement G as a deterministic SRLG for which you show that L(G) = L(G).
Solution: Recall that there is a one–to–one corespondence beween DFAs and SRLGs, and recall the
complement construction on DFAs. Let G = (N, Σ, P, S) be a deterministic SRLG. We define the
def def
complement of G as the deterministic SRLG G = (N, Σ, P , S) where P = {A → aB | A → aB ∈ P } ∪
{A → | A → 6∈ P } is the set of productions of G. Then,
+
x ∈ L(G) ⇔ S →G x {Def. L(G)}
n o
+
⇔ ∃!A ∈ N. (S →G xA ∧ A → ∈ P ) G a deterministic SRLG
n o
⇔ ∃!A ∈ N. (S →+
G xA ∧ A → 6∈ P ) Def. G
⇔ not S →+G x {G a deterministic SRLG}
⇔ x 6∈ L(G) {Def. L(G)}
⇔ x ∈ L(G) {Set theory}
and therefore L(G) = L(G).
4. Recall the Chomsky–Schützenberger Theorem (textbook Supplementary Lecture G). Show how this
theorem applies to the context–free language
A = {x ∈ {a, b}∗ | ]a(x) = ]b(x)}

def
over the alphabet Σ = {a, b}, by identifying:
• a suitable natural number n,

• a regular language R over the alphabet Σn of the n–th balanced parentheses language, and
• a homomorphism h : Σn → Σ∗ ,
for which you argue that A = h(PARENn ∩ R) holds.

Solution: Recalling that A is generated by the grammar S → | aSb | bSa | SS it is easy to see that
A = h(PARENn ∩ R) holds for n = 2, R = (Σn )∗ and h defined by h([1 ) = a, h(]1 ) = b, h([2 ) = b and
h(]2 ) = a.
5. Consider the language:

A = {am bn | m ≤ n}
(a) Use the Pumping Lemma for regular languages (as a game with a Deamon) to prove that A is
not regular.
(b) Refer to the closure properties of context–free languages to argue that A is context–free. That
is, represent A as the result of some operation(s) on context–free languages (which we already
know to be context–free) under which CFLs are closed.
def def
Solution: A = B · C for B = {am bm | m ≥ 0} and C = {bn | n ≥ 0}, both of which we know to
be context–free, and we know CFLs to be closed under language concatenation.
(c) Give a context–free grammar G generating A.
Solution: One possibility is the grammar S → | aSb | Sb.
(d) Prove your grammar correct. You are allowed to reuse results proved in class.
(e) Construct an NPDA accepting A − {} on empty stack. Explain your choice of productions.
Solution: One solution is a NPDA with one control state q and productions:
a
hq, Si ,→ hq, SAi
a
hq, Si ,→ hq, Ai
b
hq, Ai ,→ hq, Ai
b
hq, Ai ,→ hq, i
The automaton uses the first production for reading all initial a’s but the last, then guesses the
last a and uses the second production to get rid of the S at the top of the stack. The stack now
has as many A’s as the a’s read so far. The automaton guesses the number of b’s in excess of a’s
in the string, and uses the third production that many times. The stack now has as many A’s as
there are remaining (unread) b’s. The automaton uses production four to empty the stack upon
reading the whole string.
6. Let M range over deterministic finite automata (DFA).
(a) Describe a uniform, injective encoding of DFAs into strings over the alphabet {0, 1}.
Solution: Such an encoding was discussed in class.
(b) Let M̂ ∈ {0, 1}∗ denote the encoding of M . As we know from Cantor’s theorem, the set
n o
A = M̂ ∈ {0, 1}∗ | M̂ 6∈ L(M )
def
is not regular (since it is the inverted diagonal set). Argue, however, that A is recursive by giving
a (reasonably detailed) description of a total Turing machine accepting A.
Solution: (Sketch) The Turing machine T starts by modifying the input M̂ to M̂ ]qˆ0 ]M̂ where
q0 is the initial state of M . The added part qˆ0 ]M̂ represents the initial configuration of M (where
a configuration of a DFA is understood as a pair consisting of a state and the suffix of the input
string that remains to be read). T continues by simulating M on M̂ , by iteratively computing
and updating the current state of M until the input string M̂ has been completely consumed.
This is achieved by reading (and consuming) the next symbol of the input string M̂ of M , and
looking up from M̂ (always available in the first segment of the tape) the next state of M . Finally,
T checks whether the state in the final configuration of M is an accepting state, and rejects resp.
accepts accordingly. Thus, T is a total Turing machine accepting language A.
7. Consider the language n o

def
VTP = M̂ ]x̂]q̂ | M run on x visits q twice
where ”M visits q” means that Turing machine M is at a configuration with control state q. Show
that language VTP is not recursive by reducing from undecidability of the Membership Problem.
That is, given a total Turing machine MVTP deciding VTP, construct a total Turing machine MMP
deciding MP, where: n o
def
MP = M̂ ]x̂ | M accepts x
Solution: Assume there is a total Turing machine MVTP accepting VTP. Then we can construct a
Turing machine MMP as follows.
On input M̂ ]x̂, MMP modifies the input to M d0 ]x̂]v̂ where M 0 is like M but is modified as follows: two
new control states u and v are added, the latter of which is made the new accept state of M 0 , and the
transition function δ of M is extended to δ 0 so that δ 0 (t, a) = (u, \, R) and δ 0 (u, a) = (t, a, L) for all a
in the input alphabet of M , and δ 0 (t, \) = (v, \, R), where t is the original accept state of M and \ is a
tape symbol of MMP not used elsewhere. Notice that M 0 visits state t twice on input x exactly when
M visits t on x, that is, when M accepts x. MMP then continues as MVTP .
Then:
d0 ]x̂]v̂
MMP accepts M̂ ]x̂ ⇔ MVTP accepts M
0
⇔ M run on x visits v twice
⇔ M accepts x
Since MVTP is total, so is MMP , and so MMP decides MP which we know to be undecidable. Hence
there is no total Turing machine MVTP accepting VTP.

Final Exam Solution - Test Paper Final Exam Solution - Test Paper

Uploaded by

Copyright:

Available Formats

Final Exam Solution - Test Paper Final Exam Solution - Test Paper

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Final Exam Solution - Test Paper Final Exam Solution - Test Paper

Uploaded by

Copyright:

Available Formats

lOMoARcPSD|36771882

Final Exam Solution - test paper

computer organisation (The University of the South Pacific)

Scan to open on Studeersnel

Studocu is not sponsored or endorsed by any college or university

CS211: Computer Organisation

F2F & Blended Mode

Duration of Exam: 3 hours + 10 minutes

Reading Time: 10 minutes

Writing Time: 3 hours

Total Marks: 100

There are three sections in this paper

Answer all questions in the answer booklet provided

This exam is worth 50% of your overall mark

The minimum mark to pass the final exam is 20/50

The total number of pages including this cover sheet is 11

This is a closed book exam

Downloaded by Breman Wiener ([email protected])

Section A: Multiple Choice (10 Marks)

1) The circuit used to store one bit of data is known as ________________.

3) In Reverse Polish notation, expression A*B+C*D is written as ________________

Downloaded by Breman Wiener ([email protected])

9) Any computer must at least consist of

Downloaded by Breman Wiener ([email protected])

Section B: Short Answer and Problem Solving (80 Marks)

1. The truth table for the Boolean expression is given below.

Downloaded by Breman Wiener ([email protected])

3. Consider the following infix assignment statement:

Use this statement to answer the following five questions.

b) 7 operands * 2 bytes per operand + 8 instructions * 2 bytes per instruction = 30 bytes.

Downloaded by Breman Wiener ([email protected])

d) 7 operands * 2 bytes per operand + 12 instructions * 1 byte per instruction =

1010 1011 1100 0000 0001 0010 0011 0100 ½ mark

1111 1111 1010 1011 1100 0000 0001 0010 1 mark

=> FFABC012 ½ mark

5. Justify whether it is possible to design an expanding opcode to allow the following to be

1111 1110 0000 r3

1111 1111 1110 r3

1111 1111 1111 0000

1111 1111 1111 1111

Therefore, this design is possible. 1 mark

Downloaded by Breman Wiener ([email protected])

a) 8 page faults 1 mark. 1 mark for table

b) 11 page faults 1 mark. 1 mark for table

Downloaded by Breman Wiener ([email protected])

c) 11 page faults 1 mark. 1 mark for table

Cycle Instruction # Decoded Issued Retired

Downloaded by Breman Wiener ([email protected])

Cycle Instruction # Decoded Issued Retired Mark

b. 5 cycles (0.5 mark)

Cycle Instruction # Decoded Issued Retired Mark

Downloaded by Breman Wiener ([email protected])

 Position 1 checks bits 1,3,5,7,9,11: (0.75 mark)

Downloaded by Breman Wiener ([email protected])

segment 0 segment 1 segment 2 segment 3

page frame page frame page frame page frame

b. C12 = 1111 10101010  Segment 3 Page 3, Frame 7 = 111 10101010 = 7AA

00001100 =>12 (1.5 marks)

-12 (0.5 marks)

3) In Reverse Polish notation, expression AB+CD is written as ________________