MikeChen's Blog

Expressions are formed from these atomic elements: data and operators . Data may be represented either by variables or by constants. Like most other computer languages, C/C++ supports a number of different types of data. It also provides a wide variety of operations. Five basic data types There are five atomic data types in the C subset: char, int, float, double, and void The size and range of these data types may vary between processor types and compilers. In all cases a character is 1 byte. The size of an integer is usually the same as the word length of the execution environment, can be 16 bits or 32 bits. To the five basic data types defined by C, C++ adds two more: bool and wchar_t. Modifying the basic types You use a modifier to alter the meaning of the base type to fit various situations more precisely. The list of modifiers is shown here: signed unsigned long short When a type modifier is used by itself (that is, when it does not precede a basic type), the

In this semester, i enroll a module called C++ programming, aiming to learn Cpp in a systematic way. So from then on, i might rewrite the sorting algorithm in C++. Also, it will also be a recording to my learning road on C++, the structure and language might not be so precise. Acknowledgement C++ Prime The Complete reference: C++, 4th edition http://www.learncpp.com/ Content C is a middle level language Separate Compilation Most short programs are completely contained within one source file. However, as a program’s length grows, so does its compile time (and long compile times make for short tempers). Hence, C/C++ allows a program to be contained in multiple files and lets you compile each file separately. Once you have compiled all files, they are linked, along with any library routines, to form the complete object code. Compile Link with library Complete object code The advantage of separate compilation is that if you change the code of one file, you do not ne

Priority Queue and Heap A priority queue stores a collection of entries Each entry is a pair (key, value) A heap is a binary tree storing key-value pairs at its nodes and satisfying the following properties: Heap-Order : for every internal node v other than the root key(v) >= key(parent(v)) It is a complete binary tree Motivation We have three ways to implement priority queue unsorted list (O(1) for insert but O(n) for removeMin() and min()) sorted list (O(n) for insert but O(1) for removeMin()) Heap(Explain later) We want to find a data structure which can optimize priority queue operation to be better than O(n). Then, we find heap, which gives us O(logn) due to the usage of binary tree. The difference between priority queue and Maps(HashMaps)? Both have key and values. Two distinct entries in a priority queue can have the same key. But in hashmap, the key should be different. Is it a reason why PQ doesnt have find(key)? Why? It is because in pr

Amortized analysis Why talking about amortized analysis When we are learning “Vector” in ACE class, we came up with a growable array-based vector. We want to know what if we execute “push” operation, but the array is full. Instead of throwing a exception, we would like to replace the array with a larger one Algorithm push(o) if t = s.length -1 then A <- new array of size ... for i <- 0 to t do A[i] <- S[i] t <- t+1 A[t+1] <- o garbage collection S From pseudo-code above, what should be the size of the new array? There are two simple strategy you can came up with quickly • incremental strategy: increase size by a constant c • doubling strategy: double the size What is the common analysis for this question? Suppose some individual operation (such as ‘push’) takes time T in the worst-case. So for the total s operations, the worst-case time should be sT(upper bound) • however, such an upper-bound might not ever occur. Because the

Introduction to languages Overview In this year, i enrolled a module called Language and Computation which will cover automata theory, languages and computation. In the very first view, we need to define what are languages and the related terms. Reference : Introduction to Automata Theory, Languages, and Computation. A language is a (possibly infinite) set of words. A word is a finite sequence (or string) of symbols. ε denotes the empty word, the sequence of zero symbols. A symbol is anything, but it has to come from an alphabet Σ which is a finite set A common (and important) instance is Σ = {0, 1}. ε, the empty word, is never a symbol of an alphabet. alphabet so what is the difference between “alphabet” and “symbol”? On the reference book 1.5.1, it says, “an alphabet is a finite, non-empty set of symbols” Conventionally, we use the symbol Σ for an alphabet. Common alphabets include: 1. Σ = {0, 1}, the binary alphabet 2. Σ = {a, b, …, z}, the set of all lower-

1.A computer system is mainly used for non-interactive work where jobs (processes) arrive randomly, persist until completed and then leave the system. There may be many processes that need scheduling concurrently. Describe two process scheduling algorithms that would be suitable for this system and explain why they are appropriate. A different system deals mainly with multiple, concurrent, interactive processes. Give two process scheduling algorithms for this situation and explain why they are appropriate. A new system is to be developed that will run a mix of the two types of processes. Are any of the previous scheduling algorithms appropriate? Describe one new algorithm that could be used. First, we should know what the question is really asked about? non-interactive work is like you open one process, the result is done. If you scroll the page by mouse, it is a interactive work because you make an I/O and the computer response. Also a non-interactive work is like CPU bounded. So

