VKEDCO: Vladimir Kulyukin's Education Coop

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 14

2012-02-27T15:29:00.002-08:00

Polymorphism, Encapsulation, Inheritance, Riley's Duck Test, Duck Typing, Critique of Duck Typing, Polymorphism vs. Encapsulation, Encapsulation & Privacy, Class Scope, Multiple Inheritance, Multiple Inheritance Pitfalls
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 14

View more presentations from Vladimir Kulyukin

Quiz 06

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 07

2012-02-24T13:10:00.005-08:00

1. http://en.wikipedia.org/wiki/Cosine_similarity

Department of Computer Science
Utah State University

Learning Objectives

1. Basic image processing with Python Image Library (PIL)

2. Exposure to zone matching in Optical Character Recognition

3. List and dictionary manipulation in Python

Zone Matching

Zone matching is a technique used in computer vision for image matching. An image is divided into several sub-images, called zones. In each zone, a specific statistic is computed. For example, that statistic can be the number of horizontal lines or the number of pixels of a specific color. Consider the image below. The image is divided into 4 zones. Suppose that statistic that we are interested in is the count of black pixels in each zone.

Moving clockwise from the top left zone (zone 1), there are 2 black pixels in zone 1, 3 black pixels in zone 2, 4 black pixels in zone 3, and 5 black pixels in zone 4. The the zone vector for the above image is [2, 3, 4, 5].

If we want to match two images, img1 and img2, we can compute two zone vectors, zv1 and zv2, and then match them by computing their similarity index. One similarity index is cosine similarity that can be computed by the following formula, where A and B are two vectors (sequences of numbers):

The above formula can be implemented in Python as follows:

import math
def cosine_similarity(zv1, zv2):
    '''
    cosine_similarity(zv1, zv2) -> float
    this function computes the cosine similarity between two vectors zv1 and zv2.
    '''
    dotp = sum(map(lambda x, y: x * y, zv1, zv2))
    zmagn1 = math.sqrt(sum([v1*v1 for v1 in zv1]))
    zmagn2 = math.sqrt(sum([v2*v2 for v2 in zv2]))
    return float(dotp)/(zmagn1 * zmagn2)

The cosine similarity metric returns values in the range [-1, 1] with 1 referring to sameness (closest similarity) and -1 referring to the exact opposites.

>>> cosine_similarity([1, 2], [1, 2])
0.9999999999999998
>>> cosine_similarity([1, 2], [-1, -2])
-0.9999999999999998

Zone Matching in Optical Character Recognition

Suppose that we have two character bitmaps and we want to compute how similar they are. In OCR, such bitmaps can be obtained through character segmentation when an text image is segmented into individual characters.

To do zone matching, we compute two zone vectors and then apply a similarity metric, e.g. cosine similarity, that returns a number indicating how similar the two bitmaps are.

How many zones should we have? The answer depends on the needs of a specific OCR application and can range from the number of pixels in the image (essentially each pixel becomes its own zone) to 1 (the entire image is considered to be the only zone).

In this assignment, we will make two simplifying assumptions: 1) all character bitmaps are 20 x 20 and 2) each image is broken into 16 5 x 5 zones. Thus, if each zone is specified in terms of its top left and bottom right corners, the first zone in the top left corner is (0, 0, 4, 4), the second zone immediately to the right of the first zone is (5, 0, 9, 4), the third zone immediately to the right of the second zone is (10, 0, 14, 4), and the fourth zone immediately to the right of the third zone is (15, 0, 19, 4). In general, the coordinates of each zone are as follows.

>>> zone_coords = ((0, 0, 4, 4),   (5, 0, 9, 4),   (10, 0, 14, 4),   (15, 0, 19, 4),
               (0, 5, 4, 9),   (5, 5, 9, 9),   (10, 5, 14, 9),   (15, 5, 19, 9),
               (0, 10, 4, 14), (5, 10, 9, 14), (10, 10, 14, 14), (15, 10, 19, 14),
               (0, 15, 4, 19), (5, 15, 9, 19), (10, 15, 14, 19), (15, 15, 19, 19))

What to Implement

zone_vector(imgpath, zone_coords)

- imgpath is a path of an 20 x 20 RGB bitmap with a single character

- zone_coords is a list of 4-tuples, each of which specifies the top left and bottom right coordinates of a 5x5 zone

The zone_vector function returns the list of black pixel counts in each of the 16 zones:

>>> zone_vector('C:/Python27/my_code/letter_images_courR18/A.BMP', zone_coords)
[2, 13, 1, 0, 0, 12, 10, 0, 6, 13, 15, 0, 6, 6, 10, 2]

build_zone_vector_map(dir, zone_coords)

- dir is a directory, zone_coords is a sequence of zone coords (4-tuples)

- dir is assumped to store 20x20 RGB bitmaps of 26 ASCII characters: A.bmp, B.bmp, C.bmp, etc.

The function build_zone_vector_map returns a dictionary that maps characters to their zone vectors:

>>> zv_map = build_zone_vector_map('C:/Python27/my_code/letter_images_courR18/', zone_coords)
>>> zv_map
{'A': [2, 13, 1, 0, 0, 12, 10, 0, 6, 13, 15, 0, 6, 6, 10, 2], 'C': [1, 10, 12, 0, 9, 2, 4, 0, 8, 4, 2, 0, 0, 8, 8, 0], 'B': [4, 12, 10, 0, 0, 16, 16, 0, 0, 10, 7, 5, 4, 10, 9, 0], 'E': [4, 12, 12, 0, 0, 16, 12, 0, 0, 10, 7, 3, 4, 10, 10, 2], 'D': [7, 11, 9, 0, 5, 5, 7, 4, 5, 5, 8, 3, 6, 10, 7, 0], 'G': [1, 10, 11, 3, 9, 2, 2, 2, 8, 4, 14, 5, 0, 8, 8, 0], 'F': [4, 12, 11, 3, 0, 16, 10, 2, 0, 10, 4, 0, 4, 10, 2, 0], 'I': [2, 12, 8, 0, 0, 10, 0, 0, 0, 10, 0, 0, 2, 10, 8, 0], 'H': [7, 7, 12, 2, 5, 13, 14, 0, 5, 5, 10, 0, 6, 6, 10, 2], 'K': [7, 7, 13, 0, 5, 18, 3, 0, 5, 9, 11, 0, 6, 6, 6, 2], 'J': [0, 8, 12, 2, 0, 0, 10, 0, 8, 1, 11, 0, 1, 10, 3, 0], 'M': [8, 4, 10, 2, 10, 11, 19, 0, 10, 4, 10, 0, 6, 4, 8, 2], 'L': [4, 12, 2, 0, 0, 10, 0, 0, 0, 10, 6, 0, 4, 10, 10, 0], 'O': [1, 10, 9, 0, 9, 2, 7, 4, 8, 4, 9, 3, 0, 8, 6, 0], 'N': [5, 7, 10, 2, 5, 15, 10, 0, 5, 7, 18, 0, 4, 6, 7, 0], 'Q': [1, 10, 9, 0, 9, 2, 7, 4, 8, 4, 9, 3, 0, 19, 16, 2], 'P': [4, 12, 10, 1, 0, 10, 6, 5, 0, 16, 8, 0, 4, 10, 2, 0], 'S': [1, 11, 12, 0, 3, 13, 7, 0, 6, 2, 14, 0, 4, 9, 7, 0], 'R': [7, 11, 7, 0, 5, 9, 12, 0, 5, 10, 11, 0, 6, 6, 6, 2], 'U': [5, 7, 10, 2, 5, 5, 10, 0, 4, 6, 10, 0, 0, 9, 7, 0], 'T': [6, 12, 12, 0, 6, 10, 6, 0, 0, 10, 0, 0, 0, 10, 6, 0], 'W': [8, 4, 10, 2, 10, 14, 14, 0, 7, 11, 18, 0, 2, 4, 6, 0], 'V': [8, 4, 10, 2, 5, 5, 10, 0, 0, 11, 9, 0, 0, 6, 2, 0], 'Y': [8, 7, 13, 2, 1, 13, 10, 0, 0, 10, 0, 0, 0, 10, 6, 0], 'X': [8, 7, 13, 2, 1, 14, 9, 0, 3, 11, 12, 0, 6, 6, 10, 2], 'Z': [3, 11, 13, 0, 2, 5, 11, 0, 1, 13, 6, 0, 2, 10, 10, 0]}

find_best_zv_char_match(char_zv, zv_map, similarity=cosine_similarity)

- char_zv is a zone vector of a specific character

- zv_map is a dictionary computed by build_zone_vector_map

- similarity if a similarity function that computes the similarity coefficient of two vectors as explained above; the function defaults to cosine_similarity

The find_best_zv_char_match function computes the similarity coefficients between char_zv and each zone vector in zv_map and returns a 2-tuple (character, similarity) describing the best matching character, i.e., the character in zv_map whose zone vector is closest to char_zv.

## Assume that these two directories store 26 images each of characters generated with two PIL fonts: helvR18 (helvetica)

## and courR18 (courier). You can download both directories from the links below.

