The Computing Book

William Stein June 30, 1997

Contents

1 X Windows 1 1.1 XF86Config . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Window Managers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.1 Fvwm95 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Networking 8

2.1 Configuring on Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 PPP dialup networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Data Structures 10

3.1 List Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 C++ Integer Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.2 FIFO Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2.1 Dynamic array class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3.1 Adjacency matrix simple graph . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Cryptology 15

4.1 Secret Key Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1.1 Ceaser Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1.2 XOR Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Java 16 5.1 Elliptic Curve Graphing Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Chapter 1

X Windows

1.1 XF86Config

My XF86Config for my Pentium 200 is is as follows.

Section "Files"
RgbPath    "/usr/X11R6/lib/X11/rgb"
FontPath   "/usr/X11R6/lib/X11/fonts/misc:unscaled"
FontPath   "/usr/X11R6/lib/X11/fonts/75dpi:unscaled"
FontPath   "/usr/X11R6/lib/X11/fonts/100dpi:unscaled"
FontPath   "/usr/X11R6/lib/X11/fonts/Type1"
FontPath   "/usr/X11R6/lib/X11/fonts/Speedo"
FontPath   "/usr/X11R6/lib/X11/fonts/misc"
FontPath   "/usr/X11R6/lib/X11/fonts/75dpi"
FontPath   "/usr/X11R6/lib/X11/fonts/100dpi"
EndSection
Section "ServerFlags"
EndSection
Section "Keyboard"
Protocol        "Standard"
XkbRules        "xfree86"
XkbModel        "pc101"
XkbLayout       "us"
EndSection
Section "Pointer"
Protocol        "Microsoft"
Device          "/dev/mouse"
BaudRate        1200
Emulate3Timeout 50
Emulate3Buttons
EndSection
Section "Monitor"
Identifier      "Primary Monitor"
VendorName      "Unknown"
ModelName       "Unknown"
HorizSync       31.5-64.3
VertRefresh     50-90

   Modeline  "1280x1024" 110.00 1280 1328 1512 1712 1024 1025 1028 1054
   Modeline  "1152x864"   92.00 1152 1196 1356 1526 864 877 887 923
   Modeline  "1024x768"   85.00 1024 1076 1196 1340 768 776 779 819
   Modeline  "800x600"    60.75 800 816 880 1028 600 616 621 657 -hsync -vsync
   Modeline  "640x480"    36.00 640 656 712 848 480 481 484 509 -hsync -vsync
   Modeline  "640x400"    31.50 640 672 736 832 400 401 404 445 -hsync +vsync
   Modeline  "512x384"    22.00 512 528 592 640 384 385 388 404 -hsync -vsync
   Modeline  "480x300"    29.95 480 504 584 624 300 319 322 333 doublescan
   Modeline  "400x300"    25.00 400 424 488 520 300 319 322 333 doublescan
   Modeline  "320x240"    15.75 320 336 384 400 240 244 246 262 doublescan
   Modeline  "320x200"    12.59 320 336 384 400 200 204 205 225 doublescan
EndSection
Section "Device"
   Identifier      "Primary Card"
   VendorName      "Unknown"
   BoardName       "Matrox Millennium (MGA)"
EndSection
Section "Screen"
   Driver          "SVGA"
   Device          "Primary Card"
   Monitor         "Primary Monitor"
   SubSection "Display"
## comment out EXACTLY one.
#      Depth        8
#      Depth        15
      Depth        16
#      Depth        24
#      Depth        32
      Modes        "1280x1024" "1152x864" "1024x768" "800x600" "640x480"
   EndSubSection
EndSection

1.2 Window Managers

1.2.1 Fvwm95

This is my configuration file.

#############################################################################
# Win95-like but very simple and useful fvwm configuration for working with #
# shells and emacs in X-windows.  It provides exactly what I need           #
# to work -- a clock, two buttons: color-xterm and emacs, and a task bar.   #
#    1997, William Stein                                                    #
#############################################################################
WindowFont -adobe-helvetica-bold-r-*-*-12-*-*-*-*-*-*-*
IconFont fixed
MenuFont    -adobe-helvetica-medium-r-*-*-*-120-*-*-*-*-*-*
DefaultColors   Black #c3c3c3 #c3c3c3 grey51
HilightColors   White #000080
StickyColors    grey51 #60c080
Style "*" ClickToFocus
Style "*" NoIcon

