Computer Science - Practice Questions

Programming Langauges

• The C++ programming language has
  A. static typing
  B. automatic garbage collection
  C. standard template library
  D. compiler
  select all options that applies

  Answer: A, C, D

  • Static typing: the type has to be declared and once declared, it cannot be changed e.g. int a = 1
  • Automatic garbage collection: C++ does not have it, you have to do it manually.
  • Standard template library: C++ has STL library
  • Compiler: C++ has to be compiled. Python does not need a compiler.

• In the context of computer science, the term syntax refers to
  A. the complexity of a sentence
  B. the meaning of a sentence
  C. the grammatical structure of a sentence
  D. the size of a sentence
  select all options that applies

  Answer: C

  • syntax = grammatical structure

• In the context of computer science, the term semantics refers to
  A. the complexity of a sentence
  B. the meaning of a sentence
  C. the grammatical structure of a sentence
  D. the size of a sentence
  select all options that applies

  Answer: B

  • semantics = meaning

• Take the following Python function:

  def fun(s):
    if len(s) == 0 or len(s) == 1:
    	return True 
    else:
    	if s[0] == s[-1]: 
        return fun(s[1:-1])
    	else:
    		return False

• From the code, describe briefly what fun computes:

• Answer: Check if the input is palindrome e.g. “eye”, (1,3,1)

• From the code, What is the result of fun(“Hello World!”)?

• Answer: False

• From the code, What is the result of fun((4, 5, 6, 5, 4))?

• Answer: True

• From the code, What is the result of fun(4)?

  Answer: Error. int has no len() function.

Algorithms

Key concepts:

• Loop Invariant

  • Initialization, Maintenance, Termination

• Asymptotic Notations: $\Theta, O, \Omega$

  • $\Theta$ - tightbound, $O$ - upper bound, $\Omega$ - lower bound
  • We care about worst case and the average case in practical usage

• Divide-And-Conquer, Master Theorem, Dynamic Programming

  • Divide-And-Conquer split problem into n subproblems and then combine them back to the problem
  • Dynamic Programming store overlapping subproblems and store them into memory

• Greedy Algorithm

  • Greedy Algorithm aiming for first optimal part of the subproblem and then continue reaching problem

• P, NP, NP-Complete

  • $P$ : Solvable in polynomial time

  • $NP$: Verifiable in polynomial time

    • If A problem is P, then it must be NP.

  • NP-Complete: A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.

    • By performing Reduction, we can show a problem is NP-Complete

Analysis

• For any value of $n$, an algorithm with the runtime $100n^2$ runs faster than an algorithm with runtime $2^n$ (true/false).

  Answer: false We could find some $n_0 \ge 0$ where $2^n$ is smaller (faster) than $100n^2$ (you need to show for what $n_0$)

• The function $n^3/1000-100n^2-100n+3$ is of:

  a) $\Theta(n^3)$

  b) $\Theta(n^2)$

  c) $O(n^2)$

  d) $O(n)$

  Answer: a for a polynomial function the growth rate is of $\Theta$ of the largest exponent.

  • If there is an option e $O(n^3)$ the answer will be a, e

• Which one of the following methods improves the best-case running time of a sort algorithm?

  a) Check if the array is sorted, if so then do nothing.

  b) Check if only the first two elements are not in-place, if so then swap them.

  c) Check if only the last two elements are not in-place, if so then swap them.

  d) All of them.

  Answer: d each option improves the runtime for some input, hence improving the best-case.

• For any real constants $a$ and $b (b > 0)$, $(n+a)^b = \Theta(n^b)$ (true/false).

  Answer: true use the definition of $\Theta$

  • constant is not considered!

• Given that $f(n)$ and $g(n)$ are two asymptotically non-negative functions: $max(f(n),g(n)) = \Theta(f(n)+g(n))$. (true/false)

  Answer: true use the definition of $\Theta$

• The following statement is

  The running time of insertion sort is at least $O(n^2)$

  a) meaningless

  b) true only for some cases

  c) true for all cases

  d) false

  Answer: a it does not make sense to say the runtime of an algorithm is at least of $O$ (why?)

  • We dont care about the upper bound when we say it is “at least”

