| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Path: shlump.nac.dec.com!e2big.dec.com!decuac!haven!uflorida!mailrus!wuarchive\
!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu\
!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!uxa.cso.uiuc.edu!al21146
From: [email protected]
Newsgroups: sci.math
Subject: Problems
Message-ID: <[email protected]>
Date: 29 Apr 90 17:29:00 GMT
Lines: 43
Nf-ID: #N:uxa.cso.uiuc.edu:45100013:000:1866
Nf-From: uxa.cso.uiuc.edu!al21146 Apr 29 12:29:00 1990
T F 1. Let T be a given Turing machine. The question of whether T halts
on an empty input tape is undecidable.
T F 2. Let p and q denote two proositions. If p-->q is false, then
(~p or ~q)-->q is also false.
T F 3. The union of two equivalence relation is always an equivalence
relation.
T F 4. Out of a large number of pennies,nickels,and quarters, the number
of ways to select five coins is 21.
T F 5. A palindrome is a word that reads the same forwards or backwards.
The number of seven-letter palindrome that can be made out of
the 26-letter English alphabet is 1/2(26^7)
T F 6. Consider strings of 6 letters made up of the letters a,b,c The
number of strings in which each of a,b,c will appear at least
once is larger than 3(3^5-2^6)
T F 7. A sufficient condition for a graph to have an eulerian circuit is
that there are exactly twice as many edge as vertices.
T F 8. From Dijkstra's algorithm,one can conclude that an upperbound to
the complexity of the problem of finding the shortest path
between two given vertices in a graph is O(nlogn)
T F 9. Batcher's odd-even merge algorithm sorts n numbers in
O(nlog^2 n) time
T F 10. Given a constant k, it can be shown that any algorithm that sorts
n numbers. where each number is an integer between 0 and k,
requires time at least O(nlog n)
T F 11. For a finite state machine with n states, whether two states are
equivalent can be determined in O(n) time
T F 12. Assume n cities are connected by k highways. A highway is defined
to be a road between two cities that does not go through any
intermediate cities. If k> 1/2(n-1)(n-2) then one can always
travel between any two cities through connecting highways.
--------->> From general theory exam,1989
| T.R | Title | User | Personal Name | Date | Lines |
|---|