Style "*" MWMFunctions
Style "*" HintOverride
Style "*" MWMDecor
OpaqueMoveSize 100
EdgeScroll 100 100
EdgeResistance 10000 0
Style "*" RandomPlacement
Style "*" NoPPosition
DeskTopSize 1x1
ModulePath /usr/X11R6/lib/X11/fvwm95-2/
PixmapPath /usr/include/X11/pixmaps/:/usr/local/mini-icons/
IconPath   /usr/include/X11/bitmaps/:/usr/local/icons/
Style "*" BorderWidth 5, HandleWidth 5
Style "Fvwm*"        NoTitle, Sticky, WindowListSkip
Style "Fvwm Pager"   StaysOnTop, NoHandles
Style "FvwmBanner"   StaysOnTop
Style "FvwmButtons"  NoTitle, NoHandles, Sticky, WindowListSkip,BorderWidth 5
Style "*lock"        NoTitle, NoHandles, Sticky, WindowListSkip
Style "xbiff"        NoTitle,            Sticky, WindowListSkip
# Some mini-icons for the title bar
Style "*"         TitleIcon mini-x2.xpm
Style "xterm"     TitleIcon mini-sh1.xpm
Style "emacs"     TitleIcon mini-paint.xpm
Style "netscape"  TitleIcon mini-nscape.xpm
# ######### INIT: programs automatically run at start up.
AddToFunc "InitFunction"    "I" Exec xsetroot -solid cyan4 &
+                           "I" Module FvwmButtons
+                           "I" Module FvwmTaskBar
+                           "I" Exec emacs -geometry 86x62+29+8 -font 8x13 -name "book emacs" ~/book/tb.tex
+                           "I" Exec xterm -geometry 85x7+207+870 -ls -sb -sl 512 -title "commands"
+                           "I" Exec xterm -geometry 81x24+752+648 -ls -sb -iconic -sl 512 -title "term"
+                           "I" Exec xdvi -geometry 860x965+408+2 -iconic -s 3 ~/book/tb.dvi
+                           "I" Exec xdvi -geometry 672x828+594+3 -iconic -s 4 ~/book/tb.dvi
+      "I" Exec netscape -geometry 581x955+685+7 -iconic
AddToFunc "RestartFunction" "I" Module FvwmButtons
+                           "I" Module FvwmTaskBar
AddToFunc "Move-or-Raise" "M" Move
+                         "M" Raise
+                         "C" Raise
+                         "D" Maximize 100 100
AddToFunc "Move-or-Lower" "M" Move
+                         "M" Lower
+                         "C" Lower
+                         "D" RaiseLower
AddToFunc "Move-or-Iconify" "M" Move
+                           "D" Iconify
AddToFunc "Resize-or-Raise" "M" Resize