• Highlight the most appropriate representative element that describes each of the following rates of growth, e.g., the most appropriate representative of $4n^3 + n^2 + 3n$ is $n^3$.

  1. $20n^2 + 12n^{\ln(8)}+ 3n \ln(n) + 5n + 10$

     Answer: $n^{\ln(8)}$

     • $\ln(8) = 2.07$

  2. $30n + 145 \ln(n) + n \ln(n) + 312$

     Answer: $n \ln (n)$

  3. $1424n + 234n^2 + 21n^5 + 97n^3 + 9757$

     Answer: $n^5$

• Show that $2^n = \Theta(2^{n+1})$. Recall that $f(n) = \Theta(g(n))$ if $\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)}=c$ for some $0 < c < \infty$.

  Answer:
  $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \lim_{n \rightarrow \infty}\frac{2^n}{2^{n+1}} = \frac{1}{2}$

  $0 < \frac{1}{2} < \infty$

  Therefore $2^n = \Theta(2^{n+1})$

• Show that if $h(n) = O(f(n))$ and $t(n) = O(g(n))$, then $(h(n) + t(n)) = O(\max(f(n), g(n)))$. Recall that $f(n) = O(g(n))$ if $\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} < \infty$.

  Answer:

  $\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} = \lim_{n \rightarrow \infty}\frac{h(n)+t(n)}{\max(f(n), g(n))} = \lim_{n \rightarrow \infty}\frac{h(n)}{\max(f(n), g(n))} + \lim_{n \rightarrow \infty}\frac{t(n)}{\max(f(n), g(n))}$

  $\le \lim_{n \rightarrow \infty} \frac{h(n)}{f(n)} + \lim_{n \rightarrow \infty}\frac{t(n)}{g(n)}$

  ^note that the denominator is changed

  $< \infty$

  Therefore $(h(n) + t(n)) = O(\max(f(n), g(n)))$

Design

• Suppose an implementation of insertion sort with running time $8n^2$ and an implementation of merge sort with running time $64nlgn$. Then:

  a) The merge-sort implementation is faster than that of the inserstion sort

  b) The insertion-sort implementation is faster than that of the merge sort

  c) The insertion-sort implementation is faster only for $n \le 43$

  d) The merge-sort implementation is faster only for $n \le 43$

  Answer: c For $n_0 = 43$ the function $8n^2 \ge 64nlgn$

• A divide-and-conquer algorithm has the complexity $T(n) = 2T(n/4) + n^2$. This algorithm is of:

  a) $\Theta(n^2)$

  b) $\Theta(n^2lgn)$

  c) $\Theta(nlgn)$

  d) $\Theta(lgn)$

  Answer: a (use the master theorem – case 3)

  Master theorem rule:

  • $T(n)=a T(n / b)+f(n)$

  • Then $T(n)$ has the following asymptotic bounds

    1. If $f(n)=O\left(n^{\log _b a-\epsilon}\right)$ for some constant $\epsilon>0$,

       then $T(n)=\Theta\left(n^{\log _b a}\right)$

    2. If $f(n)=\Theta\left(n^{\log _b a}\right)$ ,

       then $T(n)=\Theta\left(n^{\log _b a} \lg n\right) = \Theta(f(n)\lg n)$

    3. If $f(n)=\Omega\left(n^{\log _b a+\epsilon}\right)$ for some constant $\epsilon>0$, and if $a f(n / b) \leq c f(n)$ for some constant $c<1$ and all sufficiently large $n$,

       then $T(n)=\Theta(f(n))$

  for $T(n) = 2T(n/4) + n^2$:

  $a = 2, b = 4, f(n) = n^2$

  $n^{log_42} < n^2$

  therefore it is case 3.

  then $T(n)=\Theta(f(n)) = \Theta(n^2)$

• Finding the shortest path between two nodes in an undirected graph has the optimal substructure. (true/false)

  Answer: true finding the shortest path between the source and a midpoint, and the midpoint and the destination gives us the shortest path between the source and the destination.

  • Let say we have a A-B-C-D route, A to D is basically equal to shortest path A to C + C to D

• Which greedy choice for the activity-selection problem gives us a correct solution:

  a) Selecting the last compatible activity that starts the latest

  b) Selecting the compatible activity of least duration

  c) Selecting the compatible activity that overlaps the fewest

  d) Selecting the compatible remaining activity with the earliest start

  Answer: a use the same theorem that we used in the class for selecting the first compatible activity that finishes first.

  • When using the greedy choice, we can also select the first compatible activity that finish the latest!