>>> helvR18_dir = 'C:/Python27/my_code/letter_images_helvR18/'
>>> courR18_dir = 'C:/Python27/my_code/letter_images_courR18/'

## Build zone vector maps of both directories

>>> zv_helvR18_map = build_zone_vector_map(helvR18_dir, zone_coords)
>>> zv_courR18_map = build_zone_vector_map(courR18_dir, zone_coords)

## Find which courier character in the courier map best matches 'A' in the helvetica map:
>>> find_best_zv_char_match(zv_helvR18_map['A'], zv_courR18_map)
('A', 0.8921846206693678)

find_all_zv_char_matches(char_zv, zv_map, similarity=cosine_similarity)

- char_zv is a zone vector of a specific character

- zv_map is a dictionary computed by build_zone_vector_map

- similarity if a similarity function that computes the similarity coefficient of two vectors as explained above; the function defaults to cosine_similarity

The find_best_zv_char_match returns a list of all the 2-tuple matches to char_zv in zv_map sorted by similarity from smallest to largest:

## Build the zone vector maps

>>> zv_helvR18_map = build_zone_vector_map(helvR18_dir, zone_coords)
>>> zv_courR18_map = build_zone_vector_map(courR18_dir, zone_coords)

## Fetch all the matches in the courier map to 'A' in the helvetica map

>>> find_all_zv_char_matches(zv_helvR18_map['A'], zv_courR18_map)
[('A', 0.8921846206693678), ('R', 0.8867527803753008), ('N', 0.857364436133189), ('X', 0.8410813744186475), ('W', 0.8252742885180057), ('S', 0.8117208610738799), ('K', 0.8112849008138655), ('H', 0.8110106998168068), ('E', 0.7942097508553673), ('P', 0.793036432410823), ('B', 0.7880989046578882), ('M', 0.7660952365076868), ('F', 0.7647614851398058), ('U', 0.7449156574968028), ('D', 0.7420315011847803), ('V', 0.7348251972826993), ('Z', 0.7341292322409033), ('J', 0.6969592496086756), ('O', 0.6933631327550601), ('G', 0.6704625620142035), ('L', 0.6561226059771946), ('Y', 0.6241987114939874), ('T', 0.6146999759695536), ('I', 0.5898578441953785), ('C', 0.5573705223352501), ('Q', 0.532469639637666)]

## Fetch all the matches in the courier map to 'A' in the helvetica map
>>> find_all_zv_char_matches(zv_helvR18_map['B'], zv_courR18_map)
[('D', 0.8875154490908648), ('H', 0.8735458011442355), ('M', 0.8631289484030148), ('C', 0.8230426492867466),

('O', 0.8131857091782351), ('U', 0.8124257209396084), ('R', 0.8022079736569203), ('B', 0.7963716924968524), ('E', 0.7961110741278905), ('Q', 0.794974685832749), ('T', 0.7814453499703188), ('S', 0.7731875146911998), ('X', 0.7707512518942817), ('Y', 0.7703962650853087), ('K', 0.7530620390345039), ('Z', 0.7484446753728139), ('G', 0.7374219285169179), ('N', 0.7322517854077153), ('F', 0.72647889366848), ('W', 0.7219962528093908), ('J', 0.6953747379723422), ('V', 0.6813651169374652), ('I', 0.6542987929075076), ('A', 0.6394440395522312), ('P', 0.6216523199438762), ('L', 0.6211891591279907)]

Due Date

March 03, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_07_YourFirstName_YourLastName.py and drop it into your Dropbox folder. Your code should implement zone_vector(imgpath, zone_coords), build_zone_vector_map(dir, zone_coords), find_best_zv_char_match(char_zv, zv_map, similarity=cosine_similarity), and find_all_zv_char_matches(char_zv, zv_map, similarity=cosine_similarity) according to the above specifications. You can test your code with these two bitmap directories (cour18.rar and helvR18.rar) that you can uncompress on your computer.

References

2. http://www.pythonware.com/products/pil/index.htm

3. http://en.wikipedia.org/wiki/Optical_character_recognition

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 05 Solution

2012-02-24T08:21:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 05 Solution

View more presentations from Vladimir Kulyukin

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 13

2012-02-23T07:16:00.000-08:00

PIL Basics, Creating & Saving Images, Getting & Setting Pixel Values, PIL Coordinates, PIL Colors, PIL Fonts, Image, ImageDraw, ImageFont, Classes vs. Objects, Data & Method Attributes
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 13

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Trie in Python

2012-02-21T09:35:00.000-08:00

### *********************************************************
### Module: trie.py
### Description: A list and tuple based Python implementation
### of the Trie data structure that supports the following
### methods:
### 1. insert_key(k, v, trie) - insert a non-empty string key k
###    into trie and associate k with value v
### 2. has_key(k, trie) - True if trie has key k
### 3. retrieve_val(k, trie) - retrieve value indexed under key
###    k in trie
### 4. start_with_prefix(prefix, trie) - return the list of
###    all keys in trie that start with prefix.
###
### Bugs, comments to vladimir dot kulyukin at gmail dot com
### *********************************************************

### ***************** HELPER FUNCTIONS **********************

def is_trie_bucket(x):
    return isinstance(x, tuple) and \
           len(x) == 2 and \
           isinstance(x[0], str) and \
           isinstance(x[1], list) and \
           len(x[1]) == 1

def is_trie_branch(x):
    return isinstance(x, list)

def get_bucket_key(b):
    return b[0]

def get_bucket_val(b):
    return b[1][0]

### ******************** INSERT_KEY ************************

def insert_key(k, v, trie):
    ## do not insert empty keys
    if k == '':
        return None
    ## if trie has k or stores it with the same value v,
    ## do not insert
    elif has_key(k, trie) and retrieve_val(k, trie) == v:
        return None
    else:
        tr = trie
        ## for each character c in k, find a child
        ## branch that starts with c
        for c in k:
            branch = find_child_branch(tr, c)
            ## if there is no branch that starts with c,
            ## create it and append it at the end of
            ## the current level.
            if branch == None:
                new_branch = [c]
                tr.append(new_branch)
                tr = new_branch
            else:
                tr = branch
        ## tr is now bound to the branch, so insert
        ## a new bucket.
        tr.append((k,[v]))
        return None

## a branch is either empty or it is a list whose first
## element is a character and the rest are buckets or
## sub-branches.
def get_child_branches(trie):
    if trie == []:
        return []
    else:
        return trie[1:]

def find_child_branch(trie, c):
    for branch in get_child_branches(trie):
       if branch[0] == c:
           return branch
    return None

### ************************ HAS_KEY *************************

def has_key(k, trie):
    br = retrieve_branch(k, trie)
    if br == None:
        return False
    else:
        return is_trie_bucket(get_child_branches(br)[0])

### ******************** RETRIEVE_VAL ************************

## find a branch in trie that is indexed under k.
def retrieve_branch(k, trie):
    if k == '':
        return None
    else:
        tr = trie
        for c in k:
            br = find_child_branch(tr, c)
            if br == None:
                return None
            else:
                tr = br
        return tr

## find a branch and retrieve its bucket, second element.
def retrieve_val(k, trie):
    if not has_key(k, trie): return None
    br = retrieve_branch(k, trie)
    return get_bucket_val(br[1])

### *************** START_WITH_PREFIX ************************

def start_with_prefix(prefix, trie):
    ## 1. find the branch indexed by prefix
    br = retrieve_branch(prefix, trie)
    if br == None: return []

    key_list = []
    q = get_child_branches(br)
    ## 2. go through the sub-branches of the
    ## branch indexed by the prefix and
    ## collect the bucket strings into key_list
    while not q == []:
        curr_br = q.pop(0)
        if is_trie_bucket(curr_br):
            key_list.append(get_bucket_key(curr_br))
        elif is_trie_branch(curr_br):
            q.extend(get_child_branches(curr_br))
        else:
            return 'ERROR: bad branch'
    return key_list

### ************************** TESTS **************************

### construct a trie from http://en.wikipedia.org/wiki/Trie
def test_01():
    tr = [[]]
    insert_key('to', 7, tr)
    insert_key('tea', 3, tr)
    insert_key('ted', 4, tr)
    insert_key('ten', 12, tr)
    insert_key('A', 15, tr)
    insert_key('i', 11, tr)
    insert_key('in', 5, tr)
    insert_key('inn', 9, tr)
    return tr

### test start_with_prefix on the trie returned by test_01()
def test_02():
    tr = test_01()
    print start_with_prefix('t', tr)
    print start_with_prefix('te', tr)
    print start_with_prefix('i', tr)

the_tent = '''
            THE TENT
        Jalaluddin Rumi

Outside, the freezing desert night.
This other night inside grows warm, kindling.
Let the landscape be covered with thorny crust.
We have a soft garden in there.
The continents blasted,
cities and little towns, everything
become a scorched, blackened ball.
The news we hear is full of grief for that future,
but the real news inside here
is there's no news at all.

Translated from the Persian by Coleman Barks
'''

import string

### remove punctuation and '\n' from txt
### and lowercase all characters
def normalize_text(txt):
    ntxt = txt.strip()
    for pc in string.punctuation:
        ntxt = ntxt.replace(pc, ' ')
    ntxt = ntxt.replace('\n', ' ')
    ntxt = ntxt.lower()
    return ntxt