+                           "M" Raise
+                           "C" Raise
+                           "D" RaiseLower
AddToMenu "StartMenu"
+ "Screensavers     %mini-bball.xpm%"       Popup   Screensaver1
+ "Screensavers     %mini-bball.xpm%"       Popup   Screensaver2
+ "lidia manual     %mini-man.xpm%"         Exec    xdvi -s 4 /extra/LiDIA/doc/man.dvi -geometry 674x857+589+4
+ "pari manual     %mini-man.xpm%"         Exec    xdvi -s 4 /usr/local/pari/doc/users.dvi -geometry 674x857+589+4
+ "xterm     %mini-sh1.xpm%"         Exec    xterm -sl 500 -ls -sb &
+ "emacs            %mini-paint.xpm%"      Exec    emacs -fn 8x13 &
+ "netscape         %mini-nscape.xpm%"      Exec    netscape &
+ ""                                        Nop
+ ""                                        Nop
+ "Exit Fvwm95      %mini-stop.xpm%"        Popup   Quit-Verify
AddToMenu "Screensaver1" "Screensaver (a-h)" Title
+ "Ant%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode ant &
+ "Bat%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode bat &
+ "Blank%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode blank &
+ "Blot%mini-bball.xpm%" Exec xlock -nolock -nice 0 -mode blot &
+ "Bouboule%mini-bball.xpm%" Exec xlock -nolock -nice 0 -mode bouboule &
+ "Bob%mini-bball.xpm%"    Exec xlock -nolock -nice 0 -mode image &
+ "Bounce%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode bounce &
+ "Braid%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode braid &
+ "Bug%mini-bball.xpm%"    Exec xlock -nolock -nice 0 -mode bug &
+ "Clock%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode clock &
+ "Demon%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode demon &
+ "Eyes%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode eyes &
+ "Flag%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode flag &
+ "Flame%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode flame &
+ "Forest%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode forest &
+ "Galaxy%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode galaxy &
+ "Geometry%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode geometry &
+ "Grav%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode grav &
+ "Helix%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode helix &
+ "Hop%mini-bball.xpm%"    Exec xlock -nolock -nice 0 -mode hop   &
+ "Hyper%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode hyper &
AddToMenu "Screensaver2" "Screensaver (i-z)" Title
+ "Kaleid%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode kaleid &
+ "Laser%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode laser &
+ "Life%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode life   &
+ "Life1d%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode life1d &
+ "Life3d%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode life3d &
+ "Lissie%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode lissie &
+ "Marquee%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode marquee &
+ "Maze%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode maze &
+ "Mountain%mini-bball.xpm%" Exec xlock -nolock -nice 0 -mode mountain &
+ "Nose%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode nose &
+ "Petal%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode petal &
+ "Puzzle%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode puzzle &
+ "Pyro%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode pyro &
+ "Qix%mini-bball.xpm%"    Exec xlock -nolock -nice 0 -mode qix &
+ "Random%mini-bball.xpm%" Exec xlock -nolock -nice 0 -mode random &

+ "Rock%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode rock &
+ "Rotor%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode rotor &
+ "Shape%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode shape &
+ "Slip%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode slip &
+ "Sphere%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode sphere &
+ "Spiral%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode spiral &
+ "Spline%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode spline &
+ "Swarm%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode swarm &
+ "Swirl%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode swirl &
+ "Triangle%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode triangle &
+ "Wator%mini-bball.xpm%"   Exec xlock -nolock -nice 0 -mode wator &
+ "World%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode world &
+ "Worm%mini-bball.xpm%"  Exec xlock -nolock -nice 0 -mode worm &
AddToMenu "Quit-Verify" "Quit?" Title
+ "Restart%mini-turn.xpm%" Restart fvwm95-2
+ ""  Nop
+ "Yes, Quit%mini-exclam.xpm%" Quit
+ "No, Don't Quit%mini-cross.xpm%"  Nop
AddToMenu "Window" "Window Ops" Title
+ "&Move"                     Function Move-or-Raise
+ "&Resize"                   Function Resize-or-Raise
+ "R&aise%mini-raise.xpm%"    Raise
+ "&Lower%mini-lower.xpm%"    Lower
+ "(De)Iconify"               Iconify
+ "(Un)Stick"                 Stick
+ "(Un)Maximize"              Maximize 100 100
+ ""                          Nop
+ "Kill"                      Destroy
+ "&Close"                    Delete
+ ""                          Nop
+ "Switch to..."              WindowList
+ "Refresh Screen%mini-ray.xpm%" Refresh
AddToMenu "Window-Ops2" "&Restore"        Iconify -1
+                       "&Move"           Move-or-Raise
+                       "&Size"           Resize-or-Raise
+                       "Mi&nimize"       Iconify 1
+                       "Ma&ximize"       Maximize 100 100
+                       ""                Nop
+                       "&Kill"           Destroy
+                       "&Close Alt+F4"   Delete
AddToFunc "window_ops_func" "C" PopUp Window-Ops2
+              "M" PopUp Window-Ops2
+              "D" Delete
#     Button Context Modifi  Function
Mouse 1 R    A       Menu "Utilities" Nop
Mouse 2 R     A       Menu "Window Ops" Nop
Mouse 3         R       A       WindowList
#Mouse 3 R     A       Module "winlist" FvwmWinList transient
#     Button Context Modif  Function
Mouse 0 1     A       Function "window_ops_func"
Mouse 1         2       A       Delete
Mouse 0 4     A      Maximize 100 100
Mouse 0 6     A      Iconify
Mouse 1 F A Function "Resize-or-Raise"
Mouse 1 TS A Function "Move-or-Raise"