• Why a dynamic programming approach does not speed up Merge Sort?

  a) Merge sort doesn’t have subproblems

  b) Subproblems do not overlap

  c) Merge sort is already the fastest sorting algorithm

  d) Merge sort does not optimize anything

  Answer: b merge sort divides the subarrays in a way that they do not overlap.

  • Difference between Divide-and-Conquer and Dynamic Programming:
    • Divide-and-Conquer: Break problem into n subproblems and solve them, then combine them to problem
    • Dynamic Programming: Reusing subproblem solutions (has to be overlap) to solve the problem

Complexity

• Which one is definitely true?

  a) $P \cap NP = \emptyset$

  b) $P \not = NP$

  c) $P = NP$

  d) $P \cap NP \not = \emptyset$

  Answer: d We don’t know a,b, or c yet, but we know that d is true (use the definition of P and NP).

  $N P$ : verifiable in polynomial time

  $P$ : solvable in polynomial time

  Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP. (There is overlap part beween P and NP!)

• Which one is NP-complete?

  a) Finding the shortest path between two vertices in a graph

  b) The vertex-cover problem in a graph

  c) Finding the shortest path between all pairs of vertices in a graph

  d) Finding the Euler tour in a graph

  Answer: b

• Using the cloud-computing infrastructure such as Amazon AWS with seemingly boundless computational power, we can solve any decision problem. (true/false)

  Answer: false (example: halting problem)

---

OS

Key concepts:

• OS Pipeline

  • Fetching, Decoding, Executing

• OS architecture

  • Monolithic - calling services procedures

    • easy to implement, insecure

  • Layered - abstraction layers on top of the OS, memory management in separate layer

    • Secure

  • Microkernel - only one microkernel running in kernel mode

    • Secure

• Process

• Virtual Memory

  • managing virtual memory is done in the kernel mode
  • main memory came from RAM
  • virtual memory came from disk memory

Introduction

• Which one is not the goal of having an operating system?

  a) Providing an abstraction layer for hardware

  b) Managing resources such as CPU and memory

  c) Providing application program interface for programmers

  d) Protecting hardware from unauthorized access

  Answer: c providing an API is not a goal for OS (eventhough OS provides an interface for hardware)

• What is a batch system?

  a) A system specifically designed for numerical analysis

  b) A system that processes input and output

  c) A system that runs multiple programs as jobs

  d) A system that involves human intervention for input/output

  Answer: c

  • In a batch processing system, the tasks are collected into a batch
    • batch means “a quantity or number coming at one time or taken together”

• Which one is not part of a pipeline?

  a) Fetching instructions

  b) Decoding instructions

  c) Reading values of the operands from the disk

  d) Executing instructions

  Answer: c reading from disk is an I/O operation

  • Pipeline includes: Fetching, Decoding, Executing

• Which one is the main characteristic of a microkernel architecture?

  a) It is based on calling service procedures

  b) Only one module runs in the kernel mode

  c) Provides more layers of abstraction on top of the OS

  d) The memory management is in a separate layer

  Answer: b a is in the monolithic architecture. c and d are for the layered architecture.

• We only need to be in user mode to manage the virtual memory. (true/false)

  Answer: false managing virtual memory is done in the kernel mode.

Concepts

• Which one certainly involves at least one process?

  a) Firefox 69.0

  b) A tab in Firefox

  c) A window in Firefox

  d) An instance of Firefox running

  Answer: d the rest are not clear: Firfox 69.0 could be referring to the program. A tab or window in Firefox could be running within the main process, but not be the process itself.

  • If we know it is a running instance then we know it involves at least one process (process = running program)

• Which one is NOT an element of the program context?

  a) The program counter

  b) The stack pointer

  c) The program status word

  d) The value from the first layer of the cache

  Answer: d the first layer of cache could or could not have program context (not related).

• Every process in Linux has a parent. (true/false)

  Answer: false (the init process does not have any parent)

  • the process in Linux is like a tree; the root does not have any parent.

• Which one does NOT necessarily happen during creating a process:

  a) Assigning a unique process identifier

  b) Allocating space for the process

  c) Initializing the process control block

  d) Creating a main thread

  Answer: d if we don’t have multi-threaded programming available or enabled, d does not happen.

  • if we dont use multi-threaded programming then thread is not created

• Which one is NOT necessarily a way that a process terminates?

  a) Executing exit(0);

  b) Unhandled reading from a non-existent file

  c) A segmentation fault

  d) Executing kill by the parent process

  Answer: d kill sends a signal and does not necessarily terminate a process.