### construct a trie whose keys are words in
### the normalized text of Rumi's poem 'The Tent'
def test_03():
    tent_normalized = normalize_text(the_tent)
    words = tent_normalized.split(' ')
    tr = [[]]
    for w in words:
        insert_key(w, True, tr)
    return tr

### try a few calls with start_with_prefix on
### the trie constructed in test_03()
def test_04():
    tr = test_03()
    print start_with_prefix('th', tr)
    print start_with_prefix('b', tr)
    print start_with_prefix('bl', tr)
    print start_with_prefix('bla', tr)

Python & Perl: Assignment 06

2012-02-17T16:51:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 06

View more presentations from Vladimir Kulyukin

Due Date

February 24, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_06_YourFirstName_YourLastName.py and drop it into your Dropbox folder. Your code should also implement the function discussed draw_tile_ornament(imgpath='', imgsize=(0,0), ornament=[], tileside=1). Test your code on the following ornament representation and save the generated bitmap into your Dropbox folder as my_tile_ornament.bmp.

## r is red, w is white, o is outline color (blue)
r, w, o = (255, 0, 0), (255, 255, 255), (0, 0, 255)
ornament_01 = [
        [(1, r, o), (8, w, o), (1, r, o)],
        [(1, w, o), (1, r, o), (6, w, o), (1, r, o), (1, w, o)],
        [(2, w, o), (1, r, o), (4, w, o), (1, r, o), (2, w, o)],
        [(3, w, o), (1, r, o), (2, w, o), (1, r, o), (3, w, o)],
        [(4, w, o), (2, r, o), (4, w, o)],
        [(4, w, o), (2, r, o), (4, w, o)],
        [(3, w, o), (1, r, o), (2, w, o), (1, r, o), (3, w, o)],
        [(2, w, o), (1, r, o), (4, w, o), (1, r, o), (2, w, o)],
        [(1, w, o), (1, r, o), (6, w, o), (1, r, o), (1, w, o)],
        [(1, r, o), (8, w, o), (1, r, o)],
        ]

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 12

2012-02-16T07:17:00.004-08:00

Function Parameters, Positional Parameters, Keyword Parameters, Collecting Positional and Keyword Parameters with * and ** Operators, Parameter Distribution, Scoping, Nested Scopes, Scope Sensitivity of vars(), Functional Programming, map(), reduce(), filter(), Lambda Expressions
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 12

View more presentations from Vladimir Kulyukin

Quiz 05

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 04 Solution

2012-02-14T13:14:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 04 Solution

View more presentations from Vladimir Kulyukin

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Manual and Auto Generation of Huffman Trees in Python

2012-02-14T11:26:00.000-08:00

###########################################################################
### Manual and Auto Generation of Huffman Trees
###
### PDF slides are at
### - http://vkedco.blogspot.com/2012/01/python-perl-lecture-05.html
### - http://vkedco.blogspot.com/2012/02/python-perl-assignment-04.html
###
### Bugs, comments to vladimir dot kulyukin at gmail dot com
###########################################################################

def make_leaf(symbol, weight):
    return (symbol, weight)

def is_leaf(x):
    return isinstance(x, tuple) and \
            len(x) == 2 and \
            isinstance(x[0], str) and \
            isinstance(x[1], int)

def get_leaf_symbol(leaf):
    return leaf[0]

def get_leaf_freq(leaf):
    return leaf[1]

def get_left_branch(huff_tree):
    return huff_tree[0]

def get_right_branch(huff_tree):
    return huff_tree[1]

def get_symbols(huff_tree):
    if is_leaf(huff_tree):
        return [get_leaf_symbol(huff_tree)]
    else:
        return huff_tree[2]

def get_freq(huff_tree):
    if is_leaf(huff_tree):
        return get_leaf_freq(huff_tree)
    else:
        return huff_tree[3]

def make_huffman_tree(left_branch, right_branch):
    return [left_branch,
            right_branch,
            get_symbols(left_branch) + get_symbols(right_branch),
            get_freq(left_branch) + get_freq(right_branch)]

########################################################################
###             Two Manually Constructed Huffman Trees
########################################################################

### Picture of manual_ht01 is at
### http://vkedco.blogspot.com/2012/01/python-perl-lecture-05.html
manual_ht01 = make_huffman_tree(make_leaf('A', 4),
                             make_huffman_tree(make_leaf('B', 2),
                                               make_huffman_tree(make_leaf('D', 1),
                                                              make_leaf('C', 1))))

### Picture of manual_ht02 defined below is at
### http://vkedco.blogspot.com/2012/01/python-perl-lecture-05.html
E_1 = make_leaf('E', 1)
F_1 = make_leaf('F', 1)

G_1 = make_leaf('G', 1)
H_1 = make_leaf('H', 1)

C_1 = make_leaf('C', 1)
D_1 = make_leaf('D', 1)

B_3 = make_leaf('B', 3)
A_8 = make_leaf('A', 8)

EF_2 = make_huffman_tree(E_1, F_1)
GH_2 = make_huffman_tree(G_1, make_leaf('H', 1))
EFGH_4 = make_huffman_tree(EF_2, GH_2)

CD_2 = make_huffman_tree(C_1, D_1)
BCD_5 = make_huffman_tree(B_3, CD_2)

BCDEFGH_9 = make_huffman_tree(BCD_5, EFGH_4)

ABCDEFGH_17 = make_huffman_tree(A_8, BCDEFGH_9)
manual_ht02 = ABCDEFGH_17

########################################################################
###         Huffman Encoding and Decoding
########################################################################

def huffman_decode(bits, huff_tree):
    if bits == []: return []
    curr_branch = huff_tree
    next_branch = None
    decoding = []
    while bits != []:
        next_branch = select_branch(bits[0], curr_branch)
        if is_leaf(next_branch):
            decoding.append(get_leaf_symbol(next_branch))
            curr_branch = huff_tree
        else:
            curr_branch = next_branch
        del bits[0]
    return decoding

def select_branch(bit, tree):
    if bit == 0:
        return get_left_branch(tree)
    elif bit == 1:
        return get_right_branch(tree)
    else:
        return 'ERROR: Incorrect Bit'

def huffman_encode(symbols, htree):
    encoding = []
    for s in symbols:
        encoding.extend(huffman_encode_symbol(s, htree))
    return encoding

def huffman_encode_symbol(s, htree):
    encoding = []
    curr_branch = htree
    while not is_leaf(curr_branch):
        if not s in get_symbols(curr_branch):
            return 'ERROR: Symbol not in tree'
        elif s in get_symbols(get_left_branch(curr_branch)):
            encoding.append(0)
            curr_branch = get_left_branch(curr_branch)
        elif s in get_symbols(get_right_branch(curr_branch)):
            encoding.append(1)
            curr_branch = get_right_branch(curr_branch)
        else:
            return 'ERROR: Symbol in neither branch'
    return encoding

######################################################################
###             Auto-Generation of Huffman Trees
######################################################################

the_tent = '''
            THE TENT
        Jalaluddin Rumi

Outside, the freezing desert night.
This other night inside grows warm, kindling.
Let the landscape be covered with thorny crust.
We have a soft garden in there.
The continents blasted,
cities and little towns, everything
become a scorched, blackened ball.
The news we hear is full of grief for that future,
but the real news inside here
is there's no news at all.

Translated from the Persian by Coleman Barks
'''

### take a string txt and return a dictionary that maps each
### character to its frequency in the string
def freq_table(txt):
    ftble = {}
    for c in txt:
        if c not in ftble:
            ftble[c] = 1
        else:
            ftble[c] += 1
    return ftble

### this is a comparator function that allows us to compare
### Huffman nodes to each other.
def huff_node_freq_cmp(node1, node2):
    freq1, freq2 = get_freq(node1), get_freq(node2)
    if freq1 < freq2:
        return -1
    elif freq1 > freq2:
        return 1
    else:
        return 0

### insert an item into its appropriate place in a list given
### a comparator function cmpf, e.g., huff_node_freq_cmp
def insert_item(item, lst, cmpf):
    def insert_item_aux(item, lst, cmpf, n, pos):
        if pos == n:
            lst.append(item)
        elif cmpf(item, lst[pos]) == -1 or cmpf(item, lst[pos]) == 0:
            lst.insert(pos, item)
        else:
            insert_item_aux(item, lst, cmpf, n, pos+1)

    insert_item_aux(item, lst, cmpf, len(lst), 0)

### one way to combine two Huffman nodes is to let the left node
### be the left branch and the right node be the right branch.
def combine_left_right(n1, n2):
    return make_huffman_tree(n1, n2)

### another way to combine two Huffman nodes is to let the left node
### be the right branch and the right node be the left branch.
def combine_right_left(n1, n2):
    return make_huffman_tree(n2, n1)

