Course Description

Module 1: Introduction to Data Structures and Algorithms

• Educational Goal: To introduce the fundamental concepts of data structures and algorithms, their importance in computer science, and the relationship between them.
• Topics:
  • Definition of data structures and algorithms
  • Importance of data structures in computer science
  • Algorithm design and analysis (time and space complexity)
  • Abstract data types (ADTs)
  • Installation of Ruby software

Module 2: Primitive Data Types and Data Representation

• Educational Goal: To understand the basic building blocks of data structures and how they are represented in computer memory.
• Topics:
  • Primitive data types (integers, real numbers, floating-point numbers, characters, booleans)
  • Data representation in memory (binary, hexadecimal, two’s complement, floating point with exponents)
  • Bitwise operations
  • Character encoding (ASCII, Unicode)

Module 3: Arrays and Strings

• Educational Goal: To understand the concept of arrays, their different types, and how they are used to store and manipulate collections of data.
• Topics:
  • Arrays (one-dimensional, multi-dimensional, jagged arrays)
  • Array operations (searching, sorting, insertion, deletion)
  • Strings as arrays of characters
  • String manipulation algorithms (substring, concatenation, searching)

Module 4: Records and Structures

• Educational Goal: To understand how to group related data items together using records (or structures) and their applications.
• Topics:
  • Records (or structures) as collections of different data types
  • Accessing and modifying fields within records
  • Applications of records (e.g., representing employee data, student records)
  • Unions (data structures that can hold values of different types)

Module 5: Pointers and References

• Educational Goal: To understand the concept of pointers and references, their role in memory management, and their use in implementing dynamic data structures.
• Topics:
  • Memory addresses and pointers
  • Pointer arithmetic and operations
  • Pass-by-reference vs. pass-by-value
  • Dynamic memory allocation (malloc, free)
  • Dangling pointers and memory leaks

Module 6: Linked Lists

• Educational Goal: To understand the concept of linked lists, their different types, and their applications in various data structures.
• Topics:
  • Singly linked lists
  • Doubly linked lists
  • Circular linked lists
  • Linked list operations (insertion, deletion, traversal)
  • Applications of linked lists (e.g., implementing stacks, queues)

Module 7: Stacks, Queues, and Trees

• Educational Goal: To understand the concepts of stacks, queues, and trees, their characteristics, and their implementations using arrays and linked lists.
• Topics:
  • Stacks (LIFO) and their applications (e.g., function calls, expression evaluation)
  • Queues (FIFO) and their applications (e.g., scheduling, breadth-first search)
  • Trees (binary trees, binary search trees)
  • Tree traversal algorithms (in-order, pre-order, post-order)

Module 8: Hashing and Graphs

• Educational Goal: To understand the concepts of hashing, graph data structures, and their applications in various domains.
• Topics:
  • Hashing functions and hash tables
  • Collision resolution techniques (chaining, open addressing)
  • Graphs (directed, undirected, weighted)
  • Graph traversal algorithms (depth-first search, breadth-first search)
  • Applications of graphs (e.g., social networks, transportation networks)

Module 9: Advance applications of data structures

• Introduction to nature inspired algorithms:
  • Understanding algorithm description and behavoir
  • the related data structures
  • the performance issues
• Examples:
  • genetic algorithms
  • annealing
  • ant run
  • bird flocking
  • decision tree
• Student projects

Module 1: Overview

• Module name: Introduction to Data Structures and Algorithms

• Educational Goal: To introduce the fundamental concepts of data structures and algorithms, their importance in computer science, and the relationship between them.

• Topics:

  • Definition of data structures and algorithms
  • Importance of data structures in computer science
  • Algorithm design and analysis (time and space complexity)
  • Abstract data types (ADTs)
  • Installation of Ruby software

Example of a Data analysis problem

Research focus:

You have 8 sec determine the following:

1. Are they all the same or not?

2. If they are not the same, identify the follow:

   • Which one does not belong?

   • What part of the trucks is different?

Graphic (which one is different?)

Side by side comparison

Superimpostion

Zoom and focus

Programming Insight 2