Mouse 1 I A Function "Move-or-Iconify"
Mouse 2 I A Iconify
Mouse 2 FST A Function "window_ops_func"
Mouse 3 TSIF A RaiseLower
Mouse 3         W       M       RaiseLower
# Arrow Keys
# press arrow + control anywhere, and scroll by 1 page
Key Left A C Scroll -100 0
Key Right A C Scroll +100 +0
Key Up A C Scroll +0   -100
Key Down A C Scroll +0   +100
# press arrow + meta key, and scroll by 1/10 of a page
Key Left A M Scroll -10 +0
Key Right A M Scroll +10 +0
Key Up A M Scroll +0   -10
Key Down A M Scroll +0   +10
# press shift arrow + control anywhere, and move the pointer by 1% of a page
Key Left A SC CursorMove -1 0
Key Right A SC CursorMove +1 +0
Key Up A SC CursorMove +0   -1
Key Down A SC CursorMove +0   +1
# press shift arrow + meta key, and move the pointer by 1/10 of a page
Key Left A SM CursorMove -10 +0
Key Right A SM CursorMove +10 +0
Key Up A SM CursorMove +0   -10
Key Down A SM CursorMove +0   +10
# Keyboard accelerators
Key F1 A M Popup "Utilities"
Key F1 A M Popup "Utilities"
Key F2 A M Popup "Window Ops"
Key F3 A M Module "WindowList" FvwmWinList
Key F4 A M Iconify
Key F5 A M Move
Key F6 A M Resize
Key F7 A M CirculateUp
Key F8 A M CirculateDown
Key Tab         A       M       Prev Focus
Key Tab         A       MS      Next Focus
Key Escape      A       C       WindowList
#------------------ Pager
*FvwmPagerBack grey60
*FvwmPagerFore black
*FvwmPagerFont -adobe-helvetica-bold-r-*-*-10-*-*-*-*-*-*-*
*FvwmPagerHilight #c3c3c3
*FvwmPagerGeometry -1-1
*FvwmPagerLabel 0 Desktop
*FvwmPagerSmallFont 5x8

#------------------ FvwmButtons
*FvwmButtonsFore Black
*FvwmButtonsBack #c3c3c3
*FvwmButtonsFont -adobe-helvetica-bold-r-*-*-10-*-*-*-*-*-*-*
# Geometry - really likes to pick its own size, but giving a position is OK
*FvwmButtonsGeometry +5-34
# Layout: specify rows or columns, not both
*FvwmButtonsRows 1
# Define the buttons to use.....
*FvwmButtons xterm   mini-sh1.xpm Exec  "xterm" xterm -ls -sb -sl 500 -title "xterm"
*FvwmButtons emacs   mini-paint.xpm   Exec    "emacs" emacs -fn 8x13
*FvwmButtons netscape mini-nscape.xpm Exec    "netscape" netscape
#*FvwmButtons xv       mini-xv.xpm Exec "xv" xv
#*FvwmButtons xpaint   mini-paint.xpm   Exec  "xpaint" xpaint
#------------------ FvwmWinList
*FvwmWinListBack #c3c3c3
*FvwmWinListFore Black
*FvwmWinListFont -adobe-helvetica-bold-r-*-*-10-*-*-*-*-*-*-*
*FvwmWinListAction Click1 Iconify -1,Focus
*FvwmWinListAction Click2 Iconify
*FvwmWinListAction Click3 Module "FvwmIdent" FvwmIdent
*FvwmWinListUseSkipList
*FvwmWinListGeometry +0-1
#------------------ FvwmTaskBar
Style "FvwmTaskBar" NoTitle,BorderWidth 4,HandleWidth 4,Sticky,StaysOnTop,WindowListSkip,CirculateSkip
*FvwmTaskBarGeometry +0-0
*FvwmTaskBarFore Black
*FvwmTaskBarBack #c3c3c3
*FvwmTaskBarTipsFore black
*FvwmTaskBarTipsBack bisque
*FvwmTaskBarFont -adobe-helvetica-medium-r-*-*-*-120-*-*-*-*-*-*
*FvwmTaskBarSelFont -adobe-helvetica-bold-r-*-*-*-120-*-*-*-*-*-*
*FvwmTaskBarAction Click1 Iconify -1,Raise,Focus
*FvwmTaskBarAction Click2 Iconify
*FvwmTaskBarAction Click3 Module "FvwmIdent" FvwmIdent
*FvwmTaskBarUseSkipList
*FvwmTaskBarAutoStick
*FvwmTaskBarStartName Start
*FvwmTaskBarStartMenu StartMenu
*FvwmTaskBarStartIcon mini-exp.xpm
*FvwmTaskBarShowTips
*FvwmTaskBarMailProg xterm -e mail

