Computer science

Two armies on opposite hills must attack a city at the same time to win, and an army attacking alone is destroyed. The generals can communicate only by messengers who cross a valley and may be captured. Is there a protocol with a finite number of messages that guarantees the generals always attack…

$n$ generals must agree on whether to attack or retreat by exchanging oral (unsigned) messages, and up to $m$ of them are traitors who may send arbitrary messages. All loyal generals must reach the same decision, and if the commanding general is loyal they must follow the commander's order. For…

There are $n$ men and $n$ women, and each person ranks all members of the other group. A perfect matching is unstable if some man and woman both prefer each other to their assigned partners. Prove that a stable matching always exists, and give an algorithm that finds one in $\mathcal{O}(n^2)$ time.

You have 2 identical eggs and a building with 100 floors. There is an unknown threshold floor such that an egg breaks when dropped from that floor or above and survives from any floor below, and an egg that survives can be reused. What is the smallest number of drops that guarantees finding the…

A stream of $n$ items is read once, from left to right. Using only a constant number of memory words, find an item that occurs more than $n/2$ times, assuming such an item exists. Then explain how a second pass can check whether a majority exists at all.

A singly linked list either ends in a null pointer or eventually loops back into itself. Using $\mathcal{O}(1)$ extra memory and time linear in the number of nodes, decide whether it has a cycle, and if it does, find the first node on the cycle and the cycle length.

Given an array of $n$ integers, some possibly negative, find a contiguous subarray with the largest sum. For example, in $[-2,1,-3,4,-1,2,1,-5,4]$ the best subarray is $[4,-1,2,1]$ with sum 6. Give an $\mathcal{O}(n)$ algorithm and prove it correct.

100 prisoners are put in separate cells and taken one at a time, in an order chosen by the warden, to a room with a light switch that is initially off. Every prisoner will be brought to the room again and again, but no one learns anything except the state of the switch. On each visit a prisoner may…

A closed knight's tour on an $m\times n$ board is a sequence of knight moves that visits every square exactly once and ends a knight's move away from the starting square. For which $m\le n$ does a closed tour exist? As a first step, prove that none exists when $m$ and $n$ are both odd.

$n$ disks of different sizes are stacked on one of three pegs, largest at the bottom. A move takes the top disk from one peg and places it on another peg, never on top of a smaller disk. What is the minimum number of moves needed to transfer the whole stack to another peg? Prove your answer.