\[\rm Choose\ 2:\ \left\{\begin{matrix}Fast\\ Small\\ Cheap\\ \end{matrix}\right.\]

• The nature, quality and performance of a program depend on choices made
• In the end, the role of a programmer is to choose the right variation of algorithms and data structures that balances the tradeoff with the time and resources available

TEST FOR ALL POSSIBLE FACTORS

def is_factor?(num1,num2)
  return (num1 % num2).eql?(0)
end
  
def find_primes1
  # SETUP A CONTAINER FOR THE RESULTS
  @primes = []
   
  # FOR ALL NUMBERS IN TEST RANGE
  (2..MAX_NUM).each do |num|
  
    # PRESUME NUM AS PRIME 
      is_prime = true
   
    # CHECK FOR FACTORS LESS THAN NUM
    (2...num).each do |num2|
    
      # IF FACTOR FOUND
      if is_factor?(num,num2)
      
        # MARK NUMBER AS NON-PRIME
        is_prime = false
          break
        end
      end
    end
     
    # APPEND PRIME TO LIST OF PRIMES
    if is_prime
      @primes << num
    end
end

CROSS MULTIPLES OF PRIMES OFF A TALLY

def find_primes2
  # CREATE A TALLY OF NUMBERS IN RANGE
  # CREATE AN ARRAY FOR THE RESULTS
  # TEST ALL NUMBERS IN THE RANGE
    # ELIMINATE NUMBERS LESS THAN 2
    # IF NEW PRIME FOUND
        # APPEND PRIME TO MASTER LIST
        # ELIMINATE ALL MULTIPLES OF PRIME

CROSS MULTIPLES OF PRIMES OFF A TALLY

def find_primes2
  # CREATE A TALLY OF ALL NUMBERS
  tally = (0..MAX).to_a

  # CREATE A LIST FOR PRIMES FOUND
  @primes = []

  # TEST ALL NUMBERS IN THE RANGE
  (0..MAX).each do |num|

    # ELIMINATE NUMBERS LESS THAN 2
    if num < 2
      tally[num] = nil
        
    # IF NEW PRIME FOUND
    elsif !numbers[num].nil?
    
      #APPEND PRIME TO MASTER LIST
      @primes << num
      
      # ELIMINATE MULTIPLES OF PRIME
      xnum = num
        while xnum <= MAX do
          numbers[xnum] = nil
        xnum += num
      end 
    end
  end
end

USE RUBY LIBRARY FUNCTION

require 'prime'

def find_primes3
  # SETUP A CONTAINER FOR THE RESULTS
  @primes = []
   
  # FOR ALL NUMBERS IN TEST RANGE
  (2..MAX_NUM).each do |num|
   
    # IF A NUMBER IS PRIME
    if num.prime?    
      # SAVE IT
      @primes << num
    end
  end
end

Code for finding prime numbers

# TEST FOR ALL POSSIBLE FACTORS

def is_factor?(num,factor)
  (num % factor).eql?(0)
end
  
def find_primes1
  @primes = []
  (2..MAX).each do |num|
    is_prime = true
    (2...num).each do |num2|
      if is_factor?(num,num2)
        is_prime = false
        break
      end
    end
    if is_prime
      @primes << num
    end
  end
end

# REMOVE MULTIPLES FROM TALLY 

def find_primes2
  tally = (0..MAX).to_a
  @primes = []
  (0..MAX).each do |num|
    if num < 2
      tally[num] = nil
    elsif !tally[num].nil?
      @primes << num
      xnum = num
      while xnum <= MAX do
        tally[xnum] = nil
        xnum += num
      end 
    end
  end
end

# RUBY LIBRARY CALL

require 'prime'

def find_primes3
  @primes = []
  (2..MAX).each do
      |num|
    if num.prime?    
      @primes << num
    end
  end
end

Comparison of Algorithms

Ruby development tools

• Robocop - A Ruby static code analyzer and formatter, based on the community Ruby style guide.
• rdoc - A Ruby static code analyzer and formatter, based on the community Ruby style guide.
• Rake - a tool that uses standard Ruby syntax.
• Test::Unit - checks that code is compatible with design assertions
• Cu cumber - a behavior driven development system to tests the code against the design specifications
• Rmagick - a graphic library that interfaces with imagemagick to create and modify graphic images.
• DBI: provides a database-agnostic API to load the appropriate DBD (Database Driver) for your database (e.g., MySQL, PostgreSQL, SQLite)

Ruby standard data types

• Numerical primitive objects
  • Integer (with Automatic conversion between Fixnum and Bignum)
  • Float
  • Rational
  • Complex
• Textual primitive objects
  • Characters (with code point)
  • Symbols
• Collective objects
  • Object Classes
  • Array - (includes stacks and queues)
  • Hash - (associated array)
  • String
  • Enumerable

Code examples

#!/usr/bin/env ruby
# Demonstration of Ruby's standard numeric data types

puts "Ruby Data Types".upcase

def unitheader(header)
  puts
  puts header
  puts "-" * 65
end

def example(lbl, op)
   x = eval(op)
   puts " #{lbl.ljust(12)}, #{op.ljust(27)} #{x} (#{x.class})"
end

unitheader("Integer examples:")
example("@int_a","@int_a = 42")
example("@int_b","@int_b = -100")
example("Sum:","@int_a + @int_b")

unitheader("Float examples:")
example("@float_a","@float_a=3.14159")
example("@float_b","@float_b = -0.5")
example("Product:","@float_a * @float_b")

unitheader("Rational examples:")
example("@rational_a","@rational_a = Rational(2,3)")
example("@rational_b","@rational_b = 5r")
example("Sum:","@rational_a + @rational_b")

unitheader("Complex examples:")
example("@complex_a","@complex_a = Complex(2,3)")
example("@complex_b","@complex_b = 4 + 5i")
example("Sum:","@complex_a + @complex_b")

unitheader("Type conversions:")
example("Int2Float:","@int_a.to_f")
example("Float2Int","@float_a.to_i")
example("Int2Rational","@int_a.to_r")
example("Int2Complex","@int_a.to_c")

unitheader("Automatic type promotion:")
example("Int2Float", "@int_a + @float_a")
example("Int2Rational","@int_a + @rational_a")
example("Rational2Flt","@rational_a+@float_a")
example("Complex2Int","@complex_a + @int_a")

unitheader("Edge case: very large integers")
example("@bigInt", "@big_int = 10**20")
example("inc(@bigInt)","@big_int += 1")
puts "-" * 65

Output

RUBY DATA TYPES

Integer examples:
-----------------------------------------------------------------
 @int_a      , @int_a = 42                 42 (Integer)
 @int_b      , @int_b = -100               -100 (Integer)
 Sum:        , @int_a + @int_b             -58 (Integer)

Float examples:
-----------------------------------------------------------------
 @float_a    , @float_a=3.14159            3.14159 (Float)
 @float_b    , @float_b = -0.5             -0.5 (Float)
 Product:    , @float_a * @float_b         -1.570795 (Float)

Rational examples:
-----------------------------------------------------------------
 @rational_a , @rational_a = Rational(2,3) 2/3 (Rational)
 @rational_b , @rational_b = 5r            5/1 (Rational)
 Sum:        , @rational_a + @rational_b   17/3 (Rational)

Complex examples:
-----------------------------------------------------------------
 @complex_a  , @complex_a = Complex(2,3)   2+3i (Complex)
 @complex_b  , @complex_b = 4 + 5i         4+5i (Complex)
 Sum:        , @complex_a + @complex_b     6+8i (Complex)

Type conversions:
-----------------------------------------------------------------
 Int2Float:  , @int_a.to_f                 42.0 (Float)
 Float2Int   , @float_a.to_i               3 (Integer)
 Int2Rational, @int_a.to_r                 42/1 (Rational)
 Int2Complex , @int_a.to_c                 42+0i (Complex)

Automatic type promotion:
-----------------------------------------------------------------
 Int2Float   , @int_a + @float_a           45.14159 (Float)
 Int2Rational, @int_a + @rational_a        128/3 (Rational)
 Rational2Flt, @rational_a+@float_a        3.8082566666666664 (Float)
 Complex2Int , @complex_a + @int_a         44+3i (Complex)

Edge case: very large integers
-----------------------------------------------------------------
 @bigInt     , @big_int = 10**20           100000000000000000000 (Integer)
 inc(@bigInt), @big_int += 1               100000000000000000001 (Integer)
-----------------------------------------------------------------

Vars, Constants, Arrays, Hashes & Symbols

my_variable = “Hello”
my_variable.capitalize! # ! changes the value of the var same as my_name = my_name.capitalize
my_variable ||= "Hi" # ||= is a conditional assignment only set the variable if it was not set before.

Classes

custom objects

class Person # class names are rather written in PascalCase (It is similar to camelCase, but the first letter is capitalized)
  @@count = 0
  attr_reader :name # make it readable
  attr_writer :name # make it writable
  attr_accessor :name # makes it readable and writable

  def Methodname(parameter)
    @classVariable = parameter
    @@count += 1
  end

  def self.show_classVariable
    @classVariable
  end

  def Person.get_counts # is a class method
    return @@count
  end

  private

  def private_method; end # Private methods go here
end

matz = Person.new("Yukihiro")
matz.show_name # Yukihiro

Calculation

• Addition (+)
• Subtraction (-)
• Multiplication (*)
• Division (/)
• Exponentiation (**)
• Modulo (%)
• The concatenation operator (<<)
• Increment: 1 += 1 <br> (1++ and 1– do not exist in ruby)
• Concatenation: "A " << "B" (yields) "A B"
• String/Numerical interpolation: “A #{4} B”

Conditionals

If

if 1 < 2
  puts “one smaller than two”
elsif 1 > 2 
  puts “elsif”
else
  puts “false”
end

puts "be printed" if true
puts 3 > 4 ? "if true" : "else" 

Unless

unless false
  puts “I’m here”
else
  puts “not here”
end

puts "not printed" unless true

Case

case my_var
  when "some value"
    ###
  when "some other value"
    ###
  else
    ###
end

or

case my_var
  when "some value" then ###
  when "some other value" then ###
  else ###
end

Logical functions

• &&: and
• ||: or
• !: not
• (x && (y || w)) && z: use parenthesis to combine arguments
• problem = false
• print “Good to go!” unless problem –– prints out because problem != true

Loops

While loop

i = 1
while i < 11
  puts i
  i = i + 1
end

Until loop

i = 0
until i == 6
  puts i
  i += 1
end