### the work horse function called by build_huffman_tree below.
### It takes a list of Huffman nodes and a combiner function, e.g.,
### combine_left_right and returns a Huffman tree.
### Important: nodes are assumed to be sorted by their
### frequencies from smallest to largest. So that the first
### two nodes in nodes
def build_huffman_tree_aux(node_lst, combine):
    if len(node_lst) == 0:
        return None
    elif len(node_lst) == 1:
        return node_lst[0]
    else:
        ## keep looping so long as there are more than two nodes
        ## in node_lst.
        while len(node_lst) > 2:
            ## 1. combine two nodes with the lowest frequencies
            new_node = combine(node_lst[0], node_lst[1])
            ## 2. delete two combined nodes from node_lst
            del node_lst[0]
            del node_lst[0]
            ## 3. insert new_node into node_lst into its right
            ## position.
            insert_item(new_node, node_lst, huff_node_freq_cmp)
            ## print nodes
        else:
            return make_huffman_tree(node_lst[0], node_lst[1])

def build_huffman_tree(txt, combine=combine_left_right):
    ### 1. build a frequency table from txt
    ftble = freq_table(txt)
    ### 2. get the list of Huffman nodes
    node_lst = ftble.items()
    ### 3. sort node_lst by the node frequency from smallest
    ###    to largest
    node_lst.sort(huff_node_freq_cmp)
    ### 4. call the above build_huffman_tree_aux workhorse
    return build_huffman_tree_aux(node_lst, combine)

###########################################################################
##                              Tests
###########################################################################

test_txt_01 = 'AAAAAAAABBBCDEFGH'

def test_01():
    ht = build_huffman_tree(test_txt_01)
    print huffman_encode('A', ht)
    print huffman_encode('B', ht)
    print huffman_encode('C', ht)

def test_02():
    ht = build_huffman_tree(the_tent)
    return the_tent == ''.join(huffman_decode(huffman_encode(the_tent, ht), ht))

Python & Perl: Lecture 11

2012-02-14T07:19:00.000-08:00

Run-Time Code Generation, Execution, & Evaluation, Functional Abstraction, Function Introspection, Installing Python Image Library (PIL)
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 11

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 05

2012-02-10T16:58:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 05

View more presentations from Vladimir Kulyukin

Due Date

February 17, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_05_YourFirstName_YourLastName.py and drop it into your Dropbox folder. You should use only list and tuple to implement the Trie data structure. Your code should also implement the four functions discussed in the Assignment screencast: insert_key(k, v, trie), retreive_val(k, trie), has_key(k, trie), and start_with_prefix(prefix, trie).

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 10

2012-02-08T16:17:00.000-08:00

List Comprehension with Nested For-Loops, List Comprehension with Matrices, List Comprehension & Loop Variables, List Comprehension Uses, pass, del, exec()
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 10

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 03 Solution

2012-02-07T16:44:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 03 Solution

View more presentations from Vladimir Kulyukin

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 09

2012-02-06T17:02:00.000-08:00

Variable Assignments, Sequence Unpacking, range(), xrange(), zip(), enumerate(), List Comprehension
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 09

View more presentations from Vladimir Kulyukin

Quiz 04

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 04

2012-02-03T15:17:00.001-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 04

View more presentations from Vladimir Kulyukin

Due Date

February 10, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_04_YourFirstName_YourLastName.py and drop it into your Dropbox folder.

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 08

2012-02-01T15:14:00.000-08:00

String Templates, Data Abstraction: Auto-Generation of Huffman Trees, Deep and Shallow Copying, Dictionary Access with get(), Creating Dictionaries from Keys and Key-Value Pairs, Dictionaries as Flexible Lookup Lists, Dictionaries as Sparse Data Structures, Dictionaries as Format Specifiers
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 08

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 07

2012-01-30T15:57:00.000-08:00

String Methods find(), split(), join(), replace(), translate(), Dictionaries, Dictionary Construction, Dictionary Access, Adding New Key-Value Pairs to Dictionaries
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 07

View more presentations from Vladimir Kulyukin

Quiz 03

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 03

2012-01-27T06:54:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 03

View more presentations from Vladimir Kulyukin

Learning Objectives

This assignment has three learning objectives: 1) list manipulation; 2) data abstraction with lists; and 3) huffman coding. You may want to review the slides and screencasts of Lecture 05 before working on this assignment.

Huffman Encoding

Let us use the tree on Slide 14 to see how Huffman trees can encode symbols. Suppose we need to encode a symbol. We start at the root node and check if the symbol is in its list of symbols. If it is not, we return an error message, because the tree does not have the symbol we wish to encode. If it is, we check if the symbol is in the list of symbols of the left branch or the right branch. If it is in the list of symbols of the left branch, we add 0 to our encoding and go left. If it is in the list of symbols of the right branch, we add 1 to our encoding and go right. When we reach a leaf whose only symbol is the symbol we are encoding, we are done. The gist of the Huffman encoding algorithm boils down to this simple selection: if the symbol is in the left branch, add 0 to your encoding and recurse left; if it is in the right branch, add 1 to your encoding and recurse right; if the symbol is in neither branch, return an error.

Let us consider an example. Suppose we want to encode 'B' with the tree on Slide 14 of Lecture 05. We start by checking if 'B' is on the list of symbols of the root node {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}:17. Since it is, we check if 'B' is in the list of symbols of the left branch rooted at {'A'}:8 or the list of symbols of the right branch rooted at {'B', 'C', 'D', 'E', 'F', 'G', 'H'}:9. Since 'B' is in the list of symbols of the right branch, we add 1 to our encoding and recurse to the right branch. We again check if 'B' is in the list of symbols of the left branch rooted at {'B', 'C', 'D'}:5 or in the list of symbols of the right branch rooted at {'E', 'F', 'G', 'H'}:4. Since 'B' is in the left branch, we add 0 to our encoding and recurse left to {'B', 'C', 'D'}:5. We again check if 'B' is in the left branch or the right branch of this node. It is in the left one, so we add 0 to our encoding and recursive to B:3. Since this is a leaf whose only symbol is 'B', we are done. So the resulting encoding of 'B' in this tree is 100.

To encode a list of symbols is to produce a list of bits that encodes each individual symbol in the list in the order in which they occur. For example, the encoding of ['A', 'B', 'B', 'A'] is [0, 1, 0, 0, 1, 0, 0, 0].

Huffman Decoding

Decoding is the reverse of encoding. We are given a list of bits and produce the corresponding list of symbols. For example, if our tree is the one on Slide 14 of Lecture 05 and our list of bits is equal to [0], we return ['A'].

In general, given a list of bits, we start at the root of the Huffman tree and use each bit to go either left or right. Once we reach a leaf node, we add the symbol of the leaf node to our result and start at the top. If we run out of bits before reaching a leaf, we signal an error. If the list of bits contains something other than 0 or 1, we also signal an error.

Suppose we want to use the tree on Slide 14 of Lecture 05 to decode the bit list [0, 1, 0, 0, 1, 0, 0, 0]. We start at the top of the tree. We read 0 and reach the leaf {'A'}:8. Thus, we add 'A' to our result. We start again at the top and read 1 to reach {'B', 'C', 'D', 'E', 'F', 'G', 'H'}:9. This is not a leaf, so we read the next bit, which is 0, to go to {'B', 'C', 'D'}:5. This is not a leaf either, so we read the next bit and reach B:3. This is a leaf, so we add 'B' to our result. It is easy to verify that the remainder of the bit stream, i.e., [1, 0, 0, 0], adds 'B' and 'A' to the result decoding. Thus, [0, 1, 0, 0, 1, 0, 0, 0] is decoded as ['A', 'B', 'B', 'A'].

What to Impelement

Implement the Huffman tree functions defined Lecture 05 and the accompanying screencast, and use the function make_huffman_tree to build the Huffman tree given on Slide 14 of Lecture 05.
Implement the function huffman_encode(symbols, huffman_tree) that takes a list of symbols and the root of a Huffman tree and returns the list of bits that encode the symbols. For example, if ht is a variable bound the huffman tree on Slide 14, then:

>>> huffman_encode(['B', 'A', 'C'], ht)
[1, 0, 0, 0, 1, 0, 1, 0]
>>> huffman_encode(['A', 'B', 'B', 'A'], ht)
[0, 1, 0, 0, 1, 0, 0, 0]

Implement the function huffman_decode(bits, huffman_tree) that takes a list of bits and the root of a Huffman tree and returns the list of symbols encoded by the bits. For example, if ht is a variable bound to the huffman tree on Slide 14, then:

>>> huffman_decode([0, 1, 0, 0, 1, 0, 0, 0], ht)
['A', 'B', 'B', 'A']
>>> huffman_decode([1, 0, 0, 0, 1, 0, 1, 0], ht)
['B', 'A', 'C']

Note that since encoding and decoding are the reversals of each other, the correctness of your implementation can be tested as follows:

>>> msg = ['B', 'A', 'C']
>>> code = [1, 0, 0, 0, 1, 0, 1, 0]
>>> huffman_decode(huffman_encode(msg, ht), ht)
['B', 'A', 'C']
>>> huffman_decode(huffman_encode(msg, ht), ht) == msg
True
>>> huffman_encode(huffman_decode(code, ht), ht) == code
True

Due Date

February 03, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_03_YourFirstName_YourLastName.py and drop it into your Dropbox folder.

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Eyes-Free Barcode Scanning and Nutrition Information Extraction on Smartphones

