Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 2 c Solution by
Codex 0 2026-10-31
Assume both processes are available at time zero and run the listed order, A followed by B, with no overlap even during input-output. A takes ms; B then takes ms. ThusThe scheduling turnaround time includes the time waiting before a process first runs. Reversing the serial order would leave the total at 23 ms but change completion times to 7 and 23 ms, with mean 15 ms. If arrivals were instead delayed until each serial launch, that would define a different turnaround measurement; the simultaneous-arrival convention is used for comparing the schedulers below.
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 2 b Solution by
Codex 0 2026-10-31
With nonpreemptive scheduling, a running process retains the processor until it finishes its current CPU burst, blocks or voluntarily yields. With preemptive scheduling, the operating system may suspend a runnable process and select another one.
Time-slice preemption needs a hardware timer delivering an interrupt after bounded execution time, so control returns to the scheduler even if the running program never yields. Saving and restoring the execution context then lets the interrupted process resume later. The timer mechanism should remain under operating-system control.
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 2 a Solution by
Codex 0 2026-10-31
An input-output-bound process spends much of its time waiting for input-output, often with short CPU bursts between waits. A CPU-bound process spends most of its time doing useful CPU computation, with comparatively little blocking. These descriptions concern the bottleneck in the workload; an I/O-bound process still needs CPU time.
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 1 d Solution by
Codex 0 2026-10-31
For a single read-only memory implementing both the next-state and output equations, the address has four request bits plus three present-state bits. Each word contains three next-state bits and four grant bits. HenceThree D flip-flops store the state outside this combinational ROM. This is the direct truth-table implementation for the encoding above. A smaller factored implementation exploits the independence of the next-state equations from : a next-state ROM and an output ROM use stored bits in total, or the output decoder can be ordinary logic. These are different implementation organizations, not different state counts.
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 1 c Solution by
Codex 0 2026-10-31
All requester indices in the following expressions are interpreted modulo four. Let mean that requester is the first asserted request after last recipient :An empty logical conjunction is true. Decode the remembered index and combine the four priority orders:Exactly one is high when any request is high. Write as bits . The next-state function and Moore machine outputs areThus an idle step preserves the priority memory. The are combinational selection signals, not the current-cycle grants: exposing them directly as outputs would change the design into a Mealy machine. If a requester remains continuously asserted, each intervening successful grant advances the circular order, so it receives service after at most four grant decisions.
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 1 b Solution by
Codex 0 2026-10-31
Store three state bits: a two-bit index identifying the most recent recipient, and a valid bit indicating whether that recipient is receiving service in the current cycle. ThenWhen no requests are present at a decision edge, clear but preserve . Preserving implements round-robin arbitration with idle memory. Four possible last recipients each have an active and an idle state, giving eight states. The four idle states have equal outputs but different future priorities, so they cannot all be merged. One valid reset is , which gives requester zero first priority at startup.
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 1 a Solution by
Codex 0 2026-10-31
Use four request bits and four grant bits . A high requests service for the coming allocation period, and a high identifies the requester granted the resource during the current period. At most one grant may be high. An all-zero grant vector means idle. The synchronous sequential circuit also has a clock and an initialization signal.
Requests are sampled at a clock edge; the resulting allocation appears during the following cycle. This fixes the Moore machine timing convention: current grants depend on the stored state, rather than combinationally on requests that can change within the cycle.
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 8 d Solution by
Codex 0 2026-10-31
The diagram omits the type of UK products use Celsius and left-side road traffic; US products use Fahrenheit and right-side road traffic. Here
carType and the concrete constructors. Choose String selectors "convertible", "family", and "sports", no-argument concrete car constructors, and writable temperatureScale and driverSide properties on a fresh Car. Under this explicit interface convention the two methods are:abstract class Manufacturer {
def build(carType: String): Car
}
class UKManufacturer extends Manufacturer {
override def build(carType: String): Car = {
val car: Car = carType match {
case "convertible" => new Convertible
case "family" => new Family
case "sports" => new Sports
case _ => throw new IllegalArgumentException("Unknown car type: " + carType)
}
car.temperatureScale = "Celsius"
car.driverSide = "left"
car
}
}
class USManufacturer extends Manufacturer {
override def build(carType: String): Car = {
val car: Car = carType match {
case "convertible" => new Convertible
case "family" => new Family
case "sports" => new Sports
case _ => throw new IllegalArgumentException("Unknown car type: " + carType)
}
car.temperatureScale = "Fahrenheit"
car.driverSide = "right"
car
}
}driverSide denotes the side of the road, matching the wording of the source. If the field instead means the side occupied by the steering wheel/driver inside the car, its values must be reversed: right for UK, left for US. The diagram does not resolve that naming ambiguity. With constructor-only immutable properties, pass these same settings to the concrete constructors instead of assigning setters; that is a different interface convention, not a different national policy.Each branch allocates a fresh concrete
Car; it does not reuse mutable cars across orders. Invalid selectors fail explicitly rather than returning null. The base price and description come from the chosen concrete product. Options are applied afterward by wrapping the returned car; build(carType) has no option-list parameter and therefore cannot infer which options a customer wants. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 8 c Solution by
Codex 0 2026-10-31
For the factory method pattern,
Manufacturer is the abstract creator and declares build(carType): Car; UKManufacturer and USManufacturer are concrete creators. Car is the abstract product interface, and Convertible, Family, and Sports are concrete products. Each national creator selects one product software class from carType and configures the national settings. The diagram does not contain distinct families of national product interfaces or several abstract product-creation operations, so abstract factory pattern is not the most precise identification of this single-operation design.For the decorator pattern,
Car is also the component interface. Convertible, Family, and Sports are concrete components; Option is the abstract decorator, both a subtype of Car and associated with a wrapped Car. DieselEngine, AlarmSystem, and AutomaticTransmission are concrete decorators. Each delegates baseline behavior to its wrapped car, augments description, and adds its surcharge to price. National properties should delegate unchanged through decorators.A customer can compose options, for example
new AlarmSystem(new DieselEngine(baseCar)). Every layer remains usable through the Car interface; each layer adds its own description and price contribution. Factory methods choose/configure the base car, and decorators compose optional additions without requiring a subclass for every option combination. If applying each option at most once is required, enforce that as a separate ordering constraint; unrestricted decorator nesting alone permits repeated options. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 8 b Solution by
Codex 0 2026-10-31
The two patterns are the factory method pattern and the decorator pattern.
Manufacturer.build is the factory operation specialized by the two national manufacturer software classes. Option and its subclasses wrap a Car to add configurable behavior. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 8 a Solution by
Codex 0 2026-10-31
Use the iterator pattern when clients need sequential access to a collection's elements without depending on its internal representation. A collection supplies a traversal object with operations such as
hasNext and next; the client uses the same traversal interface whether the collection is an array, linked list, or another data structure.The iterator keeps the traversal state separate from both the collection and client, so several independent traversals can coexist and the representation can change without rewriting traversal logic. It can also support incremental or lazy evaluation of elements. Exhaustion must have defined behavior, and a mutable collection must define how updates during traversal are handled. The pattern does not by itself promise that arbitrary concurrent modifications are safe.
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 7 e Solution by
Codex 0 2026-10-31
Use a Scala For example,
object for the singleton pattern, and replace Performance with a version that reports to it. This code plugs into the source's Equipment, GymEquipment, and Functionality definitions; Prediction can remain an independent observer once its displayed string line break is made executable.object GymStandings {
private var scores = Map.empty[GymEquipment, Int]
def record(e: GymEquipment, calories: Int): Unit = {
scores = scores.updated(e, calories)
}
def remove(e: GymEquipment): Unit = {
scores = scores - e
}
def leaders: List[(GymEquipment, Int)] = {
if (scores.isEmpty) Nil
else {
val best = scores.values.max
scores.toList.filter { case (_, score) => score == best }
.sortBy { case (equipment, _) => equipment.name }
}
}
}
class Performance(e: GymEquipment) extends Functionality {
private def calories: Int =
((e.age - e.weight + e.heartRate) * e.time) / 10
e.addFunctionality(this)
GymStandings.record(e, calories)
def update(): Unit = {
val current = calories
GymStandings.record(e, current)
println("Your current performance is: " + current + " calories burned.")
}
}new Performance(treadmill) and new Performance(bike) attach two observers; later GymStandings.leaders returns the leading equipment/score pairs. Initial registration records the equipment's present score, even before its first subsequent update. Recording replaces the same equipment's previous score, so repeated notifications do not multiply its contribution. The explicit remove supports taking an equipment object out of the comparison; detaching its observer when its session ends also prevents later re-registration through another notification. In the original single-threaded event model no extra synchronization is needed.All equipment observers report to the same standings software object, and
leaders returns every maximum or Nil if empty. The query takes to find/filter scores for active equipment objects, plus sorting the tied names for deterministic presentation by name; equal names may remain in either order and still denote distinct equipment. This uses the exact supplied integer score formula and its integer division; it does not substitute a different performance metric. A functioning unsubscribe operation, if required, must explicitly correct the source to _functionalities = _functionalities diff List(f). Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 7 d Solution by
Codex 0 2026-10-31
Introduce one shared
GymStandings singleton object. It stores the latest current-performance score for every participating GymEquipment, using the equipment reference as key, and returns every equipment object tied for the maximum score. Performance.update sends each freshly computed score to this object. The previous observer pattern and its prediction observer remain in use.The added
Performance -> GymStandings dependency means “reports to,” while GymStandings -> GymEquipment represents the equipment keys in its stored score map. GymStandings is an software object, so clients share its unique instance instead of constructing one standings object per machine. The singleton pattern centralizes the current scores and the maximum-score query. Equipment objects, rather than user names, are the keys because two users can have the same name. Scores are current readings, not an accumulation of all historical notifications; the largest reported score wins, with all ties retained. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 7 c Solution by
Codex 0 2026-10-31
The system uses the observer pattern with a pull-style update.
Equipment provides the subject interface and stores registered observers; GymEquipment is the concrete subject. Functionality is the observer interface, with Performance and Prediction as concrete observers. Their constructors subscribe them with addFunctionality(this).When
GymEquipment.updateUserMeasures is called, it first updates both measurements through super, then calls notifyFunctionalities. Every subscribed observer receives update() and reads the new measurements from its stored equipment reference. Performance calculates the current score; Prediction calculates the score at time time+5, keeping the other quantities fixed. Since observers are prepended to a list, notification follows reverse registration order.The source has two independent implementation defects.
deleteFunctionality(f) computes _functionalities diff List(f) but does not assign it back, so it does not actually unsubscribe anything. The prediction message also contains a physical newline inside an ordinary quoted Scala string in the PDF; executable code must join that string, concatenate pieces, or use a multiline string. Neither issue changes the intended observer pattern. The source's score is treated as the specified arithmetic expression, not as an independently validated physiological model. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 7 b Solution by
Codex 0 2026-10-31
The UML class diagram below uses dashed hollow-triangle arrows for trait realization and ordinary arrows for stored references or navigable associations. Visibility is
+ for public and - for private.GymEquipment implements Equipment. Performance and Prediction implement Functionality, each retaining one GymEquipment reference and registering itself with that equipment. Each equipment keeps a list of zero or more Functionality references; one functionality can in principle be registered with multiple equipment objects through the public method, although the supplied constructors register it only with their own equipment. Hence the generic registration association does not imply exclusive ownership or composition in UML.There are two traits, one concrete equipment software class, and two concrete observer software classes.
GymEquipment implements name, age, and weight as read-only values and overrides updateUserMeasures; the mutable measurement state and observer list are defined privately in Equipment. The diagram reflects the source, including deleteFunctionality returning a new list rather than mutating the stored list. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 7 a Solution by
Codex 0 2026-10-31
Creational patterns organize object creation; behavioral patterns organize interactions and responsibility for behavior. A creational pattern controls how concrete software objects are selected, instantiated, or shared, so clients need not hard-code the entire construction policy. Examples include the factory method pattern and the singleton pattern.
A behavioral pattern describes how objects collaborate, receive requests, or distribute an algorithm's behavior. For example the observer pattern lets a subject notify dependants after its state changes, and the strategy pattern supplies interchangeable implementations of an operation. This distinction concerns the pattern's principal responsibility; a system can use both kinds together.
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 6 d Solution by
Codex 0 2026-10-31
Each The Scala assignment
play call should make at most one hit and return true exactly when it did so; the supplied while loop invokes it again to decide whether another hit is needed. Add these accessors inside Player:def cards: List[Int] = _cards
def cards_=(cs: List[Int]): Unit = { _cards = cs }
def visibleValue: Int = _visibleValue
def visibleValue_=(v: Int): Unit = { _visibleValue = v }temp.cards = cs calls the setter, and visibleValue += cards.head uses the getter followed by the setter. The list getter exposes an immutable list value; updating the player's field still goes through the setter. The supplied initialization and hit maintain the hidden card at the last list position and visibleValue == cards.init.sum for each nonempty dealt hand.The concrete software classes implement the supplied strategies literally:
class Regular extends Player {
def play(visibleCards: List[Int]): Boolean = {
require(visibleCards.length == 1)
val total = value
if (total < 21 && total <= 21 - visibleCards.head) {
hit
true
} else false
}
}
class Optimistic extends Player {
def play(visibleCards: List[Int]): Boolean = {
if (value != 21) {
hit
true
} else false
}
}
class House extends Player {
def play(visibleCards: List[Int]): Boolean = {
val total = value
if (total < 21 && visibleCards.forall(v => total <= 21 - v)) {
hit
true
} else false
}
}House receives all other players' final visible totals, whereas a non-house player receives the singleton containing the house's first visible card. The universal test implements “for each other player,” including the vacuously true case of no other players. Subtype polymorphism gives the common player list a Player interface, and dynamic dispatch chooses the appropriate play implementation.These are the literal missing methods, but the printed specification does not guarantee a terminating game. An optimistic player with total who draws reaches ; every further positive card keeps the total above , so
value != 21 remains true. The claim that only finitely many further cards are requested is therefore inconsistent with the optimistic strategy on such executions, in the intended arithmetic model without overflow. If the intended rule is “stop on reaching or exceeding 21,” the necessary correction is to replace its test by value < 21; that changes the printed strategy and is not silently made here.There is a second printed mismatch:
nextInt(10) yields , so 1 + nextInt(10) yields , not . Preserve the supplied hit when filling its missing pieces; generating every value from through would require an explicit change to nextInt(11) in both dealing and hitting.[ref]https://www.scala-lang.org/api/2.11.12/scala/util/Random.html#nextInt(n:Int):Int. Scala 2.11.12 Random.nextInt, upper bound is exclusive
No winner-computation code is requested; the supplied loop only deals and requests cards. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 6 c Solution by
Codex 0 2026-10-31
Two mechanisms are subtype polymorphism and parametric polymorphism.
With subtype polymorphism, a trait or abstract class declares an operation and concrete subclasses implement or override it. A
Player reference holding a House object invokes House.play through dynamic dispatch. The client is written against the common contract.With parametric polymorphism, a software class or generic method has a type parameter, such as
List[T] or def identity[T](x: T): T = x. The same definition works for many supplied type arguments, with static relationships between input and output types. Method overloading is another mechanism, usually called ad hoc polymorphism: alternatives share a name but are selected from their parameter signatures at compile time. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 6 b Solution by
Codex 0 2026-10-31
Programming language polymorphism permits one interface or piece of code to work with values of several types, while providing the behavior appropriate to those values. For example a routine that calls
play through a Player reference can use a Regular, Optimistic, or House object without knowing its concrete software class.Use programming language polymorphism when clients should depend on a common contract while concrete behavior varies, or when an algorithm is independent of the element type. It avoids duplicating client logic or repeatedly inspecting concrete runtime types, and supports extensions behind the same interface. A shared interface must still have meaningful behavioral guarantees: merely giving unrelated operations the same name does not establish that implementations can safely replace one another.
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 6 a Solution by
Codex 0 2026-10-31
The output is
1, with no newline. The Any in class B[Any] and class C[Any] is a type parameter name that shadows the standard type scala.Any inside those class bodies. Renaming it to T preserves the program's meaning. Thus new B[Int] has an inherited m(Double) and its own m(Int); obj1.m(1) selects the latter and prints 1. The call with 2.3 can only use the inherited m(Double), which computes a sum without printing.For
new C[Any], the supplied type argument is the standard scala.Any, so the overloads are m(Double) and m(scala.Any). The more-specific Double alternative accepts 4 by numeric widening, and accepts 5.6 directly. Both return sums without printing. A computed result is not automatically screen output. This reasoning uses the Scala 2.11 overload conventions of Question 5(a); type erasure does not turn either class's generic-argument overload into an method overriding of m(Double). Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact







