Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Fall 2023 -- CSC 2700 Section 01 (2317 Patrick Taylor, 6:00 PM - 7:50 PM)



Continuum of a Program

If you look a program, you will see data and code -- logical. Have you ever thought about their interrelationships?

The choice of data structure predestines some of the code. The choice of some code predestines some data structures. In fact, the two could be perceived as opposite ends of a continuum. When you design/implement a program, you choose what to do. Consider that choice a slider on a scale. It can be heavy data structure and lighter code or the other way around.

Programs can be optimized for speed or for data usage (usually these goals are diametrically opposed).

Here are 3 different implementations that produce the same result:

Nested If Statements

if (1 == i)
 { total = total + 17; }
elseif (2 == i)
 { total = total + 29; }
elseif (3 == i)
 { total = total + 99; }

Case Statement

switch (i)
 { // switch
 Case 1: total = total + 17; break;
 Case 2: total = total + 29; break;
 Case 3: total = total + 99; break;
 } // switch

Array Implementation

 int ary[4] {0, 17, 29, 99};


 total = total + ary[i];

Here are some code segments to perform the same task. Look at them.

Nested ifs Using case: 
#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

/* direction is left or right */
.
.
.
if (NORTH == curMove)
   if (LEFT == direction)
      nextMove = WEST;
   else
      nextMove = EAST;
else
if (EAST == curMove)
   if (LEFT == direction)
      nextMove = NORTH;
   else
      nextMove = SOUTH;
else
if (SOUTH == curMove)
   if (LEFT == direction)
      nextMove = EAST;
   else
      nextMove = WEST;
else
if (WEST == curMove)
   if (LEFT == direction)
      nextMove = SOUTH;
   else
      nextMove = NORTH;

#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

/* direction is left or right */
.
.
.
switch (curMove)
 { // switch
   case NORTH: 
        if (LEFT == direction)
           nextMove = WEST;
        else
           nextMove = EAST;
        break;
   case EAST: 
        if (LEFT == direction)
           nextMove = NORTH;
        else
           nextMove = SOUTH;
        break;
   case SOUTH: 
        if (LEFT == direction)
           nextMove = EAST;
        else
           nextMove = WEST;
        break;
   case WEST: 
        if (LEFT == direction)
           nextMove = SOUTH;
        else
           nextMove = NORTH;
        break;
 } // switch
Using 2D array Using 1D array 
#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

int next[4][2];

next[NORTH][LEFT]  = WEST;
next[NORTH][RIGHT] = EAST;
next[EAST][LEFT]   = NORTH;
next[EAST][RIGHT]  = SOUTH;
next[SOUTH][LEFT]  = EAST;
next[SOUTH][RIGHT] = WEST;
next[WEST][LEFT]   = SOUTH;
next[WEST][RIGHT]  = NORTH;

/* direction is left or right */
.
.
.
nextMove = next[curMove][direction];

#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  2
#define SOUTH 4
#define WEST  6

int next[8];

next[NORTH + LEFT]  = WEST;
next[NORTH + RIGHT] = EAST;
next[EAST  + LEFT]  = NORTH;
next[EAST  + RIGHT] = SOUTH;
next[SOUTH + LEFT]  = EAST;
next[SOUTH + RIGHT] = WEST;
next[WEST  + LEFT]  = SOUTH;
next[WEST  + RIGHT] = NORTH;

/* direction is left or right */
.
.
.
nextMove = next[curMove + direction];
Using clock arithmetic   
#define LEFT  3
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

/* direction is left or right */
.
.
.
nextMove = (curMove + direction) MOD 4;
 

Above are five different ways of doing the same thing. Consider the code.

Realize that computers (cpus) tend to have many common features even though they do differ in implementation. Here are some of the features that are common but differ in size:

Reducing size of code and data after compilation increases the probability that the code/data will be in cache (dramatically improving runtime. Branching can destroy performance by not using prefetch or clearing a pipeline.