Networking

2.1 Configuring on Linux

2.1.1 PPP dialup networking

I am using PPP on my Linux system. To configure linux networking one may have to modify the

following files: /etc/hosts, /etc/resolv.conf, /etc/rc.d/rc.inet2. I only had to modify

the first two.

   My /etc/hosts is:
127.0.0.1 localhost
127.0.0.1 number
   My /etc/resolv.conf is:
domain autobahn.org
nameserver 206.79.223.27
nameserver 206.79.223.28
nameserver 206.79.223.100
address  206.79.223.27 206.79.223.28 206.79.223.100

To connect I use the command dip autobahn.dip 2>&1 where autobahn.dip is the following script.

#Make a PPP connection with autobahn ISP  647-0500
get $mtu 1006
port modem
speed 57600
initialize:
print Initializing modem...
send atz0\n
print Dialing AutoBahn, call waiting disabled (*70--6470500).
dialseq:
# Need t prefix for tone dial.
print Dialing
dial t*70--6470500
# BUSY
if $errlvl == 3 goto redial
# ERROR
if $errlvl == 2 goto error
# NO CARRIER

if $errlvl == 4 goto redo
# OK
if $errlvl == 0 goto redo
# NO DIALTONE
if $errlvl == 5 goto redo
print Connected...
wait login: 120
if $errlvl != 0 goto fatal
print login: was
send was\n
wait assword: 120
if $errlvl != 0 goto fatal
print password: xxxxxxx
send my_password
## Get the dynamically allocated names.
get $remote remote
if $errlvl != 0 goto error
# Get local IP address from server, assign to variable $local.
get $local remote
if $errlvl != 0 goto error
# Set up default route.
default
print Default route...
print Setting up PPP connection...
print $local (local) <--> $remote (remote)
mode PPP
goto exit
error:
print Error detected, reinitializing modem and restarting...
goto initialize
redial:
print Busy signal detected, redialing...
goto dialseq
redo:
print Dial sequence failed, retrying...
goto dialseq
fatal:
print Fatal error occured, exiting...
exit:

Data Structures

3.1 List Structures

3.1.1 C++ Integer Stack

This is a C++ linked list implementation of a stack of integers.

// stack.C -- a stack class
#include<iostream.h>
class Node {
int data;
Node* below;
public:
Node(Node* node, int n=0) { below=node; data=n;}
~Node() { if(below) delete below; }
// Chop off the node from the buttom of the stack.  Returns the top
// of the stack which was just chopped off and is left dangeling below.
Node* Chop() { Node* temp=below; below=NULL; return temp; }
int Data() { return data; }
};
class Stack {
Node* top;
public:
Stack() { top=NULL; }
~Stack() { if(top) delete top; }
void Push(int data) { Node* temp=new Node(top,data); top=temp; }
int Pop() { if(top!=NULL) {
    Node* temp=top;
    int data=top->Data();
    top=top->Chop();
    delete temp;
    return data;
  }
  cout << "Error: Pop from empty stack!" << endl; return 0;
}
};
main() {
Stack s;

for(int i=1;i<10;i++) s.Push(i*i);
for(int i=1;i<5;i++) cout << s.Pop() << endl;
}

3.1.2 FIFO Queue

The following is a first-in-first-out (FIFO) queue of integers implemented in C++. It uses a “sentinel” node so that when the queue is empty there are less special cases to take care of. Think of the sentinel as a guard who always stands at the front of the queue.

