Tree Data Structure Definition of a Tree A tree is a data structure that must be connected and contain no circles. A single node is a valid tree. A collection of disconnected trees is a “forest”. A binary tree is a specific type where each node has at most two children.
Class and Object (Instance) A class is a blueprint for creating objects; an object is an instance of that blueprint. A circle requires a center point and a radius, which become the Circle class’s data fields. The center point is modeled as a Point class encapsulating x and y coordinates. Access Modifiers (public, private, package-default, protected) private: Members are accessible only within their class. Instance variables should be private to maintain data integrity (bank account analogy). public: Members are accessible from any class. Common for methods (like getters) that expose controlled access to private data. The main method must be public for the Java runtime to invoke it. package (default): If no modifier is specified, the member is accessible only within the same package. (BTW, don’t include package declarations from some IDEs when submitting to OJ.) protected: Mentioned in the context of inheritance (will be covered in a future lecture). Members are accessible to subclasses. Method Overriding vs. Overloading ...
Preface An Online Judge (OJ) is a platform where users submit code to solve problems and receive immediate feedback. DMOJ is a flexible, open-source OJ that supports customization. I’m a TA for a CS course covering Java and data structures, and I set up DMOJ to host practice problems and auto-grade submissions. This post documents the environment, installation notes, and a few customizations that worked well for our class. Environments Server: 8 vCPU, 16 GB RAM OS: Ubuntu 24.04 LTS Installation The official DMOJ docs provide a thorough step-by-step guide. The points below highlight gotchas and tweaks I encountered on Ubuntu 24.04. ...
Introduction In the MIPS architecture, an exception is a general label for interrupts and errors that require the processor to temporarily abandon sequential execution. An interrupt is an asynchronous request from an external device (e.g., timer, network), while a trap is a synchronous request from software (e.g., a system call). Errors detected inside the CPU (e.g., illegal instructions, misaligned accesses) are also treated as exceptions. When an exception occurs, the CPU saves the current program counter (PC) and status in dedicated registers, enters kernel mode, and jumps to an exception handler. ...
1. Introduction Is C always faster than other programming languages? Well, the performance of a program is ultimately determined by the machine instructions the CPU executes and how efficiently they use the underlying hardware. A high-level programming language is an abstraction, and the way it’s translated down to the processor’s Instruction Set Architecture (ISA), like MIPS or ARM64, is the primary factor behind its performance. Direct Compilation (C): A language like C is a relatively “thin” abstraction over the hardware. The C compiler’s job is to translate the code directly into a sequence of machine instructions for a specific ISA. A C statement like is_prime[j] = 0; can be compiled into a very small number of assembly instructions, similar to a sw (store word) instruction in MIPS that writes a value to a calculated memory address. This direct translation allows for maximum speed because there is no intermediary at runtime. ...
Useful Component in Logisim for the Simulation I/O To input or get the output from the circuit, we need to have I/O, and Logisim provides a component called Pin. It has some properties, for example, the Output? property will change the pin between the input mod and the output mod, and the Data Bits property can give us an easy way to input/output multiple bits. But since one wire can only contain one bit 1/0, when we want to get multiple bits from a pin, we need another component called Splitter. Similar to pin, the splitter also has properties to control the behavior. ...
The Complete Assembly Code Structure The first thing I’ve noticed about the assembly code file is the structure. Based on the comments, there are two parts of code segment and data segment. Code segment: .text .align # align number (not necessary) .globl [func name] (not necessary) [func name]: # something Data segment: .data [declaration of the data schema] name: type value Pseudoinstructions about Load Data Besides the lw instruction that we’ve learned in class, the simple assembly code uses li and la. After searching, I learned that these are some pseudoinstructions for loading. ...
The Maximum Network Flow Problem Let’s begin with some key ideas about the network flow problem and relevant concepts. Given a directed graph $G=(V,E)$, a source node $s \in V$, and a sink node $t \in V$. For each $e \in E$, there is a capacity, denoted as $c(e)$ or $c(u,v)$. When $(u,v) \notin E $, we assume $c(u,v)=0$. Our goal for the maximum flow problem is to push as much flow as possible from $s$ to $t$ in the graph (network). The rules are that no edge can have flow exceeding its capacity, and for any vertex except $s$ and $t$, the in to the vertex must equal the flow out from the vertex. That is, ...
Today I want to create an environment via conda, but I got an error when I typed the following command: $ conda create -n notion python=3.7 Channels: - defaults Platform: osx-arm64 Collecting package metadata (repodata.json): done Solving environment: failed PackagesNotFoundError: The following packages are not available from current channels: - python=3.7* Current channels: - defaults To search for alternate channels that may provide the conda package you're looking for, navigate to https://anaconda.org and use the search bar at the top of the page. By some searching, I first tried the command conda config --append channels conda-forge, but the problem still persists. ...
Stack and Heap The first thing to understand about ownership is to know about the stack and heap memory. This concept will be quite easy if you have learned C or C++, since they are almost the same. Stack Memory If you simply declare a variable in a function, then it will live in the stack. For example, the code below declares some such variables: fn main() { let a = 1; let y = plus_one(a); } fn plus_one(x: i32) -> i32 { x + 1 } The variables a, x, and y are all allocated and deallocated automatically, just like C/C++ compiler. ...