Show Menu
Cheatography

COMP2123 Cheat Sheet (DRAFT) by

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Bashshell Basic Commands

gedit exampl­e.txt &
create a new empty file

1.1 Bashshell Directory Manipu­lation

pwd
Name of the current directory
cd dir
change the directory to cd
cd ~
Change to home directory
cd ..
Change to parent directory
cd .
Change to current directory
mkdir dir
Creates a new directory
rmdir dir
removes a directory
rm -rf dir
Removes non-empty directory dir and all of its subdir­ect­ories and files
mv dir1 dir2
Rename dir1 to dir2

1.2 Bashshell File Manipu­lation

gedit hello.cpp &
Starts the gedit program to edit file hello.cpp
g++ hello.cpp -o hello.o
compile hello.cpp to create executable a.o
./a.o
invoke a.o
cp file1 file2
Copy file1 into file2
cp -r dir1 dir2
Copy dir1 (including its subdir­ect­ories) to dir2
mv file dir
moves file to dir
rm file
remove file
rm dir
remove all files and direct­ories in dir
touch file
Create an empty file called file
cat file
Display the content of file

File Security and Permission

ls -lt print in long form with security level indication
chmod [who] [operator] [permi­ssions] filename
[who] u = user; g = group; o = other; a = all
[operator] + = add; - = remove; = set
[permi­ssion] r = read; w = write; x = execute

1.3 Bash Shell Searching

find . -name "­hel­lo.t­xt­" -type f
Search by name for a file
find . -name "­hel­lo.*­" -type f
Search any file type with the name "­hel­lo"
find . -name "­hel­lo" -type d
Search for a directory called "­hel­lo"
find . -name "­*.c­"
find .c files
`find . -name "­*.[­ch]­"
find .c and .h files
grep '^apple' example
match beginning of a line
grep 'apple$' example
match the end of a line
grep '^apple$' example
match the exact contents of a line
grep 'p?' example
match zero or one occurrence
grep 'p+' example
match one or more occurr­ences
grep 'p*' example
match zero or more occurr­ences
grep 'p.' example
match a single character "­p"
'[12345]' or '[1-5]'
match any character enclosed by []
(ab){3}
3 occurr­ences of "­ab"
(ab){1,3}
1 to 3 occurr­ences of "­ab"
(ab){3,}
3 or more occurr­ences of "­ab"
grep -c "­UNI­X" bar.txt
no. of occurrence for "­UNI­X"
sed s/UNIX­/Unix/g bar.txt
replace all "­UNI­X" to "­Uni­x"
Note that (ab) can also be other valid patterns

1.4 Useful Bash Shell Commands

wc -c file
return no. of bytes
wc -l file
returns no. of lines
wc -w file
returns no. of words
sort file
sort file in alphab­etical order and output the sorted texts
sort -n file
numerical sort
sort -n -r file
-r for reverse sort
sort -k3 -n filename
sort by field no. 3
sort -t, -k3 -n filename
sort by field no.3 but the delimiter is comma
cut -d ' ' -f 1,3 example1
return 1st and 3rd columns where the delimiter is a space
uniq file
remove adjacent duplicate lines
diff fileA fileB
how to transform fileA to fileB
0a1
add the line1 of fileB after line0 of fileA
2,3C3
change line2,3 of fileA to line3 of fileB
spell file
display all incorrect words in file
su
change to super user mode
yum install [program]
install program

1.5 Standard I/O and pipe

wc data.txt 1> result.txt
send standard output to file
wc data.txt > result.txt
same as above
[command] >> file
append result of [command] to the file
[command] 2> file
send standard error to file
./add.o < input.txt > output.txt
add.o takes input from input.txt and output to output.txt
ls -l | grep "Jan 25"

C user input

int a; float b; 
scanf("%d%f", &a, &b);
printf("%g", a*b);

C++ const keyword

BigInteger add(const BigInteger & a, const BigInteger & b)
{
  // Cannot modify any of the parameters
}

string BigInteger::setNumber(string number) const {
  // setNumber is a read-only function. 
  sign = "-"; // error because sign is a member variable of BigInteger
}

C++ Constr­uctor

class Point{
private: 
  int x, y; 
public:
    Point() { // default
      a = 10; b=20
    }
    Point(int x1, int y1){ // parameterised
      x = x1; y = y1;
    }
}

int main(){
  Point p; // default
  Point q(10, 20); // parameterised
}
Constr­uctor is a member function that shares the same name as the class

C++ friend

// --- In .h file --- 
class BigInteger{
  public:
    void setNumber( string );
    string getNumber();
  private: 
    char sign;
    int length; 
    int value[100];
  friend BigInteger add(BigInteger a, BigInteger b);
};

BigInteger add(BigInteger a, BigInteger b); 
// add declaration of friend function AFTER the declaration fo the big integer class

// --- in .cpp file --- //
BigInteger add(BigInteger a, BigInteger {
  // implement the function
}
 

2.1 Shell Script basics

echo -n "­hello world"
print without \n
read name
read user input and store it in a var called "­nam­e"
a=apple
no quote
a='apple pie'
single quote (strings)
a="$­a\$­"
can handle special characters
$
variable substi­tution
\
escape special characters
`cat hello.txt`
enclose bash commands
a="`wc -l file | cut -d\"­\" -f1`"
echo "­there are $a lines in file"