// fifo.C -- a linked list FIFO queue of integers.
#include<iostream.h>
class Node {
int n;
Node* next;
public:
Node(int ini_n=0, Node* ini_next=0) : n(ini_n), next(ini_next) { }
~Node() { if(next) delete next; }
int N() { return n; }
void SetNext(Node* new_next) { next=new_next; }
Node* GetNext() { return next; }
};
class Fifo {
Node *front, *back;  // front and back of queue, insert in back, take from front.
public:
Fifo() { front=back=new Node; }  // create sentinel.
~Fifo() { delete front; }
void EnQueue(int n) {
  back->SetNext(new Node(n,0));
  back=back->GetNext();
}
int DeQueue() {
  if(front==back)
    { cerr<<"DeQueue error: there is nothing in the queue."<<endl; return 0; }
  Node* AfterSent=front->GetNext();
  int n=AfterSent->N();
  front->SetNext(AfterSent->GetNext());
  AfterSent->SetNext(0); delete AfterSent;
  // if we just deleted what back pointed to, set it to point at the sentinel.
  if(front->GetNext()==0) { back=front; }
  return n;
}
};
main() {
Fifo fifo;
for(int i=0;i<25;i++) fifo.EnQueue(i);
for(int i=0;i<25;i++) cout<<fifo.DeQueue()<<" ";
cout<<endl;
}

3.2 Arrays

3.2.1 Dynamic array class