2012-01-25T12:30:00.000-08:00

Eyes-Free Barcode Scanning and Nutrition Information Extraction on Smartphones
Research Seminar at the Faculty of Informatics, University of Ljubljana, Ljubljana, Slovenia
Vladimir Kulyukin

Department of Computer Science

Utah State University

Eyes-Free Barcode Scanning and Nutrition Information Extraction on Smartphones

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 02

2012-01-19T14:38:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 02

View more presentations from Vladimir Kulyukin

Due Date

January 27, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_02_YourFirstName_YourLastName.py and drop it into your Dropbox folder.

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 06

2012-01-19T06:47:00.000-08:00

Strings, String Manipulation, String Formatting, Format Specifiers, Specifier Widths, Specifier Precision, Optional Conversion Flags, String Module, join(), Object Comparison, While and For Loops
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 06

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 05

2012-01-18T17:30:00.000-08:00

Data Abstraction, Building Huffman Trees with Lists and Tuples, List Manipulation, list.append(), list.extend(), list.remove(), list.reverse(), list.index(), list.count(), list.sort(), Customizing list.sort()
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 05

View more presentations from Vladimir Kulyukin

Quiz 02

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 04

2012-01-18T13:58:00.000-08:00

Types in Python, Dynamic and Strong Typing, Duck Typing, Python Built-in Sequences, Lists
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 04

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Toward Real Time Eyes-Free Barcode Scanning on Smartphones in Video Mode

2012-01-17T18:10:00.000-08:00

Toward Real Time Eyes-Free Barcode Scanning on Smartphones in Video Mode
Vladimir Kulyukin

Department of Computer Science

Utah State University

Aliasgar Kutiayanawala

Department of Computer Science

Utah State University

John Nicholson

Computer Science & IT Department

Austin Peay University

Toward Real Time Eyes-Free Barcode Scanning on Smartphones in Video Mode

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 03

2012-01-17T07:19:00.000-08:00

Python Built-In Objects, Numbers, Numeric Operations, Modules, User Input, Strings
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 03

View more presentations from Vladimir Kulyukin

Quiz 01

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignment 01

2012-01-13T12:28:00.000-08:00

Department of Computer Science
Utah State University

Python & Perl: Assignment 01

View more presentations from Vladimir Kulyukin

Due Date

January 20, 2012, by 11:59pm

What and Where to Submit

Save your code in Assignment_01_YourFirstName_YourLastName.py and drop it into your Dropbox folder.

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Eyes-Free Barcode Scanning and Nutrition Information Extraction on Smartphones

2012-01-12T15:51:00.000-08:00

Eyes-Free Barcode Scanning and Nutrition Information Extraction on Smartphones
Research Seminar at the Faculty of Informatics, Masaryk University, Brno, Moravia, Czech Republic
Vladimir Kulyukin

Department of Computer Science

Utah State University

Eyes-Free Barcode Scanning and Nutrtition Information Extraction on Smartphones

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 02

2012-01-12T07:37:00.000-08:00

Editing Python Code, Running Python Code, Python Code Execution, Functional Abstraction, Tuples
Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 02

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Lecture 01

2012-01-10T07:18:00.000-08:00

Python Overview (History, Features, Strengths, Weaknesses), Python Installation on Windows/Linux/Mac, Python Interpreter, Python 2 vs Python 3, Comments, Booleans, Variables, Lists, Strings, Tuples, Built-in Functions and Methods

Vladimir Kulyukin

Department of Computer Science

Utah State University

Python & Perl: Lecture 01

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Python & Perl: Syllabus

2012-01-09T13:14:00.000-08:00

Vladimir Kulyukin

Department of Computer Science

Utah State University

General Info
Dates Jan 09, 2012 - May 04, 2012
Meeting Times 9:00am - 10:15am, TU & TH
Location Geology 308
Instructor's Office Old Main, 401E
Office Hours
1:00 - 2:00pm, TU &TH
Email vladimir dot kulyukin at usu dot edu

Prerequisites

CS 1400 (Introduction to Programming in C++);
Completion of University Studies Breadth of Life Sciences (BLS) course;
Fulfillment of University Studies Quantitative Literacy (QL) requirement.

Course Description and Objectives

The primary objective is to introduce you to the two programming languages Python and Perl. We will do 10 weeks of Python and 5 weeks of Perl. By the end of the class you should be able to write programs in each language: more advanced programs in Python and less advanced programs in Perl. By the end of the class, you will have mastered or become closely familiar with the following concepts and topics:

Python

Platforms
Data types and operations
Main control structures
Functions
File I/O
OOP basics
Network programming
Basics of image processing
CGI scripting
Online resources & communities

Perl
- Platforms
- Data types and operations
- Control structures
- Subroutines
- Regular expressions
- CGI scripting
- Online resources & communities

Text Books

Exams

Midterm: March 08, 2012, 9:00 - 10:15, online
Final Exam: May 01, 2012, 9:30 - 11:20am, online

The midterm exam will be exclusively on Python. The final exam will be both on Python and Perl, but heavily biased toward Perl. There will also be regular 5- or 10-minute in-class quizes. The quizes will not be worth any points and will not contribute to your final grade. Their purpose is twofold: to help you evaluate your knowledge and understanding of the previously covered material and to help me adjust my in-class presentations on the basis of your quiz performance.

Assignments

All coding assignments and the final project will be submitted and graded through Dropbox. If you do not have Dropbox installed on your machine yet, go to www.dropbox.com and take a few minutes to install it. After you have Dropbox installed, send me an email with the subject "CS3430 Dropbox Folder" from the email address that you intend to use for this class (e.g., john.nicholson@aggiemail.usu.edu). In the body of your email write your first and last names in full (e.g., John Nicholson, Chaitanya Gharpure, Aliasgar Kutiyanawala). I will check your name against the class roster and, If you are registered, will create a Dropbox folder cs3430_s12_yourfirstname_yourlastname (e.g., cs3430_f11_john_nicholson), and share that folder with the email address of your message.

No late submissions will be accepted unless there is a good reason. So be cognizant of the deadlines and due dates.

Assignments

I plan to have to have 12 assignments (8 in Python and 4 in Perl) plus a final project in the last 4 weeks of the semester. The final project will require a 3-5 page writeup in addition to the source code.

All coding assignments and the final projects will be submitted and graded through Dropbox. If you do not have Dropbox installed on your machine yet, go to www.dropbox.com and take a few minutes to install it. After you have Dropbox installed, send me an email with the subject "CS6890 Dropbox Folder" from the email address that you intend to use for this class (e.g., john.nicholson@aggiemail.usu.edu). In the body of your email write your first and last names in full (e.g., John Nicholson, Chaitanya Gharpure, Aliasgar Kutiyanawala). I will check this name against the class roster. If you are registered, I will create a Dropbox folder cs6890_f11_yourfirstname_yourlastname (e.g., cs6890_f11_john_nicholson), and share that folder with the email address of your message.

No late submissions will be accepted unless there is a good reason. So be cognizant of the deadlines and due dates.

Assignments & Projects

I plan to have eight regular assignments in the first 10 weeks of the semester and a final project in the last 4 weeks of the semester. All assignments will be coding. The final project will require a 3-5 page writeup in addition to the source code.

All coding assignments and the project will be submitted and graded through Dropbox. If you do not have Dropbox installed on your machine yet, go to www.dropbox.com and take a few minutes to install it. After you have Dropbox installed, send me an email with the subject "CS6890 Dropbox Folder" from the email address that you intend to use for this class (e.g., john.nicholson@aggiemail.usu.edu). In the body of your email write your first and last names in full (e.g., John Nicholson, Chaitanya Gharpure, Aliasgar Kutiyanawala). I will check this name against the class roster. If you are registered, I will create a Dropbox folder cs6890_f11_yourfirstname_yourlastname (e.g., cs6890_f11_john_nicholson), and share that folder with the email address of your message.

No late submissions will be accepted unless there is a good reason. So be cognizant of the deadlines and due dates.

There will be approximately one assignment per week. The load may vary, however, depending on how fast we move through the material. It is the responsibility of the student to ensure that their assignment is complete and correct. The written portion of assignments may consist of short programming and design questions. Grading of the programming assignments will be based on the following criteria:

Completion of program features as outlined in the assignment description;
Ability to handle error conditions (i.e. the program does not crash);
Clear and concise code comments;
Code elegance and efficiency: meaningful variable, function, and class names, functional abstractions, etc.

In week 11, you will be given a four-week programming project that will be due on the day of the final exam. You will be required to write not only the source code but also document it. I will give you two project topics of which you can choose the one on which you will work on for five weeks.

You can negotiate your own project with me. For example, if you work for a company or a research project and want to implement some programming tool, please contact me before the final project is assigned. The two main criteria that I will use to decide whether you should be given the go-ahead are:

The complexity of the project (it has to be comparable to the complexity of the assignend projects); and
Your ability to complete the project on time given your previous class performance. It is unlikely that you will be able to choose your own project if your previous performance record is average or below average. Do not get too ambitious on your project's scope: there will be several regular Perl assignments in addition to the project and, of course, other courses. Please do not start your project before you get my approval.