• If a thread in a process blocks, the entire process must also block. (true/false)

  Answer: false not necessarily, there could be other threads within the process in the ready state that can execute.

• Using the virtual memory expands the address space of the main memory. (true/false)

  Answer: true that’s one of the main reasons to use virtual memory.

  • main memory came from RAM
  • virtual memory came from disk memory

• An OS with good resource management:

  a) maximizes throughput

  b) responds differently to different processes

  c) minimizes response time

  d) all

  Answer: d

  a and c are obvious. c refers to prioritizing processes, for example based on whether they are I/O-bound or CPU-bound.

---

Propositional Logic

Key concepts:

• Suitable, Model, Valid, Satisifable

  • Suitable = all atomic propositions in a formula are assigned with truth value (0 or 1)
  • Model = a formula has to be suitable, and the output is 1
  • Valid = a formula that all the output is 1
  • Satisifable = a formula that at least 1 output is 1

• Truth Table

• CNF and DNF

  • clause = $(literal \vee literal)$
  • CNF = $(clause \wedge clause) = ((literal \vee literal) \wedge (literal \vee literal))$
  • DNF = $(clause \vee clause)$

• Semantic Equivalence

  • deMorgan’s law:

    • $\neg (X \vee Y) = (\neg X \wedge \neg Y)$
    • $\neg (X \wedge Y) = (\neg X \vee \neg Y)$

  • Distributivity:

    • $(X \vee Y) \wedge Z = (X \wedge Z) \vee (X \wedge Y)$
    • $(X \wedge Y) \vee Z = (X \vee Z) \wedge (X \vee Y)$

• Resolution Graph

  • $\square$ (empty clause) means unsatifiable
  • If any of the combined clause is $\square$ , the whole thing is unsatifiable!

Questions of Propositional Logic

• “If I run the 100 meter race faster than 10.0 seconds, I will be admitted to the Olympic games. Since I am not running the 100 meter race faster than 10.0 seconds, I will not be admitted to the Olympic games.” (true/false)

Answer: false ($p \longrightarrow q$ does not mean $\neg p \longrightarrow \neg q$)

• Note that $p \longrightarrow q = \neg p \vee q$ ; that means $p$ does not fully determine $q$.

• $F \longrightarrow (\neg A \longrightarrow (A \longrightarrow B))$ is:

  a) A tautalogy

  b) Satisfiable

  c) Valid

  d) All

  Answer: d The formula is a tautology/valid (and hence satisfiable).

  let A = 0, B = 0. $A \longrightarrow B = \neg A \vee B = 1$, $\neg A \longrightarrow (A \longrightarrow B) = 1$.

  In that case, if A = 1, B = 0, $\neg A \vee B = 0$. But $\neg A \longrightarrow (A \longrightarrow B) = 1$.

  That means $\neg A \longrightarrow (A \longrightarrow B)$ is always 1 and $F \longrightarrow (\neg A \longrightarrow (A \longrightarrow B))$ is always 1 too.

  Therefore it is both SAT (has 1) and Valid/tautalogy (all 1).

• According to the following blurb, what is the most simplified diet that the centenarian follows?

  “What is the secret of your long life?” a centenarian was asked.
  “I strictly follow my diet. If I don’t drink beer for dinner, then I always have fish. Any time I have both beer and fish for dinner, then I do without ice cream. If I have ice cream or don’t have beer, then I never eat fish.”

  a) Only drink beer!

  b) Drink beer and eat ice cream!

  c) Drink beer and do not eat fish!

  d) Drink beer, do not eat fish, and eat ice cream!

  Answer: d create an atomic proposition for each fact, and write the logical formula (or the truth table). The simplest correct form is d. (This is a tricky one)

