Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
--------------------------------------------------------------------------- Computer Science Tripos Part 1 - Easter Vac Revision Questions These questions may be helpful. Some might be impossible or off syllabus. (C) DJ Greaves 1995-9. --------------------------------------------------------------------------- > Part Ib - Basic Revision Half Questions (C) 1999 DJ Greaves Most of the questions below are designed to approximate half of a standard examination question: ie 10 marks, although some are longer. Note that real exam questions tend to have a second half which requires real thinking: the questions below do not! =========================================================================== Michaelmas Term 1998: Part IB lectures --------------------------------------------------------------------------- ECAD EC1) Give the Verilog for a four bit up/down counter module. It should have two inputs, for up, down, hold and parallel load. EC2) Discuss the differences between formal verification of a design and simulation. What do they have in common in terms of goals and what problems arise ? EC3) Explain the model of a 3 input AND gate used in a typical ECAD system. Explain what software may generate the gate and what is done when a chip is fabricated and wire delays are known. --------------------------------------------------------------------------- Concurrent Systems CS1) Explain the concept of a spin-lock and describe the facilities available to improve efficency at the operating system and HighLevel Language level. ADVICE: GIVE TEN POINTS FOR 10 MARKS. CS2) Compare and contrast message passing with byte streams for IPC. ADVICE: GIVE TEN POINTS FOR 10 MARKS. CS3) Explain how a VM system can help implement fork, memcopy, shared memory IPC, multiple stacks, quick start of programs. CS4) Explain deadlock. How can it be avoided at compile time and run time ? CS5) Explain the need for atomic operations and discuss whether they can be emulated in software on a multiprocessor ? --------------------------------------------------------------------------- Unix Tools - not examinable --------------------------------------------------------------------------- Logic and Proof LP1) Define first order logig. LP2) Define how to convert to clause form using the Davis-Putnam procedure clearly explaining the semantic implications of each step. What is a most general Unifier ? Does it always exist ? LP3) Explain the need for Skolem variables and functions. LP4) What is an interpretation ? Give an example logical system and its Herbrand universe. LP5) What happens if you try to prove a discrete maths problem (e.g. all squares are the sum of consecutive odd numbers) or a continuous maths problem (e.g. sin^2 + cos^2 = 1) using the above proof tools? LP6) Prove or disprove that P(x, y) & ~P(y, x) & (P(x,z) or P(z,x)) implies there exists r such that P(r, r). LP7) In a formal system what do the following words mean: axiom, theorem, proof, correctness, satisfiable, valid, false, tautology. --------------------------------------------------------------------------- Data Structures and Algorithms DSCORE0) Explain open and closed hashing. How would you store the lexical tokens in an ML interpreter ? How would a FSA (as generated by lex) organise its tables. Explain whether arrays are needed in functional languages. DSCORE1) Compare reference counts with mark and sweep or copying GC. DSCORE2) How does the buddy system of free store management work? Sketch code. DSCORE3) What is a B-tree? Mention Larsen. How does it relate to a 2-3-4 and red/black tree? DSCORE4) Compare bubble, shell quick and heap sorts. DSCORE5) Are sets needed in high level languages as built in abstract datatypes ? DSCORE6) How would you find a string in some text ? DSCORE7) What is LZ compression ? What happens with errors ? Modify the LZ algorithm to run continuously with error recovery (e.g. as needed on a digital video stream run over a network). DSCORE8) Explain MPEG and JPEG in detail. DSCORE9) Make sure you know Warshall, Floyd, Dijkstra, Prim and Kruskal algorithms and how to do matchings in bi-partite graphs. PROG1) Explain how you would go about a project to emulate real code running on a processor while evaluating the performance of different cache algorithms ? GIVE THE DATASTRUCTURES. PROG2) How would you arrange a database for the phone directory for planet Earth? Explain how updates would be handled. DSA1) When sorting N objects into order it would seem evident that if there are only M different keys, M < N, the sort should be cheaper. Discuss the effect of key coincidence on three different sorting algorithms, including at least one where it helps and one where it doesn't. DSA2) Describe the use of dynamic programming to solve the integer knapsack problem. Why is the all-pairs shortest path algorithm in graph theory sometimes described as dynamic programming ? DSA3) A polygonal island is specified by the (x,y) coordinates of its vertices. Describe an algorithm to determine if a boat is within the territorial waters of the island. DSA4) Implement heapsort in a language of your choice. Can you implement heapsort in a non-imperative language such as functional ML or lisp ? DSA5) State Dijkstra's algorithm and prove that it works. What happens if the graph does not obey the triangle inequality, in that there is a shorter indirect route between two nodes than the direct route? --------------------------------------------------------------------------- Computer Design CD1) Explain why bytecodes are used and how they can run faster than real code with certain caches ? Compare with microcoded architectures and native Java processors. CD2) Explain the need for the different busses in your PC and give their data rates and latencies. ARM1) Sketch an assembly language program to find the most frequently occuring ASCII character in a null-terminated string. On entry, the start address of the string is in a register and on exit the register should contain the modal character code. ARM2) In you program of ARM1 above, how might the cache performance be altered if you modified your main data structure ? Consider using a repeated scanning approach rather than an array. ARM3) Describe the term `pipelining' and the effects of conditional and unconditional branches on a pipeline. How does the ARM's conditional execution facility help avoid pipeline breaks ? ARM4) Explain a set-associative cache and a fully associative cache. A processor has four caches as follows: the TLB, the Data Cache, the Instruction Cache and a second-level general cache. What level of associativity is suitable for each and which should contain virtual and which physical addresses ? How many caches should we have and which caches need to snoop when two processors are combined to make a multiprocessor system ? ARM5) What is the `Von Neumann bottleneck' and how can memory bandwidth be made best use of or increased in processor design. ARM6) * Design a dataflow machine. How would you add further processors and what would need to be changed ? Don't worry about I/O, filing, program loading or anything useful like that. --------------------------------------------------------------------------- Numerical Analysis I NA1) What is the format of single-precision IEEE floating point and how precise is it in decimal terms ? NA2) Explain loss of precision and underflow. Give an example where guard digits help. NA3) Find the order of convergence of Newton Raphson. NA4) A program is very multiply-intensive. Comment on whether logs could help speed it up. --------------------------------------------------------------------------- Further Java FJ1) Describe the threads support in Java. What has to be in the core language and what in a library. When Java is compiled to native mode, what facilities from the Java runtime system are needed to support concurrency? FJ2) Explain the difference between JavaScript and an applet. FJ3) Why is an interface class useful ? How would it be implemented in the compiler ? How does it compare with the virtual classes of C++ ? FJ4) How can code using the RMI system be used to connect both to Java and non-Java systems? --------------------------------------------------------------------------- Continuous Mathematics CM1) Explain how partially overlapping windows with trapezoid windows can be used with the Fourier transform to allow fairly good frequency domain processing of infinite, continuous, aperiodic waveforms. What are the shortcomings ? CM0) Describe the Gabor Wavelet transform. What freedom is available in selecting the basis functions ? How can this be used ? --------------------------------------------------------------------------- --------------------------------------------------------------------------- Lent Term 1999: Part IB lectures --------------------------------------------------------------------------- Comparative Programming Languages -- Macro Processing Some languages have a macro processor builtin and others are implemented entirely by macroprocessing. Why are macro processors used and what is their disadvantage? Relate this to template classes in C++. -- Orthogonal Persistency Some languages enable the heap records of one run to retain data for future runs. How could this be implemented and compare it with other approaches ? -- Shared memory, Unions and Common Blocks More that one processes in Unix can access a shared memory segment. Say why this is useful. How does this compare with the C union and FORTRAN common block ? -- Screen and Graphics Processor access How is access to the screen and AGP gained on a PC by a fast game ? -- Call by Value What is call by value and why is it useful? List other calling forms giving examples of their operation in real languages. -- Dynamic Store Allocation FORTRAN, Occam and COBOL had no dynamic storage allocation and Java has no pointers. How can programs be written in these languages ? What support for automatic garbage collection does a language need to provide. Explain why the keyword 'new' was not built in to C. -- Objects and Inheritance Define an object and explain inheritance. What problems can multiple inheritance in C++ cause and how does the Java `interface' mechanism help. -- Infix Operator and Function overloading ML and C++ allow new infix operators to be defined. Explain how this works. Java and C++ allow functions to be overloaded and Modula 3 allowed default values for missing function parameters. Explain this. -- Dynamic Free Variables ML, Algol and Pascal support full function closures with dynmaic free variables. How can this behaviour be achieved in other languages and why do implementors not support it. -- Casts and other non-typesafe operations Why do we need casts ? Why do we embed assembler in C? -- Non-blocking message passing Smalltalk, I think, provides a non-blocking method invocation, meaning that a message was passed to another object on the heap and it was up to the caller of the method whether to wait for a reply. Is this highly efficient and does it provide too much concurrency ? -- Link Editing Explain how a link editor works by detailed reference to the record types found in a .o file. Explain how things are enhanced to support dll's or .so shared libraries. -- RPC and future-proof interfaces. Corba and Java RMI provide RPC packages that allow calls between parts of a program running on different machines. Explain the problem of adding a new function to some of the machines without making them incompatible with other machines. Can XML help ? -- Reflection Explain the Java reflection API. How is the same achieve in C or is it ? -- 4G languages Explain the type system of PERL and say whether it is good or bad. -- Functional, Imperative and Declarative Programming languages are moostly Functional, Imperative or Declarative. What does this mean ? -- Formally Amenable Explain the assign once concept. Certain programming language are easier to reason about than others. Why is this ? -- Markov Algorith and Type 0 Grammar Chomsky defined four classes of grammar, with type 0 being a turin powerful programming language. Explain why this was a useful thing to do. What is a Markov Algorithm ? -- Recursion Cobol did not allow program recursion. Why was this and how is it provided these days ? -- Mutexes and Threads Multi-threaded programs often use the pthreads API. Describe one or two of the main procedures this offers. CSP, Occam and Verilog have explicit fork/join language statements. C has a fork call. Explain how all these achieve the same thing. -- BCD coding COBOL has extensive builtin functions for handling data in base 10. Why is this and what is done in other languages ? -- Formatted I/O COBOL, FORTRAN and BASIC provide a lot of built-in features for reading and writing data in formatted format. Compare this with printf and scanf in C ? -- Lists ML and LISP provide built-in features for lists. If the list was not built in to ML, what could you do and how would this compare with C where lists are also not built in. -- Migration A running program could jump from a PDA to a server in your house. This is called migration. What problems arise when moving a running programming from one host to another. What are the alternatives? -- Middleware Should middleware be builtin to the operating system or the programming language or the network ? Or should it be left in the middle ? C1) Explain five primitives that enable a complete LISP system to be built up. C2) Define a set of macros for C which simulate the `dynamic free variables' of languages such as Pascal, Algol and Modula. Can closures be supported ? What are the perceived costs and benefits of supporting local functions and dynamic free variables. First define all the terms. C3) Give an implementation of an exhange subroutine swap(&x, &y) in C. How does C++ help the programmer provide such `call-by-name' operations. C4) Discuss the merits of automatic garbage collection in real-time systems. C5) Some languages do not have pointers. Explain and discuss. CQ.1 Function Calls Describe each of these using words or the semantic representations covered in semantics: Call by value Call by reference Lazy Call by Value Call by Macro Expansion (call by name or textual replacement) Describe the call-by semantics used in each of the programming languages you know well. Give an illustative example of each form of call in one language or another. Which call techniques are suitable for dynamic programming or meoising systems ? How can the compiler optimise the passing of large constant arguments ? CQ.2. What is a dynamic free variable ? Give an ML example of a dynamic free variable and another example in Algol, Pascal or Modula 2 or 3. Explain the static chain method of access to dynamic free variables and show how a function closure can be stored in a variable and passed as an argument. In Java, what can be stored on a stack and what on the heap ? CQ.3 Explain the difference between interpretation and compilation ? How does Java byte code fit in to this classification ? What is or was threaded code ? What is a 4G language (4th generation), if anything ? Compare 4G languges such as perl, python and TCL with Java or Visual Basic that have very large standard libraries. CQ4. It is proposed to develop a new programming language for control of interaction between home devices ? Should this language be functional, imperative or declarative (logic)? Is a new programming language needed or does a suitable language exist ? Explain the concepts of meta-programming and reflection. Give the details of how a remote procedure call be made to a device that is newly introduced into the home environment. What can happen in typical HLLs if the called stubs use abstract data types that were not defined at the time the calling code was written ? --------------------------------------------------------------------------- Operating System Functions OS1) Describe an I-node in Unix. Why are they needed. Explain how small files are stored. OS2) Consider a disk drive which is directly connected to the network yet appears as a local disk for a typical single user operating systems such as W95. What problems arise under W95? Would it be easier under Unix ? OS3) Describe how a network disk drive, similar to the one in OS2, could receive video directly from a network attached video camera without the data going through other computers. How is the directory entry and free-store managed ? OS4) How can a device be made to appear like a file, as done in the Unix /dev directory ? Sketch all of the data structures and explain how a new device is added. OS5) Explain how the memory on nearby computers might be used as backing store as an alternative to local swap disks or partitions. How does disk and network speed affect things ? OS6) What does Microsoft's direct-X API do and why is it needed when Unix manages without ? --------------------------------------------------------------------------- Compiler Construction CC1) Many programming languages use call-by-value and do not prescribe the order of evaluation of arguments. Explain these terms and why the lack of prescription can make things easier for the compiler or compiler writer. Mention functions which can take a varying number of arguments, such as printf. CC2) Compare general precedence with SLR(1) parsing. Explain what they are first using an example grammar. CC3) Calling conventions either save registers before calling the subroutine or save registers within the subroutine before dirtying them. Compare the efficiency of both approaches taking into account that leaf routines can be handled separately. Remember that arguments can be passed in registers or on the stack. CC4) Give examples of code optimisation steps. Why do some languages provide the storage class modifier `volatile' ? CC5) What is a static chain ? Which languages need it? When might it not link to the most recent parent stack frame of the appropriate type? CC6) Give a full interface to a lexical analyser for the ML language, as seen by the parser. Give an example of its use. CC7) When is run-time type checking needed for statically compiled code ? How does dynamic code loading alter things ? CC8) Give code examples illustrating the semantics of logical AND (&&) and bitwise AND (&) and show the compiled code generated. CC9) Explain the format of a common object file suitable for link editing. CC10) * Why is intermediate code used ? CC11) Explain the C storage modifiers volatile, inline, unsigned, static and register. Give the Java equivalents of each. Why might a compiler ignore some of these? --------------------------------------------------------------------------- Computation Theory CT1) Describe the primitive and partial recursive functions. What then are the total recursive functions ? CT2) If a set is recursive then what can we say about its complement ? CT3) Design a register machine to determine whether two numbers are integer multiples of each other or not. CT4) Design a one-tape Turing machine which simulates a two register machine and say why this is significant. CT5) Present the halting problem in 5 concise lines (and commit it to your memory for the exams). CT6) What is a Recursive Bag ? CT8) Can programs in a Turing-powerful language have a normal form ? --------------------------------------------------------------------------- Semantics of Programming Languages Invent a simple imperative language which has sufficient power to answer all the questions here and give its syntax. It must have two built in datatypes (e.g. the string and real paradigm found in BASIC) together with list, tupple and array constructors. S0) Define the execution state of your language (i.e. environment) as a mapping from variable names to values. S1) Give the structural operational semantics of the language. S2) Define a function C which takes a section of code and an execution state and returns the new state. It might need to call another, similar function E which handles expressions. S3) How might operational semantics be used to prove that two sections of code perform the same function? S?) Write a routine to exponentiate one integer to another in your simple imperative language and prove that it is correct. [Floyd/Hoare Not covered this year ?] --------------------------------------------------------------------------- Digital Communication I DC1) Explain the Ethernet. What restricts its size? DC2) Why are Internet addresses different from MAC addresses. A user tries to join a token ring to an Ethernet with one of the following repeater bridge router firewall gateway explain what happens. [LONG 20] DC3) What is the difference between switching and multiplexing ? DC4) Why does queuing occur and what is the idea of statistical multiplexing gain ? DC5) What is packet switch and circuit switching? What is Frame Relay and ATM then ? DC6) What happens if you click on a new URL (i.e. how does the Internet name server work) ? DC7) A radio channel offers 2 MHz bandwidth and 40 dB StoN. What is its capacity ? What error rate is possible in theory ? What is Manchester coding and why is it needed ? Is it good for radio links ? DC8) Explain the functions of a plain old telephone. How is a PC doing Internet Telephony different ? --------------------------------------------------------------------------- Prolog for Artificial Intelligence P1) Explain a difference structure and give an example of its use, showing every step. P2) Relate Prolog to the clauses generated by Putnam-Davis clauses. P3) What list functions does Prolog normally have ? P4) Give an example of where the order of clauses in a Prolog program makes a difference and comment on the semantics. P5) A programming language which is an extension of Prolog allows users to restrict the variables in the head terms to be input, output or inout. How might this improve efficiency, especially when a good deal of functional programming style is used. --------------------------------------------------------------------------- Introduction to Security S0) How are nonces used to overcome replay attacks ? S1) Explain how a cash machine works. What advantage could be gained by a chappie who taps the wired network could this be avoided by using a smart card cashcard? S2) Describe DES. How and why is chaining sometimes used ? S3) Describe Diffie-Hellman. --------------------------------------------------------------------------- Computer Graphics and Image Processing G1) Objects represented as faceted polyhedra are to be displayed in a perspective view on a screen. Suppose that all the facets have been p-scaled in readiness for this and it remains to determine their combined effect in forming the view. Describe the calcualations involved. How is cyclic overlap of facets handled. G2) Compare and contrast vector and raster graphic displays. Why do aircraft flight simulators use a combination of the two ? G3) Describe a method for testing whether two-dimensional line segments intersect. How does this method help clip two dimensional polyhedra against each other ? What happens if one or both hedra are concave ? G4) What are primary colours? What resolution can be achieved by a 25 mm lense, a flat-bed scanner, an ink jet printer, a 21 inch VDU, a projection TV ? What are the theoretical and cost limitations in each case? G5) Explain ray tracing? How can translucent materials be handled ? G6) Explain the functions of sprite displays and 3D video cards. --------------------------------------------------------------------------- --------------------------------------------------------------------------- Easter Term 1999: Part IB lectures --------------------------------------------------------------------------- Computer Graphics and Image Processing --------------------------------------------------------------------------- Foundations of Functional Programming --------------------------------------------------------------------------- Databases DB1) Explain what is meant by the term Normal Form in mathematics. Why is this term used in Databases and is it meaningful ? DB2) Explain how consistency can be ensured in a database. DB3) Explain a shadow page mechanism and construct a database system that relies on shadow pages and the concept of atomic commit on disk sector writes. Is this a good model these days ? --------------------------------------------------------------------------- Complexity Theory --------------------------------------------------------------------------- CT1) How many frenchmen does it take to change a lightbulb ? =========================================================================== Part Ia =========================================================================== > Digital Electronics DE1) Explain the purpose and use of a Karnough Map. Draw K-maps for functions Fx of four variables which have the following properties: F0 is a function of two inputs only, F1 has five minterms, F2 has four prime implicants, F3 has a prime implicant that cannot appear in any minimal sum of products. DE2) Give the circuit for a three bit gray code counter using T-types. DE3) Give a synchronous counter circuit to divide by 4 or 5 (according to an external input) (ie a dual modulus counter) which will clock as fast as possible. What might happen to your counter if the control input changes at the wrong time ? DE4) Give the truth table, fundamental mode and pulse mode state diagrams for a JK flip-flop. Produce a circuit for a JK made out of two input NAND elements. DE5) Describe the operation of an N-channel FET and an NMOS inverter. Why is CMOS more often used today ? DE6) Using two input NAND gates as your only type of gate, sketch designs for ripple and lookahead carry adders. How many inputs must your adder have before the lookahead approach is faster ? DE7) Design a synchronous and a ripple counter to divide by ten. Use an asynchronous reset to the flip-flop(s) in the ripple version. Which works faster and how do the outputs of the two designs behave as the clock frequency is increased ? DE8) How may a tri-state bus be used to connect a number of peripherals to a microprocessor ? A chip contains both a microprocessor and its peripherals. Tri-state busses are discouraged on chip owing to manufacture and testability issues. Design alternatives to tri-state busses that could be used on chip, taking into account issues such as gate fan-in, fan-out and total wiring complexity. Why is an arbiter sometimes needed with a bus structure ? DE9) Give the circuit of a full adder using ripple carry for 4 bit inputs. How does one convert the circuit to a subtractor ? --------------------------------------------------------------------------- > Discrete Maths (16L) DM1) Define with an example the terms `relation' and `powerset'. DM2) Define with examples a `partial order' and a `complete partial order'. What is a `well ordering' ? DM3) Weak and strong induction. Define these terms and give an example where strong induction is needed. How can induction be applied to a partial order ? How can structural induction be applied to a function of the form ZxZ->Z which generates a set to prove a property of the set ? DM4) Give an algorith to find the minimum cost spanning tree for a directed graph and state its running cost. Why is your algorithm not very useful for finding the shortest path from where you currently are to all other points ? DM5) Give a recurance relation whose closed form is bounded by a linear function if one of the coefficients is 10 and which is bounded by a n log n function if that coefficient is 100. DM6) Define the concept of closure with regard to a set and a diadic operator. DM7) Let X be a partially ordered set. State what is meant by X being well-ordered. Prove that if X is well ordered, so is X*X under the obvious lexicographical order. A pair of elements x and y of X are said to be separated if there exists one or more z's such that x < z_1 < z_2 < .... z_n < y. Give an example of a well-ordered set containing infinitely many separated pairs. Prove that in no well-ordered partially ordered set is every pair separated. DM8) * Let the overspend encountered by the European Commission for a project with budget N ecus be x(N) ecus. Experience has shown that within your division x(N) = 3 n2 + N where n2 is the cost of a project half the size. Your Commissioner cannot cope with this method of budget estimation: can you offer him a closed form solution ? DM9) * `A hypercube offers the smallest diameter regular interconnection pattern for a given number of nodes.' Why is this not true, why are hypercubes ever used and what regular interconnection pattern achieves the lowest arity nodes for an arbitrary sized network ? DM10) Describe the use of dynamic programming to solve the integer knapsack problem. Why is the all-pairs shortest path algorithm in graph theory sometimes described as dynamic programming ? DM11) A set of N (distinguishable) elements may be partitioned into C different possible equivalence class partitionings. Give an expression (recurrence relation) for C(N+1) in terms of C(N). Give a closed form. --------------------------------------------------------------------------- > Foundations of Computer Science ML1) Give an ML definition of a datatype of a binary tree with integers at its nodes and leaves. i) Give a routine called P to print the numbers within the tree in ascending order. ii) Give a routine to return a tree which has the heap property given a random tree. Is using a heap the best way to achieve part i) using ML ? ML2) Give routines in Java and in ML which reverse a list with and without using continuation passing (four routines are required). How do they compare ? ML3) A square matrix can be represented as a list of lists. Write ML and Java routines to transpose such a matrix. ML4) Describe the facilities in ML for pattern matching. What happens if the same variable is given twice inside a single match clause ? ML5) Write an ML data type for a general lazy list and an instance of a lazy list which generates odd numbers. Write a function which returns a new lazy list from an input integer lazy list where multiples of five are missing. ML6) Define breadth-first search and provide a function which applies another function to the nodes of a binary tree under breadth-first order. ML7) Give an ML program which, given an arbitrary graph returns a pair containing a depth first spanning tree for the graph and a list of the unused back and cross edges. Define all these terms first. ML8) Write an ML function to raise an integer to the nth power in O(log n) steps. Rewrite the function to combine n copies of its argument with a given associative operator. Propose a representation for square matrices in ML and show how to use your code to raise a matrix to a power. ML9) Explain how a cyclic data structure can be created in ML. Write a predicate function which determines whether a data structure has cycles. --------------------------------------------------------------------------- > Java MT1) Describe the built-in data types of Java and the facilities for manipulating strings and sets. What would you say or do if you were asked by your software manager to define a datatype to handle a set of strings ? MT2) Explain how separate compilation of modules can be used in Java. What advantages and disadvantages does separate compilation have ? How does run-time loading of additional code work. When should applets be used ? MT3) Explain inheritance, method masking and supertype initialisation in Java. When is the keyword `this' needed ? MT4) Write a Java program to read a set of integers from a file and write them out to another file in ascending order. --------------------------------------------------------------------------- > Probability / Stochastic Processes P1) A game for two players involves throwing sticky lumps of slime at each other and the looser is the first person to have more than 10 lumps on his/her person. Not all of the slumps thrown hit the opponent of course, and they only stick for a while, depending on what the players are wearing. Lumps can be thrown at an average rate of one per second by all players and stick to Amanda for 20 seconds on average and to Beatrice for 35 seconds on average. If Amanda is only half as accurate at throwing as Beatrice, is it clear who will win ? (DO NOT ANSWER THIS IF YOU HAVE NOT STUDIED MARKOVIAN STOCHASTIC PROCESSES). p2) A system of 15 railway points allows trains to get from one source station to 16 destinations. If one set of points is broken, in that it is stuck in one position, what is the expected number of destinations that can now be reached ? P3) What is the probability that out of a class of 35 people two or more have their birthdays on the same day ? P4) If two machines make cakes and one of them has twice the probability of missing out all the currents, what is the probability that a given currentless cake was made by each machine, given that it was made by one of them ? P5) What is the chance of winning the National Lottery ? --------------------------------------------------------------------------- > Regular Languages and Finite Automata RLFA1) `Any non-deterministic finite state automata can be replaced with an equivalent deterministic one.' Explain and prove this and give an example of when it is useful. RLFA2) Give a syntax for a language of regular expressions (as a phrase-structured grammar or otherwise) and explain why it cannot be fully checked with a finite state automata. Give the equivalent regular expression for a finite state syntax checker which does the best it can to check your regular expressions. RLFA3) Design a programming language with regular syntax. Does a regular syntax allow one to make more silly programming mistakes than in most common languages (which have context-free syntax) ? Computing theory add on :Is it possible to implement all known algorithms in your pogramming language ? Is there a normal form for programs written in your language ? How do the answers to these two questions relate ? --------------------------------------------------------------------------- > System Architecture (Easter Term) SD1) Describe the typical sequence of actions that occurs on a typical Unix workstation (or PC if you must) from the time it is switched on to the time the first user application program starts running. SD2) What is likely to be found in the memory map of a microprocessor inside a CD player ? How can information about tracks the owner loves and hates be handled ? SD3) * Give three different ways of organising files on a disk. How do they perform in terms of writing speed and error recovery after a partial disk crash ? SD4) * How many types of identifier does a link editor deal with ? How is type checking across separately compiled modules normally achieved ? SD5) When should assembly language programming be used and when should it be discouraged ? Give an Intel x86 program to write Hello World to the console using a system call. SD6) Compare interpreted versus compiled programming. Is there an absolute distinction or is there a continuous spectrum of possibilities ? SD7) Describe the operation of and typical programming model for a UART. How and when are receive and transmit interrupts handled ? SD8) Describe a system where it is impossible for a user to execute code which has not been generated by the one built-in compiler provided with the system. How can such a system replace conventional system protection mechanisms. SD9) What busses are typically found on a PC motherboard and how can BIOS settings adjust system performance ? --------------------------------------------------------------------------- > Unix Case Study and Tools (Easter Term) U1) Describe Unix. Be concise and complete. U2) Give an implementation of the code found in the kernel to implement either pipes or sockets. U3) When does the Unix scheduler typically get called ? What is the function of the `signal' call in Unix? What is the definition of `signal' in concurrency textbooks? --------------------------------------------------------------------------- Software Engineering SE1) Answer the following (real-world) enquiry about use of free libraries: "What I am wondering about is the use of open source libraries in an application. Many open source licenses (eg. Mozilla Public License) require that if the open source software is modified, the changes must be made public and given back to the community. However, is building an application which uses the library source code to be understood as a change to the library - i.e. would we have to make the source of the whole application public? Where is the boundary between modifications to the library source and external code? If I write subclasses of a library class which extend its functionality, would they be understood as part of the library?" =========================================================================== End of Part One.