2.2.1 Shell Script - Using Strings

${#a}
length of string
${a:po­s:len}
substring (assume index 0)
${a/fr­om/to}
change part of string
a="Apple pie"; from="p­ie"; to="­jui­ce";

2.2.4 Shell Scripting - Variable as numbers

let "­a=$­a+1­"
increment a by 1

2.3 Shell Scripting - Control Flow

# --- if-else statements --- #

if [ condition ]
then
  echo "Action 1"
elif [ condition2 ]
then
  echo "Action2"
else 
  echo "Action neither"
fi
#example
#!/bin/bash
echo "Do you want to remove all .cpp files (Y/N)"
read ans
if [ "$ans" == "Y" ]
then
  rm -rf *.cpp
  echo "All .cpp files are removed"
fi

# --- for-in loop --- #

#!/bin/bash
list="1 2 3 4 5"
for i in $list
do 
  echo "This is iteration $i"
done 

# --- for-loop with a range --- #

for ((i=0; i<=100; i=i+3))
do
  echo $i
done

2.4 Shell Scripting - Useful techniques

$#
number of arguments input by user
$0; $1; $2
1st argument, 2nd argument, etc
cp file123 fileabc 1> /dev/null 2> &1
/dev/null is system dust bin
&1 is the standard output
echo "­$0:­err­or:Copy failed­" >&2
&2 is error output

Shell Script Conditions

String comparison
[ "­$s" ]
iff length of s is non-zero
[ "­s1" == "­$s2­" ]
[ "­$s1­" != "­$s2­" ]
[ "­$s1­" /> "­$s2­" ]
s1 sorted after s2
[ "­$s1­" /< "­s2" ]
File Checking
[ -e $file ]
iff exists
[ -f $file ]
iff is a file
[ -d file ]
iff is a directory
Number Comparison
[ $a -eq $b ]
iff a = b
[ $a -ne $b ]
iff a!=b
[ $a -lt $b ]
iff a<b
[ $a -le $b ]
iff a<=b
[ $a -gt $b ]
iff a>b
[ $a -ge $b ]
iff a>=b

Iterate words in a file

list=`cat wordlist.txt`
for line in $list
do
  echo "$line"
done

C++ Misc

void func(int array[]); // array as parameter

C++ Dynamic Array

int * a = NULL; int n; 
cin >> n; a = new int[n];
...
delete[] a; // free memory

Pointers C++

int *baz
define a pointer
&foo
address of foo
*baz
value pointed by baz
void PBV(int *p)
parameter is a pointer
void PBR(int *&p)
parameter is address of pointer
modifying the parameter modifies the original variable

C++ Linked List and Various functions

int main(){ Node *head = NULL; ... }
void headInsert(Node *&head, int k, int v){
    Node *newNode = new Node;
    newNode -> key = k;
    newNode -> value = v;
    newNode -> next = head;
    head = newNode;
}
void printList(Node *head){
    Node *current = head;
    while (current!=NULL){
        cout << "Key:" << current->key << ",value:" << current->value << endl;
        current = current->next;
    }
}
bool isSorted(Node *head){
    Node *current = head;
    Node *previous = NULL;
    while (current!=NULL){
        if (previous !=NULL){
            if (previous->key > current->key)
                return false;
        }
        previous = current;
        current = current->next;
    }
    return true;
}
void insertInOrder(Node *&head, int k){
    Node *newNode = new Node;
    newNode->key = k;

    if (head == NULL)
    {
        newNode->next = NULL;
        head = newNode;
    }
    else
    {
        Node *current= head;
        Node *previous = NULL;
        while(current!=NULL)
        {
            if (current->key > k)
                break;
            previous = current;
            current=current->next;
        }
        newNode->next = current;
        if (previous!=NULL)
            previous->next = newNode;
        else
            head = newNode;
    }
}

4. Separate Compil­ation and Makefile

census.o: census.cpp BigInteger.h Country.h
  g++ -c census.cpp

BigInteger.o:BigInteger.h BigInteger.cpp
  g++ -c BigInteger.cpp

Country.o:BigInteger.h Country.h Country.cpp
  g++ -c Country.cpp

census:census.o BigInteger.o Country.o 
  g++ census.o BigInteger.o Country.o -o census

C++ Traverse Linked List using for-loop

void TraverseList(Node *head){
  for(Node *n = head; n -> next != NULL; n = n -> next){//do something to n}
}

C++ Operator overlo­ading

// Using friend functions
BigInteger operator+(const BigInteger &a, const BigInteger &b);
istream &operator >> (istream &cin, BigInteger &b);
ostream &operator << ostream &cout, BigInteger &b);

C AVL Tree - Node and maximum

struct treeNode { 
  int key; struct treeNode * left; 
  struct treeNode * right;
}
typedef struct treeNode treeNode; 
int maximum(int a, int b){
  return (a > b ? a : b);
}

C AVL - Rotation Functions

treeNode* R_rotation(treeNode *parent){
    treeNode *child = parent -> left;
    parent -> left = child -> right;
    child -> right = parent; return child;}

treeNode* L_rotation(treeNode *parent){
    treeNode *child = parent -> right;
    parent -> right = child -> left;
    child -> left = parent; return child;}

treeNode* LR_rotation(treeNode *parent){
    treeNode *child = parent -> left;
    parent -> left = L_rotation(child);
    return R_rotation(parent);}

treeNode* RL_rotation(treeNode *parent){
    treeNode *child = parent -> right;
    parent -> right = R_rotation(child);
    return L_rotation(parent);}

C AVL - Insert()

treeNode* Insert(treeNode *currentNode, int key){
  if(currentNode == NULL){		
    currentNode = (treeNode*)malloc(sizeof(treeNode));
    currentNode -> key = key; 
    currentNode -> left = currentNode -> right = NULL;
  } 
  else if(key > currentNode -> key){
    currentNode -> right = Insert(currentNode -> right, key);
    currentNode = balance_tree(currentNode);
  }
  else if(key < currentNode -> key) {
    currentNode -> left = Insert(currentNode -> left, key);
    currentNode = balance_tree(currentNode);
  }
  else { 
    printf("fail! - duplicated key \n");
    exit(-1);
  } 
  return currentNode; 
}

C AVL - get_height

int get_height(treeNode *currentNode)
{
  if(currentNode == NULL)
    return 0; 
  else{
    int height = 1 + maximum(get_height(currentNode->left), get_height(currentNode->height)); 
    return height; 
  }
}

C AVL - getBal­ance()

int get_balance(treeNode * currentNode){
  if(currentNode == NULL) return 0; 
  else return get_height(currentNode->left) - get_height(currentNode->height);
}

C AVL - balanc­e_t­ree()

treeNode* balance_tree(treeNode * currentNode){
  int height_diff = get_balance(currentNode);
  if(height_diff > 1)
  {
    if(get_balance(currentNode -> left) > 0){
      currentNode = R_rotation(currentNode);
    } else {
      currentNode = LR_rotation(currentNode);
    }
  } else if(height_diff < -1){
    if(get_balance(currentNode->right) < 0){
    currentnode = L_rotation(currentNode);
    } else {
      currentNode = RL_rotation(currentNode);
    }
  }
  return currentNode; 
}

C AVL - main()

int main(){
  treeNode *root = NULL;  root = Insert(root, 5);}
 

5.1 Containers

vector­<in­t> v;
vector definition
v[i]
i-th item in the vector
v.pop_­back()
remove last item
v.size()
size of vector
list<i­nt> l;
list definition
l.push­_fr­ont()
insert item at front
l.push­_back()
insert item at back
l.pop_­front()
remove the first item
l.pop_­back()
remove last item
l.front()
access the first item
l.back()
access the last item
l.size()
return num of items
map<K, V> m;
map definition
m[i]
i-th item in the list
m.count(k)
return no. of pairs in the map with key = k
m.size()
no. of items

Using map with user define objects

bool operator<(const Record& a, const Record& b){
  return a.name < b.name; 
}
Must overload "­<" operator

Directives for STL

#include<vector>; #include<list>; #include<map>; #include<algorithm>;

Algorithms

Sorting
sort(v.be­gin(), v.end()) // vector
sort(a, a+10); // array
c.sort() // list and maps
sort(v­,be­gin(), v.end(), compare);// descend
bool compar­e(int a, int b){ return a > b; }
overload operat­or<() for special tricks
Binary Search
binary­_se­arc­h(v.be­gin(), v.end(), target); //returns bool
"­tar­get­" is what you are looking for in v
Upper & lower bound
`lower­_bo­und­(v.b­eg­in(), v.end(), target); // returns Forwar­dIt­era­tor­"
upper_­bou­nd(­v.b­egin(), v.end(), target);
lower_­bound() returns the earliest postion
upper_­bound() returns the lastest position
binary­_se­arch(), upper_­bound() and lower_­bound() can be used with vectors, lists, and maps
Random Shuffle (see appendix)
need <cs­tdl­ib>, <ct­ime>, srand(­tim­e(N­ULL))

C++ STL Template Class

template <class T>
class MyCollection{
    vector<T> data; 
  public:
    void Add(const T &);
};
template <class T>
void MyCollection <T> :: Add(const T & d){
  data.push_back(d);
}

C++ Template Operator Overlo­ading (One-t­o-one)

template <class T>
class MyCollection{
    vector<T> data;
  public:
    void Add(T const &);
    T & Draw();
  friend ostream & operator<<(ostream & cout, const MyCollection<T> &q){
    cout << "Collection" << endl;
    typename vector<T>::const_iterator itr; 
       for(itr =q.data.begin(); itr != q.data.end(); itr++)
         cout << " " << *itr << endl;
         return cout; 
    }
}

C++ Template Overlo­ading (many-­to-­many)

template <class T>
class MyCollection{
    vector<T> data;
  public:
    void Add(T const &);
    T & Draw();
  template <class U>
  friend ostream & operator<<(ostream & cout, const MyCollection<U>& q);
};
template <class U>
ostream & operator<<(ostream &cout, const MyCollection<U> & q)
{
  typename vector<U>::const_iterator itr; 
  ... (same)
}

C Conversion Specifier

int
%d
float
%f
double
%lf
char
%c
string
%s

C string

char name[] = "­Ala­n";
char name[100]; scanf(­"­%s", name);
#inclu­de<­str­ing.h>
more functions
strcop­y(char s1[], char s2[])
copy s2 to s1
strcat­(char s1[], char s2[])
append s2 to end of s1
strcmp­(char s1[], char s2[])
return -ive if s1<s2. return +ive if s1>s2. return 0 if s1==s2
strlen­(char s1[])
return length of string

C Functions

Pass by reference
void swap(d­ouble *a, double *b){...}
Using this function: pass the address
swap(&a, &b);

C Arrays

int array[] = {1, 2, 3};
a[i] is the same as *(a+i)

C Memory Allocation

int size; int *a; scanf(­"­%d", &s­ize);
a = malloc­(si­ze*­siz­eof­(int));
free(a); // a is pointer

C Structure and typedef

struct student { char name[20]; int uid; } 
typedef struct student student; 
int main(){ student a; ... }

Python

int(a); float(a); str(a)
type casting
a+b
concat­enation
s[i]
access i-th
s[1:5]
substring s[1] to s[4]
s[1:]
s[1] to end
s[:4]
start to s[3]
len(s)
length of the string
print "­how­dy!­",
print without newline
s = input(­"­pro­mpt­")
take user input as strings

Python File Input

with open("f­ile­nam­e", "­mod­e") as f:
open file. define scope
f.close()
end of scope
s = f.read();
read from file
f.writ­e(s­tr(a));
write to the file
file modes
r
read only
r+
reading and writing
w
write only
w+
writing and reading (overw­rite)
a
appending
a+
appending and reading

Python Flow of Control

#if-else statement
if condition:
  statement
elif condition:
  statement
else:
  statement
Conditions are not enclosed by brackets

Python Logical operators

&&
and
||
or
!
not

Python For-loops

for i in list:
  statement
  statement

#Example 1
i = 1
for dir in [ "n", "e", "w", "s" ]:
  print "the" + str(i) + "-th direction is" + dir
  i+=1

#Example2
for i in range(0, 71):
  if i % 7 == 0:
    print i,

Python Array

arr = [0] * i
empty array with size i
arr[i]
i-th item in array