• Which one of the following statements is true:

  1. If $(F \longrightarrow G)$ is valid and $F$ is valid, then $G$ is valid.
  2. If $(F \longrightarrow G)$ is satisfiable and $F$ is satisfiable, then $G$ is satisfiable.
  3. If $(F \longrightarrow G)$ is valid and $F$ is satisfiable, then $G$ is satisfiable.

  a) 1 and 2

  b) 2 and 3

  c) 1 and 3

  d) All

  Answer: c 2 is not necessarily true because it F and G might be satisfiable on different rows in their truth tables (write a counter-exmaple).

  Case1 :

  • $(F \longrightarrow G) = \neg F \vee G = 1$, and $F = 1$. In this case, $G$ must be $1$ because $\neg F$ is $0$. Thats why case 1 is true.

  Case2:

  • $(F \longrightarrow G) = \neg F \vee G = 0$, and $F = 1$. In this case, $G$ must be $0$ because $\neg F$ is $0$. (Counter example.)

  Case3:

  • $(F \longrightarrow G) = \neg F \vee G = 1$, and $F = 0$. In this case, $G$ can be $0$ or $1$.
  • $(F \longrightarrow G) = \neg F \vee G = 1$, and $F = 1$. In this case, $G$ can only be $1$.
  • So case 3 is also true.

• $B$ is equivalent to $(A \longrightarrow B) \wedge (\neg A \longrightarrow B)$ (true/false).

  Answer: true use truth-table

  $A = 0, B = 0, (A \longrightarrow B) = 1, (\neg A \longrightarrow B) = 0, (A \longrightarrow B) \wedge (\neg A \longrightarrow B) = 0$

  $A = 0, B = 1, (A \longrightarrow B) = 1, (\neg A \longrightarrow B) = 1, (A \longrightarrow B) \wedge (\neg A \longrightarrow B) = 1$

  $A = 1, B = 0, (A \longrightarrow B) = 0, (\neg A \longrightarrow B) = 1, (A \longrightarrow B) \wedge (\neg A \longrightarrow B) = 0$

  $A = 1, B = 1, (A \longrightarrow B) = 1, (\neg A \longrightarrow B) = 1, (A \longrightarrow B) \wedge (\neg A \longrightarrow B) = 1$

  • $(A \longrightarrow B) \wedge (\neg A \longrightarrow B) = (\neg A \vee B) \wedge (A \vee B) = B$

• Which one is an element of a formal logic?

  a) Syntax

  b) Semantics

  c) Proof system

  d) All

  Answer: d.

• Which one is a statement in propositional logic?

  a) There exists a positive integer x, where $x^2 \le x$

  b) For all real numbers x, $\sqrt x > x$

  c) $p \wedge q$ where $p$ and $q$ are Boolean variables

  d) All

  Answer: c

  a and b are first-order logic

• Which one indicates two formulas that are equivalent (multi-select):

  a) Two formulas with same truth tables

  b) All tautologies

  c) All unsatisfiable formulas

  d) All satisfiable formulas

  Answer: a, b, and c

  d is not true because two formulas can be true with different values on different rows of their truth tables.

  • two formulas that are equivalent when they have same All tautologies
  • two formulas that are equivalent when they have same All unsatisfiable formulas
  • But two formulas are not equivalent when they have same All satisfiable formulas

• Which formula is in CNF (multi-select)?

  a) $A \wedge B$

  b) $A \vee B$

  c) $\neg (A \wedge B)$

  d) $\neg A \vee \neg B$

  Answer: a, b, and d --definition of CNF

  a is CNF $(clause \wedge clause)$

  $b, d$ are a clause ($literal \vee literal$)

• There is a polynomial-time algorithm that converts any Boolean formula into a CNF equivalent. (true/false)

  Answer: true --Tseitin’s algorithm is one that we discussed in the class.

  • CNF —Tseitin’s algorithm—> CNF equivalent -------> SAT Solver

• Which one is NP-complete (multi-select):

  a) 2-CNF-SAT

  b) 3-CNF-SAT

  c) CNF-SAT

  d) Converting a CNF into a 3-CNF equivalent

  Answer: b and c– a is P because there is a polynomial-time algorithm for 2-CNF-SAT

  • Only CNF-SAT and 3-CNF-SAT are NP-complete!

• $F = (\neg (A \wedge B) \longrightarrow \neg A) \longrightarrow B$ is

  a) a tautology

  b) satisfiable

  c) valid

  d) false

  Answer: b --create the truth-table

  • $A = 0, B = 0, \neg (A \wedge B) = 1, (\neg (A \wedge B) \longrightarrow \neg A) = 1, (\neg (A \wedge B) \longrightarrow \neg A) \longrightarrow B = 0$
  • $A = 1, B = 0, \neg (A \wedge B) = 1, (\neg (A \wedge B) \longrightarrow \neg A) = 0, (\neg (A \wedge B) \longrightarrow \neg A) \longrightarrow B = 1$
  • $A = 0, B = 1, \neg (A \wedge B) = 1, (\neg (A \wedge B) \longrightarrow \neg A) = 1, (\neg (A \wedge B) \longrightarrow \neg A) \longrightarrow B = 1$
  • $A = 1, B = 1, \neg (A \wedge B) = 0, (\neg (A \wedge B) \longrightarrow \neg A) = 1, (\neg (A \wedge B) \longrightarrow \neg A) \longrightarrow B = 1$

  Since 0 and 1 both occur, it is not valid/tautology but only SAT.