Grading Percentages

The class will be graded as follows:

Python Assignments - 40%;
Perl Assignments - 20%;
Midterm Exam - 10%;
Final Exam - 10%;
Final Project - 20%

Grade Argumentation

If you think that I or the grader or I made a mistake, let me know. You deserve credit when it is due. If you are concerned about your grade, do not ask what you can do to raise it one week before the final. That is a too late. In order for me to help you, we both need time in order to solve the issue. Come see me as soon as you perceive a problem. Obviously, you should have satisfied the course prerequisites. If you have not, you should complete them before taking this class. Do not attempt to negotiate grades. If you just “need” B- instead of a C+ for whatever reasons, it will not happen. Students must be officially registered for this course. Attending class beyond the last date to add without being officially registered is not allowed and will not be approved by the dean’s office. No assignments or tests of any kind will be graded for students whose names do not appear on the class list.

Plagiarism

The basic rule about cheating is DO NOT DO IT!

You are free to talk with each other about regular assignments in general terms. However, you must write your own solutions and/or computer code. No collaboration is allowed on exams. Activities that violate the plagiarism policy include (but are not limited to): copying another person's work on a programming project, homework assignment, or exam; using any reference not authorized by the instructor on a programming project, homework assignment, or exam. The penalty for violating the plagiarism policy may be an F in the course. Appropriate university authorities may be informed of cheating incidents in a formal letter.

You can always ask me before you do something. Some examples of cheating include copying another's work, turning in another's work as your own, allowing someone else to copy your work, doing work for another, letting another have access to your solution, using unapproved materials during a test, turning in duplicate or near-duplicate assignments, and working with another person to complete an assignment.

You are required to do your own work. This does NOT mean working together and turning in two solutions. You are also responsible for protecting your code. Take care to keep your code unavailable to other students. Occurrences of cheating will have serious consequences for all involved. The first incident will carry a penalty of the student being given negative points equal to the value of the assignment or test. A second occurrence is grounds for a failing grade in the course and possible University action.

Please refer to the USU Computer Science Department official cheating policy at http://digital.cs.usu.edu/cheating_policy.html. Files submitted for homework may be electronically compared to detect cheating.

ADA Compliance

If a student has a disability that will likely require some accommodation by the instructor, the student must contact the instructor and document the disability through the Disability Resource Center, preferably during the first week of the course. Any request for special considerations relating to attendance, pedagogy, taking of examinations, etc. must be discussed with and approved by the instructor. In cooperation with the Disability Resource Center, course materials can be provided in alternative formats, e.g., large print, audio, diskette, or Braille.

Incompletes

The University policy will be adhered to for incompletes. This means that an incomplete cannot be given to prevent receipt of a bad grade. Under no circumstances can an incomplete be given for which a re-take of the class is required to make up the work. In such situations, a withdrawal or late withdrawal is required. If a student feels that an incomplete is appropriate, it is their responsibility to immediately discuss the matter with their instructor.

Add & Drop Dates

The university's academic calendar can be found at http://www.usu.edu/registrar/dates/. Please note that a student who signs up after the beginning of classes is still responsible for any homework assigned and due before that date.

Copyright (C) Vladimir Kulyukin

Python & Perl: Lectures

2012-01-09T12:40:00.002-08:00

Vladimir Kulyukin

Department of Computer Science

Utah State University

Copyright (C) Vladimir Kulyukin

Python & Perl: Assignments

2012-01-09T12:36:00.003-08:00

Vladimir Kulyukin

Department of Computer Science

Utah State University

Assignment 01, Due Jan 20, 2012, by 11:59pm, in your Dropbox folder
Assignment 02, Due Jan 27, 2012, by 11:59pm, in your Dropbox folder
Assignment 03, Due Feb 03, 2012, by 11:59pm, in your Dropbox folder, Solution
Assignment 04, Due Feb 10, 2012, by 11:59pm, in your Dropbox folder, Solution
Assignment 05, Due Feb 17, 2012, by 11:59pm, in your Dropbox folder, Solution
Assignment 06, Due Feb 24, 2012, by 11:59pm, in your Dropbox folder, Solution
Assignment 07, Due Mar 03, 2012, by 11:59pm in your Dropbox folder

Copyright (C) Vladimir Kulyukin

Python & Perl: Home

2012-01-09T12:35:00.002-08:00

Vladimir Kulyukin

Department of Computer Science

Utah State University

Syllabus	Syllabus
Lectures	Lectures
Assignments	Assignments
Quizzes	Quizzes

Copyright (C) Vladimir Kulyukin

RoboCart: Toward Robot-Assisted Navigation of Grocery Stores by the Visually Impaired

2012-01-05T10:43:00.000-08:00

Vladimir Kulyukin Chaitanya Gharpure John Nicholson

Department of Computer Science, Utah State University

Abstract: This paper presents RoboCart, a proof-of-concept prototype of a robotic shopping assistant for the visually impaired. The purpose of RoboCart is to help visually impaired customers navigate a typical grocery store and carry purchased items. The current hardware and software components of the system are presented. For localization, RoboCart relies on RFID tags deployed at various locations in the store. For navigation, RoboCart relies on laser range finding. Experiences with deploying RoboCart in a real grocery store are described. The current status of the system and its limitations are outlined.

Reference: Kulyukin, V., Gharpure, C., and Nicholson, J. (2005). "RoboCart: Toward Robot-Assisted Navigation of Grocery Stores by the Visually Impaired." Proceedings of the IEEE/RJS Conference on Intelligent Robots and Systems (IROS 2005), pp. 2845 - 2850, DOI: 10.1109/IROS.2005.1545107, IEEE/RJS, Edmonton, Alberta, Canada.

RoboCart: Toward Robot-Assisted Navigation of Grocery Stores by the Visually Impaired

View more documents from Vladimir Kulyukin

Wireless Indoor Localization with Dempster-Shafer Simple Support Functions

2012-01-03T10:03:00.000-08:00

Vladimir Kulyukin Amit Banavalikar John Nicholson

Department of Computer Science, Utah State University

Abstract: A mobile robot is localized in an indoor environment using IEEE 802.11b wireless signals. Simple support functions of the Dempster-Shafer theory are used to combine evidence from multiple localization algorithms. Emperical results are presented and discussed. Conclusions are drawn regarding when the proposed sensor fusion methods may improve performance and when they may not.

Reference: Kulyukin, V., Banavalikar, A., and Nicholson, J. (2005). "Wireless Indoor Localization with Dempster-Shafer Simple Support Functions." Technical Report USU-CSATL-1-05-05, Computer Science Assistive Technology Laboratory, Department of Computer Science, Utah State University.

Wireless Indoor Localization with Dempster-Shafer Simple Support Functions

View more documents from Vladimir Kulyukin

A Software Tool for Rapid Acquisition of Streetwise Geo-Referenced Maps

2012-01-02T12:58:00.000-08:00

Vladimir Kulyukin Aliasgar Kutiyanawala Ramya Venugopalan

Department of Computer Science, Utah State University

Abstract: RapGeoRef,a software tool for rapid acquistion of streetwise geo-referenced maps,is presented.

Reference: Kulyukin, V., Kutiyanawala, A., and Venugopalan, R. (2009). "A Software Tool for Rapid Acquisition of Streetwise Geo-Referenced Maps." Proceedings of the 24th Annual International Technology and Persons with Disabilities Conference (CSUN 2009), Los Angeles, CA.

A Software Tool for Rapid Acquisition of Streetwise Geo-Referenced Maps

View more documents from Vladimir Kulyukin

On Sufficiency of Verbal Instructions for Independent Blind Shopping

2011-12-22T17:55:00.000-08:00

John Nicholson Vladimir Kulyukin

Department of Computer Science, Utah State University

Abstract: Afield study of independent blind shopping in a modern supermarket suggests that verbal instructions may be sufficient for retrieving shelved products.

Reference: Nicholson, J., Kulyukin, V., and Coster, D. (2009). "On Sufficiency of Verbal Instructions for Independent Blind Shopping." Proceedings of the 24th Annual International Technology and Persons with Disabilities Conference (CSUN 2009), Los Angeles, CA.

On Sufficiency of Verbal Instructions for Independent Blind Shopping

View more documents from Vladimir Kulyukin

CRISS: A Collaborative Route Information Sharing System for Visually Impaired Travelers

2011-12-21T14:55:00.000-08:00

John Nicholson Vladimir Kulyukin
Department of Computer Science, Utah State University

Abstract: Limited sensory information about a new environment often requires people with a visual impairment to rely on sighted guides for showing or describing routes around the environment. However, route descriptions provided by other blind independent navigators, (e.g., over a cell phone), can also be used to guide a traveler along a previously unknown route. A visually impaired guide can often describe a route as well or better than a sighted person since the guide is familiar with the issues of blind navigation. This chapter introduces a Collaborative Route Information Sharing System (CRISS). CRISS is a collaborative online environment where visually impaired and sighted people will be able to share and manage route descriptions for indoor and outdoor environments. It then describes the system’s Route Analysis Engine module which takes advantage of information extraction techniques to find landmarks in natural language route descriptions written by independent blind navigators.

