581. Big-O estimates for (n log n+n²)(n³+2) & (n!+2ⁿ)/(n³+log(n²+1)) are

Discrete Structures and Optimization • Asymptotic analysis • JUNE 2013

582. How many different Boolean functions of degree 4 are there?

Discrete Structures and Optimization • Boolean algebra • JUNE 2013

583. Test has 100 T/F questions; answers may be blank also. How many ways to answer?

Discrete Structures and Optimization • Counting • JUNE 2013

584. Which connected simple graph has exactly one spanning tree?

Discrete Structures and Optimization • Graph theory • JUNE 2013

585. How many edges must be removed to form a spanning forest with N vertices, M edges, C components?

Discrete Structures and Optimization • Graph theory • JUNE 2013

586. A vertex cover of G(V,E) is a subset V₁⊆V such that for every (u,v)∈E

Discrete Structures and Optimization • Graph theory • JUNE 2013

587. Conversion ∃u∀v∀x∃y P→Q to ∀v∀x(P(f(a),v,x,g(v,x))→Q(a,v,g(v,x))) is called

Discrete Structures and Optimization • Logic • JUNE 2013

588. Truth values of ∃!x P(x)→∃x P(x) and ∃!x ¬P(x)→¬∀x P(x) are

Discrete Structures and Optimization • Predicate logic • JUNE 2013

589. Compound proposition true exactly when two of p,q,r are true is

Discrete Structures and Optimization • Propositional logic • JUNE 2013

590. Relation “divides” on positive integers is

Discrete Structures and Optimization • Relations • JUNE 2013

591. In the simplex method, if Δⱼ=0 for a nonbasic variable, the solution is

Discrete Structures and Optimization • Simplex method • JUNE 2013

592. A BFS to m×n transportation problem is degenerate if positive allocations < m+n–1.

Discrete Structures and Optimization • Transportation problem • JUNE 2013

593. Transportation problem cost by Vogel’s method on matrix (given) is

Discrete Structures and Optimization • Transportation problem • JUNE 2013

594. Processors P₁…P_k execute in parallel iff Bernstein’s conditions hold pairwise: which?

Operating System • Concurrency • JUNE 2013

595. With semaphores S=Q=1, P1 does wait(S),wait(Q); P2 does wait(Q),wait(S); then signals—this can cause

Operating System • Concurrency • JUNE 2013

596. User–kernel switch time T₁ vs. process–process switch T₂: which is larger?

Operating System • Context Switching • JUNE 2013

597. Processes A,B,C,D arrive at 0,1,2,3 with CPU 8,4,9,5 and RR quantum=4 ms. Average turnaround is

Operating System • CPU Scheduling • JUNE 2013

598. Ten identical resources; P1,P2,P3 max(4,5,8); allocated state1=(2,3,4); state2=(0,2,4). State1/2 are

Operating System • Deadlock Avoidance • JUNE 2013

599. For FCFS disk queue [98,37,14,124,65,67] starting at 32, total head moves =

Operating System • Disk scheduling • JUNE 2013

600. The mv command changes

Operating System • File systems • JUNE 2013