• Which one is the consequent of $F = (\{\neg A, B\}, \{\neg B, C\}, \{A, \neg C\}, \{A,B,C\})$:

  a) A

  b) A and B

  c) A and B and C

  d) None

  Answer: c --use resolution

  • Note that we might get another consequent like {B, C} but it is not in the options.

• Propositional resolution is ____ proof principle for propositional logic.

  a) complete

  b) sound

  c) exponential

  d) awesome

  Answer: Propositional resolution is an exponential proof principle for propositional logic.

  • every time we perform resolution, we end up with more list.

• Given the following propositional logic formula $F = (A \vee B)\rightarrow C$, Which of the following assignments are suitable for this formula:

  a) $A = 1$
  b) $A = 0, B = 1$
  c) $A = 0, B = 1, C = 0$
  d) $A = 0, B = 0, C = 0 , D = 1$
  Select all options that might apply.

  Answer: c, d

  Suitable = every atomic proposition is assigned

• Given the following propositional logic formula $F = (A \vee B)\rightarrow C$, Which of the following assignments are a model for this formula:

  a) $A = 1$
  b) $A = 0, B = 1$
  c) $A = 0, B = 1, C = 0$
  d) $A = 0, B = 0, C = 0 , D = 1$
  Select all options that might apply.

  Answer: d.

  a and b can be ignored because they are not suitable

  For c: using the truth values we get $F = 0$. therefore it is not model.

  For d: using the truth values we get $F = 1$. therefore it is a model.

• Given the following propositional logic formula $F = (A \vee B)\rightarrow C$, Which of the following formulas are semantically equivalent to F and in conjunctive normal form (CNF):

  a) $(A \rightarrow C) \wedge (B \rightarrow C)$
  b) $(\neg A \vee C) \wedge (\neg B \vee C)$
  c) $(A \vee C) \wedge (B \vee C)$
  d) $A \wedge (B \vee C)$
  Select all options that might apply.

  Answer: b.

  $F = \neg(A \vee B) \vee C$

  For a: it is clearlty not in a CNF form. in fact a is exactly equal to b.

  For b: look at deMorgan’s law; $\neg(A \vee B) = (\neg A \wedge \neg B)$; and then Distributivity $(\neg A \wedge \neg B) \vee C = (\neg A \vee C) \wedge (\neg B \vee C)$

  Recall deMorgan’s law:
  $\neg(X \vee Y) = (\neg X \wedge \neg Y)$

  $\neg(X \wedge Y) = (\neg X \vee \neg Y)$

  Recall Distributivity:
  $(X \wedge Y) \vee Z = (X \vee Z) \wedge (Y \vee Z)$

  $(X \vee Y) \wedge Z = (X \wedge Z) \vee (Y \wedge Z)$

---

Multiprocess & Multithreaded

Key concepts:

• IPC : fork, dup2, pipe

  • Pipe[0] is for read
  • Pipe[1] is for write

• Thread

• User-level thread and kernel-level thread

  • OS is not aware of user-level threads.
  • kernel-level thread are managed by the OS kernel itself.

• Semaphore, Mutex

  • Semaphore:

    • sem_wait operation – count
    • sem_signal operation ++ count
    • the positive value in semaphore means how many available resources and negative value means how many threads are waiting.

  • Mutex:

    • A mutex has two states (0 or 1). It can be either locked or unlocked.
      • Use between critical section

• Race Condition, Critical Section

• Deadlock, Starvation

Questions of Multiprocess & Multithreaded

• How many “Hello, world!” is printed after running the following program?

  int main() {
    fork();
    fork();
    fork();
    std::cout << "Hello, world!\n";
    return 0;
  }

  a) 3

  b) 4

  c) 7

  d) 8

  Answer: d create the tree of the processes.

  • fork => 2^1 then fork => 2^2 then fork => 2^3

• If a thread blocks, the entire process blocks. (true/false)

  Answer: false other ready threads within the process can still run.