Reference: Nicholson, J., Kulyukin, V. (2009). CRISS: A Collaborative Route Information Sharing System for Visually Impaired Travelers. In M. M. Cruz-Cunha; E. F. Oliveira; A. J. Tavares; L. G. Ferreira (Edtrs.), Handbook of Research on Social Dimensions of Semantic Technologies and Web Services (Volume II), pp. 720-741, ISBN: 978-1-60566-650-1, IGI Global, Hershey, PA, USA.

CRISS: A Collaborative Route Information Sharing System for Visually Impaired Travelers

View more documents from Vladimir Kulyukin

Teleassistance in Accessible Shopping for the Blind

2011-12-20T12:59:00.000-08:00

Aliasgar Kutiyanawala (1) Vladimir Kulyukin (1) John Nicholson (2)
(1) Department of Computer Science, Utah State University
(2) Computer Science and Information Technology Department, Austin Peay University

Abstract: In this paper, we present TeleShop, the teleassistance module of ShopMobile 2, our mobile accessible shopping system for visually impaired (VI) and blind individuals that we have been developing for the past several years. TeleShop enables its users to obtain help from remote sighted guides by transmitting images and voice from their smartphones to the guides’ computers or phones. We have successfully tested TeleShop in a laboratory study in which a married couple (a blind husband and a sighted wife) used it to retrieve grocery products and read nutrition facts from product packages.

Reference: Kutiyanawala, A., Kulyukin, V., and, Nicholson, J. (2011). "Teleassistance in Accessible Shopping for the Blind." Proceedings of the the 2011 International Conference on Internet Computing ( ICOMP 2011), pp. 190-193, July 18-21, 2011, Las Vegas, USA.

Teleassistance in Accessible Shopping for the Blind

View more documents from Vladimir Kulyukin

Teleassistance in Blind Shopping: Laboratory Experiment 01

Teleassistance in Blind Shopping: Laboratory Experiment 02

Teleassistance in Blind Shopping: Laboratory Experiment 03

Teleassistance in Blind Shopping: Laboratory Experiment 03

Teleassistance in Blind Shopping: Laboratory Experiment 04

Teleassistance in Blind Shopping: Exit Interviews with Participants

On Automated Landmark Identification in Written Route Descriptions by Visually Impaired Individuals

2011-12-19T12:49:00.000-08:00

John Nicholson Vladimir Kulyukin Aliasgar Kutiyanawala
Department of Computer Science, Utah State University

Abstract: Route descriptions are used to describe how to complete a route from one location to another location. A key component of route descriptions is the set of landmarks that are mentioned in the description and will be encountered as the actions in the description are executed. People with visual impairments mention more landmarks than people with normal vision. They also refer to landmarks experienced along non-turning segments of the route, not just at turns. This paper describes an analysis of a set of route descriptions written by people with visual impairments. The analysis is centered on understanding the types of language patterns that people use in route descriptions and that can used to identify mentions of landmarks. The patterns can subsequently be used to build tools that can automatically extract landmarks from text. One set of techniques used to automatically extract information from natural language text is Information Extraction (IE). When developing IE-based tools, natural language texts are analyzed and rules are created that can automatically extract the desired information from the text. We have been developing the Route Analysis Engine (RAE), an IE-based tool that can automatically identify landmarks in route descriptions. In 2007, an online web-based survey was used to collect real-world route descriptions from visually impaired individuals. Respondents were asked to submit two route descriptions, an outdoor route description for guiding travelers from one building to another building and an indoor route description for guiding travelers from one room to another room in the same building. We received 52 responses, providing 104 English route descriptions: 52 indoor route descriptions and 52 outdoor route descriptions. Two thirds of the route descriptions were placed in the training set for the purpose of analysis and IE rule development. The remainder were placed in an evaluation set used to test the effectiveness of the IE rules .

Reference: Nicholson, J., Kulyukin, V., Kutiyanawala, D. (2010). "On Automated Landmark Identification in Written Route Descriptions by Visually Impaired Individuals." Proceedings of the 25th Annual International Technology and Persons with Disabilities Conference (CSUN 2010), San Diego, CA.

On Automated Landmark Identification in Written Route Descriptions by Visually Impaired Individuals

View more documents from Vladimir Kulyukin

On Self-Sufficiency of Verbal Route Directions for Blind Navigation with Prior Exposure

2011-12-19T12:39:00.000-08:00

Aliasgar Kutiyanawala Vladimir Kulyukin Daniel Bryce
Department of Computer Science, Utah State University

Abstract: We define verbal route directions to be self-sufficient if they can be used by independent visually impaired (VI) travelers to successfully navigate a route from A to B in a given environment without any electronic aid capable of receiving external signals or any human assistance. We distinguish self-sufficient route directions from self-sufficient routes. A self-sufficient route anticipates potential route execution failures and provides either extra localization actions or contingencies for route repair. Self-sufficient verbal route directions are complete or partial verbal realizations of self-sufficient routes. We conducted a preliminary investigation of the self-sufficiency of verbal route directions for outdoor environments with three completely blind students of Utah State University (USU). In this study, the generation of routes and route directions was done manually. We selected two routes on the Utah State University (USU) campus and manually wrote a set of route directions which we believed to be self-sufficient and then encoded our route directions in a computer program than ran on a Nokia E70 cellular phone. Furthermore, our investigation was confined to the case when VI individuals receive prior exposure to the route they will have to navigate independently. This study models the situation when a visually impaired student navigates the route once with an O&M instructor or a friend and then has to navigate the route independently.

Reference: Kutiyanawala, A., Kulyukin, V., Bryce, D. (2010). "On Self-Sufficiency of Verbal Route Directions for Blind Navigation with Prior Exposure." Proceedings of the 25th Annual International Technology and Persons with Disabilities Conference (CSUN 2010), San Diego, CA.

On Self-Sufficiency of Verbal Route Directions for Blind Navigation with Prior Exposure

View more documents from Vladimir Kulyukin

Automated SVG Map Labeling for Customizable Large Print Maps for Low Vision Individuals

2011-12-19T12:25:00.000-08:00

Vladimir Kulyukin (1), James Marston (2), Joshua Miele (3), Aliasgar Kutiyanawala (1)
(1) Department of Computer Science, Utah State University
(2) Atlanta VA Rehabilitation R&D Center for Vision Loss
(3) Smith-Kettlewell Eye Research Institute

Abstract: Many people with visual impairments do not read Braille and have problems interpreting tactile information. Some of them have enough residual vision so that if streets and their names were presented in the proper color, size, and style, they could benefit from customizable large print maps. Such maps would allow people with low vision to study a new area, pre-‐plan travel, and have portable maps to consult while navigating in unfamiliar areas. This paper presents an algorithm for placing street names on street maps produced by the Tactile Map Automated Product on (TMAP) software in the Scalable Vector Graphics (SVG) format.

Reference: Kulyukin, V., Marston, J., Miele, J., and Kutiyanawala, A. (2010). "Automated SVG Map Labeling for Customizable Large Print Maps for Low Vision Individuals." Proceedings of the 2010 Rehabilitation Engineering and Assistive Technology Society of North America Conference (RESNA 2010), Las Vegas, NV.

Automated SVG Map Labeling for Customizable Large Print Maps for Low Vision Individuals

View more documents from Vladimir Kulyukin

From ShopTalk to ShopMobile: Vision-Based Barcode Scanning with Mobile Phones for Independent Blind Grocery Shopping

2011-12-19T12:09:00.000-08:00

Vladimir Kulyukin and Aliasgar Kutiyanawala
Department of Computer Science, Utah State University

Abstract: Independent grocery shopping is a major challenge for many visually impaired (VI) individuals. In 2006, we began our work on ShopTalk, a wearable system for independent blind supermarket shopping. ShopTalk consisted of a small OQO computer, a wireless barcode reader, and a numeric keypad, and was based on a simple insight: independent blind shopping = verbal route instructions + barcode scans. The system was the first attempt reported in the accessible shopping literature to use shelf barcodes as topological points for locating products through verbal directions. In 2008-‐09, we ported ShopTalk to a mobile phone platform. This paper presents a vision-‐based barcode scanning method that will allow ShopMobile, the next generation of ShopTalk, to run on a mobile phone with no external barcode scanner.

Reference: Kulyukin, V. and Kutiyanawala, A. (2010). "From ShopTalk to ShopMobile: Vision-Based Barcode Scanning with Mobile Phones for Independent Blind Grocery Shopping." Proceedings of the 2010 Rehabilitation Engineering and Assistive Technology Society of North America Conference (RESNA 2010), Las Vegas, NV.

From ShopTalk to ShopMobile: Vision-Based Barcode Scanning with Mobile Phones for Independent Blind Grocery Shopping

View more documents from Vladimir Kulyukin

User Intent Communication in Robot-Assisted Shopping for the Blind

2011-12-16T16:19:00.000-08:00

Vladimir Kulyukin (1) and Chaitanya Gharpure (2)
(1) Department of Computer Science, Utah State University
(2) Google, Inc