This class is a C++ integer array. It is dynamically allocated so the user can make arrays of any size during execution. It can be resized, the old array being copied into the new array, as best as possible. It has a copy constructor and an equality operator. All entries are initialized to 0. It is robust: if the calling program tries to access an invalid component of the array, then an error message is reported and a dummy data location is set up to be used in place of the invalid array entry. Thus the program continues to execute. The [ ] operator is overloaded, so if a is an IntArray, then a[5]=2 assigns 2 to the sixth component of a (the first component is

a[0].
// array.C -- robust dynamic integer array.
#include<iostream.h>
class IntArray {
int* a;
int size;
int ErrorCheck(char* message, int prop) {
  if(!prop) cerr << "Error: " << message << "!" << endl;
  return prop;
}
public:
IntArray(int n=0) : size(n) {
  a=new int[size]; for(int i=0;i<size;i++) a[i]=0;
}
IntArray(const IntArray& other) {
  size=other.size; a=new int[size];
  for(int i=0;i<size;i++) a[i]=other.a[i];
}
~IntArray() { delete a; }
int& operator[](int n) {
  if(ErrorCheck("array access out of bounds",0<=n && n<size)) return a[n];
  else { static int bad; return bad; }
}
int get(int n) const {
  if(ErrorCheck("array access out of bounds",0<=n && n<size))
    return a[n];
  else return 0;
}
int operator==(const IntArray& other) {
  if(size!=other.size) return 0;
  for(int i=0;i<size;i++) if(a[i]!=other.a[i]) return 0;
  return 1;
}
void resize(int newsize) {
  int* t=new int[newsize];
  int i, cpsize=(size<newsize)?size:newsize;
  for(i=0;i<cpsize;i++) t[i]=a[i];
  for(;i<newsize;i++) t[i]=0;
  delete a; a=t;
  size=newsize;
}
void print() const {
   cout<<"<"; for(int i=0;i<size;i++) cout<<a[i]<<((i<size-1)?",":">\n");
}

int length() const { return size; }
};

Here is a recursive merge sort program which demonstrates the use of IntArray. [Can it be made more efficient by avoiding all of the copies? As is, it can sort an array of 25000 entries in a second.]

// given two IntArray's, assumed sorted, creates a third IntArray,
// sort-merges them into it and returns a pointer to the new IntArray.
IntArray* SortedMerge(const IntArray& a, const IntArray& b) {
IntArray* c = new IntArray(a.length()+b.length());
int ai=0, bi=0;
for(int i=0;i<c->length();i++) {
  if(ai==a.length())
    (*c)[i]=b.get(bi++);
  else if(bi==b.length())
    (*c)[i]=a.get(ai++);
  else
    (*c)[i]=(a.get(ai)<b.get(bi))?a.get(ai++):b.get(bi++);
}
return c;
}
void Sort(IntArray& a) {
if(a.length()<=1) return;
if(a.length()==2) {
  if(a[0]>a[1]) {int t=a[0];a[0]=a[1];a[1]=t;}
  return;
}
int i, half=a.length()/2;
IntArray left(half), right(a.length()-half);
for(i=0;i<half;i++) left[i]=a[i];
for(;i<a.length();i++) right[i-half]=a[i];
Sort(left); Sort(right);
IntArray* c=SortedMerge(left,right);
a=*c;
}
main() {
IntArray a(25000);
for(int i=0;i<25000;i++) a[i]=(i*i)%25000;
cout << "start sorting..." << endl;
Sort(a);
cout << "Done!" << endl;
}

3.3 Graphs

3.3.1 Adjacency matrix simple graph

The following is a C++ implementation of a simple graph using a dynamically allocated upper triangular adjacency matrix. It is good for smaller or dense graphs, but not for large sparse graphs having many vertices but few edges.

// graph1.C -- adjacency matrix implementation of a (simple) graph class.
#include<iostream.h>

void ERROR(const char* offender) { cout<<"Error in: "<<offender<<endl; exit(0);}
typedef char BOOL;
const BOOL FALSE=0, TRUE=1;
const char* BOOLSTRING[]={"FALSE","TRUE"};
class Graph {
BOOL** m;  // (dynamically allocated) upper triangular adjacency matrix.
int size;  // number of vertices
public:
Graph(int n) : size(n) {
  if(size<0) ERROR("Graph::Graph -- invalid graph size");
  m=new (BOOL*)[size];
  for(int i=0;i<size;i++) { // make upper triangular matrix.
    m[i]=new BOOL[i+1];
    for(int j=0;j<i+1;j++) m[i][j]=FALSE;   // initialized to FALSE.
  }
}
~Graph() { for(int i=0;i<size;i++) delete m[i]; delete m; }
void Print() {
  for(int i=0;i<size;i++)
    for(int j=0;j<=i;j++)
      if(m[i][j]==TRUE) cout<<"["<<i<<"]------["<<j<<"]"<<endl;
}
void MakeEdge(int v1, int v2) {
  if(v1<0||v2<0||v1>=size||v2>=size) ERROR("Graph::MakeEdge -- invalid vertices");
  if(v1>=v2) m[v1][v2]=TRUE; else m[v2][v1]=TRUE;
}
BOOL IsEdge(int v1, int v2) {
  if(v1<0||v2<0||v1>=size||v2>=size) ERROR("Graph::IsEdge -- invalid vertices");
  if(v1>=v2) return m[v1][v2]; else return m[v2][v1];
}
};
main(){
// this class is good for small graphs.
Graph G(10); G.MakeEdge(2,1); G.Print();
cout << BOOLSTRING[G.IsEdge(5,1)] << ", " << BOOLSTRING[G.IsEdge(2,1)] << endl;
for(int i=0;i<8;i++) G.MakeEdge(i,1);  G.Print();
// but for large sparse graphs it is disastrously inefficient.
Graph H(10000);
for(int i=0;i<10000;i++) H.MakeEdge(i,0);
H.Print();
}

Cryptology

4.1 Secret Key Encoding

4.1.1 Ceaser Cipher

C++ Implementation of Ceaser Cipher

/* ceaser.c -- ceaser cipher: shifts characters from stdin a given amount. */
#include<stdio.h>
int main(int argc, char* argv[]) {
   char c; int n;
   if(argc!=2) { fprintf(stderr,"usage: %s [shift-by]\n",argv[0]); return 1; }
   n=atoi(argv[1]);
   while(EOF!=scanf("%c",&c)) printf("%c",c+n);
   return 0;
}

4.1.2 XOR Cipher

The following is an xor cipher. Although it is easily broken it is commonly used in Mac and PC software and is touted as “being more secure than DES.” From standard input it takes plaintext or ciphertext. The output is the corresponding ciphertext or plaintext. Successive letters of the encryption key are XOR’d with each character of input. See page 12 of [?].

/* xor.c -- xor cipher */
#include<stdio.h>
int main(int argc, char* argv[]) {
  char c; char* key=argv[1];
  if(argc!=2) { fprintf(stderr,"usage: %s key\n", argv[0]); return 0; }
  while(EOF!=scanf("%c",&c)) {
    if(*key==0) key=argv[1];
    c ^= *(key++);
    printf("%c",c);
  }
  return 1;
}

Here is how to use xor. The command xor dona < xor.c > xor.encrypted creates an encrypted file xor.encrypted. The command xor dona < xor.encrypted outputs the plaintext

of xor.c.

Java

5.1 Elliptic Curve Graphing Program

The following program is a very simple interactive tool for understanding how the shape of an elliptic curve varies as the parameters which define it vary. To me the code seems very bad, but the program itself seems to work flawlessly. To use this I first compiled the source file Elliptic.java to produce the byte code Elliptic.class using the command javac Elliptic.java. Then I ran the program using either the Sun appletviewer or Netscape. The

file go.html is:
<title>Elliptic Curve Grapher</title>
<hr> <applet code=Elliptic.class width=400 height=400> </applet> <hr>
<a href="Elliptic.java">Source.</a>

The source file Elliptic.java is:

// elliptic.java -- Play with an elliptic curve. (by William Stein, 6/30/97)
import java.applet.*;
import java.awt.*;
public class Elliptic extends java.applet.Applet {
  private static double step=0.05;
  private double a=0,b=0,
         scale_x=75,scale_y=75;
  private Button a_up_button, a_down_button, b_up_button, b_down_button;
  public void init() {
    super.init();
    a_up_button=new Button("Increase a"); this.add(a_up_button);
    a_down_button=new Button("Decrease a"); this.add(a_down_button);
    b_up_button=new Button("Increase b"); this.add(b_up_button);
    b_down_button=new Button("Decrease b"); this.add(b_down_button);
  }
  public boolean action(Event event, Object arg) {
    if      (event.target==a_up_button)
      { a+=step; paint(this.getGraphics()); return true; }
    else if (event.target==a_down_button)
      { a-=step; paint(this.getGraphics()); return true; }
    else if (event.target==b_up_button)
      {  b+=step; paint(this.getGraphics()); return true; }
    else if (event.target==b_down_button)

  { b-=step; paint(this.getGraphics()); return true; }
else return super.action(event,arg);
}
double f(double x) { return x*x*x+a*x+b; }
double y(double x) { return Math.sqrt(f(x)); }
double tograph_x(double x) { return (double) (x-size().width/2)/scale_x; }
double tograph_y(double y) { return (double) (y-size().height/2)/scale_y; }
int toscreen_x(double x) { return (int)(x*scale_x+size().width/2); }
int toscreen_y(double y) { return (int)(y*scale_y+size().height/2); }
private void clear_screen(Graphics g) {
Rectangle r=this.bounds();
g.setColor(this.getBackground());
g.fillRect(r.x,r.y,r.width,r.height);
g.setColor(this.getForeground());
}
private void display_weierstrass(Graphics g) {
double tolerance=0.0001;
g.drawString("Y^2 = X^3 + aX + b",40,40);
if(Math.abs(a)>=tolerance && Math.abs(b)>=tolerance)
   g.drawString("Y^2 = X^3 + "+a+"X + "+b,40,55);
else if(Math.abs(b)>=tolerance)
   g.drawString("Y^2 = X^3 + "+b,40,55);
else if(Math.abs(a)>=tolerance)
   g.drawString("Y^2 = X^3 + "+a+"X",40,55);
else g.drawString("Y^2 = X^3",40,55) ;
}
public void paint(Graphics g) {
clear_screen(g);
display_weierstrass(g);
for(int x=0;x<size().width;x++) {
  double xx=tograph_x((double)x), xxplusone=tograph_x((double)x+1);
  if(f(xx)>=0 && f(xxplusone)>=0) {
    g.drawLine(x,toscreen_y(y(xx)),x+1,toscreen_y(y(xxplusone)));
    g.drawLine(x,toscreen_y(-y(xx)),x+1,toscreen_y(-y(xxplusone)));
  } else if(f(xxplusone)>=0) {  // draw a vertical line to avoid holes.
      g.drawLine(x,toscreen_y(y(xxplusone)),x,toscreen_y(-y(xxplusone)));
  } else if(f(xx)>=0) {
      g.drawLine(x,toscreen_y(y(xx)),x,toscreen_y(-y(xx)));
  }
}
}
}