• Which one a user-level thread does NOT have:

  a) Execution state

  b) Execution stack

  c) Static storage for global variables

  d) An ID assigned by the OS

  Answer: d OS is not aware of user-level threads. Note the thread might still have an ID but it is not assigned by the OS.

• Which one is NOT a benefit of using threads:

  a) Faster creation

  b) Faster termination

  c) Faster context switch between threads

  d) Better inter-thread protection

  Answer: d because of shared memory between the threads there is actually less protection.

• In concurrency, a race condition refers to
  A. an access to a shared resource
  B. a competition between different threads
  C. an outcome that depends on the order of execution
  D. a constraint that execution of one thread excludes all the others
  select all that applies

  Answer: B

• In concurrency, a critical section refers to
  A. a section of a latex document that is most important
  B. a section of code that modifies shared data
  C. a section of code that always executes
  D. a section of code that requires atomicity select all options that applies

  Answer: B and D.

• You are given two programs A and B. You would like to execute the two programs in parallel such that the standard input of B is connected to the standard output of A and the standard input of A is connected to the standard output of B. Sketch a code for the main() function of the parent process that creates the above configuration. You might need to use the following system calls: fork(), dup2(), pipe(), close(), and exec(). You can write exec(A) to mean that program A is to be executed (i.e., don’t worry about the exact syntax of exec() family of commands). You will be graded on the general correctness of your solution, but not on the exact API usage and syntax.

Answer: see following code

int main()
{
	int AtoB[2]; int BtoA[2];
  pipe(AtoB); pipe(BtoA);
  pid_t kid;
  kid = fork();
  if (kid == 0)
  {
    dup2(AtoB[1]); // 1 is for write
    close(AtoB[0]); close(AtoB[1]);
    dup2(BtoA[0]); // 0 is for read
    close(BtoA[0]); close(BtoA[1]);
    exec(A);
  }
  kid = fork();
  if (kid == 0)
  {
    dup2(BtoA[1]); // 1 is for write
    close(BtoA[0]); close(BtoA[1]);
    dup2(AtoB[0]); // 1 is for read
    close(AtoB[0]); close(AtoB[1]); 
    exec(B);
  }
}

• 

  In Producer thread:

  • Use mutex to protect the critical section “add_item()”
  • After producing item, we have item available. therefore sem_wait(items): items => 1

  In Consumer thread:

  • Use mutex to protect the critical section “retrieve_item()”
  • To consume the item, we do sem_signal(items): items => 0

  

---

ADT

Key concepts:

• Data Property (Symmetry, Reflexivity, Transitivity)

  • Symmetric: $x \sim y, y \sim x$
  • Reflexive: $x \sim x$
  • Transitive: If $x \sim y$ and $y \sim z$, then it must be true that $x \sim z$

• Data Relation

  • No relation, Adjacency, Equivalence
    • Containers: hash sets & maps
  • Parital orderings, Hierarchical orderings
  • Linear orderings, Weak orderings
    • Linear orderings: array, vector, list, stack, queue, priority queue
    • Weak orderings: set, multiset, map, multimap
  • Implicit vs Explicit, Global vs Local
    • Implicit: using comparison symbols (>, <)
    • Explicit: using a class object

• Data Structure

  • List, Array, Stack (LIFO), Queue (FIFO)

• ADT

  • Examples of ADT: Set, List, Queue, Map, Graph

Questions of ADT

• Which one is NOT an ADT?

  a) Int in C++

  b) A class that implements a graph

  c) Boolean values in C++

  d) All of Above

  Answer: d all are implementation of an ADT, not an ADT iteslf.

• One key relation in Facebook database is “friendship” between two users. Which property holds for this relationship?

  a) Reflexivity

  b) Symmetry

  c) Transitivity

  d) Equivalence

  Answer: b

  a is not true because you are not a friend with yourself (in facebook, in real world hopefully you are!). c is not true because friendship does not ‘hop’ over poeple. d follows from a and c being not true.

• Which dataset does NOT have linear orderings?

  a) Bitmap of an image (only the colours)

  b) Real numbers

  c) The alphabet

  d) Memory address

  Answer: a the bitmap of an image does not have linear ordering (the coordinates of the pixels are).

• Any hierarchy ordering is transitive (true/false).

  Answer: true defintion of hierarchical ordering

  • partial ordering is also transitive!

