47th BCS Technicalপ্রশ্ন ও সমাধান

Feature	Von Neumann Architecture	Harvard Architecture
Memory	Single shared memory for instructions and data	Separate physical memories for instructions and data
Bus	One common bus for both instructions and data	Separate instruction bus and data bus
Instruction execution	Needs multiple cycles (fetch then execute share the bus)	Can fetch instruction and access data in the same cycle
Simultaneous access	Not possible (bus is a bottleneck — the "Von Neumann bottleneck")	Possible, since paths are independent
Cost/complexity	Simpler, cheaper	More complex, costlier
Typical use	General-purpose PCs, laptops, servers	Microcontrollers, DSPs, embedded/signal-processing chips

graph TD
subgraph VonNeumann["Von Neumann Architecture"]
  M[(Shared Memory\nInstructions + Data)] <--> BUS[Common Bus] <--> CPU1[CPU: ALU + Control Unit]
end
subgraph Harvard["Harvard Architecture"]
  IM[(Instruction Memory)] <--> IB[Instruction Bus] <--> CPU2[CPU: ALU + Control Unit]
  DM[(Data Memory)] <--> DB[Data Bus] <--> CPU2
end

Exam takeaway: Von Neumann's single shared bus is simple but creates the "fetch vs access" bottleneck; Harvard's dual-bus design removes that bottleneck at the cost of extra hardware, which is why it dominates in performance-critical embedded/DSP chips.

A graph G = (V, E) is a set of vertices V connected by a set of edges E; in an undirected graph each edge {u, v} has no direction.

• Degree of a vertex = number of edges incident to it.
• Path = a sequence of distinct vertices where consecutive ones are connected by an edge.
• Cycle = a path that starts and ends at the same vertex, with no repeated edges/vertices in between.
• Connectedness = a graph is connected if there exists a path between every pair of vertices.

Eulerian vs Hamiltonian graphs

Aspect	Eulerian Graph	Hamiltonian Graph
Definition	Contains a closed walk that uses every edge exactly once	Contains a cycle that visits every vertex exactly once
Existence condition	Connected graph where every vertex has even degree	No simple general condition (NP-complete to decide)
Focus	Edge-covering	Vertex-covering
Classic example	K4 is not Eulerian (odd-degree vertices); a cycle graph Cₙ is Eulerian	K4 (complete graph on 4 vertices) is Hamiltonian

graph LR
A((A)) --- B((B))
B --- C((C))
C --- D((D))
D --- A
A --- C

The graph above (a 4-cycle plus one diagonal A-C) has vertices of degree 3,2,3,2 — since A and C are odd-degree, it is not Eulerian, but a Hamiltonian cycle A→B→C→D→A visiting every vertex once does exist, so it is Hamiltonian.

Exam takeaway: Eulerian-ness is easy to check (even degree + connected) and solvable in polynomial time; Hamiltonian-ness has no such shortcut and is NP-complete in general — the two properties are independent of each other.