Repository Tools for SWM Trello Trello is a project management tool Can be used to organise individual project, but especially useful for teams Basic version is free Work in process(WIP) limits: Treat the cards like a limited currency – prevents overloading developers Pros: Free!(at least the basic version) Open to members and non-members Private or Public Boards(limited to a group of members or anyone) Natural user interface, support for agile projects Ease of use, visibility and tracking, collaborative Available on Iphone/Android/Windows Developer API supports Agile feature Cons: Cards/tasks cannot be assigned to multiple boards/projects No tagging capability Difficult to move/copy etc. multiple cards No due dates per tasks Checklist are not easily visible inside cards Have to pay for the full experience Managing source code Using a source code version control or repository system, such as git, SVN(SubVersionN), CVS(Concurrent Versioning system) Why

Software Maintenance 2 Coding tools for SWM There are tools and processes in eclipse which will help you with software maintenance tasks Adding documentation Working with build files(to control your compilation, testing and deployment steps) Building a test suite(for regression testing) Javadoc comments Special comments embedded in the source code, which can be used by Eclipse and by a tool to generate HTML documentation /**....*/ <-note the extra first asterisk Tags are keywords that do special things, such as @param, @return, @see Javadoc in Eclipse–> Project->Generate Javadoc Build files(ANT, Maven, Gradle) also known as build scripts a set of instructions for how the project should be ‘compiled’ or built Eclipse handles some of this for you automatically But as projects get bigger or more complex, or rely on more external resources, custom build scripts are needed. They can build in dependencies, package files, run tests, deploy software etc. Why us

Software Maintenance 1 3 main categories of maintenance Corrective maintenance Fixing errors in the system e.g. Bugs Adaptive maintenance Modifying due to changes in the environment of the software e.g. new laws, change of business needs Perfective/performance maintenance Improving system without changing its functionality e.g. improving performance, ease of maintenance What do you need to know to do maintenance? Understanding the client Understanding the code Refactoring the code Extending the code Working as a team Managing client expectations Managing maintenance process Useful OO concepts Abstraction: concentrating only on essential characteristics; allows complexity to be more easily managed Inheritance: One object acquires the properties of another; information is made manageable in a hierarchical order Encapsulation: Hiding internal state and requiring all interaction to be performed through an object’s methods Modularity: The source code fo

1.Using a simple system call as an example (e.g. getpid, or uptime), describe what is generally involved in providing the result, from the point of calling the function in the C library to the point where that function returns. A system call is completed as follows: As the function is called, an interrupt of the type “software exception” is placed on the processor, causing a Context Switch to take place between the calling function and the kernel. The exception handler will clear out and save user registers to the kernel stack so that control may be passed on to the C function corresponding to the syscall. The syscall is executed. The value(s) returned by the syscall is placed into the correctly corresponding registers of the CPU The handler takes this value, restores user registers and returns said value to the user program that called it. 2.Describe a sequence the sequence of step that occur when a timer interrupt occurs that eventually results in a context switch to anothe

1.List two examples where it is important for the operating system to take the architecture of the hardware into account. Processes : multi-core scheduling, processor affinity, true parallelism Memory : large memories, multi-level page tables, inverted page tables, MMU, TLB FS + Disks : solid state disks eliminate rotational latency/seek times, disk scheduling becomes less important, no rotational delays, FCFS becomes more practical 2.Keeping in mind the implementation differences between threads and processes on an operating system level, explain why thread creation and switching are faster than process creation and switching. Thread control blocks contain less information, less data structures have to be created . Hence, creating the thread control block is much faster than creating the process control block Since threads share memory with processes , the memory map/page table does not change when a context switch takes place between threads. Also the TLB entries remain va

Virtualization Fundamental idea: Virtual Machines Abstract hardware of a single computer into several different execution environments. Similar to layered approach, but layer creates virtual system(virtual machine, or VM) on which operation systems or applications can run several components The base is hardware, and there is a VMM, on the top is different server on different OS We have already seen that an OS virtualises(Why?) Virtual Memory Virtual file system However, a VM virtualises an entire physical machine: Providing the illusion that software has full control over the hardware As implication, you can run multiple instances of an OS(or different OS) on the same physical machine Components Host -underlying hardware system Virtual machine manager(VMM) or hypervisor - creates and runs virtual machines by providing an interface that is identical to the host(Except in the case of paravirtualization ) Guest -process provided with virtual copy of the host(us