• Which data relation is best to use to implement a proof system (for example a SAT-solver)?

  a) Linear ordering

  b) Hierarchy ordering

  c) Partial ordering

  d) Weak ordering

  Answer: c the proof can be shown as a partial ordering between proof statements (or a directed acyclic graph).

  • proof statements or DAG are Partial ordering!

• Which asymptotic relation can be used to define an equivalency class of functions?

  a) $O$

  b) $\Omega$

  c) $\Theta$

  d) All

  Answer: d show that all these relations are reflexive, symmetric, and transitive.

• The big-O notation defines a “weak ordering” on the asymptotically non-negative functions (true/false).

  Answer: true use the definition of weak ordering and the big-O notation.

• Which property is necessary for the following relation between the nodes in a directed graph: node B is reachable from node A:

  a) Reflexivity

  b) Transitivity

  c) Symmetry

  d) Equivalence

  Answer: b if node p is reachable through q, and node r is reachable through q, then node r is reachable through p as well. Note that a and c could be true too, but do not have to.

• The relationship of student data to the class data is:

  a) Hierarchical

  b) Equivalence

  c) Weak ordering

  d) Adjacency

  Answer: d use the definition of a, b, and c and none applies here.

  • Note that Adjacency is the most generic relation between two data objects.

• The data objects that represent intersections for a street grid are defined:

  a) Locally

  b) Globally

  c) Explicitly

  d) Based on a weak ordering

  Answer: a

Questions of Data Structures

• Which data structure is ideal to store the coordinates of the intersections in city of Waterloo:

  a) An array

  b) A singly-linked list

  c) A doubly-linked list

  d) All

  Answer: a small number of intersections that do not change very often, so we can use a fixed-size array and have a good performance.

  • Comparing Array and List:
    • Array: faster append and access
    • List: faster search and insertion

• We can implement a stack ADT using an array. (true/false)

  Answer: true use an array, and a variable that has the index of the top of the stack. Exercise: define all the methods of a stack for it.

• What is an ideal DS to implement process scheduling in an OS?

  a) A stack

  b) A queue

  c) A tree

  d) a hash table

  Answer: b based on prioritizing processes we can use a priority queue, or just a FIFO queue.

• Which data structure is ideal to implement the depth-first and breadth-first search, respectively, in a graph:

  a) An array and a linked list

  b) A linked list and an array

  c) A stack and a queue

  d) A queue and a stack

  Answer: c For depth-first you can use a stack, backtracking is popping from the stack. For breadth-first we use a queue to visit the nodes in an FIFO order.

  • BFS (use FIFO = Queue)
  • DFS (use LIFO = Stack)

• For which usage using a Tree is an ideal DS:

  a) Checking if a set of parantheses is balanced, for example, (())() is balanced.

  b) UNIX file system

  c) Function calls within a program

  d) List of symbols in a program

  Answer: b For a and c we can use a stack (why?), for d we can use an array (again why?). Tree is ideal for the hierarchical structure of the UNIX file system.

• A good size for a hash table that stores 2000 strings, and handles the average of a collision-chain of length 3 is:

  a) [2000/3]

  b) 700

  c) 701

  d) [2000/3]-1

  Answer: c (closet prime to [2000/3]

• Which one is NOT a characteristic of a good hash function?

  a) Uniform hashing

  b) Minimizes number of collisions

  c) Reduces the search-time to $O(1)$

  d) Reduces the insertion-time to $O(1)$

  Answer: d insertion-time in a hash is not as important as the time of finding an element (all a,b, c are related to that).

---

• 

def init_array(n):
  a = init_queue()
	for _ in range(n):
    push_back(a, 0)
  return a

def set(a, index, i):
  if index < 0 or index >= size(a):
    return error
  temp = init_queue()
  for _ in range(index):
    push_back(temp, pop_front(a))
  pop_front(a)
  push_back(temp, i)
  while(!is_empty(a)):
    push_back(temp, pop_front(a))
  a = temp

def get(a, index):
  if index < 0 or index >= size(a):
    return error
  temp = a
  for _ in range(index):
    pop_front(temp)
  return pop_front(temp)

• 

def Queue():
  s = Stack()
  return s

def Enqueue(x):
  Push(x)

def Dequeue():
  temp = Stack()
  while(Top()):
    temp.Push(Top())
    Pop()
  res = temp.Pop()
  while(temp.Top()):
    Push(temp.Top())
    temp.Pop()
  return res