Abstract: The research reported in this chapter describes our work on robot-assisted shopping for the blind. In our previous research, we developed RoboCart, a robotic shopping cart for the visually impaired (Gharpure, 2008; Kulyukin et al., 2008; Kulyukin et al., 2005). RoboCart's operation includes four steps: 1) the blind shopper (henceforth the shopper) selects a product; 2) the robot guides the shopper to the shelf with the product; 3) the shopper finds the product on the shelf, places it in the basket mounted on the robot, and either selects another product or asks the robot to take him to a cash register; 4) the robot guides the shopper to the cash register and then to the exit. Steps 2, 3, and 4 were addressed in our previous publications (Gharpure & Kulyukin 2008; Kulyukin 2007; Kulyukin & Gharpure 2006). In this paper, we focus on Step 1 that requires the shopper to select a product from the repository of thousands of products, thereby communicating the next target destination to RobotCart. This task becomes time critical in opportunistic grocery shopping when the shopper does not have a prepared list of products. If the shopper is stranded at a location in the supermarket selecting a product, the shopper may feel uncomfortable or may negatively affect the shopper traffic.

Reference: Advances in Human-Robot Interaction, Vladimir Kulyukin (Edtr), ISBN 978-953-307-020-9, INTECH, December 2009.

Full Chapter: User Intent Communication in Robot-Assisted Shopping for the Blind

View more documents from Vladimir Kulyukin

Eyes-Free Barcode Localization and Decoding for Visually Impaired Mobile Phone Users

2011-12-14T10:35:00.000-08:00

Vladimir Kulyukin and Aliasgar Kutiyanawala

Abstract: An eyes-free barcode localization and decoding method is presented that enables visually impaired (VI) mobile phone users to decode MSI (Modified Plessy) barcodes on shelves and UPC barcodes on individual boxes, cans, and bottles. Simple and efficient barcode localization and decoding techniques are augmented with an interactive haptic feedback loop that allows the VI user to align the phone’s camera with a fixed surface in the pitch and yaw planes. The method is implemented on a Google Nexus One smart phone running Android 2.1. A laboratory study is presented in which the method was evaluated by one VI and four blindfolded sighted participants.

Reference: Proceedings of the 2010 International Conference on Image Processing, Computer Vision, & Pattern Recognition (IPCV 2010), Vol. 1, pp. 130-135. July 12-15, 2010, Las Vegas, NV. CSREA Press.

Full Paper: Eyes-Free Barcode Localization and Decoding for Visually Impaired Mobile Phone Users

View more documents from Vladimir Kulyukin

ShopMobile: Mobile Eyes-Free Shopping System on Android Smartphone

ShopMobile: Eyes-Free Barcode Scanning on Android Smartphone (User Trial)

Theory of Computation: Lecture 39

2011-12-09T12:30:00.000-08:00

Stages of Compilation, Syntactic Analysis, Tokenization with Non-Deterministic Finite State Automata, Recursive Descent Parsing with Context-Free Grammars

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 39

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 38

2011-12-07T12:31:00.001-08:00

CFL Membership, Cocke-Younger-Kasami (CYK) Algorithm

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 38

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Assignment 09: Final Project Submission

2011-12-07T10:04:00.000-08:00

Department of Computer Science
Utah State University

Due Date

Your final project submissions are due on December 14, 2011, by 11:59 p.m. in your Dropbox folder.

What to Submit

You need to submit your source code and documentation. Give your submission folder an easily identifiable name such as CS6890_F11_FinalProject, for example. Your documentation should contain detailed instructions of how to run your project. Use cases and control charts would be greatly appreciated.

Scheduling Demos

If your project is not self-contained, you need to schedule a demo. I set up an online scheduling poll and had a Python script drop a html file with a link to it into your Dropbox folder. A project is not self-contained if it requires third-party installations (e.g., a computer vision library, a game engine, a graphics package, etc.).

If your project consumes web sites and services (RSS feeds, YouTube channels, Amazon Mechanical Turk, etc.), your project is self-contained. Make sure that if your application requires a password to consume a site or a service, it must be included and, if necessary, encrypted in your apk.

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Android Programming: Lecture 14

2011-12-06T16:35:00.000-08:00

Touchscreens, Drag and Drop, Android Native Development Kit

Vladimir Kulyukin

Department of Computer Science

Utah State University

Android Programming: Lecture 14

View more presentations from Vladimir Kulyukin

Source for DragDropTouchDemo Project (zip)
Source for BuiltGestureConsumer Project (zip)
Source for NDKDemo Project (zip)
Source for NDKIncrementArray (rar)
Source code for NDKImageBinarization Project (zip)

Screencast 01: Android NDK: Native Array Manipulation

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 37

2011-12-05T13:36:00.000-08:00

Stack Machines, Acceptance by Empty Stack, Converting FSAs to Stack Machines, Converting CFGs to Stack Machines, Useless Symbols in CFGs, Elimination of Useless Symbols, Chomsky Normal Form

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 37

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 36

2011-12-02T12:19:00.000-08:00

Context-Free Grammars (CFGs), Backus-Naur Notation (BNN), Stack Machines

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture36

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 35

2011-11-30T12:25:00.000-08:00

Regular Grammars, Right Linear Grammars, Left Linear Grammars, Language Reversals, Regular Grammars and Regular Languages

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 35

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Android Programming: Lecture 13

2011-11-29T16:38:00.000-08:00

AIDL and Bounded Services, AIDL Complex Types, Speech Synthesis, Overcoming TTS Limitations through Phonetic Spelling, Overcoming TTS Limitations through Human Recording, Teaching Android to Speak Sanskrit and Russian

Vladimir Kulyukin

Department of Computer Science

Utah State University

Android Programming: Lecture 13

View more presentations from Vladimir Kulyukin

Screencast 01: Android Bound (Remote) Services with AIDL Primitive Types

Screencast 02: Bhagavatgita in Sanskrit and Russian on Android

AIDLService Project's source code (zip)
AIDLServiceConsumer Project's source code (zip)
SimpleTTSDemo Project's source code (zip)
TTSDonQuixote Project's source code (zip)
BhagavatGitaTTS Project's source code (zip)

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 34

2011-11-28T12:21:00.000-08:00

Pumping Lemma for Regular Languages, Finite Automata in Robotics, EGREP and Java Patterns, Grammars and Derivations

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 34

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Android Programming: Lecture 12

2011-11-24T12:46:00.000-08:00

Started (Local) Intent Services, Shared Agendas, Loopers and Handlers, Bound Services, Android Interface Definition Language

Vladimir Kulyukin

Department of Computer Science

Utah State University

Android Programming: Lecture 12

View more presentations from Vladimir Kulyukin

StartedSumIntent Project's source code (zip)
StartedSumLooperService Project's source code (zip)
StartedSumLooperService2 Project's source code (zip)

Screencast 01: Consumption and Development of Android Intent Services

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 33

2011-11-21T11:43:00.000-08:00

Equivalence of DFAs and NFAs, Epsilon Closures, Regular Expressions, Converting Regular Expressions into NFAs, Pigeon Hole Principle

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 33

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 32

2011-11-18T12:29:00.000-08:00

Non-Determinism, Non-Deterministic Finite Automata (NFAs), How NFAs Work, Subset Construction, Equivalence of DFAs and NFAs, NFA Implementation

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 32

View more presentations from Vladimir Kulyukin

Errata: The author of the 2nd reference on the Slide "References and Reading Suggestions" A. Brooks Webber.

Copyright (C) Vladimir Kulyukin

Android Programming: Lecture 11

2011-11-16T14:55:00.000-08:00

Multitasking, Services, Started (Local) Services, Bound (Remote) Services, Consumption of HTTP Services, Development of Started Services, Process Lifecycle, Process Importance Levels

Vladimir Kulyukin

Department of Computer Science

Utah State University

Android Programming: Lecture 11

View more presentations from Vladimir Kulyukin

HttpGetURLSource Project's source (zip)
HttpGetURLSource2 Project's source (zip)
StartedCatalanService Project's source (zip)
Coding Solution to Assignment 08 (watch Screencast 03 below for details)

ScienceCPBuilder Project's source (zip)
ScienceCPConsumer Project's source (zip)

Screencast 01: Consumption and Development of Services (Part 01)

Screencast 02: Consumption and Development of Services (Part 02)

Screencast 03: Auto Generation of Content Providers from XML Resources (Part 02)

Screencast 04: Started (Local) Intent Service for Computing Catalan Numbers

Back to Class Home Page

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 31

2011-11-16T12:19:00.000-08:00

Deterministic Finite Automata (DFAs), How DFAs Work, DFA Transition Function, Formal Languages Accepted By DFAs, Sample DFA Problems, Sample DFA Implementation

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 31

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 30

2011-11-16T11:56:00.000-08:00

Computable Functions That Are Not Primitive Recursive

Vladimir Kulyukin

Department of Computer Science

Utah State University

Theory of Computation: Lecture 30

View more presentations from Vladimir Kulyukin

Copyright (C) Vladimir Kulyukin

Theory of Computation: Lecture 29

2011-11-04T11:08:00.000-07:00

Primitive Recursiveness and Min/Max Games

Vladimir Kulyukin

Department of Computer Science

Utah State University

Power Point Presentation (pdf)